Внедрить уменьшение ключа в переполнении стека очереди приоритетов STL
Я пытаюсь реализовать Алгоритм Прима, и для этого мне нужно иметь метод lowerKey для приоритетной очереди (чтобы обновить значение ключа в приоритетной очереди). Могу ли я реализовать это в очереди приоритетов STL?
Если это поможет, вот алгоритм, которым я следую:
- для каждой вершины u в графе G
- установите ключ от вас в бесконечность
- установить родительский элемент для NIL
- установить ключ исходной вершины в 0
- вход в очередь с приоритетной очередью Q все вершины графа с ключами, как указано выше
- пока Q не пусто
- поп-вершина и с самым низким ключом в Q
- для каждой смежной вершины v вы делаете
- если (v все еще в Q) и (клавиша (u) + весовая функция (u, v) < ключ (v)) затем
- установить вас, чтобы быть родителем V
- обновить ключ v до равного ключа (u) + весовая функция (u, v) // Эта часть доставляет мне проблемы, так как я не знаю, как реализовать lowerKey в приоритетной очереди
- если (v все еще в Q) и (клавиша (u) + весовая функция (u, v) < ключ (v)) затем
Решение
Я не думаю, что вы можете реализовать это в контейнере STL. Помните, что вы всегда можете написать свою собственную кучу (очередь приоритетов) на основе вектора, но есть обходной путь:
Сохраняйте массив расстояний, допустим d, В вашу приоритетную очередь вы помещаете пары расстояний и указатель вершины этого расстояния. Если вам нужно удалить какое-либо значение из очереди, не удаляйте его, просто обновите значение в d массив и поставить новую пару в очередь.
Каждый раз, когда вы берете новое значение из очереди, проверьте, действительно ли расстояние в паре так хорошо, как в вашем массиве. d, Если не игнорировать это.
Время такое же O (MlogM). Память O (MlogM), где M — количество ребер.
Есть другой подход: используйте RB-Tree, он может вставлять и удалять ключи в O (logN), а также получать минимум. Вы можете найти реализацию в STL RB-Tree в std::set контейнер.
Но, хотя сложность времени та же, RB-Tree работает медленнее и имеет большую скрытую константу, поэтому может быть немного медленнее, appx. В 5 раз медленнее. Зависит от данных, конечно.
Другие решения
Для другого подхода: лучше, чем использовать std :: set.
Вы можете использовать btree :: btree_set (или btree :: safe_btree_set).
Это реализация, идентичная std :: set, созданная Google с использованием B-Tree, в отличие от stl, использующей RB-Tree. Это намного лучше, чем std :: set, а также O (logN).
проверить сравнение производительности:
http://code.google.com/p/cpp-btree/wiki/UsageInstructions
И он также имеет гораздо меньший объем памяти.
Я не эксперт, так что надеюсь, что это не слишком глупо, но сработает ли вектор в сочетании с lower_bound?
Если вы используете lower_bound для поиска правильного места для вставки новых значений, ваш вектор всегда будет сортироваться по мере его построения, сортировка не требуется. Когда ваш вектор отсортирован, не является ли lower_bound бинарный поиск с производительностью логарифмического класса?
Так как он отсортирован, найти значение min (или max) совсем несложно.
Чтобы уменьшить ключ, вы должны выполнить поиск по нижнему пределу, удалить и снова сделать понижение, чтобы вставить сокращенный ключ, что = 2 операции логарифмического класса. Все еще не плохо.
Кроме того, вы можете обновить ключ и отсортировать вектор. Я предположил бы с произвольным доступом, что все еще должен быть в логарифмическом классе, но не знаю точно, что там делает stl.
С отсортированным вектором, если вы знаете, что ключ-кандидат меньше, чем тот, который находится там, то, возможно, вы могли бы даже просто отсортировать часть вектора, которая имеет все меньшие значения, для еще большей производительности.
Другое соображение, я думаю, что наборы / карты имеют немного больше памяти, чем векторы?
Я думаю, что большая часть сортировки ограничена NLogN, так что 2 LogN для повторной вставки, а не сортировки может быть лучше для операции сокращения ключа.
Другое дело, что вставка в vector не так уж и актуальна, однако в целом стоит ли рассматривать идею вектора w lower_bound?
Спасибо
detector