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

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

忽略平衡,这是图形着色.

域<=>图的顶点

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

排他性约束<=>图的边缘.

不幸的是,图形着色是NP难的,并且可证明的近似比率不好.有很多很多启发式方法.