Реализация C++ A-star, определяющая, находится ли узел уже в приоритетной очереди открытых элементов

Один шаг в алгоритме поиска пути A * требует поиска в списке открытых узлов узла, с которым вы в данный момент взаимодействуете, и добавления этого узла в список, если его еще нет, или обновления его значения и родителя, если он присутствует. но с большим весом, чем текущая версия узла.

Эти варианты поведения не поддерживаются в структуре priority_queue STL. Как мне реализовать этот шаг?

Обновления, так как этот вопрос получает много просмотров:

  • std::priority_queue может показаться хорошим выбором для этого, но это не так.

  • Внедрение A* самостоятельно значительно повышает уверенность в себе, но после того, как вы это сделаете, вы должны попытаться переключиться на использование того, что предлагает boost. Я нервничал по поводу его установки, когда задавал этот вопрос, но установка очень проста и не вызовет никаких сложностей; и A * — не единственная полезная функциональность, которую предоставляет boost. (В частности, если вы не используете их функции обработки строк, вы в конечном итоге напишете свою собственную копию; я говорю из личного опыта...)


c++ algorithm path-finding a-star stl
person ExOttoyuhr    schedule 11.08.2012    source источник
comment
В любом случае, я бы даже этого не делал, если только место не в цене. Есть ли причина, по которой вы не можете/не должны поддерживать отдельный набор, поддерживающий быстрые запросы?   -  person harold    schedule 11.08.2012
comment
Не могли бы вы уточнить, что здесь не нужно делать? @ybungalobill ниже сказал, что обновление узла до самой дешевой версии было обязательным для достижения оптимальных результатов.   -  person ExOttoyuhr    schedule 11.08.2012
comment
Это так, но поиск нужного узла для изменения в очереди приоритетов — медленная операция. Вы можете поддерживать отдельную структуру данных для обработки этой части.   -  person harold    schedule 11.08.2012
comment
Я понимаю. Спасибо, что разъяснили это.   -  person ExOttoyuhr    schedule 11.08.2012

Ответы (5)


arrow_upward
1
arrow_downward

Вы можете использовать простой вектор или массив для хранения элементов, а затем использовать std::make_heap, std::push_heap, std::pop_heap, std::sort_heap, std::is_heap и std::is_heap_until для управления ими.

Это позволяет вам нарушать изоляцию и реализовывать пользовательские операции в очереди с приоритетом без необходимости самостоятельно выполнять стандартные операции.

person Andrew Tomazos    schedule 11.08.2012
comment
Если я выберу этот подход, как мне передать другую функцию-предикат в make_heap()? Он отказывается от большего ‹SearchNode›, говоря, что имя типа не разрешено. - person ExOttoyuhr; 11.08.2012
comment
Обновление: похоже, мне просто нужно было объявить экземпляр большего ‹SearchNode›. Пожалуйста, дайте мне знать, если я ошибаюсь. - person ExOttoyuhr; 11.08.2012
comment
@ExOttoyuhr: я добавил пример кода, показывающий, как использовать std::greater. Я предполагаю, что вы забыли поставить скобки после него, чтобы указать, что вы хотите создать анонимный временный объект. - person Andrew Tomazos; 11.08.2012

arrow_upward
2
arrow_downward

Если вы ограничены STL, вы можете использовать STL Set и постоянно стирать и повторно вставлять элементы (с новым приоритетом).

Set< pair<int,int> > s; // < priority,value >
s.insert( make_pair(0,5) );

// Decrease Key operation //
s.erase( s.find( make_pair(0,5) ) );
s.insert( make_pair(1,5) );

Временная сложность по-прежнему составляет O(log N), но для больших наборов, вероятно, потребуется больше времени.

person kkanellis    schedule 11.08.2012

arrow_upward
2
arrow_downward

STL priority_queue не подходит для реализации A*. Вам нужна структура кучи, поддерживающая операцию increase для изменения приоритета уже вставленных элементов. Используйте Boost.Heap для реализации многих классических куч. .

EDIT: в библиотеке Boost.Graph есть реализация поиска A* тоже.

person Yakov Galka    schedule 11.08.2012
comment
Правильно ли будет сказать, что если вы найдете версию определенного узла с более низкой общей стоимостью, чем версия, которая в данный момент находится в очереди, вы должны заменить версию в очереди на новую, более дешевую версию? Звучит так, но я хочу быть уверен. - person ExOttoyuhr; 11.08.2012
comment
@ExOttoyuhr: да, иначе вы не получите оптимальных решений. См. псевдокод алгоритма wikipedia. - person Yakov Galka; 11.08.2012
comment
Спасибо. Но есть ли способы получить подходящий контейнер без установки Boost? - person ExOttoyuhr; 11.08.2012
comment
@ExOttoyuhr: вы можете использовать multi_set, как предложил @compileGuy, или использовать функции кучи, перечисленные @Andrew, и реализовать increase/decrease для куч на основе массива самостоятельно. Однако эти подходы приведут к обновлениям O(log N), в то время как большинство куч Boost имеют амортизированные обновления O(1). - person Yakov Galka; 11.08.2012
comment
ybungalobill: В настоящее время я занимаюсь поиском пути на карте мира 24x13 для относительно небольшого числа актеров, поэтому я думаю, что O (log N) терпимо; но если в какой-то момент в будущем я обнаружу, что интегрирую Boost в проект, это, безусловно, будет областью, в которой его можно использовать. - person ExOttoyuhr; 11.08.2012
comment
не является приоритетной очередью среди лучших способов оптимизации A* - person Thomas; 04.01.2013
comment
@ThomasVerbeke: приоритетная очередь лучше, но не STL priority_queue, о которой я говорил. Проблема стандарта priority_queue заключается в том, что... поясняется в ответе. - person Yakov Galka; 04.01.2013
comment
comp.dit.ie/bduggan/research/ прочитать эту статью :) - person Thomas; 04.01.2013
comment
@ThomasVerbeke: Боже мой... Это статья, написанная любителями. На самом деле важна не статья (которая ничего не объясняет), а реализация. И проблема реализации заключается в том, что она вызывает неопределенное поведение, делая недействительными инварианты priority_queue (то есть изменяя значения напрямую, не позволяя priority_queue предварительно организовать себя. См. строку 90 PathFinder.cpp). Их алгоритм просто сломан, и им повезло, что они получили правильные результаты (если они вообще проверяли правильность, в чем я сомневаюсь). - person Yakov Galka; 04.01.2013
comment
Я согласен; однако я все еще думаю, что в этом случае можно использовать приоритетную очередь STL (даже если структура кучи, очевидно, является лучшей реализацией), и это то, что я пытался вам показать. - person Thomas; 04.01.2013
comment
@ThomasVerbeke: Если вы все еще так думаете, то вы должны доказать что можно. Мое доказательство невозможности простое: A* изменяет значения приоритета узлов в очереди приоритетов, priority_queue не поддерживает такие модификации, поэтому невозможно использовать priority_queue для реализации A*. - person Yakov Galka; 04.01.2013
comment
хорошо; я не поддерживаю это (напрямую) нет, но вы можете создать две приоритетные очереди и просто скопировать их в другую приоритетную очередь, когда вам нужно изменить fscore (или приоритет) для узла; code.activestate.com/recipes/ ( Чайник Рассела: хороший реф.). - person Thomas; 04.01.2013
comment
@ThomasVerbeke: но тогда (как в приведенном вами коде) вы нарушаете временную сложность A *. - person Yakov Galka; 04.01.2013

arrow_upward
2
arrow_downward

Вот решение, которое я использовал для этого, если вы действительно хотите использовать std::priority_queue:

Когда вам нужно обновить узел, который уже находится в очереди приоритетов, просто вставьте в очередь новый узел с тем же состоянием, новым значением стоимости и родителем. Самая последняя обновленная копия этого узла выйдет из очереди первой и будет добавлена ​​в ваш посещенный набор. Чтобы справиться со старыми дубликатами, перед обработкой проверьте любой узел, выходящий из очереди, на соответствие с вашим посещенным набором. Если он есть в посещенном наборе, то путь с наименьшей стоимостью через этот узел уже был замечен, поэтому просто игнорируйте его и обрабатывайте следующий узел.

person P_D    schedule 04.10.2015
comment
Вероятно, это самый простой подход, который избегает накладных расходов. связанные с «изменяемыми» очередями приоритетов. - person Rufflewind; 09.03.2017

arrow_upward
0
arrow_downward

Здесь есть три возможных решения:

  1. Отслеживайте список узлов, открытых в данный момент, независимо от приоритетной очереди. Попробуйте создать список узлов таким же образом, как и для закрытых узлов.

  2. Создайте карту узлов (по координатам) в открытое-закрытое состояние.

  3. Установите библиотеку Boost, которая включает шаблонную реализацию A* (думаю, в <graph>).

person ExOttoyuhr    schedule 11.08.2012