Korzystanie z algorytmu wyszukiwania * do rozwiązania puzzli trójwymiarowych 3x3?

Question

Pracuję nad zagadnieniem trójwymiarowych puzzli 3x3 w mojej pracy domowej. Będę kodu z C

Istnieje 26 pudełek i na początku, pierwsze miejsce jest puste. Przesuwając pudła, muszę je uporządkować w odpowiedniej kolejności. Czerwone liczby pokazują poprawną kolejność, a 27 miejsce musi być puste. Nie chcę, żebyś dał mi kod; Szukałem na forach i wydaje mi się, że muszę używać A* search algorithm, ale jak?

Czy możesz podać mi wskazówki, w jaki sposób mogę użyć algorytmu A * w tym problemie? Jakiego rodzaju struktury danych powinienem użyć?

Answer 1

Wiesz, jak działają wykresy i jak A * znajduje najkrótsze ścieżki na nich, prawda?

Podstawową ideą jest to, że każdą konfigurację układanki można uznać za wierzchołek na wykresie, a krawędzie reprezentują ruchy (poprzez połączenie konfiguracji przed i po ruchu).

Znalezienie zestawu ruchów prowadzących od oryginalnej konfiguracji do wybranej może być postrzegane jako problem ze znalezieniem ścieżki.

Answer 2

Definiowanie problemu jako Stanów wykresie:
G=(V,E) gdzie V=S={(x_1,x_2,...,x_54) | all possible states the 3d board can be in} [każdy numer reprezentuje jeden „kwadrat” na pokładzie 3d].
i zdefiniować E={(v1,v2)| it is possible to move from state v1 to state v2 with a single step} alternatywną definicję [identyczną] dla E jest za pomocą funkcji successors(v):
Dla każdego v w V: successors(v)={all possible boards you can get, with 1 step from v}

Będziesz także potrzebować admissible heuristic function, dość dobry dla tego problemu może być: h(state)=Sigma(manhattan_distance(x_i)) where i in range [1,54]) w zasadzie jest to suma manhattan distances dla każdej liczby od celu.

Teraz, gdy otrzymamy te dane, możemy rozpocząć uruchamianie A * na zdefiniowanym wykresie G, z określoną heurystyką. A ponieważ nasza funkcja heurystyczna jest dopuszczalna [przekonaj się dlaczego!], Gwarantuje się, że rozwiązanie znalezione przez A * będzie optymalne z powodu admissibility and optimality of A*.
Znajdowanie faktycznej ścieżki: A * zakończy się, gdy rozwiniesz stan docelowy. [x_i=i w terminach, które użyliśmy wcześniej]. Ścieżkę do niej znajdziesz, cofając się od celu do źródła, używając pola parent w każdym węźle.