Deckblatt setzen: Testinstanzen generieren

Question

Ich freue mich, die Set Cover Problem mit einem genetischen Algorithmus zu lösen. Ich habe überall nach guten Testinstanzen gesucht, aber ohne großen Erfolg.

Wonach ich suchen möchte, sind einige Instanzen unter der Form: eine Menge U = {1,2, ..., n} und eine Sammlung ihrer Teilmengen S = {{1,2}, {4 }, {3,4,5}}, wo die Vereinigung von S ist U.

Natürlich ist dies ein kleines Beispiel, wie ich gerne einige größere Beispiele finden würde.

Also, hat jemand eine Idee über eine gute Quelle für diese Art von Instanzen, oder vielleicht über eine Möglichkeit, sie zu generieren?

Spätere Bearbeitung: So sehe ich, dass die Frage auf Eis gelegt wurde. Meine schlechte, dann werde ich ein bisschen mehr Details hinzufügen.

Erstens habe ich für einige Test-Instanzen für Set Cover-Problem gegoogelt. Was ich erwartet habe, waren einige Beispiele wie die oben beschriebenen. Hartes Glück, ich habe etwas ähnlich zu this gefunden. Ich muss sagen, dass es in dem Link nicht so viele Details gab, die mich diesen Instanzen verleihen.

Also fing ich an, eine Methode zu denken, sie zu erzeugen. Eine pseudocodish Lösung:

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) 

Obwohl ich war, wenn Vereinigung (Subsets) = G nicht sicher, so dass es, wo meine Zweifel waren, ist also, warum ich in der Notwendigkeit für einige bereits produzierten Testinstanzen war.

Answer 1

Sie können ein Set generieren, indem Sie eine zufällige Stichprobe aus einer Liste möglicher Zahlen erhalten. Und sie erzeugen eine Liste (mit vorherbestimmter Größe) ihrer Teilmengen, indem sie zufällige Stichproben mit zufälliger Größe erhalten, und für die letzte Teilmenge vervollständigen Sie einfach, was fehlte, so dass die Summe der Teilmengen vollständig gesetzt wird.

Beispiel:

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}]