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

我有算法问题。我不知道如何解决它。也许有人可以帮助我？查找具有属性的对象的最小子集。

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

    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}。我无法生成所有可能的子集，因为它可能需要太多时间。

来源

2010-09-21 mirt

这正是set cover problem。这个问题非常困难，所以如果您至少需要使用最少的数量，那么生成所有可能的子集的时间并不比其他解决方案差。

但是有一些多项式时间近似算法。详情请参阅维基百科页面。 “最佳”是贪心算法，其运行是这样的：

初始化未执行的功能为{特征1，特征2，特征3，...}
选择它实现了大部分未执行的功能的对象。
重复2，直到实现所有功能。

来源

2010-09-21 18:01:31 kennytm

贪婪算法很好，但是以这种方式我只能找到一个子集（通常它可能多于一个子集） – mirt 2010-09-21 18:32:41

您的答案是贪婪算法的一个子集。只是扔掉所有尺寸大于最小值的子集，并且你有答案。 – John 2010-09-21 20:03:41

您可以通过包含必需的所有对象来减少问题，这些对象是给定特征（或特征）的唯一拥有者。 Object1是唯一拥有Feature1的人，因此您知道在解决方案中需要该人员。

来源

2010-09-21 18:01:37 John

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

回答

相关问题