Überlegen Sie:
%Vor% Ein Alphabet i_index ist benachbart zu einem anderen Alphabet j_index in der Kachel, wenn i_index neben j_index in einer der folgenden Positionen steht:
Hier geben alle * den Ort an, der an x angrenzt.
Die Aufgabe besteht darin, eine gegebene Zeichenfolge in der Kachel zu finden. Die Bedingung ist, dass alle Zeichen der gegebenen Zeichenfolge benachbart sein sollten und dass kein einziges Zeichen in der Kachel mehr als einmal verwendet werden darf, um die gegebene Zeichenfolge zu konstruieren.
Ich habe eine einfache Backtracking-Lösung entwickelt, für die die Lösungen ziemlich schnell sind, aber die Worst-Case-Zeit ist wirklich schlimmer.
Für ein Beispiel: Sagen wir, die Kachel hat 4x4 gefüllt mit allen a , also 16 a , und die zu suchende Zeichenfolge ist aaaaaaaaaaaaaaab , das heißt 15 a und ein b . Eine Möglichkeit, Strings mit Zeichen zu eliminieren, die nicht in der Kachel erscheinen. Es kann aber immer noch der schlimmste Fall auftreten, wenn die Kachel abababababababab hat und die zu suchende Zeichenfolge abababababababbb ist.
Mein Versuch ist so:
Ссылка :
%Vor%was druckt:
%Vor% Die Funktion sp erledigt die Arbeit, führt die Rückverfolgung durch.
Gibt es einen besseren Weg? Oder ist es möglich, die Worst-Case-Zeit zu senken?
Es gibt keinen Polynomalgorithmus, also glaube ich nicht, dass Sie viel besser werden können ...
Es ist möglich, jedes Gitterdiagramm (ein ebenes Diagramm mit Knoten mit Grad & lt; = 4) unter Verwendung einer Buchstabenmatrix zu codieren. Das folgende Raster
%Vor%Kann konvertiert werden, indem Kanten in 'a's, Ecken in' b's und leere Räume in 'z's
umgewandelt werden %Vor%Die Suche nach einem Hamilton-Pfad in der ursprünglichen Grafik entspricht der Suche nach der Zeichenfolge BaBaBaBaBaBaBaBaB (mit allen 9 Bs). Aber das Hamilton-Pfad-Problem für Gitter in NP-vollständig *, so dass das Wortsuchproblem NP-schwer ist.
Da ein Wortpfad eindeutig ein Polynomzertifikat ist, ist das Wortsuchproblem in Matrizen NP-vollständig .
* Ich erinnere mich, dass ich vor einiger Zeit einen Beweis dafür gesehen habe und Wikipedia bestätigt habe, aber ohne auf eine Referenz & gt; : /
Ich bin mir ziemlich sicher, dass da draußen mehr zu diesem Problem ist. Ich habe diesen Beweis gerade aus meinem Arsch gezogen und ich bin mir ziemlich sicher, dass nicht die Ersten das Problem betrachtet haben. Zumindest gibt es eine gute Chance für nette Heuristiken auf die nicht-degenerierten Fälle, die Sie in einem echten Magazin Puzzle bekommen ...
Eine einfache Verbesserung besteht darin, den Wert von r nach jedem Aufruf von sp zu überprüfen. Wenn r == 1 , dann hör auf, sp aufzurufen. Du hast deine Lösung gefunden. Dies ist, es sei denn, Sie müssen alle möglichen Lösungen finden.
In etwa so (logischer ODER-Operator berechnet den zweiten Operanden nicht, wenn der erste wahr ist):
%Vor%Ich denke, Sie könnten feststellen, dass die Konzentration auf den schlimmsten Fall hier kontraproduktiv ist, weil es keine wirkliche Verbesserung gibt. Es gibt jedoch viele nützliche Verbesserungen in "echten" Fällen. Zum Beispiel, wenn die Wörter immer aus einem Wörterbuch stammen, wenn sie in der Länge begrenzt sind (oder statistisch gesehen eine natürliche Längenverteilung haben). Bei kleinen Rastern können Sie sich vorstellen, sie im Voraus zu suchen, um alle Wörter aus einem Wörterbuch zu finden, die Liste in einer Hashmap zu speichern und dann eine einfache Suche durchzuführen, da Wörter "getestet" werden müssen. Die ganze Zeit geht in den Aufbau Ihres Indexes, aber das kann akzeptabel sein, wenn sich das Raster selten ändert.
Tags und Links algorithm backtracking