Suchen Sie aus einer Menge von Mengen die kleinste (n) Menge (n) mit mindestens einem Element aus jeder Menge

15

Bei einer Menge von Mengen würde ich gerne eine Menge so dass jede Menge in mindestens ein Element von . Ich möchte auch, dass so wenig Elemente wie möglich enthält, während dieses Kriterium noch erfüllt ist, obwohl es möglicherweise mehr als ein kleinstes mit dieser Eigenschaft gibt (die Lösung ist nicht unbedingt eindeutig). M S S M M MSMSSMMM

Nehmen wir als konkretes Beispiel an, dass die Menge die Menge der Nationalflaggen ist und dass für jede Flagge in die Elemente die Farben sind, die in der Flagge dieser Nation verwendet werden. Die Vereinigten Staaten hätten und Marokko hätte . Dann wäre eine Menge von Farben mit der Eigenschaft, dass jede Nationalflagge mindestens eine der Farben in . ( Die olympischen Farben Blau, Schwarz, Rot, Grün, Gelb und Weiß sind ein Beispiel für ein solches , oder waren es zumindest 1920.) S S S = { r e d , wSSSS = { r e d , g r e e n } M M MS={red,white,blue}S={red,green}MMM

Gibt es einen allgemeinen Namen für dieses Problem? Gibt es einen akzeptierten "besten" Algorithmus zum Finden der Menge ? (Ich bin mehr an der Lösung selbst interessiert als an der Optimierung des Prozesses für die Komplexität der Berechnungen.)M

bdesham
quelle
2
Könnten Sie nach dem Set-Cover-Problem suchen ?
Juho
@Juho Nicht ganz. In meinem Beispiel wäre das Problem, eine Reihe von Flags zu finden, so dass die Vereinigung dieser Flags alle Farben enthält, die für alle Flags verwendet werden. Im Gegensatz dazu suche ich nach etwas, das nur eine Liste von Farben und keine Liste von Flaggen ausspuckt, und ich brauche nicht die Menge , um jede mögliche Farbe zu enthalten. Ich werde mich auf Wikipedia in diesem Bereich umsehen, ich glaube, du hast mich auf den richtigen Weg gebracht. Vielen Dank! M
Bdesham

Antworten:

13

Das Problem ist das bekannte NP- Complete Problem Hitting Set . Es ist eng mit Set-Cover verwandt . Der NP-Vollständigkeitsnachweis findet sich im klassischen Buch von Garey und Johnson .

Wenn Sie es approximieren möchten, möchten Sie Ihre Instanz möglicherweise zuerst in Set-Cover übersetzen und dann einen Approximationsalgorithmus für Set-Cover anwenden. Set-Cover kann jedoch nicht durch einen konstanten Faktor in der Polynomzeit approximiert werden, es sei denn, P = NP, wie von Lund und Yannakakis gezeigt .

Wenn Sie an genauen Lösungen interessiert sind und sich Ihre Eingaben gut verhalten, würde ich die Verwendung eines Tractable mit festen Parametern empfehlen . Die Laufzeit wird hier nicht nur über die Eingabelänge ausgedrückt, sondern auch über einen zusätzlichen Parameter . Ist die Laufzeit , nennen wir den Algorithmus einen FPT-Algorithmus. Hier ist eine zunehmende Funktion. Wenn also konstant ist, haben wir einen Polyzeitalgorithmus. Das erste Kapitel des Buches von Flum und Grohe erklärt einen FPT-Algorithmus zum Schlagen von Mengen (genauer gesagt fürnkO(f(k)nO(1))f(k)kp kp-Kartenschlagset). Der Algorithmus ist einfach zu implementieren und verwendet die Methode der begrenzten Suchbäume. Trotzdem braucht es zu viel Platz, um dies zu erklären. Im Grunde genommen zerlegen Sie die notwendige (?) Brute-Force-Suche in kleine Stücke (wenn klein ist).k

A.Schulz
quelle
Vielen Dank. Können Sie irgendwo eine Referenz für aktuelle Implementierungen bereitstellen? Dh wie würde ich mein Problem in ein Set-Cover-Problem übersetzen und wie würde ich das dann lösen?
Bdesham
1
Stellen Sie sich jedes Element als die Menge der Mengen vor, zu denen es gehört. Führen Sie set cover für die Eingabe elements-as-sets aus. Lesen Sie auch die hier verlinkte Wiki-Seite.
Sasho Nikolov
Interessieren Sie sich für eine ungefähre Lösung oder möchten Sie die genaue Lösung haben?
A.Schulz
Ich hätte gerne eine genaue Lösung. Die Datenmengen, mit denen ich arbeite, sind so klein, dass ich nicht denke, dass dies ein Problem sein sollte.
Bdesham
1
@Keyser: Du hast recht. Es ist jedoch üblich, das Entscheidungsproblem mit dem entsprechenden Optimierungsproblem zu verknüpfen, da diese für NP-vollständige Probleme eng verwandt sind.
A.Schulz
2

Eine Idee , die helfen könnte: wenn der Schnittpunkt aller Sätze in in nicht leer ist , dann können Sie jedes Element auswählen in der Kreuzung und setzte . Wenn die Schnittmenge leer ist, suchen Sie ein Element (Farbe) dessen Vorkommen in Mengen maximal ist, und ersetzen Sie alle Mengen, in denen es vorkommt, durch den Singleton . Tun Sie dies so lange, bis die Anzahl der Vorkommen jedes Elements gleich und setzen Sie dann auf die Vereinigung der verbleibenden Mengen. Wenn beispielsweise ist die Leistung Satz von irgendeinem Satz dann . Ich könnte mich jedoch irren. s M = { s } c { c } 1 M S A M = ASsM={s}c{c}1MSAM=A

Saadtaame
quelle
2

Schauen Sie sich Ray Reiters "Eine Theorie der Diagnose anhand erster Prinzipien" an, in dem er einen Algorithmus zur Berechnung von Schlagmengen und diese zusätzliche Anmerkung "Eine Korrektur ..." vorstellt .

Der Algorithmus ist allgemein als "Hitting Set Tree" -Algorithmus bekannt. Es sollte nicht zu schwierig sein, eine Implementierung zu finden. Sie haben erwähnt, dass Sie sich nicht zu sehr für die Laufzeit interessieren, aber Optimierungen wie die vorzeitige Beendigung von Zweigen usw. sind für die Implementierung sehr wichtig und auch interessant :)

papercutexit
quelle
2
Können Sie den Algorithmus zusammenfassen, um Ihre Antwort eigenständiger zu machen? Links können und werden brechen.
Juho
0

In der Praxis ist eine der besseren Möglichkeiten (sicherlich eine der einfachsten), Instanzen von Set Cover / Hitting Set zu lösen, die Programmierung von gemischten Ganzzahlen. Dies beinhaltet die Übermittlung der ganzzahligen Programmierformulierung an den Löser Ihrer Wahl.

Barney
quelle