Алгоритмы поиска путей на графах дорог СПбАУ, 12 мая 2011

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

3

4 Dijkstra(G,s) dist[1..|V|] = {, …,} dist[s] = 0 Q = MakePriorityQueue(V, dist) while Q != 0 u = ExtractMin(Q) for all (u,v) E if dist[u] + w(u,v) < dist[v] dist[v] = dist[u] + w(u,v) DecreaseKey(Q,v)

5 Алгоритм Дейкстры Dijkstra(G,s,t) dist[1..|V|] = {, …,} is_finished[1..|V|] = {false, …, false} dist[s] = 0 Q = MakePriorityQueue(s, dist[s]) while Q != 0 u = ExtractMin(Q) is_finished[u] = true if u = t return for all (u,v) E and (is_finished[v] = false) if dist[u] + w(u,v) < dist[v] dist[v] = dist[u] + w(u,v) DecreaseKey(Q,v) // or Insert

6

7 Bi-Dijkstra S T A BC

8 Направленный поиск

9 A* - Дейкстра на графе с длинами На каждом шаге ищем вершину с минимальным значением следующей величины: Для корректность A* необходимо выполнение следующих свойств: 1)Эвристическая функция даёт нижнюю оценку длины пути до цели 2)Эвристика монотонна (выполняется неравенство треугольника)

10 Препроцессинг

11 ALT

12 ALT

13 Reach

14 Reach

15 Reach

16 Спасибо за внимание!