查找具有屬性的對象的最小子集。

我有算法問題。我不知道如何解決它。也許有人可以幫助我？查找具有屬性的對象的最小子集。

我有對象。每個對象都具有相同的功能。它可以在表格中說明：

    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

查找具有屬性的對象的最小子集。

回答

相關問題