算法挑戰合併集合

Question

給定n組數字。每個集合包含一些從1到100的數字。如何選擇要合併到特殊規則下最長集合的集合，只有兩個非重疊集合可以合併。 [1,2,3]可以與[4,5]合併，但不合並[3,4]。什麼將是一個有效的算法合併成最長的集合。

我的第一次嘗試是形成一個n乘n的矩陣。每行/列代表一個集合。如果兩個集合重疊，則條目（i，j）等於1，則條目（i，i）存儲集合i的長度。那麼問題就變成了我們可以同時執行行和列操作，以在左上角創建對角線子矩陣，其軌跡儘可能大。

但是，我陷入瞭如何高效地執行行和列操作以在左上角形成這樣的對角子矩陣。

Answer 1

正如在評論（最大覆蓋問題）中已經指出的那樣，您有一個NP-hart問題。幸運的是，matlab爲整數線性編程提供解算器。

所以我們儘量減少問題的形式：

min f*x subject to Ax<=b , 0<=x 

有N套，我們可以編碼設置爲0和1組成的向量。例如，(1,1,1,0,0,...)將代表{1,2,3}和(0,0,1,1,0,0...)-{3,4}。

A的每列表示一組。 A(i,j)=1意味着i第012個元素位於第j個集合中，A(i,j)=0意味着第i個元素不在第j個集合中。

現在，x代表我們選擇集：如果x_j=1超過設定j選擇，如果x_j=0 - 比沒有選擇！

由於每一個元素必須是最多的一組，我們選擇b=(1, 1, 1, ..., 1)：如果我們把它含有i個元素兩套，比(Ax)的i個元素是至少2

剩下的唯一問題是什麼f？我們嘗試最大化聯合中的元素數量，因此我們選擇f_j=-|set_j|（減去由於最小<→最大轉換），其中|set_j|-第j個集合中的元素數目。

把它全部在MATLAB我們得到：

f=-sum(A) 
xopt=intlinprog(f.',1:n,A,ones(m,1),[],[],zeros(n,1),ones(n,1)) 

• f.' - 成本函數列
• 1:n - 的x所有n元素都是整數
• A - 編碼n套
• ones(m,1) - b=(1,1,1...)有m=100元素
• [],[] - 沒有形式的約束Aeq*x=beq
• zeros(n,1), 0<=x必須持有
• ones(n,1), x<=1從別人的約束已經遵循，但也許這將有助於求解一點點

Answer 2

您可以將組表示爲位域。按位和操作產生零將指示不重疊的集合。根據底層數據類型的寬度，您可能需要執行多個操作。例如，對於64位機器字大小，我需要兩個字來覆蓋1到100作爲位域。