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

11

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?

Kosmoza
źródło
Prawdopodobnie uznasz to za interesujące.
Tom van der Zanden,
ciekawy! mówisz, że on „glazuruje” coś w gazecie. lepiej byłoby sprecyzować sekcję, która nie jest „rozwinięta”. mówisz także, że to działa. jaka jest twoja początkowa implementacja indeksowania? czy to jest projekt szkolny? zasugeruj dalszy czat informatyki na ten temat. także np. blogowanie na ten temat lub otwarte pozyskiwanie kodu kod może być pomocny dla innych i prowadzić do bardziej szczegółowych informacji. również papier nie wydają się odnosić do jakichkolwiek funkcji mieszaja ...
vzn
Zaimplementowałem algorytm Korfa: github.com/benbotto/rubiks-cube-cracker . Ja również uznałem, że indeksowanie jest trudne, więc napisałem o tym artykuł na Medium: medium.com/@benjamin.botto/…
avejidah

Odpowiedzi:

6

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ę(pi,oi)(p0,,p7)(0,,7)oi{0,1,2}o7o0,,o68!37=88179840{0,,23}(pi,oi)(p0,,p7)(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.o0,,o637p+o8!o+p

Yuval Filmus
źródło
Hej Yuval, dzięki za komentarz. Dla mnie od 0 do 23 to sposób, w jaki identyfikuję unikalną pozycję / orientację, w której może znajdować się sześcian narożny. 8 pozycji razy 3 orientacje na pozycję = 24. Na szczęście mogę łatwo podzielić tę wartość na osobne krotki pozycji / orientacji. Twoja odpowiedź zaprowadziła mnie do tego kodu, który jest implementacją opisywanego algorytmu. github.com/brownan/Rubiks-Cube-Solver/blob/master/cornertable.c Będę musiał trochę popracować, aby uczynić to bardziej ogólnym (aby móc obsługiwać inne wzory niż „tylko narożniki”), ale teraz Jestem na dobrej drodze dzięki!
Cosmosis,