Der Dancing-Links-Algorithmus - Eine Erklärung, die weniger erklärend, sondern mehr auf die Umsetzung?

Die Sie interessieren könnten meine Implementierung in javascript.

Erstens müssen Sie verstehen, die Genaue Abdeckung. Eine genaue Abdeckung problem ist ein problem, wo Sie gegeben sind eine Reihe von Entscheidungen, und einen Satz von Einschränkungen und Ihre Herausforderung besteht darin, wählen Sie ein paar der Möglichkeiten, die füllen jede Einschränkung genau einmal.

Betrachten wir zum Beispiel den Fall von jemandem, der Erstellung Ihrer eigenen Eis-Tanz-routine. Sie haben eine Reihe von tricks, die Sie brauchen, um zu zeigen, die Richter, und nicht wollen, ausführen, trick mehr als einmal. Sie haben eine Reihe von Sequenzen, die Gruppen von tricks, die zusammengestellt werden können, und Sie möchten, wählen Sie die ideale Auswahl der Sequenzen, um alle tricks einmal. In diesem Beispiel, die Einschränkungen, die Sie ausführen müssen, jeden trick. Die Entscheidungen, sind die möglichen Sequenzen, die Sie könnte integrieren in Ihre routine.

Einer netten Art und Weise zu vertreten, Probleme dieser Art zu erstellen, die eine Tabelle, wo die Einschränkungen sind Spalten und die Möglichkeiten sind Zeilen, und Sie haben ein großes X in den Zellen, in denen eine bestimmte Auswahl erfüllt das constraint.

Wie es sich herausstellt, das Recht erhalten, Zwänge und Möglichkeiten, sudoku kann beschrieben werden als eine Genaue Abdeckung problem.

Ok, vorausgesetzt, Sie haben, jetzt müssen Sie verstehen, Algorithmus X. Knuth sagte "Algorithmus X ist einfach eine Aussage, die offensichtlich trial-and-error-Ansatz. (In der Tat, ich kann nicht denken von jedem anderen vernünftigen Weg, um die Arbeit zu tun, im Allgemeinen.)". Also hier ist meine Beschreibung des Algorithmus X:

1. Wenn Ihre Tabelle hat keine Spalten, stop - du hast es gelöst. Wenn Sie haben eine teilweise Lösung gespeichert, dann ist es tatsächlich eine echte Lösung, es zurückzugeben.
2. Wählen Sie eine Spalte (Darstellung einer integritätsregel).
3. Finden Sie eine Zeile mit einem Kreuz in Spalte (für eine Wahl, die erfüllt, die Einschränkung). Fügen Sie es zu irgendeiner Art von Struktur, wo Sie die Speicherung von möglichen Lösungen. Wenn Sie nicht finden können, eine Zeile, aufgeben - gibt es keine Lösungen.
4. Davon ausgehen, dass die Zeile, die Sie in 3 ist in der Lösung, so entfernen Sie alle Spalten, die es ein X in die betreffende Zeile. Beim entfernen alle Spalten, auch entfernen Sie alle Zeilen, die ein X in die Spalten, die Sie entfernen (da Sie bereits zufrieden die Einschränkung, so sind Sie ausgeschlossen von der Wahl etwas, das erfüllen würde, es wieder).
5. Jetzt rekursiv lösen Sie die reduzierte Tabelle. Wenn Sie nicht können, entfernen Sie die Zeile, die Sie versucht, aus dem Potenzial der Lösung, Struktur, wiederherstellen Sie alle Zeilen und Spalten entfernt, die in den Schritten 3 und 4, und versuchen Sie eine andere Zeile. Wenn Sie Zeilen, dann aufgeben - gibt es keine Lösungen.

Nun, dass Sie verstehen, dass Sie verstehen können, tanzen links. Dancing Links ist die Art der Umsetzung, dass der Algorithmus effizient. Der entscheidende Punkt der dancing-links, die in einer verknüpften Liste beim löschen eines Knotens (was kann getan werden, effizient durch ändern der Zeiger der Nachbarn), den Knoten, den Sie entfernt haben alle Informationen, die Sie brauchen, um es zurück zu der verlinkten Liste (in dem Fall, es stellt sich heraus, Sie waren falsch wenn Sie Ahnen, dass es war Teil der Lösung). Das plus die Tatsache, dass, wenn Sie alle Ihre verknüpften Listen kreisförmigen dann plötzlich verlieren Sie eine Menge von speziellen Fällen ist so ziemlich alles tanzen-links ist.

InformationsquelleAutor der Antwort kybernetikos