用最小标签覆盖人口的算法

Question

我的数据属于人员和标签，具有多对多的关系。

我需要一个算法，会发现一组最少的标签，使得人们在溶液标记与每个标签组的联盟将覆盖整个人口。

任何想法？

Answer 1

这相当于vertex cover的NP完全问题。

简单的证明：如果我们可以找到最小顶点覆盖，我们可以找到最小的一组标签。只需使用vertices = tags union persons创建一个图形并适当地链接它们，并将所有标签连接在一起。最小的顶点覆盖对应于最小的标记集合，一旦我们认识到对于这个图形中的每个顶点覆盖，都有一个相同大小的顶点覆盖仅由“标记” - 翻译构成。

的oposite（顶点盖可以减少到最少的代码）可以通过创建一个标签和一个人的每个顶点，并与人连接的标签为每个顶点为同一顶点+它的邻居中显示。

Answer 2

这是一个NP难题。这将需要大量的处理来确保你确实拥有绝对最少数量的标签。

，我会用漂亮的快速和容易的解决办法是

while there are users left in the pool: 
    find the tag that represents the most users 
    add that tag to the list 
    remove all the users that that tag represents from the pool 

If you want, you can then loop through and make sure there aren't any 
unnecessary tags //but that probably won't help much 

有，当然也有一定数量的标签可以进行布局方式，使得不是最好的方式，不会找到最佳解决方案。但是，我非常确定它应该非常接近。

Answer 3

人员和标签之间的许多一对多的关系，形成了一个二分图，这是幸运从一般的情况完全不同。因此，这个问题不是NP完整的，但是can be solved in polynomial time。这似乎等于找到最大匹配，维基百科提供了几个alternatives。