1

考虑由 n 个有限集合组成的集合 A，其成员不一定是不相交的。令 P={P[1], P[2], ..., P[m]} 是 A 的一个分区，并且对于 1..m 中的每个 i，令 U[i] 是所有的并集P[i] 的元素。所以 U={U[1], U[2], ..., U[m]}。我想要一个算法来找到一个 P 使得相应的 U 是一个分区，并且使得 U 的最小和最大元素之间的基数（即大小）差异最小化。

数据特征：

  • m 很小（2 到 5）且 n<10000
  • 通常，A 中有很大比例的一元集
  • A 中的成对集合之间的交点通常很小或为空
4

2 回答 2

1

我在问题评论中的项链类比提出了这个解决方案：

  1. 构建一个无向图 G，其顶点是 A 的元素，并且当 A[i] 与 A[j] 相交时，有一条从 A[i] 到 A[j] 的边。
  2. 找到 G 的连通分量 C。这可以通过简单的广度优先或深度优先算法来完成。
  3. 对于每个 C[i]，取 C[i] 的顶点并将它们联合在一起，产生 D[i]。您现在已将问题简化为一种特殊情况，因为集合 D 是 A 的元素并集的一个分区。
  4. 使用 bin-packing 算法尝试将 D 的元素精确放入 m 个 bin，每个 bin 的大小为 ceil(t/m)，其中 t 是 D 的所有元素的并集大小。如果失败，则增加大小重复垃圾箱，直到它成功或很明显它永远不会成功。装箱算法通常是启发式的，因此可能找不到完美的解决方案。此外，这不仅仅是一个简单的装箱问题，因此即使是完美的装箱算法也可能找不到最佳解决方案。

我很想知道是否有更有效的解决方案。特别是，我有一种预感，在步骤 4 中重复使用 bin-packing 算法是不明智的。

于 2011-03-05T10:16:36.280 回答
0

我将从 A 的交集图开始，当两个节点具有非空交集时，它具有 A 的节点元素和边。对于某些 i，该图的每个连通分量必须包含在单个 P(i) 中。

令 C(1),...,C(k) 为图的连通分量。让

size(j)=|union(a in C(j))|

现在您可以根据 size(i) 值重写问题，其中 i=1...k。即，给定正整数值 s(1),..,s(k)。对于 [1,..k] 的子集 P，我们定义 s(P)=sum(j in P) s(j)。

我们希望找到 [1,..,k] 的分区 P'=(P'(1),...,P'(m)) ，条件是它最小化值：

max s(P'(j)) - min s(P'(j))

因此，我们真的需要知道的不是 A 的元素的可能大小，而是图的连通分量的可能大小，以提出“最佳”算法。

于 2011-03-16T18:17:27.470 回答