набор c ++ против вектора + операции кучи для очереди с приоритетом A *

Question

Когда использование std :: set более эффективно (время w.r.t.), чем использование std :: vector вместе с make_heap/push_/pop_ для очереди приоритетов в операции A *? Я предполагаю, что если вершины в открытом списке маленькие, лучше использовать вектор. Но есть ли у кого-нибудь опыт с этим?

Answer 1

Если бы я рискнул предположить? Я предполагаю, что векторная версия, вероятно, является хорошим выбором, потому что, как только она вырастет до определенного размера, не будет очень много ресурсов.

Но я не люблю угадывать. Я предпочитаю жесткие цифры. Попробуйте оба, профиль!

Answer 2

Если вы занимаетесь поиском путей, ознакомьтесь со статьями в AI Wisdom Дана Хиггинса. Там есть описание того, как быстро получить структуры данных. Он упоминает «дешевый список», который похож на «горячий» кеш для недавних узлов и позволяет избежать множества штрафов за поиск данных в структурах.

http://introgamedev.com/resource_aiwisdom.html

Answer 3

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

Когда я реализовал A * в Java несколько недель назад, я использовал Java PriorityQueue, который, очевидно, основан на куче приоритетов, и это кажется хорошим способом сделать это. Я рекомендую использовать set в C ++.

РЕДАКТИРОВАТЬ: спасибо Ники. Теперь я понимаю, как реализованы двоичные кучи (с массивом), и я понимаю, что вы на самом деле спрашиваете в своем вопросе. Я подозреваю, что priority_queue - лучший вариант, хотя (как сказал Игорь) было бы нетрудно заменить его на set, чтобы проверить его производительность. Я предполагаю, что есть причина, по которой очереди с приоритетами (по крайней мере, в Java и C ++) реализованы с использованием двоичных куч.

Answer 4

Использовать приоритетную очередь. Это нормально для двоичной кучи (например, для очереди с приоритетами на основе вектора). Вы можете построить кучу за O (n), и все соответствующие операции занимают O (logn). В дополнение к этому вы можете реализовать операцию уменьшения клавиши, которая полезна для *. Однако это может быть сложно реализовать для очереди std. Единственный способ сделать это с помощью набора - удалить элемент и вставить его с другим приоритетом.

Редактировать: вы можете захотеть использовать

std::make_heap

(и связанные с ними функции). Таким образом, вы получаете доступ к вектору и можете легко реализовать клавишу_меньшения.

Редактировать 2: я вижу, что вы намеревались использовать make heap, поэтому все, что вам нужно сделать, это реализовать ключ уменьшения.

Answer 5

1. Для поиска * я бы пошел с std :: vector-очередь приоритетов.
2. Однако изменение в реализация из std :: vector в другой контейнер STL должна быть довольно тривиально, поэтому я бы поэкспериментировал с разными версиями и увидел, как это влияет на алгоритм спектакль. В дополнение к stl :: map я бы определенно попробовал stl :: deque.