Jak wdrożyć algorytm AO *?

16

Zauważyłem, że podczas implementacji algorytmów wyszukiwania stosowane są różne struktury danych. Na przykład używamy kolejek do implementacji pierwszego wyszukiwania szerokości, stosów do implementacji wyszukiwania z głębokości pierwszej i stosów min do implementacji algorytmu A * . W takich przypadkach nie musimy jawnie budować drzewa wyszukiwania.

Ale nie mogę znaleźć prostej struktury danych symulującej proces wyszukiwania algorytmu AO * . Chciałbym wiedzieć, czy jawne zbudowanie drzewa wyszukiwania jest jedynym sposobem na implementację algorytmu AO *? Czy ktoś może zapewnić mi skuteczne wdrożenie?

algorithms graphs data-structures search-algorithms Zhang
źródło
3
Witamy! Pamiętaj, aby dołączyć odniesienia do niestandardowych materiałów, z których korzystasz. Ponieważ AO * nie ma artykułu w Wikipedii, link jest z pewnością w porządku. Mam nadzieję, że znalazłem dobry, proszę sprawdzić.
Raphael
1
Czy to nie tylko wykres (z funkcją, która pozwala przejść do „następnego” węzła)?
soandos
pomogłoby to, gdyby ktoś naszkicował, czym AO * różni się od algorytmu A *. nie mogłem tego pojąć na podstawie linku. co do implementacji, jakakolwiek struktura dla drzew wydaje się rozsądna ... przemierza drzewo, prawda?
vzn

Odpowiedzi:

1

W odniesieniu do tego artykułu za każdym razem, gdy rozwijasz węzeł w algorytmie AO *, musisz cofnąć się, aby zaktualizować wszystkie szacunkowe koszty jego poprzedników.

Kiedy używasz liniowej struktury danych do zawarcia węzłów, musisz kolejno przechodzić między elementami danych i tylko jeden element danych może być bezpośrednio pobrany (stos, kolejka, kolejka priorytetowa…).

W AO * za każdym razem, gdy węzeł jest brany do rozbudowy na podstawie jego szacunkowego kosztu, algorytm iteruje wszystkie węzły, które są jego poprzednikami (w celu zaktualizowania szacowanego kosztu). Oznacza to, że czasami powinieneś wziąć element na podstawie jego szacunkowego kosztu, a czasem na podstawie jego następcy. W ogólnym przypadku nie ma kolejności, w której można spełnić oba te warunki. Prawdopodobnie istnieje sposób na użycie „zagnieżdżonych” liniowych struktur danych, ale powinno to po prostu imitować strukturę drzewa i lepiej będzie zamiast tego zbudować drzewo wyszukiwania.

Anton
źródło
0

Po prostu odejdę od opisu, do którego linkujesz, ale co z BST? Być może będziesz w stanie go zbudować, aby zrównoważyć nierozwiązane węzły. Mogłoby to zaoszczędzić czas na kroku 2 i pomóc w skróceniu ogólnego czasu w zależności od liczby przejść. Oczywiście, jeśli zbalansowałeś / posortowałeś swoje drzewo według nierozwiązanych węzłów, prawdopodobnie byłbyś co najmniej lepszy niż bardziej uproszczona struktura danych, potencjalnie utrzymująca czas logarytmiczny / około niego.

http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree

Univ426
źródło
2
Czy potrafisz to zrobić?
Raphael
nie jest dla mnie tak jasne, w jaki sposób zostanie użyty BST, ponieważ BST mają indeks numeryczny dla każdego węzła i zostały użyte do ich umieszczenia. jaki jest używany indeks liczbowy?
vzn