Эвристики для поиска кратчайших путей

Данная статья - перевод выступления Renato F. Werneck в Microsoft Data Structures and Algorithms School в 2010 году.

Проблема поиска кратчайшего пути

Дано:

• ориентированный граф [math]G=(V,E)[/math]
• [math]l(u,v) \geqslant 0[/math]
• [math]|V|=n, |E|=m[/math]
• отправная точка - вершина [math]s[/math], пункт назначения - вершина [math]t[/math]

Цель: найти кратчайший путь [math] s \rightsquigarrow t[/math]

Мы будем рассматривать сеть автомобильных дорог:

• [math]V[/math] - множество перекрёстков
• [math]E[/math] - множество дорог
• [math]l(u,v)[/math] - среднее время, которое занимает проезд по дороге

Алгоритм Дейкстры

основная статья: Алгоритм Дейкстры

• на каждом шаге выбирает из множества непросмотренных вершин вершину с наименьшим расстоянием до старта и релаксирует рёбра, исходящие из неё
• завершает свою работу, когда цель достигнута (или просмотрены все вершины)

Скорость работы алгоритма Дейкстры сильно зависит от скорости операций с приоритетной очередью.

Поскольку мы рассматриваем сеть автомобильных дорог, то [math]m = O(n)[/math] (граф планарен почти везде).

Для фибоначчиевых куч время работы алгоритма составляет [math]O(V\log{V}+E)[/math], для двоичных куч: [math]O(E\log{V})[/math]

Но на практике чаще используются 2-, 4- и 8-ичные кучи: они более простые, оценка времени работы содержит меньшее количество скрытых констант.

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

Многоуровневые корзины(multi-level buckets, MLB)

Сравнение различных структур данных для поиска кратчайшего пути на карте Европы (CPU 2,4GHz, 16MB RAM)

Структура данных	Время работы (сек)
Двоичная куча	12,38
4-куча	11,53
8-куча	11,52
MLB	9,36
MLB + калибровка	8,04

Подходит только графов с целочисленными рёбрами.

• Будем складывать вершины в "корзины" [math]B[i] \subset V: {d(u)=i} [/math]
• Наша структура данных будет поддерживать индекс [math]L: \forall B[i]: i\lt L \Rightarrow B[i] = \emptyset [/math]
• На каждом шаге алгоритма, если [math]B[L][/math] пусто, то увеличим [math]L[/math], а иначе достанем одну вершину из [math]B[L][/math]
• При релаксации будем убирать вершину из исходной корзины и класть в корзину, соответствующую новому значению [math]dist(u)[/math]

Можно заметить, что при такой реализации, все операции с приоритетной очередью будут выполняться за [math]O(1)[/math]. Тогда, для одного уровня корзин время работы алгоритма Дейкстры можно оценить как [math]O(m+nC)[/math], где [math]C[/math] - максимальная длина ребра в графе.

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

Соответственно, нам нужно поддерживать два индекса [math]L_{top}[/math] и [math]L_{bottom}[/math] для каждого из уровней соответственно.

При такой реализации, время работы алгоритма Дейкстры можно оценить как [math]O(m+n(1+ \sqrt{C}))[/math]

Калибровка(caliber)

Введём величину "калибр" вершины [math]v[/math]- вес минимального ребра, входящего в [math]v[/math].