Wahrscheinlich war jeder mit der Tatsache konfrontiert, dass er sich einer schwierigen Aufgabe stellen musste, deren Lösung nicht sofort gefunden werden konnte - sondern auch nach langen, hartnäckigen Arbeitsstunden oder Tagen. Heute werden wir über eine der Klassen solcher Probleme sprechen - NP-vollständig.
Ist es im Allgemeinen realistisch, solche Aufgaben im Alltag zu erfüllen? Tatsächlich treten sie in einer Vielzahl von Fällen auf: Kombinatorik, Graphen und Netzwerke, Ausführung logischer Formeln, Arbeiten mit Karten, optimale Ladungen, Karten, diskrete Optimierungsprobleme, Finden der längsten Sequenzen, Finden gleicher Summen und viele festgelegte Probleme! Und dies ist keine vollständige Liste.
Unter dem Schnitt befindet sich eine informelle Anleitung - wie man versteht, dass Sie möglicherweise ein NP-Problem vor sich haben und was zu tun ist, wenn sich herausstellt, dass dies so ist. Heute greifen wir dieses Problem von der praktischen Seite an.
Stellen Sie sicher, dass sie wirklich vor Ihnen ist
Woher wissen Sie, wann Sie mit einem NP-vollständigen Problem konfrontiert sind? Erstens ist die einfachste Erkennungsheuristik das Durchsuchen bereits bekannter NP-vollständiger Probleme, um etwas Ähnliches zu bestimmen. Es gibt zum Beispiel viele solcher Listen .
Zweitens sollten Sie die folgenden Eigenschaften von Aufgaben berücksichtigen:
- Wir müssen eine Lösung wählen, in der n Elemente aus dem Raum exp (n)
- Wenn Sie bereits eine Lösung der Länge n aus diesem Raum haben, kann diese leicht (polynomiell) überprüft werden
- Die Wahl eines der Entscheidungselemente (kann) beeinflusst die Wahl aller anderen (nicht unbedingt aller).
- Im schlimmsten Fall können die Optionen immer aufgelistet werden, wobei der gesamte Exponentialraum durch eine einfache Aufzählung berücksichtigt wird.
- Die Parameter n - die Länge der Lösung oder der Raum selbst haben keinen festen Wert, dh wir sprechen nicht über das immer feste 8 x 8-Schachbrett, sondern über die allgemeine Form des N-mal-N-Problems.
Lesen Sie hier und hier mehr über die Eigenschaften von NP-vollständigen Problemen .
Ein Beispiel für die Arbeit an dieser Liste
Lassen Sie uns ein einfaches Beispiel für ein Problem geben, das kürzlich als NP-vollständig genehmigt wurde!
Basierend auf den Materialien des Artikels. Sie müssen N Königinnen auf ein Brett der Größe N mal N legen, vorausgesetzt, dass bereits K <= N auf dem Brett platziert sind (Bild aus dem ursprünglichen wissenschaftlichen Artikel).
Beachten Sie zunächst, dass ein sehr ähnliches Problem mit teilweise eingeschränkten lateinischen Quadraten NP vollständig ist.
Und dann gehen wir die Liste durch:
- Sie müssen N Königinnen aus dem Raum exp (N) (= N ^ 2 * (N ^ 2-1) * ....) finden.
- Die Lösung von N Königinnen wird trivial überprüft - für jede Königin müssen Sie die Diagonalen, Vertikalen und horizontalen Linien überprüfen.
- Wenn Sie eins einstellen, wird die Auswahl einer Reihe anderer ungültig - d. H. Es gibt Abhängigkeiten zwischen den Elementen der Lösung (Sie können Königinnen nicht unabhängig voneinander anordnen).
- Hier können Sie das Problem mit brutaler Gewalt für ein willkürlich ausgewähltes Board in exp (N) lösen - wir setzen das erste in das erste auf die Position (i, j), das zweite auf ein anderes unbesetztes Board und so weiter. Backtracking ist garantiert, um eine Lösung zu finden.
- Das Problem hat keine festen Parameter - das heißt, es wird in einer allgemeinen Form formuliert und mit zunehmendem N wächst auch die Komplexität.
Beachten Sie, dass eines der Elemente in der Liste fehlschlägt, wenn bekannt ist, dass das Board immer sauber ist und die Aufgabe trivial wird.
Darüber hinaus handelt es sich um einen bedingten praktischen Ansatz - eine Heuristik zur Erkennung von NP-vollständigen Problemen (mit allen Vor- und Nachteilen).
Mischen
Quelle
Warum ist es angesichts ähnlicher Probleme formal nicht leicht zu verstehen, dass wir mit einem NP-Problem konfrontiert sind? Wir müssen wirklich ein NP-Problem für uns lösen, dann werden wir sicher wissen, dass unser Problem NP-schwer ist! Und wenn wir es simulieren könnten, wie in der obigen Liste, dann ist es vollständig - das heißt, mindestens NP und nicht mehr als NP, tatsächlich „das schwierigste unter den NP-Problemen“ (wie der Rest der NP-vollständigen).
Okay, brauchen wir es? Nicht wirklich, wenn Sie nach all den Überprüfungen unkompliziert sind, dass Sie mit einem NP-Problem konfrontiert sind, müssen Sie nichts beweisen, es sei denn, Sie schreiben einen wissenschaftlichen Artikel.
Und Sie brauchen auch (wir werden unten darüber sprechen):
- Simulieren Sie Ihre Aufgabe mit Systemen, die solche Aufgaben lösen.
- Finden Sie eine Lösung, die in Ihrem Fall schnell genug funktioniert.
- Finden Sie eine ungefähre Lösung, die uns zufriedenstellt.
Gib nicht auf!
Das Wichtigste ist, Dimensionsparameter und realistische Szenarien zu bewerten!
xkcd.com/287
Sie wissen beispielsweise, dass trotz der Tatsache, dass die Werte der Parameter nicht festgelegt sind, die bedingte N <100 nicht in allen praktischen Szenarien implementiert ist, was bedeutet, dass die bedingte Aufzählung eine echte Lösung für Sie sein kann.
Sie müssen selbst bestimmen: Was sind meine tatsächlichen Werte von Parametern, die möglich sind und wirklich in das System gelangen, wie ist die allgemeine Verteilung und die Merkmale der Daten, was ist real und was nicht? Benötigen wir die optimalste Lösung? Lassen Sie uns diese Punkte durchgehen.
Verteilung der Eingabedaten
Oder trotz der Tatsache, dass die Eingabedaten im allgemeinen Fall beliebig sein können, aber auch hier für das Beispiel der Königinnen - normalerweise ist eine Königin fest oder gar keine. Dies bedeutet, dass Sie in 90% der Fälle eine sehr einfache Lösung verwenden und nur in extremen Fällen eine komplexe aufrufen können.
Ein Beispiel, bei dem im Durchschnitt alle üblichen Kombinationen einfach sind: das Problem der Ergänzung von Königinnen - wir wissen, dass bedingte DFS + -Heuristiken in den meisten Fällen sehr schnell Lösungen finden können und nur in sehr ungewöhnlichen Situationen äußerst schwierig sein können.
Hier ist ein Beispiel dafür, wie die Lösung für ein sehr spezialisiertes NP-vollständiges Kachelproblem anhand einer allgemeinen Methode zur Modellierung einer ganzen Klasse solcher Probleme unter Verwendung logischer Programmiertechniken bewertet wurde:
(aus dem Artikel Relationale Datenfaktorisierung (Paramonov, Sergey; van Leeuwen, Matthijs; De Raedt, Luc: Relationale Datenfaktorisierung, Maschinelles Lernen, Band 106))
Erstens unterscheiden sich die Geschwindigkeit der speziellen LTM-k-Lösung und die allgemeine Methode erheblich. Somit kann eine heuristische Lösung für genau diese Art von Problem dieses Problem vollständig lösen.
Zweitens ergab die allgemeine Approximationsmethode durch Einbußen bei der Qualität der Lösung eine sehr ähnliche Geschwindigkeit.
Heuristik und Approximation
Das letzte und leistungsstärkste Tool ist die Verwendung von NP-vollständigen Problemmodellierungssystemen wie Answer Set Programming .
Mehr über logische Programmiersprachen.
Die Lösung für das Problem der Platzierung von Königinnen sieht beispielsweise folgendermaßen aus:
% domain
row(1..n).
column(1..n).
% alldifferent: guess a solution
1 { queen(X,Y) : column(Y) } 1 :- row(X).
1 { queen(X,Y) : row(X) } 1 :- column(Y).
% remove conflicting answers: check this solution
:- queen(X1,Y1), queen(X2,Y2), X1 < X2, Y1 == Y2.
:- queen(X1,Y1), queen(X2,Y2), X1 < X2, Y1 + X1 == Y2 + X2.
:- queen(X1,Y1), queen(X2,Y2), X1 < X2, Y1 - X1 == Y2 - X2.
Nachdem wir ein einfaches Experiment durchgeführt haben, um Lösungen für eine andere Anzahl von Königinnen N zu finden, erhalten wir Folgendes: entlang der X-Achse - Königinnen, entlang der Y - Zeit pro Sekunde, um eine Lösung zu finden:
Wir sehen, dass wir trotz der Tatsache, dass das Zeitwachstum eindeutig kein Polynom ist (was logisch ist), gute Arbeit mit einer angemessenen Anzahl von Königinnen und Brettgrößen leisten.
Wenn wir dann wissen, welche Platinenabmessungen für uns real sind, können wir verstehen, wie diese genaue Lösung für uns in einem realen System akzeptabel ist.
Schlussfolgerungen
Lassen Sie uns die Ideen aus dem Artikel in Form einer Checkliste durchgehen
- Stellen Sie fest, dass Sie wirklich ein NP-Problem haben.
- Verstehen Sie, was realistische Parameterwerte und Datenverteilung sind.
- Versuchen Sie zu schreiben (die Reihenfolge hängt vom Entwickler und / oder der Aufgabe ab):
- Eine genaue heuristische Lösung (basierend auf unserer Analyse) - wird sie schnell genug sein?
- — ?
- NP- — ? , CPU ? .
- : , .
- — , — . !
:
