算法問題 - 找到最小公共子集

a是具有多個「類別」的對象，b的例如a1具有三個附件b1，b2，b3。問題在於，將類別數量（可以增長得相當大）減少爲總是一起出現的組。一個「最大的共同子集」的東西。算法問題 - 找到最小公共子集

因此，例如，給出下面的數據集：

a1{ b1,b2,b3 } 
a2{ b2,b3 } 
a3{ b1,b4 }

我們可以發現，B2和B3總是在一起..

b23 = {b2,b3}

..和我們可以減少設置的類別這個：

a1{ b1, b23 } 
a2{ b23 } 
a3{ b1,b4 }

所以，我的問題是找到一些算法來解決這個問題。

我已經開始考慮Longest Common Sequence問題了，它可能是一個解決方案。即像重複分組這樣的類別，如b' = LCS(set_of_As)，直到所有類別都被遍歷。但是，這並不完整。我必須以某種方式限制輸入域，以使其成爲可能。

我想念一些明顯的東西嗎？您可以指向我的任何問題域的提示？有沒有人認識到解決這個問題的其他方法。

你很可能是正確的。 LCS絕對是一個可以解決手頭問題的解決方案。 **主要問題**的最短答案是**不，你沒有錯過任何明顯的**。看起來像一個不錯的問題，但。 –

真的，所有你需要做的就是運行相同的配對算法，就像你在那裏得到b23對一樣。重複它直到沒有更改集。第一次運行會產生配對，第二次運行會產生配對或成對配對和單個配對。所以你會有三胞胎和四倍的復發。 – Ghlitch

我認爲你可以通過說你的分類是有序的來改善你的表現。因此，如果繪製所有類別x所有對象（axb矩陣）的矩陣，您只需找到相等的列即可。我知道，它也很大，但可能會更快:) –

變換你的套有集B的，包括一個年代：

b1 { a1, a3 } 
b2 { a1, a2 } 
b3 { a1, a2 } 
b4 { a3 }

確保新B設定的內容進行排序。

按你的b集的內容排序。

具有相同元素的任何兩個相鄰的集合都出現在相同的一組集合中。

2012-10-23 18:46:18

另外一個優化是首先按長度排序b集，然後按內容排序。 – coproc

謝謝！沒有想到這一點。 –

我認爲如果您可以對分類進行排序（如果不是，那麼LCS算法無法識別{b3，b4}和{b4，b3}），我認爲您的LCS處於正確的軌道上。如果你可以強加和排序他們然後我認爲這樣的事情可以工作：


As = {a1={b1, b2},a2={b3},...} 
while ((newgroup = LCS(As)) != empty) { 
    for (a in As) { 
    replace newgroup in a 
    } 
}

2012-10-23 18:46:22

回答