Jak zaimplementować algorytm AO *?

Question

Zauważyłem, że niektóre struktury danych są używane, gdy wdrażamy algorytmy wyszukiwania. Na przykład używamy kolejki do implementacji BFS, stosu do implementacji DFS i min-sterty, aby zaimplementować algorytm A *. W takich przypadkach nie musimy bezpośrednio tworzyć drzewa wyszukiwania.

Ale nie mogę znaleźć prostej struktury danych do symulacji procesu wyszukiwania algorytmu AO *. Chciałbym wiedzieć, czy jawne zbudowanie drzewa wyszukiwania jest jedynym sposobem na wdrożenie algorytmu AO *? Czy ktokolwiek może mi zapewnić wydajną implementację? Doceniam twoją pomoc.

Answer 1

Nota prawna: Nie zaimplementowałem AO *, więc mogę się mylić.

Wykonanie AO * nie powinno różnić się od A *. Używa się sterty, ale zamiast mieć tylko jeden węzeł, każdy element powinien być wektorem węzłów (jeden lub więcej węzłów). W pewnym stopniu zależy to od tego, jakie reguły są (i), ale wypełnianie kupy powinno być naprawdę łatwe. Tak więc odpowiedź na pierwsze pytanie brzmi: nie, nie ma potrzeby konstruowania drzewa jawnie, jak w tym sensie, że nie robisz tego dla A *. Pamiętaj, że stertę stanowi reprezentacja drzewa wyszukiwania, więc można by argumentować, że naprawdę konstruujesz drzewo podczas jego przechodzenia. Jeśli chodzi o

Czy ktoś może zapewnić mi wydajną implementację?

Musisz pokazać trochę wysiłku, podając przynajmniej część pseudokodu lub jeszcze lepiej fragment kodu pokazujący, w jaki sposób zaatakowałeś problem. Następnie możemy wymyślić sugestie, jak zwiększyć wydajność, poprawiając strukturę danych.