Как реализовать алгоритм AO *?

Question

Я заметил, что некоторые некоторые структуры данных используются при реализации алгоритмов поиска. Например, мы используем очередь для реализации BFS, stack для реализации DFS и min-heap для реализации алгоритма A *. В этих случаях нам не нужно явно строить дерево поиска.

Но я не могу найти простую структуру данных для имитации процесса поиска алгоритма AO *. Я хотел бы знать, является ли построение дерева поиска явным образом единственным способом реализации алгоритма AO *? Может ли кто-нибудь обеспечить мне эффективную реализацию? Я действительно ценю твою помощь.

Answer 1

Отказ от ответственности: Я не реализовал AO *, поэтому я могу ошибаться.

Реализация AO * не должна отличаться от A *. Вы используете кучу, но вместо того, чтобы иметь только один узел, каждый член должен быть вектором узлов (один или несколько узлов). В какой-то степени это зависит от того, как вам даются (и-или) правила, но заполнение кучи должно быть очень простым. Таким образом, ответ на первый вопрос - нет, нет необходимости строить дерево явно, как в том смысле, что вы не делаете этого для A *. Помните кучу на самом деле представление дерева поиска, поэтому можно утверждать, что вы действительно строите дерево при его перемещении. Что касается

Может ли кто-нибудь предоставить мне эффективную реализацию?

Вам нужно показать некоторые усилия, предоставив хотя бы некоторый псевдокод или даже лучше часть кода, показывающую, как вы атаковали проблему. Затем мы можем придумать рекомендации по повышению эффективности за счет улучшения структуры данных.