用于查找最小组件集合的算法

Question

我正在寻找一种算法来解决以下问题.我有一组给定集合(ah)的子集(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

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

谢谢!

更新

图形着色让我走了很长的路,谢谢.但是,在我的情况下,允许子集重叠.例如:

  a b c d
1 1 1 1  
2 1 1 1 
3 1 1 1
4     1 1
5 1 1 1 1

图形着色给了我这个解决方案:

x 1 1
x     1
x       1     

但是这个也是有效的,而且更小:

1 1 1 1  
4     1 1

Answer 1

这个问题被称为Set Basis,它是NP-complete(Larry J. Stockmeyer:集合基础问题是NP-complete.技术报告RC-5431,IBM,1975).它作为图形问题的公式是Bipartite Dimension.由于一般来说很难解决,因此查看数据是否有任何有用属性可能很有用(例如,集合是否小？解决方案是否小？是否可以进行所有集合？)

我想不出一个简单的ILP配方.相反,你可以尝试将问题减少到Clique Cover,这是一个更好的研究,使用Kou&Wong的减少或Nor等人的减少..我已经讨论了一篇讨论Clique Cover算法的论文,并用一个精确的求解器和两个启发式编写了一个Clique求解器.

Answer 2

这个问题在Coursera 的离散优化讲座视频中有所展示。IIRC，这称为集合覆盖问题。

IIRC，它是 NP 完全的或 NP 困难的，因此请研究典型算法（小型数据集的精确算法，中/大数据集的元启发式）和典型框架（OptaPlanner，...）