Indeksowanie w bazie danych wzorców - rozwiązanie Corf Optimal Rubik's Cube

Jako zabawny projekt pracowałem nad implementacją C # Richarda Korfa - Znalezienie optymalnych rozwiązań dla kostki Rubika przy użyciu baz danych wzorców.

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

Właściwie to działa, staram się tylko ulepszyć swoje rozwiązanie.

Jedną rzeczą, na którą Korf patrzy w swoim artykule, jest to, jak przechowuje i indeksuje bazy danych wzorców. Idealnie, myślę, że chcemy użyć instancji kostki rubika do wygenerowania indeksu w tablicy.

Moje pytanie dotyczy najlepszego sposobu wygenerowania tego indeksu.

Moim rozwiązaniem jest wygenerowanie minimalnego idealnego skrótu. Obejmuje to przechowywanie WSZYSTKICH kostek w pamięci, dopóki nie odkryję całej bazy danych wzorców, a następnie wygenerowanie minimalnego idealnego skrótu na podstawie tego. Uruchomienie MPH zajmuje kilka godzin, w zależności od rozmiaru bazy danych wzorców, ale muszę to zrobić tylko raz, odkąd zapisuję go na dysku. Na koniec mogę wyrzucić same kostki przechowujące tylko MPH. W ten sposób mogę wziąć losową kostkę Rubika, zastosować wzór, a następnie sprawdzić indeks tablicy w MPH, aby uzyskać szacunkową długość rozwiązania.

Wierzę, że Korf i Shultz opisują lepszy sposób określania indeksu kostki w artykule z 2005 r. Zatytułowanym „Duże wyszukiwanie w pierwszej skali”

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

W tym artykule opisano algorytm generowania indeksu na podstawie uporządkowania leksykograficznego permutacji. Zasadniczo możesz wziąć permutację {1, 2, 3} i przekonać się, że jest ona najmniejsza z indeksem 0. {1, 3, 2} jest następnie z indeksem 1 i tak dalej.

Wydaje mi się, że powinienem być w stanie zastosować ten algorytm do kostki Rubika, aby uzyskać jej indeks w bazie danych wzorców, ale trudno mi się zorientować, jak będzie działać w praktyce.

Baza danych wzorów tylko na rogach zawiera na przykład wszystkie kostki Rubika, które zostały zdjęte z krawędzi. W tym zestawie znajduje się dokładnie 88 179 840 kostek. Dowolny narożny sześcian na kostce rubika może znajdować się w jednym z 24 różnych stanów. Stan kostki 8 narożnika można obliczyć na podstawie pozostałych 7, więc każda kostka w bazie danych wzorów tylko w rogach ma 7 wartości od 0 do 23

np. {0, 3, 6, 9, 12, 15, 18, 21} definiuje „rozwiązany” sześcian ze wszystkimi naklejkami na krawędzi.

jeśli obrócę przednią powierzchnię o 90 stopni, permutacja może wyglądać następująco: {0, 3, 11, 23, 12, 15, 8, 20}

Czy istnieje sposób na uzyskanie indeksu z tego rodzaju permutacji?

Nie wyjaśniasz, co oznaczają liczby od 0 do 23, ale zgodnie z tą odpowiedzią możesz przedstawić stan narożników za pomocą ośmiu par , gdzie jest permutacją , i (powiedzmy) jest określony przez . W sumie daje to stopni swobody. Zakładając, że możesz rozłożyć swoje na pary , możesz łatwo przekonwertować pozycję na indeks, kodując osobno permutację$(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)$(co w dokumencie AAAI wyjaśnia, jak to zrobić) oraz wartości , które można zakodować w bazie 3. Złożenie dwóch wartości w oczywisty sposób (na przykład lub ), otrzymujemy indeks.$o_0,\ldots,o_6$$3^7p + o$$8!o + p$