查找具有属性的最小对象子集.

Question

我有算法问题.我不知道如何解决它.也许有人可以帮助我？

我有对象.每个对象具有相同的功能.它可以在表格中说明:

                 Feature1    Feature2    Feature3   Feature4
      Object1       1           0           1          1

      Object2       0           0           0          1

      Object3       0           1           1          1

      Object4       0           1           0          0

现在我想找到所有最小的对象子集.对于每个特征,每个子集应至少具有一个值"1".对于上表,结果是两个子集:{Object1,Object3}和{Object1,Object4}.我无法生成所有可能的子集,因为它可能需要太多时间.

Answer 1

这正是设置封面问题.这个问题是NP难的,所以如果你需要精确的最小值,那么生成所有可能的子集不会比其他解决方案更糟糕.

但是有一些多项式时间近似算法.有关详细信息,请参阅Wikipedia页面."最好的"是贪心算法,运行方式如下:

1. 将未实现的功能初始化为{Feature1,Feature2,Feature3,...}
2. 选择实现大多数未实现功能的对象.
3. 重复2,直到实现所有功能.