Я заметил, что при реализации поисковых алгоритмов используются разные структуры данных. Например, мы используем очереди для реализации поиска в ширину, стеки для поиска в глубину и мини-кучи для реализации алгоритма A * . В этих случаях нам не нужно явно создавать дерево поиска.
Но я не могу найти простую структуру данных для моделирования процесса поиска алгоритма AO * . Я хотел бы знать, является ли построение дерева поиска в явном виде единственным способом реализации алгоритма AO *? Кто-нибудь может предоставить мне эффективную реализацию?
Ответы:
Что касается этой статьи, каждый раз, когда вы расширяете узел в алгоритме AO *, вы должны возвращаться назад, чтобы обновить оценочную стоимость всех его предшественников.
Когда вы используете линейную структуру данных, чтобы содержать узлы, вы должны последовательно проходить элементы данных, и только один элемент данных может быть взят напрямую (стек, очередь, приоритетная очередь ...).
В AO * каждый раз, когда узел берется за расширение на основе его оценочной стоимости, алгоритм выполняет итерации по всем узлам, которые являются его предшественниками (для обновления их оценочной стоимости). Это означает, что иногда вы должны брать элемент на основе его предполагаемой стоимости, а иногда на основе его преемника. Не существует порядка последовательности, который может удовлетворить оба эти условия в общем случае. Возможно, есть способ использовать «вложенные» линейные структуры данных, но он должен просто имитировать древовидную структуру, и вместо этого будет лучше построить дерево поиска.
источник
Я просто отказываюсь от описания, с которым вы связаны, но как насчет BST? Вы можете построить его так, чтобы сбалансировать нерешенные узлы. Это может сэкономить ваше время на шаге 2 и поможет сократить общее время в зависимости от количества обходов. Конечно, если вы уравновешивали / сортировали свое дерево по нерешенным узлам, вы, вероятно, были бы по крайней мере лучше, чем более упрощенная структура данных, потенциально сохраняя логарифмическое время или около него.
http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree
источник