创建覆盖所有数据的最小数量的集合

Question

我在创建最小数量的数据集来覆盖整个数据集时遇到问题。

该问题具有数据域和一些排他性约束。排他性约束规定哪些数据不应该在同一组中。

目标是找到最少的组数。组数不必尽可能平衡（但如果有的话就更好了）。

示例 1：

Domain = {1, 2, 3, 4, 5, 6}
Exclusivity = 1!=2, 3!=4, 4!=5, 5!=6,

Answer is two sets: {1, 3, 5}, {2, 4, 6}

示例 2：

Domain = {1, 2, 3, 4, 5, 6}
Exclusivity = 1!=2, 2!=3, 3!=4, 4!=5

anwser is two sets: {1, 3, 5, 6}, {2, 4}

示例 3：

Domain = {1, 2, 3, 4, 5}
Exclusivity = 1!=2, 2!=3, 3!=4, 4!=5, 5!=1

answer is three sets : {1, 3}, {2, 4}, {5}

示例 4：

Domain = {1, 2, 3, 4, 5}
Exclusivity = 1!=2!=3!=4, 4!=5,

answer is four sets : {1, 5}, {2}, {3}, {4}

这里的 != 是传递性的。

有谁知道这样的算法可以有效地解决这个问题。我不记得从学校学到的任何算法可以解决这个问题，但那是十多年前的事了。

感谢帮助。

杰特

Answer 1

忽略平衡，这是图形着色。

域 <=>图集的顶点

<=>具有特定颜色

排他性约束的所有顶点<=>图的边缘。

不幸的是，图着色是 NP 困难的，并且可证明的近似比不好。有很多很多启发法。

Answer 2

从我的角度来看，我认为你可以创建一个加权图。对于相互排除的节点，将顶点权重设置为 Int.MAX，将其他节点设置为 0。

然后，您可以尝试缩小此图，以查找彼此之间具有零路由的节点。 （我确信这个问题存在一些算法）。

华泰

Answer 3

首先，将这个问题描述为覆盖问题有点误导。这实际上是一个带有分区约束的集合分区问题。

解决方案 1

将其表述为整数线性规划 (ILP) 并求解。 Google 公布了 Java ILP。如果您有兴趣，我可以发布有关如何将您的问题表述为 ILP 的更多信息。

解决方案 2

让数据集中的每个元素（Domain 集）代表无向图中的一个节点。从完整的图开始（即所有节点都相互连接），并根据排他性约束删除边（即如果您使用邻接矩阵 A 来表示您的图，1 !=2 意味着 A(1,2) = 0 和 A(2,1) = 0)。

然后找到 最小 clique 分区，它相当于 最小图形着色。

但是，您可以列出所有最大派系并从那里开始工作。