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

Question

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

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

Answer 1

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

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

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

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