Почему алгоритм Дейкстры использует ключ уменьшения?

Алгоритм Дейкстры научили меня такому

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, чем при использовании кучи Фибоначчи. Это связано с тем, что куча Фибоначчи включает в себя более крупные постоянные коэффициенты, а фактическое количество операций с уменьшением ключа имеет тенденцию быть намного меньше, чем прогнозируется в худшем случае.

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

Другие вопросы по тегам