Was wird der beste Algorithmus sein, um ein Puzzle zu lösen

Question

Es ist nicht angegeben, welcher König des Puzzles es ist.

Ich gehe von einem normalen Bild wie Puzzle mit Standardstücken aus. die q-Anweisung: Code zum Lösen von Jigsaw puzzle.Was sind die Datenstrukturen? Angenommen, Sie haben eine Methode, die Ihnen sagen kann, ob zwei Teile zusammenpassen. Wie würdest du das Rätsel lösen und die Anzahl der Male minimieren, die du diese Funktion aufrufen musst?

Wird teilen und erobern der beste Weg sein? Datenstruktur muss ein zweidimensionales Array nach mir sein, was noch?

Answer 1

Kryptoquoten und Kryptogramme werden formal als Substitutions- chiffre bezeichnet. Das ist das Schlüsselwort, das Sie verwenden möchten, wenn Sie mehr Material zu diesem Thema suchen.

Die Substitution Chiffre ist ziemlich einfach zu brechen, sowohl für eine Person und für einen Computer.

Normalerweise ein automatisiertes Solver würde darin bestehen aus zwei Teilen:

• eine Funktion, die einen Text nehmen und bewerten, wie eng es Klartext in der erwarteten Sprache
• einen Algorithmus ähnelt, die für das aussieht Chiffrierschlüssel, der die bestklingenden entschlüsselten Text erzeugt (wobei „bestklingenden“ bedeutet, dass es das Optimum der Funktion in dem vorherigen Punkt erwähnt)

Für die einfache Substitution ist eine gute Wahl für den zweiten Teil jede Art einer heuristischen lokalen Suche, zum Beispiel Hill climbing: Beginne mit zufälligen Permutationen und wende dann kleine Änderungen an, die die Punktzahl des entzifferten Textes verbessern. Die Substitutionsverschlüsselung hat die schöne Eigenschaft, dass der Lösungsraum "glatt" ist: kleine Änderungen am Schlüssel (wie das Vertauschen der Bilder zweier Buchstaben) führen zu kleinen Änderungen am entzifferten Text. Bereits ein paar Iterationen des einfachsten Bergsteigens reichen meist aus, um das globale Optimum zu finden.

Für die Funktion, die die Lösung auswertet, wäre für Cryptoquotes und ähnliche Rätsel eine ziemlich einfache Aufgabe, die überprüft, ob die entschlüsselten Wörter in einer Wortliste für die erwartete Sprache gefunden werden können und möglicherweise ihre Frequenzen für eine weitere verwenden präzise Bewertung. Dies kann gemacht werden, weil die Puzzle-Versionen dieser Chiffre normalerweise Räume und Interpunktion beibehalten.

Ein anderer Ansatz (mein bevorzugter, und einer, der allgemeiner und robuster ist) ist die Verwendung von Statistiken. Anstelle der Wortliste berechnen Sie die Frequenzen von Tetragrammen in Ihrer Sprache vorberechnen. (In diesem Kontext ist Tetragramm = vier aufeinanderfolgende Buchstaben.) Diese können als Wahrscheinlichkeiten für ein Hidden-Markov-Modell verwendet werden, das Strings erzeugt, die der tatsächlichen Sprache ziemlich ähnlich sind, und wir können unsere Bewertungsfunktion als (Logarithmus der) Wahrscheinlichkeit definieren Generator würde die bestimmte Zeichenfolge erzeugen, die wir bewerten. Je höher diese Wahrscheinlichkeit ist, desto mehr klingt die Saite "wie etwas in unserer Sprache".

• Liste item