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

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}

这里的 != 是可传递的。

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

感谢您的帮助。

JT

Answer 1

忽略余额，这是graph coloring .

域<=>图的顶点

设置<=>所有具有特定颜色的顶点

排他性约束 <=> 图的边。

不幸的是，图形着色是 NP-hard，可证明的近似率并不好。有很多很多启发式方法。