Ich suche nach einer Möglichkeit, Diagramme zu erstellen, damit die optimale Scheitelpunktabdeckung bekannt ist. Es gibt keine Einschränkungen hinsichtlich der Anzahl der Knoten oder Kanten, nur dass der Graph vollständig verbunden ist.
Die Idee ist, ein Diagramm zu erstellen, das nicht einfach ist, die optimale Scheitelpunktabdeckung zu finden, um verschiedene Heuristiken darauf testen zu können
Ich fand die Zeitung Arthur, J. & Frendeway, J. Generating Travelling-Salesman Problems with Known Optimal Tours, The Journal of the Operational Research Society, Vol. 3, No. 2 (Februar 1988), S. 153-159 zur Erzeugung von TSP mit bekanntem Optimum, leider kann ich nicht darauf zugreifen.
Gibt es einen bekannten Algorithmus?
Antworten:
Erweitern des Kommentars von vzn zu einer Antwort: Die Standardreduktion von CNF-SAT auf Scheitelpunktabdeckung ist ziemlich einfach: Erstellen Sie einen Scheitelpunkt für jeden Term (Variable oder deren Negation), verbinden Sie jede Variable mit ihrer Negation durch eine Kante, erstellen Sie eine Clique für jede Klausel und verbinden Sie jeden Scheitelpunkt in der Clique mit dem Scheitelpunkt für einen der Begriffe in der Klausel. Wenn Sie mit einem Erfüllbarkeitsproblem mit einer bekannten zufriedenstellenden Zuweisung beginnen, erhalten Sie ein Scheitelpunktabdeckungsproblem mit einer bekannten optimalen Lösung (wählen Sie den durch die Zuweisung gegebenen Begriff Scheitelpunkte aus, und wählen Sie in jeder Klauselclique alle bis auf einen Scheitelpunkt aus, so dass die Der nicht ausgewählte Klauselscheitelpunkt grenzt an einen ausgewählten Begriffsscheitelpunkt.
Jetzt müssen Sie also Erfüllbarkeitsprobleme finden, die eine bekannte zufriedenstellende Aufgabe haben, bei denen die Lösung jedoch schwer zu finden ist. Es gibt viele bekannte Möglichkeiten, um schwierige Erfüllbarkeitsprobleme zu generieren (z. B. zufällige k-SAT-Instanzen nahe der Erfüllbarkeitsschwelle zu generieren), aber die zusätzliche Anforderung, dass Sie die zufriedenstellende Zuweisung kennen, schränkt die Möglichkeiten ein. Eine Sache, die Sie hier tun können, ist, eine andere Reduktionsstufe zu durchlaufen, die von einem kryptografisch schwierigen Problem wie der Faktorisierung ausgeht. Das heißt, Sie wählen zwei große Primzahlen p und q, richten eine Boolesche Schaltung zum Multiplizieren von p und q als Binärzahlen ein und übersetzen sie in eine CNF-Formel, in der für jeden Eingang (p und q) und für jeden Zwischenwert eine Variable vorhanden ist ein Draht in der Schaltung, eine Klausel für jeden Ausgang, die ihn zwingt, den richtigen Wert zu haben, und eine Klausel für jedes Gate, die die Ein- und Ausgänge des Gates zwingt, miteinander konsistent zu sein. Übersetzen Sie dann diese CNF-Formel in die Scheitelpunktabdeckung.
Wählen Sie für eine einfachere Strategie zuerst die zufriedenstellende Zuordnung zu einer 3CNF-Formel aus und generieren Sie dann zufällige Klauseln, wobei nur die Klauseln beibehalten werden, die mit der Zuweisung übereinstimmen, und konvertieren Sie sie dann in die Scheitelpunktabdeckung. Wenn die Klauseln eine einheitliche Wahrscheinlichkeit haben, ist dies anfällig für eine gradbasierte Heuristik (der Begriff Scheitelpunkte, der mit der ausgewählten Zuordnung übereinstimmt, hat einen niedrigeren Grad als der Begriff Scheitelpunkte, die dies nicht tun). Dieser Mangel kann jedoch durch Anpassen der Wahrscheinlichkeiten der Klauseln vermieden werden je nachdem, wie viele Bestimmungen der Klausel mit der gewählten Zuordnung übereinstimmen. Wahrscheinlich ist dies anfällig für eine Art Polynom-Zeitangriff, aber es ist möglicherweise kein natürlicher Angriff für die Scheitelpunktabdeckung, sodass möglicherweise eine gute Reihe von Testinstanzen erstellt wird, obwohl nicht viel Garantie für die Härte besteht.
quelle
Der nächste Ref, den ich gefunden habe, war ... Auf harten Fällen von ungefährer Vertex-Abdeckung durch Sundar Vishwanathan. Ich habe keine Refs gesehen, um schwierige Fälle des genauen Problems zu untersuchen.
Wie in meinem Kommentar gibt es eine Menge Forschung zu diesem entsprechenden Ansatz für SAT, der auf die Vertex-Abdeckung reduziert werden kann.
In Bezug auf DEs Kommentar erscheint mir die Idee, zufällige Instanzen zu generieren und nur diejenigen Instanzen auszuwählen, die für einen Standardalgorithmus schwierig sind, völlig vernünftig, insbesondere mit einem empirischen / experimentellen Forschungsansatz [1], der ein Standardarbeitsanweisung für ähnliche Untersuchungen des SAT ist Übergangspunkt. [2]
was übrigens etwas zu sagen hat, wo sich die "harte" Region für jedes andere vollständige NP-Problem befindet [3,4,5], das sich ungefähr auf einen kritischen Punkt in der "Dichte" von 1s in zufälligen Instanzen bezieht, die in binär angegeben sind. für die Scheitelpunktabdeckung würde dies wahrscheinlich der Kantendichte entsprechen.
Beachten Sie, dass der Nachweis, dass man eine Reihe von harten Instanzen und nur harte Instanzen erstellen kann, im Grunde dem P vs NP-Problem entspricht. Eine formellere Analyse dieser Äquivalenz findet sich in der Arbeit Razborov / Rudich Natural Proofs.
[1] experimentelle Algorithmen
[2] SAT-Phasenübergangsforschung
[3] Phasenübergänge bei NP-Problemen
[4] Phasenübergänge bei NP-vollständigen Problemen: eine Herausforderung für Wahrscheinlichkeit, Kombinatorik und Informatik von Moore
[5] Phasenübergangsverhalten von Walsh
quelle