算法寻找组件最小集合 [英] Algorithm for finding smallest collection of components

问题描述

我在寻找一种算法来解决以下问题。我公司拥有一批一组给定的（啊）的子集（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
×1
×1
×1
×1
×1
×1
×1

1 1
×1
×1
×1
×1
X 1 1
×1
 

我相信这一定是一个已知的问题，但我不是很熟悉的算法。任何帮助是非常AP preciated，作为一个建议一个更好的主题标题。

谢谢！

更新

图着色让我很长的路要走，谢谢。但是，在我的情况的子集可以重叠。例如：

  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
×1
×1
 

不过这个人是有效的，以及，更小：

  1 1 1 1
4 1 1
 

解决方案

这个问题称为集基础，这是一个NP完全（拉里J. Stockmeyer：本组基本的问题是NP完全技术报告RC- 5431，IBM公司，1975年）。它的配方中的图形问题是偶尺寸。因为它是非常难以解决的一般情况下，它可能是有用的看看是否有您的数据（例如，是集小？是解决小？所有的设置组发生的？）

任何有用的特性

我想不出一个简单的ILP制定的。相反，你可以尝试使用无论是从寇和放大器的降低，可以降低问题桂系封面，这是更好的研究，;黄或也不等人之一。 。我已经coauthered论文讨论算法派盖，并写了的派盖求解既精确的求解器和两个启发。

I'm looking for an algorithm to solve the following problem. I have a number of subsets (1-n) of a given set (a-h). I want to find the smallest collection of subsets that will allow me to construct, by combination, all of the given subsets. This collection can contain subsets that do not exist in 1-n yet.

  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

Below are two possible collections, the smallest of which contains seven subsets. I have denoted new subsets with an 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

I believe this must be a known problem, but I'm not very familiar with algorithms. Any help is very much appreciated, as is a suggestion for a better topic title.

Thanks!

Update

Graph coloring gets me a long way, thanks. However, in my case subsets are allowed to overlap. For example:

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

Graph coloring gives me this solution:

x 1 1
x     1
x       1     

But this one is valid as well, and is smaller:

1 1 1 1  
4     1 1

解决方案

This problem is known as Set Basis, and it is NP-complete (Larry J. Stockmeyer: The set basis problem is NP-complete. Technical Report RC-5431, IBM, 1975). Its formulation as a graph problem is Bipartite Dimension. Since it is very hard to solve in general, it might be useful to look if there are any helpful properties of your data (e.g., are the sets small? Is the solution small? Can all sets occur?)

I cannot think of an easy ILP formulation. Instead, you could try to reduce the problem to Clique Cover, which is better studied, using either the reduction from Kou&Wong or the one from Nor et al.. I have coauthered a paper discussing algorithms for Clique Cover, and written a Clique cover solver with both an exact solver and two heuristics.

这篇关于算法寻找组件最小集合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！