Indizierung in eine Musterdatenbank - Korfs Optimal Rubik's Cube-Lösung

11

Als lustiges Projekt habe ich an einer C # -Implementierung von Richard Korfs gearbeitet - Suche nach optimalen Lösungen für Rubiks Würfel mithilfe von Musterdatenbanken.

https://www.cs.princeton.edu/courses/archive/fall06/cos402/papers/korfrubik.pdf

Ich habe es tatsächlich zum Laufen gebracht, ich versuche nur, meine Lösung zu verbessern.

Eine Sache, die Korf in seinem Papier glasiert, ist, wie er die Musterdatenbanken speichert und indiziert. Im Idealfall möchten wir eine Instanz eines Zauberwürfels verwenden, um einen Index in ein Array zu generieren.

Meine Frage ist, wie dieser Index am besten generiert werden kann.

Meine Lösung besteht darin, einen minimalen perfekten Hash zu generieren. Dies beinhaltet, ALLE Cubes im Speicher zu halten, bis ich die gesamte Musterdatenbank entdeckt habe, und daraus einen minimalen perfekten Hash zu generieren. Die Ausführung des MPH dauert je nach Größe der Musterdatenbank einige Stunden. Ich muss ihn jedoch nur einmal ausführen, da ich ihn auf der Festplatte speichere. Am Ende kann ich die Würfel selbst wegwerfen und nur das MPH speichern. Auf diese Weise kann ich einen zufälligen Zauberwürfel nehmen, das Muster anwenden und dann den Array-Index im MPH nachschlagen, um eine geschätzte Lösungslänge zu erhalten.

Ich glaube, Korf und Shultz beschreiben in ihrer Veröffentlichung von 2005 mit dem Titel "Large Scale Breadth-First Search" einen besseren Weg, um den Index des Würfels zu bestimmen.

https://www.aaai.org/Papers/AAAI/2005/AAAI05-219.pdf

In diesem Artikel wird ein Algorithmus zum Generieren eines Index basierend auf der lexikografischen Reihenfolge einer Permutation beschrieben. Grundsätzlich können Sie die Permutation {1, 2, 3} nehmen und herausfinden, dass sie mit einem Index von 0 die kleinste ist. {1, 3, 2} folgt mit einem Index von 1 und so weiter.

Ich denke, ich sollte in der Lage sein, diesen Algorithmus auf einen Zauberwürfel anzuwenden, um seinen Index in einer Musterdatenbank abzurufen, aber es fällt mir schwer, herauszufinden, wie er in der Praxis funktionieren würde.

Die Musterdatenbank nur für Ecken enthält beispielsweise alle Rubik-Würfel, deren Kantenaufkleber entfernt wurden. Es gibt genau 88.179.840 Würfel in diesem Set. Jeder Eckwürfel auf einem Zauberwürfel kann sich in einem von 24 verschiedenen Zuständen befinden. Der Zustand des Würfels der 8. Ecke kann basierend auf den anderen 7 berechnet werden, sodass Würfel in der Nur-Ecken-Musterdatenbank jeweils 7 Werte zwischen 0 und 23 haben

Beispiel: {0, 3, 6, 9, 12, 15, 18, 21} definiert den "gelösten" Würfel, bei dem alle Kantenaufkleber entfernt sind.

Wenn ich die Vorderseite um 90 Grad drehe, kann die Permutation wie folgt lauten: {0, 3, 11, 23, 12, 15, 8, 20}

Gibt es eine Möglichkeit, aus solchen Permutationen einen Index zu erhalten?

Kosmose
quelle
Sie werden wahrscheinlich finden diese interessant.
Tom van der Zanden
interessant! Sie sagen, er "glasiert" etwas in der Zeitung. Es wäre besser, genauer auf den Abschnitt einzugehen, der nicht "konkretisiert" ist. Sie sagen auch, Sie haben es funktioniert. Was ist Ihre anfängliche Indizierungsimplementierung? Ist das ein Schulprojekt? Schlage einen weiteren Informatik-Chat vor. Auch zB das Bloggen darüber oder Open Sourcing des Codes kann für andere hilfreich sein und zu mehr Details führen. auch scheint sich das Papier nicht auf irgendwelche Hashing-Funktionen zu beziehen ...
vzn
Ich habe Korfs Algorithmus implementiert: github.com/benbotto/rubiks-cube-cracker . Auch ich fand die Indizierung schwierig, deshalb schrieb ich einen Artikel darüber auf Medium: medium.com/@benjamin.botto/…
avejidah

Antworten:

6

(pi,oi)(p0,,p7)(0,,7)Öich{0,1,2}}Ö7o0,,o68!37=88179840{0,,23}(pi,oi)(p0,,p7)o0,,o637p+Ö8!Ö+p

Yuval Filmus
quelle
Hey Yuval, danke für den Kommentar. Mit 0 bis 23 identifiziere ich für mich die eindeutige Position / Ausrichtung, in der sich ein Eckwürfel befinden kann. 8 Positionen mal 3 Ausrichtungen pro Position = 24. Glücklicherweise kann ich diesen Wert leicht in separate Positions- / Ausrichtungstupel aufteilen. Ihre Antwort führte mich zu diesem Code, der eine Implementierung des von Ihnen beschriebenen Algorithmus darstellt. github.com/brownan/Rubiks-Cube-Solver/blob/master/cornertable.c Ich muss ein bisschen arbeiten, um dies allgemeiner zu gestalten (damit ich andere Muster als "nur Ecken" verarbeiten kann), aber jetzt Ich bin auf dem richtigen Weg, danke!
Cosmosis