algorithm - 查找具有属性的对象的最小子集。

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 难的，所以如果你需要精确的最小值，生成所有可能的子集不会比其他解决方案更糟糕。

但是有一些多项式时间逼近算法。有关详细信息，请参阅维基百科页面。“最好的”是贪心算法，它的运行方式如下：

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

Answer 2

您可以通过在必要时包括作为给定特征（或特征）的唯一拥有者的所有对象来减少问题。 Object1是唯一一个，Feature1因此您知道您的解决方案中需要那个。