我需要幫助！
我想知道從這個問題中得到答案的有效演算法。
問題：可以從給定的集合中選擇獲取最大的集合數
集 = {1,2,4}, {2,3,4}, {3,4,5}, {1,2,6}, {2,3,5}
預期答案是 2！{1,2,6}, {3,4,5}
當集合變得眾多時，我怎樣才能得到答案？沒有什么演算法可以解決這個問題嗎？
uj5u.com熱心網友回復：
您的問題是最大獨立集問題的一個實體。
使用 python 和 networkx' maximum_independent_set：
from networkx import Graph
from networkx.algorithms.approximation.clique import maximum_independent_set
from itertools import combinations
V = [frozenset(s) for s in [{1,2,4}, {2,3,4}, {3,4,5}, {1,2,6}, {2,3,5}]]
E = [(x,y) for x,y in combinations(V, 2) if x&y] # "if x&y" means "if intersection of sets x and y is non-empty"
G = Graph()
G.add_nodes_from(V)
G.add_edges_from(E)
print( maximum_independent_set(G) )
# {frozenset({1, 2, 6}), frozenset({3, 4, 5})}
請注意，networkxmaximum_independent_set函式使用近似演算法，即在大圖中，它找到的最大獨立集可能不是最大尺寸。檔案頁面鏈接了詳細介紹該演算法的研究論文，并評論說：“找到這樣一個集合的問題稱為最大獨立集問題，是一個 NP 難優化問題。因此，不太可能存在有效的演算法用于找到圖的最大獨立集。”
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/380765.html
標籤：算法