algorithm - 集合简化

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。

我的目标基本上是能够生成要使用的最佳公共(public)部分。只有一个公共(public)部分，这并不太具有挑战性，但我需要允许多个(但不是无限的，否则获得的好处将是微不足道的)。

我所说的最佳是指“表达的元素数量最少”。所以在上面的例子中，制作 common 变量“花费”5(元素数量)。然后设置 1 和 2 都花费 2(一个用于引用公共(public)元素，一个用于添加额外元素)，总计 7。如果没有替换，这些将花费 12 来存储(每个 6 个元素)。同样，从引用中减去一个元素将“花费”1。

另一个例子， {a,b,c,d}、{a,c,d,e}、{e,f,g,h} 和 {e,f}

可能是

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

通过允许多个公共(public)部分，这变得更具挑战性。是否有此类问题或类似问题的名称？它似乎与压缩有关，但我找不到太多关于从哪里开始的资源。

一些其他可能相关的细节:

• 允许引用多个公共(public)部分来表示一组可能是有效的，但不是必需的。
• 对于我的用例，集合通常包含大约 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。现在要找到公共(public)集合问题的最小解，你需要找到一个最小权重生成树，它覆盖您感兴趣的每个集合。如果您发现可以使用它来构建一个最小的公共(public)集合——这些将是等效的。在节点加权图中寻找最小权重树称为节点加权斯坦纳树问题。节点加权斯坦纳树问题可以等效于斯坦纳树问题。 Steiner Tree 问题可以证明是 NP-Hard 问题。所以我强烈怀疑您要解决的问题是 NP-Hard。

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

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