Скачать презентацию
Идет загрузка презентации. Пожалуйста, подождите
1
Алгоритмы поиска путей на графах дорог СПбАУ, 12 мая 2011
2
2 Алгоритм Дейкстры
3
3
4
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)
![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)](http://images.myshared.ru/6/682008/slide_4.jpg "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
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
![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] =](http://images.myshared.ru/6/682008/slide_5.jpg "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] =")
6
6
7
7 Bi-Dijkstra S T A BC
8
8 Направленный поиск
9
9 A* - Дейкстра на графе с длинами На каждом шаге ищем вершину с минимальным значением следующей величины: Для корректность A* необходимо выполнение следующих свойств: 1)Эвристическая функция даёт нижнюю оценку длины пути до цели 2)Эвристика монотонна (выполняется неравенство треугольника)
10
10 Препроцессинг
11
11 ALT
12
12 ALT
13
13 Reach
14
14 Reach
15
15 Reach
16
16 Спасибо за внимание!
Еще похожие презентации в нашем архиве:
![Test 4 Вопрос 1. public class TestOutput { public static void main(String[] args) throws IOException { PrintStream out = new PrintStream( new BufferedOutputStream(](/thumbs/7/823067/big_thumb.jpg "Test 4 Вопрос 1. public class TestOutput { public static void main(String[] args) throws IOException { PrintStream out = new PrintStream( new BufferedOutputStream(")
