какой стандартный контейнер использовать в openSet алгоритма A *?

Я реализую алгоритм A*, используя std::priority_queue в openSet. В какой-то момент алгоритма, как в псевдокоде Википедии:

else if tentative_g_score < g_score[neighbor]
    tentative_is_better := true

с последующим

if tentative_is_better = true
    came_from[neighbor] := current
    g_score[neighbor] := tentative_g_score
    f_score[neighbor] := g_score[neighbor] + h_score[neighbor]

означает, что нужно выполнить поиск по priority_queue и изменить значение одного из их элементов, что невозможно (насколько я понял).

Также в этой строке:

if neighbor not in openset

нельзя выполнять поиск в очереди с приоритетом, и поэтому это невозможно реализовать в очереди с приоритетом, что я решил, создав std::set, который только сообщает нам, какие элементы находятся в openSet (так что, когда я добавляю/удаляю один элемент в openSet, я добавляю/удаляю как std::set, так и std::priority_queue).

Итак, мне интересно, как мне избежать первой проблемы или какой std::container действительно следует использовать для этой конкретной (но общей A *) реализации.

В более общем плане мне интересно, какой эффективный подход к A * с использованием стандартных контейнеров?


c++ containers algorithm path-finding
person Jorge Leitao    schedule 01.05.2012    source источник

Ответы (4)


arrow_upward
0
arrow_downward

К сожалению, контейнеры std:: в настоящее время не поддерживают операции, которые вам требуются. Что действительно необходимо, так это «индексированная» приоритетная очередь, поддерживающая операции в стиле decrease/increase_key.

Один из вариантов — свернуть свой собственный контейнер (на основе расширенной двоичной кучи), который делает это. Если это кажется слишком трудоемким, вы можете почти сымитировать его, используя расширенную структуру данных std::set — оба варианта обсуждаются более подробно. здесь.

Как уже говорили другие, другой вариант - просто полностью удалить очередь приоритетов и попытаться сохранить отсортированный std::vector. Этот подход наверняка сработает и может потребовать от вас наименьшего количества кода, но у него есть существенные последствия для асимптотического масштабирования всего алгоритма — больше невозможно добиться быстрых O(log(n)) обновлений очереди при сохранении сортировки. приказ.

Надеюсь это поможет.

person Darren Engwirda    schedule 01.05.2012
comment
В порядке. Тогда что, если я использую приоритетную очередь с указателями вместе с набором объектов (в идеале несортированным набором)? Когда я хочу узнать, находится ли узел в openSet, я использую метод Set; когда мне нужно получить лучший узел, я использую указатели из очереди приоритетов. Я могу гарантировать, что набор и очередь имеют одинаковое количество элементов, что делает алгоритм O (log (n)). Это выглядит разумным? - person Jorge Leitao; 01.05.2012
comment
Если вы собираетесь использовать std::priority_queue или алгоритмы std::make_heap, std::pop_heap, вам придется столкнуться с проблемой, как реализовать эффективное обновление очереди приоритетов при изменении оценок узлов. К сожалению, алгоритмы std:: просто не поддерживают decrease/increase_key. Я не уверен, как предложенная вами структура данных преодолевает это? - person Darren Engwirda; 02.05.2012
comment
Что я пробовал и работал, так это то, что каждый раз, когда я меняю значение узла, я нажимаю временный узел с максимальным значением (чтобы он был сверху) и возвращал его обратно. В нескольких простых примерах с указателями типа int это сработало: приоритет очереди устанавливался после каждого push/pop. Я не уверен, что это действительно каждый раз, хотя это не должно ... - person Jorge Leitao; 02.05.2012

arrow_upward
2
arrow_downward

Я реализовал алгоритм A* с STL раньше и прошел примерно ту же ситуацию.

В итоге я просто работал только с std::vector, используя стандартные алгоритмы, такие как push_heap и pop_heap (которые использует priority_queue), чтобы поддерживать их порядок.

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

Обновлять:

Сегодня я обязательно попробую некоторые из контейнеров Boost, например эти: http://www.boost.org/doc/libs/1_55_0/doc/html/heap.html Но только если мне разрешено использовать Boost (например, для моего собственного кода).

person Klaim    schedule 01.05.2012
comment
Это больше комментарий, чем ответ... xD - person Jorge Leitao; 01.05.2012
comment
Нет, я предлагаю отказаться от приоритетной очереди или других контейнеров и попробовать работать только с векторами. С ним будет легче работать и потенциально более эффективно. - person Klaim; 01.05.2012
comment
@ J.C.Leitão: это почти ответ. Если бы он упомянул, что нужно использовать алгоритмы push_heap и pop_heap (которые использует priority_queue), то он был бы полным. - person Mike Seymour; 01.05.2012
comment
Хорошо, но я сделал это. Я уже реализовал с вектором... Но алгоритм явно запрашивает приоритетную_очередь... поэтому и спрашиваю здесь... - person Jorge Leitao; 01.05.2012
comment
@MikeSeymour Спасибо, не помню, что я использовал, но я думаю, что это был тот, добавлю. - person Klaim; 01.05.2012
comment
@ JCLeitão Алгоритм представляет собой псевдокод, независимо от реализации необходима только предложенная логика. Здесь priority_queue — это просто ярлык для автоматической сортировки вектора, но он запрещает вам напрямую манипулировать вектором, поэтому использование алгоритмов такое же, без этой проблемы. - person Klaim; 01.05.2012
comment
Итак, вы предполагаете, что использование std::vector с упомянутыми вами std::algorithms аналогично использованию priority_queue? (например, О то же самое?) - person Jorge Leitao; 01.05.2012
comment
Хотя этот тип подхода будет работать, он изменяет асимптотическую сложность алгоритма - вызов std::make_heap является как минимум операцией O(n). Очередь с приоритетом, которая поддерживает decrease/increase_key, получит O(log(n)) обновлений, но, к сожалению, std::priority_queue не поддерживает эти операции... - person Darren Engwirda; 01.05.2012
comment
priority_queue — это только класс-оболочка, по умолчанию над вектором, см. cplusplus.com/reference/stl/ priority_queue, а также то, что говорит Даррен. - person Klaim; 01.05.2012
comment
@MichalPrzybylowicz Нет, это был код консольной игры, так что вы никогда его не увидите. Это тоже было много лет назад, у меня нет к нему доступа. В любом случае вам не нужно видеть конкретный код, чтобы понять, как использовать вектор. - person Klaim; 31.01.2014
comment
Сегодня я обязательно попробую некоторые из контейнеров Boost, например эти: boost.org/doc/libs/1_55_0/doc/html/heap.html Но только если мне разрешено использовать Boost (например, для моего собственного кода). - person Klaim; 31.01.2014

arrow_upward
1
arrow_downward

Вы можете решить эту проблему, полагаясь на поведение алгоритма. Используйте стандартный priority_queue, но вместо операций увеличения/уменьшения ключа вы вставляете новый узел в приоритетную очередь. Оба преемника теперь находятся в приоритетной очереди. Тот, у кого приоритет выше, будет взят первым, а затем расширен и добавлен в закрытый список. Когда дополнительный узел с более высоким приоритетом удаляется, он уже закрыт и, следовательно, отбрасывается.

person dornhege    schedule 31.01.2014

arrow_upward
0
arrow_downward

Без decrease_key вместо этого вы можете просто повторно добавить узел в открытый набор. Всякий раз, когда вы вытаскиваете узел из открытого множества, проверяйте, был ли его ключ больше, чем текущая оценка этого узла; если это так, продолжайте без обработки узла. Это ставит под угрозу доказательство эффективности A*, но на практике это не является серьезной проблемой.

person Sneftel    schedule 31.01.2014