A * Какова лучшая структура данных для открытого набора?
Я разрабатываю A * впервые, и я использовал priority_queue для открытого набора, пока не пойму, что вам нужно проверить, находятся ли узлы также в открытом наборе, а не только в закрытом.
Дело в том, что вы не можете перебрать приоритетную очередь. Так почему все рекомендуют приоритетную очередь для открытого набора? Это еще не лучший вариант? Я думаю, что единственный способ повторить это — сделать копию, чтобы я мог извлечь из нее все (огромные затраты).
Какую структуру данных лучше использовать на A *?
Решение
Очередь приоритетов (PQ) — это абстрактная структура данных (ADS). Есть много возможностей для их реализации. К сожалению, priority_queue, поставляемый со стандартной библиотекой C ++, довольно ограничен, и другие реализации намного лучше подходят для реализации A *. Спойлеры: вы можете использовать std :: set / multiset вместо std :: priority_queue. Но читайте дальше:
Итак, что вам нужно из очереди приоритетов для реализации A *:
- Получить узел с наименьшей стоимостью
- Уменьшить стоимость произвольных элементов
Любая приоритетная очередь может сделать 1., но для 2. вам нужна «изменяемая» приоритетная очередь. Standard-Lib никто не может сделать это. Кроме того, вам нужен простой способ найти записи в приоритетной очереди, чтобы выяснить, где уменьшить ключи (для случая, когда A * находит лучший путь к уже открытому узлу). Для этого есть два основных способа: вы сохраняете дескриптор приоритетного элемента очереди в вашем узле графа (или используете карту для хранения этих дескрипторов для каждого узла графа) — или вы вставляете сами узлы графа.
В первом случае, когда вы храните дескрипторы для каждого узла, вы можете использовать std :: multiset для своей очереди приоритетов. std :: multiset :: first () всегда будет вашим ключом «самой низкой стоимости», и вы можете уменьшить ключ, удалив его из набора, изменив значение и повторно вставив и обновив дескриптор. В качестве альтернативы, вы можете использовать изменяемые очереди с приоритетами из Boost.Heap, которые напрямую поддерживают «клавишу уменьшения».
Во втором случае вам понадобится какое-то «навязчивое» двоичное дерево — поскольку ваши узлы поиска пути должны находиться в очереди с приоритетами. Если вы не хотите бросать свои собственные, посмотрите упорядоченные ассоциативные контейнеры в Boost.Intrusive.
Другие решения
Тема очень обширная, я предлагаю вам прочитать эту страницу, если вы хотите узнать о различных возможностях и хорошо понять, какая структура данных адаптирована к вашей ситуации:
http://theory.stanford.edu/~amitp/GameProgramming/ImplementationNotes.html#set-representation
В моем случае двоичная куча была хорошим балансом между сложностью реализации и производительностью, что было именно тем, что я искал. Но, может быть, вы ищете что-то другое?
Остальная часть документа — очень хороший справочник для A * по разработке игр.
http://theory.stanford.edu/~amitp/GameProgramming/index.html
Они означают очередь с приоритетами, не обязательно класс std :: priority_queue, который поставляется с языком. Если встроенный не делает то, что вам нужно, чтобы написать свой или найти другой.