寻找最小组件集的算法

Question

寻找最小组件集的算法

algorithmcombinationsgraph-theorymathematical-optimizationdiscrete-mathematics

8

我正在寻找一个算法来解决以下问题。我有一个给定集合(a-h)的多个子集(1-n)。我想找到最小的子集合，通过组合可以构建出所有给定的子集。这个子集合可以包含1-n中不存在的子集。

  a b c d e f g h
1 1
2 1   1
3   1     1   1
4 1       1
5   1         1
6 1     1   1   1
7 1       1 1   1
8 1   1       1
9 1         1   1

以下是两个可能的集合，其中最小的包含七个子集。我已用x标记新的子集。

1 1
x   1
x     1
x       1
x         1
x           1
x             1
x               1

1 1
x   1         
x     1
x       1        
x         1    
x           1   1
x             1

我相信这一定是一个已知的问题，但我对算法不是很熟悉。非常感谢任何帮助，以及更好的话题标题建议。

谢谢！

更新

图着色可以让我有很大进展，谢谢。然而，在我的情况下，子集允许重叠。例如：

图着色给我提供了这个解决方案：

x 1 1
x     1
x       1

但是这个也是有效的，并且更小：

1 1 1 1  
4     1 1

- user3170702

1

“通过组合”是什么意思？ - hugomg

@missingno 我需要能够通过对解决方案中的若干子集执行OR操作来获取所有给定的子集。因此，“组合”1100和0110会产生1110。我希望这更清晰明了。 - user3170702

2

@user3170702：这样更清晰了。顺便说一下，那个的正常名称是集合并。 - hugomg

我认为你的六个子集解决方案不正确。对于它们两个，我看不到获取集合8的方法。 - Henry

关于图着色的更新...如果你只是在原始集合的负数上应用图着色，你会得到允许重叠的解的负数。这是因为如果你说解行可以有重叠元素，并寻找最小行数，那么要求它们的负数不重叠并在负数或给定数据行上使用着色是相同的。换句话说：你正在对空白进行着色，而这些空白不允许重叠！ - Diego Mazzaro

显示剩余2条评论

3个回答

1

对于这个变体的Set Cover问题，这里提供了一种用行生成的整数规划形式方法。

让我们通过它们的列号来表示组件a、b、c、d等。a=1，b=2等。

行是“子集”。假设现有子集为S1，...，Sm。（这些子集必须被覆盖）

新子集的符号表示法

这一步是引入新子集的步骤。让我们把“原子”子集称为a_x。所有a子集只有一个组成部分。

   a1 is the subset {1,0,0,0}
   a2 is the subset {0,1,0,0}
   a3 is the subset {1,0,1,0}
   ...

令bxy为具有两个组成部分的子集。

So `b13` is the subset with component 1 and 3 being present.
b13 = {1, 0, 1, 0}
b34 = {0, 0, 1, 1} etc.

cxyz are subsets with three components.
For example, c124 = { 1, 1, 0, 1} etc.

d subsets will have 4 components
e subsets will have 5 components 
and so on.

生成行的步骤

给定一个已存在的集合，我们只会在需要时生成所需的新的a、b、c等子集。

For example, let's take the subset S1 = {1, 0, 1, 1}
Meaningful sets needed that can help create S1 are
a1, a3, a4. (Note that a2 is not needed since component b is not a component in S1}
b11, b13, b34.
c134

预处理步骤：对于现有集合中的每个Sj，使用上述过程生成新的子集。我们只创建所需的ax、bxy、cxyz、dxyzw等。在制定步骤之前需要执行此步骤。

在最坏情况下，每个Sj需要(2^num_components-1)个子集。但它们很容易生成。

示例问题

现在针对以下问题进行公式化：

我们将为每一行设置一个限制条件。每个集合都必须被“覆盖”。

针对上述问题，以下是公式：

公式

Objective Minimize sum of all Subsets.
 Min sum (a_x) + sum (b_xy) + sum (c_xyz) + sum (d_xyzw)

Subject to:

   a1 + a2 + a3 + b11 + b12 + b13 + c123  >= 1 \\ Set 1 has to be formed
   a1 + a2 + a3 + b11 + b12 + b13 + c123  >= 1 \\ Set 2 has to be formed
   a1 + a2 + a3 + b11 + b12 + b13 + c123  >= 1 \\ Set 3 has to be formed
   a4 + a5            + b34               >= 1 \\ Set 4 has to be formed
   a1 + a2 + a3 + a4 + b11 + b12 + ..+  b34 + c123 + ...+ d1234  >= 1 \\ Set 5 has to be formed

 a's, b's, c's, d's Binary

上界：通过利用你最多需要 j 个子集（现有子集数）的事实，甚至可以添加一个割。目标函数必须是 j 或更低。

希望这能帮到你。

- Ram Narasimhan

但目标不是覆盖组件空间，而是能够构建所有给定的子集。输出可以包含任意集合，而不仅仅是给定的集合。 - harold

啊，谢谢Harold。我误解了。我会重新表述（如果我无法这样做，我将撤回答案）。谢谢。 - Ram Narasimhan

请解决这个问题，我真的很好奇答案是什么 :) - harold

好的，那我肯定是漏了什么。为什么所有组件的集合=1 {1,1,1,1} 不是解决方案呢？在 OP 更新的问题中，为什么 5 不是解决方案呢？ - Ram Narasimhan

因为只有5个元素，无法通过合并集合的方式得到1或者4，只能得到5。 - harold

1

这个问题在Coursera的离散优化课程的一个视频中被提出。如果我没记错的话，它被称为集合覆盖问题。

如果我没记错的话，它是NP完全或NP难的，因此需要研究典型算法（针对小数据集的精确算法，针对中/大数据集的元启发式算法）和典型框架（OptaPlanner，...）。

- Geoffrey De Smet

1

你确定吗？这是我最先看到的事情之一，我得出结论它不能像那样被规划。问题在于，目标不是覆盖所有元素，而是确保每个给定的子集都可以通过取某些东西的并集来构建。 - harold

好的观点，它不是一个标准的集合覆盖问题，而是一种变体，因为您的每个子集本身都是一个集合覆盖问题。不过我想知道：如果您解决了整个集合的集合覆盖问题，那么您对于每个子集的解决方法不就出来了吗？（虽然这可能不是最有效的子集） - Geoffrey De Smet

@GeoffreyDeSmet能否详细说明一下？您所说的解决整个集合是什么意思？ - user3170702

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Falk Hüffner · Accepted Answer

这个问题被称为集合基础问题，它是NP完全问题（Larry J. Stockmeyer: The set basis problem is NP-complete. Technical Report RC-5431, IBM, 1975）。将其作为图问题的表述是Bipartite Dimension。由于通常情况下很难解决，因此查看数据是否具有任何有用的属性可能会有所帮助（例如，集合是否很小？解决方案是否很小？所有集合是否都可能出现？）

我无法想出一个简单的ILP公式。相反，您可以尝试将问题简化为更好研究的Clique Cover问题，使用Kou&Wong或Nor et al.中的任一减少方法。我共同撰写了一篇关于Clique Cover算法的论文，并编写了一个包含精确求解器和两种启发式方法的Clique Cover求解器。