設置簡化

Question

說我有兩組，set1 = {a,b,c,d,e,f}和set2 = {a,b,c,d,e,g}。而不是明確地表達這些，我要像

common = {a,b,c,d,e} 
set1 = common + f 
set2 = common + g 

創造的東西如果我們想代表{a,b,c,h}，我們可以把它表示common - d - e + h。

我的目標基本上是能夠生成要使用的最佳公共部分。只有一個共同的部分，這不是太具有挑戰性，但我需要允許多個（但不是無限的，或獲得的好處將是微不足道的）。

通過優化，我的意思是「表達的元素數量最少」。所以在上面的例子中，它使得成本5（元素的數量）使common變量。然後，設置1和2的成本均爲2（一個用於引用通用，一個用於添加額外元素），總計爲7.如果沒有替換，這些將需要12個存儲（每個6個元素）。類似地，在來自被引用將「成本」 1

又如減去的元件， {a,b,c,d}, {a,c,d,e}, {e,f,g,h} and {e,f}

可能是

common1 = {a,c,d} 
common2 = {e,f,g} 
set1 = common1 + b 
set2 = common1 + e 
set3 = common2 + h 
set4 = common2 - g 

通過允許這成爲很多更具挑戰性的多個共同的部分。是否有這種類型的問題或類似的名稱？看起來它可能與壓縮有關，但是我從沒有找到太多的資源來說明從哪裏開始。

可相應和其他一些細節：

• 被允許引用多個共同的部分來表示的一組可以是有效的，但不是必需的。
• 對於我的用例，這些集合通常會包含大約20個元素和大約10個不同的集合。

Answer 1

你可以找到所有的原子集，也就是所有永遠不會分開的集合。

{a,b,c,d,e,f,g,h}  | {a,b,c,d} = {a,b,c,d},{e,f,g,h} 
{a,b,c,d},{e,f,g,h}  | {a,c,d,e} = {a,b,c,d},{e,f,g,h} 
{a,c,d},{b},{e},{f,g,h} | {e,f,g,h} = {a,c,d},{b},{e},{f,g,h} 
{a,c,d},{b},{e},{f,g,h} | {e,f}  = {a,c,d},{b},{e},{f},{g,h} 

{a,b,c,d} = {a,c,d},{b} 
{a,c,d,e} = {a,c,d},{e} 
{e,f,g,h} = {e},{f},{g,h} 
{e,f}  = {e},{f} 

這有點接近，但它並不能解決最小的故障。

我不認爲你可以找到最小的，因爲我懷疑這是NP-Hard。如果考慮一個集合S並創建一個圖，其中S的每個可能子集都是一個節點G.現在根據子集的長度給出一個節點權重，並在每個節點之間繪製一條對應於變化量的邊。 {abc} - > {a}的權重爲2. {bcd} - > {abe}的權重爲4.現在要找到常見集合問題的最小解決方案，您需要找到一個最小權重生成樹每個你感興趣的集合。如果你發現你可以用它來建立一個最小的公共集合 - 這些將是相等的。在節點加權圖中查找最小權重樹被稱爲節點加權Steiner樹問題。節點加權Steiner樹問題可以等價於Steiner樹問題。 Steiner樹問題可以表現爲NP-Hard。所以我強烈懷疑你試圖解決的問題是NP-Hard。

http://theory.cs.uni-bonn.de/info5/steinerkompendium/node15.html

http://theory.cs.uni-bonn.de/info5/steinerkompendium/node17.html