用最小標籤覆蓋人口的算法

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。