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

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 $\mathbf{S}$$M$$S$$\mathbf{S}$$M$$M$$M$

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 , $\mathbf{S}$$S$$\mathbf{S}$S = { r e d , g r e e n } M M $S = \{red, white, blue\}$$S = \{red, green\}$$M$$M$$M$

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$

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ür$n$$k$$O(f(k)\cdot n^{O(1)})$$f(k)$$k$p k$p$-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$

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 = $\mathbf S$$s$$M = \{s\}$$c$$\{c\}$$1$$M$$\mathbf S$$A$$M = A$

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 :)

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.