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?
źródło
Odpowiedzi:
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} o7 o0,…,o6 8!⋅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,…,o6 37p+o 8!o+p
źródło