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

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?

$(p_i,o_i)$$(p_0,\ldots,p_7)$$(0,\ldots,7)$$o_i \in \{0,1,2\}$$o_7$$o_0,\ldots,o_6$$8! \cdot 3^7 = 88179840$$\{0,\ldots,23\}$$(p_i,o_i)$$(p_0,\ldots,p_7)$$o_0,\ldots,o_6$$3^7p + o$$8!o + p$