セットカバー：テストインスタンスの生成

Question

遺伝子アルゴリズムを使用してSet Cover Problemを解決することを楽しみにしています。私はいくつかの良いテストのインスタンスを探していましたが、大きな成功はありませんでした。

私が探しているのは、ある集合U = {1,2、...、n}とその部分集合の集合S = {{1,2}、{4 }、{3,4,5}}、ここでSの和集合はUです。

私はいくつかのより大きなインスタンスを見つけたいので、これは小さな例です。

だから、誰かがこの種のインスタンスの良い情報源について、あるいはそれらを生成する方法について考えていますか？

後で編集：質問が保留になっていることがわかります。私の悪いところ、私は少し詳細を追加します。

まず、私はセットカバーの問題のためのいくつかのテストインスタンスを探してきました。私が見いだしたいと思っていたのは、私が上に述べたもののようなものでした。幸運にも、thisと似たようなものが見つかりました。私はそれらのインスタンスに私を貸すリンクに多くの詳細がないと言う必要があります。

私はそれらを生成する方法を考え始めました。 pseudocodishソリューション：

given set G=[1,2....,n] 
no_of_subsets = random integer 
subsets = [] 
for i in k: 
    subset = random.sample(G, random(0, len(G)) 
    subsets.add(subset) 

私は労働組合（サブセット）= G、もしわからなかったので、私はいくつかすでに生産テスト・インスタンスを必要としていた理由ですので、私の疑問があったところがあったけど。

Answer 1

可能な番号のリストからランダムサンプルを取得するセットを生成できます。また、ランダムなサイズのランダムサンプルを取得することによってサブセットのリスト（あらかじめ決められたサイズ）を生成します。最後のサブセットでは、欠落したものだけを完成させるので、サブセットの合計が完全に設定されます。

例：

import random 

n = 100 
m = 10 #size of set 
l = 5 #size of list of subsets 
possible_numbers = range(n) 

U = set(random.sample(possible_numbers, m)) 

subsets = [] 
control = set() 
for i in range(l - 1): 
    sub_size = random.randrange(m) 
    sub = set(random.sample(U, sub_size)) 
    subsets += [sub] 
    control |= sub 

rest = U - control  
if rest: 
    subsets += [rest] 

print(U) 
--> {97, 99, 69, 9, 15, 52, 53, 55, 28, 30} 

print(subsets) 
--> [{28, 52, 69, 55}, {69}, {99, 28, 52, 55}, {69, 9, 15, 52, 53, 55}, {97, 30}]