Почему алгоритм Дейкстры использует ключ уменьшения?
Алгоритм Дейкстры научили меня такому
while pqueue is not empty:
distance, node = pqueue.delete_min()
if node has been visited:
continue
else:
mark node as visited
if node == target:
break
for each neighbor of node:
pqueue.insert(distance + distance_to_neighbor, neighbor)
Но я немного читал об этом алгоритме, и во многих версиях я вижу уменьшение ключа, а не вставку.
Почему это так и каковы различия между этими двумя подходами?
2 ответа
Причина использования ключа уменьшения вместо повторной вставки узлов заключается в том, чтобы количество узлов в приоритетной очереди оставалось небольшим, таким образом уменьшая общее количество очередей приоритетной очереди небольшим и стоимость каждого баланса приоритетной очереди низка.
В реализации алгоритма Дейкстры, который повторно вставляет узлы в очередь приоритетов с их новыми приоритетами, один узел добавляется в очередь приоритетов для каждого из m ребер в графе. Это означает, что в очереди приоритетов имеется m операций постановки в очередь и m операций снятия очереди, что дает общее время выполнения O (m Te + m Td), где Te - время, необходимое для постановки в очередь в очереди приоритетов, а Td - время, необходимое для удаления из очереди с приоритетами.
В реализации алгоритма Дейкстры, который поддерживает клавишу уменьшения, очередь приоритетов, содержащая узлы, начинается с n узлов в ней и на каждом шаге алгоритма удаляет один узел. Это означает, что общее количество удалений кучи равно n. Каждому узлу будет назначен ключ уменьшения, возможно, один раз для каждого входящего в него ребра, поэтому общее количество выполненных ключей уменьшения составляет не более m. Это дает время выполнения (n Te + n Td + m Tk), где Tk - время, необходимое для вызова клавиши уменьшения.
Так как это влияет на время выполнения? Это зависит от того, какую очередь приоритетов вы используете. Вот краткая таблица, в которой показаны различные очереди с приоритетами и общее время выполнения различных реализаций алгоритма Дейкстры:
Queue | T_e | T_d | T_k | w/o Dec-Key | w/Dec-Key
---------------+--------+--------+--------+-------------+---------------
Binary Heap |O(log N)|O(log N)|O(log N)| O(M log N) | O(M log N)
Binomial Heap |O(log N)|O(log N)|O(log N)| O(M log N) | O(M log N)
Fibonacci Heap | O(1) |O(log N)| O(1) | O(M log N) | O(M + N log N)
Как вы можете видеть, с большинством типов очередей с приоритетами на самом деле нет разницы в асимптотическом времени выполнения, и версия с уменьшением ключа вряд ли будет работать намного лучше. Однако, если вы используете реализацию кучи Фибоначчи для очереди с приоритетами, то алгоритм Дейкстры действительно будет асимптотически более эффективным при использовании клавиши уменьшения.
Короче говоря, использование клавиши уменьшения плюс очередь с хорошим приоритетом может отбросить асимптотическое время выполнения Дейкстры сверх того, что возможно, если вы продолжаете выполнять постановки в очередь и удаления.
Помимо этого, некоторые более продвинутые алгоритмы, такие как алгоритм кратчайших путей Габова, используют алгоритм Дейкстры в качестве подпрограммы и в значительной степени полагаются на реализацию с уменьшением ключа. Они используют тот факт, что, если вы заранее знаете диапазон допустимых расстояний, вы можете построить суперэффективную очередь приоритетов на основе этого факта.
Надеюсь это поможет!
В 2007 году была опубликована статья, в которой изучались различия во времени выполнения между использованием версии с ключом уменьшения и версией вставки. См. http://www3.cs.stonybrook.edu/~rezaul/papers/TR-07-54.pdf.
Их основной вывод не состоял в том, чтобы использовать клавишу уменьшения для большинства графиков. Специально для разреженных графиков ключ без уменьшения значительно быстрее, чем версия с уменьшением ключа. Смотрите статью для более подробной информации.
Есть два способа реализовать Dijkstra: один использует кучу, которая поддерживает клавишу уменьшения, а другой - кучу, которая этого не поддерживает.
Оба они действительны в целом, но обычно предпочтительнее последнее. Далее я буду использовать букву m для обозначения количества ребер и n для обозначения количества вершин нашего графа:
Если вам нужна наилучшая возможная сложность в наихудшем случае, вы должны использовать кучу Фибоначчи, которая поддерживает клавишу уменьшения: вы получите хороший O(m + nlogn).
Если вас интересует средний случай, вы также можете использовать двоичную кучу: вы получите O(m + nlog(m/n)logn). Доказательство здесь, страницы 99/100. Если граф плотный (m >> n), и этот, и предыдущий стремятся к O(m).
Если вы хотите знать, что произойдет, если вы запустите их на реальных графиках, вы можете проверить эту статью, как предложил Марк Мекетон в своем ответе.
Результаты экспериментов покажут, что "более простая" куча в большинстве случаев дает наилучшие результаты.
Фактически, среди реализаций, в которых используется клавиша уменьшения, Dijkstra лучше работает при использовании простой двоичной кучи или кучи Pairing, чем при использовании кучи Фибоначчи. Это связано с тем, что куча Фибоначчи включает в себя более крупные постоянные коэффициенты, а фактическое количество операций с уменьшением ключа имеет тенденцию быть намного меньше, чем прогнозируется в худшем случае.
По тем же причинам куча, которая не должна поддерживать операцию уменьшения ключа, имеет еще меньше постоянных факторов и фактически работает лучше всего. Особенно, если график разреженный.