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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм Дейкстры)
(Многоуровневые корзины(multi-level buckets, MLB))
Строка 30: Строка 30:
 
==Улучшения алгоритма Дейкстры==
 
==Улучшения алгоритма Дейкстры==
 
===Многоуровневые корзины(multi-level buckets, MLB)===
 
===Многоуровневые корзины(multi-level buckets, MLB)===
 +
<div >[[Файл:multilevel_buckets.jpg ]]</div>
  
 
{| border="1" cellspacing="0" cellpadding="5" align="right"
 
{| border="1" cellspacing="0" cellpadding="5" align="right"
Строка 42: Строка 43:
 
  |-
 
  |-
 
  |}
 
  |}
 
 
Подходит только графов с целочисленными рёбрами.
 
Подходит только графов с целочисленными рёбрами.
 
* Будем складывать вершины в "корзины" <tex>B[i] \subset V: {d(u)=i} </tex>
 
* Будем складывать вершины в "корзины" <tex>B[i] \subset V: {d(u)=i} </tex>
Строка 48: Строка 48:
 
* На каждом шаге алгоритма, если <tex>B[L]</tex> пусто, то увеличим <tex>L</tex>, а иначе достанем одну вершину из <tex>B[L]</tex>
 
* На каждом шаге алгоритма, если <tex>B[L]</tex> пусто, то увеличим <tex>L</tex>, а иначе достанем одну вершину из <tex>B[L]</tex>
 
* При релаксации будем убирать вершину из исходной корзины и класть в корзину, соответствующую новому значению <tex>dist(u)</tex>
 
* При релаксации будем убирать вершину из исходной корзины и класть в корзину, соответствующую новому значению <tex>dist(u)</tex>
 
  
 
Для одного уровня корзин время работы алгоритма Дейкстры можно оценить как <tex>O(m+nC)</tex>, где <tex>C</tex> - максимальная длина ребра в графе.
 
Для одного уровня корзин время работы алгоритма Дейкстры можно оценить как <tex>O(m+nC)</tex>, где <tex>C</tex> - максимальная длина ребра в графе.

Версия 19:58, 1 декабря 2013

Данная статья - перевод выступления 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)

Multilevel buckets.jpg
Сравнение различных структур данных для поиска кратчайшего пути на карте Европы
Структура данных Время работы (сек)
Двоичная куча 12,38
4-куча 11,53
8-куча 11,52

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

  • Будем складывать вершины в "корзины" [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(m+nC)[/math], где [math]C[/math] - максимальная длина ребра в графе.

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

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

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