Материал: Задача поиска кратчайшего пути

Шаг №1. Начиная со стартовой клетки, помещаем ее в «открытый список» клеток, которые необходимо обработать. Ищем доступные клетки, граничащие с текущей, игнорируя непроходимые клетки. Добавляем найденные клетки в открытый список, указывая в качестве родителя текущую клетку. Удаляем стартовую клетку из открытого списка, и переносим в «закрытый список».

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

Шаг №2. Необходимо выбрать одну из клеток открытого списка для последующей обработки, в качестве таковой выбирается клетка с наименьшей стоимостью. Стоимость пути Fрассчитывается как сумма Gи H. F = G+H, где G-стоимость передвижения от стартовой точки A к данной клетке, по найденному пути. H - примерная стоимость передвижения от данной клетки к целевой (точке B). Стоимость Hрассчитывается с помощью эвристической (прогнозирующей) функции.

Как описано выше - Gэто стоимость передвижения со стартовой клетки, до текущей. В данном примере стоимость вертикальных и горизонтальных передвижения равняется 10, а диагональных - 14. Итак, G рассчитывается как стоимость пути к той точке, в которой мы сейчас находимся, плюс 10 в случае горизонтального расположения текущей клетки, относительно родительской, либо 14 в случае диагонального её расположения.

Стоимость H можно вычислить множеством различных способов, самым простым является метод Манхеттена. Метод Манхеттена заключается в расчете пути общего количества клеток до конечной по горизонтали и вертикали, игнорируя диагональные перемещения и препятствия. Затем полученное количество клеток умножается на стоимость перемещения по одной клетке - в данном случае 10.

На следующе рисунке - в каждой клетке открытого списка записаны значения F, Gи H. F- в левом верхнем углу, G - в левом нижнем и H- в правом нижнем. У ортогональных клеток G равно 10, у диагональных - 14.

Расстояние H просчитано с помощью метода Манхеттена, из рисунка видно, что клетка справа от стартовой без учета преград находится за 3 клетки до конечной и имеет расстояние 30. (3 * 10 = 30). Клетка сверху - 5клеток и расстояние 50.

Шаг № 3. Для продолжения поиска выбираем клетку с наименьшей стоимостью F из всех клеток, находящихся в открытом списке. Удаляем её из открытого списка и добавляем в закрытый.

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

Пересчитываем пути к соседним клеткам, уже находящимся в открытом списке, если путь через текущую клетку меньше, то устанавливаем этой клетке родителем текущую, и пересчитываем путьF и G.

Из 9 клеток, исключая стартовую, добавленную в закрытый список, в открытом списке осталось 8, следующей клеткой является клетка, находящаяся справа от стартовой, т.к. у неё наименьший путь F (F = 40).

Сначала удаляем ее из открытого списка и добавляем в закрытый. Затем мы проверяем соседние клетки. Клетки, сразу справа от этой клетки - стены, поэтому их игнорируем. Клетка, прямо слева - стартовая клетка. Она находится в закрытом списке, поэтому ее тоже игнорируем.

Оставшиеся 4 клетки уже находятся в открытом списке, поэтому нужно проверить, не короче ли пути к этим клеткам, через текущую. Сравнение происходит по стоимости G. Давайте посмотрим на клетку, прямо под нашей выбранной клеткой. Ее стоимость G равна 14. При движении через к этой клетке через текущую её стоимость G будет равна 20 (10, стоимость G чтобы добраться к текущей клетке плюс 10 для движения вертикально вверх, к соседней клетке). G = 20>G = 14, потомуметка остается прежней.То есть более целесообразным будет движение по диагонали на одну клетку, чем движение на одну клетку по горизонтали, а потом одну по вертикали.

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

В качестве следующей нужно выбрать клетку с меньшей стоимостью F из оставшихся 7 в открытом списке. На данный момент наименьшую стоимость F= 54имеют 2 клетки, для алгоритма не имеет значения, какую из них выбирать, зато это является причиной того, что разные реализации алгоритма могут находить одинаково короткие, но разные по сути пути в одной задаче. В нашем случае, наугад выберем клетку, находящуюся справа снизу от начальной, как показано на рисунке.

Клетка справа (стена) и клетка справа снизу пропускаются (справа снизу пропускается из-за того, что её не достичь без среза стены, зависит от условия задачи).

Остается еще 5 клеток. 2 клетки, находящиеся под текущей, еще не в открытом списке, потому их добавляем в открытый список и назначаем текущую клетку их "родителем". Из 3-х других клеток 2 уже находятся в закрытом списке (стартовая клетка и клетка, прямо над ней, на диаграмме обе подсвечены голубым цветом) их игнорируем. Последняя клетка, которая находится прямо слева от текущей, проверяется на длину пути по текущей клетке через эту клетку по стоимости G. Путь не станет короче, метка не меняется.Все соседние клетки рассмотрены, можно переходить к следующей.

Шаг 4 - N-1. Повторяем этот процесс до тех пор, пока не добавим целевую клетку в открытый список. К конечному шагу должна получиться схема похожая на приведенную на рисунке.

Можно заметить, что родительская клетка, для клетки находящейся на 2 клетки под стартовой изменилась. До этого ее родителем была клетка справа сверху, и стоимость была равна 28. После пересчета, оказалось, что до нее существует более короткий путь, равный 20, через вершину сверху (теперь туда направлен указатель).Стоимость F также изменилась.

Шаг N. Последним шагом является определение пути. Начиная поиск с конечной точки будем двигаться по указателям на родителя, постепенно доходя до начальной вершины, пройденные клетки и будут являться кратчайшим путем.

. ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ

Как и было сказано во введении, данные алгоритмы широко применяются в различных задачах для поиска кратчайшего пути.

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

Например протокол динамической маршрутизации «OSPF»разбивает процесс построения таблицы маршрутизации на 2 этапа.

Второй этап состоит в нахождении оптимальных маршрутов с помощью созданного на первом этапе графа. На этом этапе применяется итеративный алгоритм Дейкстры.Каждый маршрутизатор считает себя центром сети и ищет оптимальный маршрут до каждой известной ему сети.В каждом найденном таким образом маршруте запоминается только один шаг-до следующего маршрутизатора,в соответствии с принципом одношаговой маршрутизации.Данные об этом шаге и попадают в таблицу маршрутизации.Если несколько маршрутов имеют одинаковую метрику до сети назначения,то в таблице маршрутизации запоминаются первые шаги всех этих маршрутов.

Также алгоритм применяется при эвакуации населения из очагов бедствия. Оптимальные маршруты до пунктов сбора транспорта для каждой группы людей(дом,улица, школа и т.п)в штабе МЧС рассчитывает программа на основе алгоритма Дейкстры.

В области разработки игр широкое применение находит алгоритм А*, классическим примером его применения является игра «Lines», «ColorLines», в которой игроку необходимо составить в ряд несколько шаров, путь шара как раз рассчитывается с помощью этого алгоритма. Кроме этого А* применяется во многих играх жанра «RTS» (RealTimeStrategy), для расчете траектории движения юнитов, его модификации применяются в таких крупных проектах как «StarCraft2» и «Warcraft3».

ЗАКЛЮЧЕНИЕ

В данной курсовой работе была освещена задача поиска кратчайших путей на графе, а также рассмотрены 3 наиболее популярных алгоритма для ее решения. Были написаны программы, реализующие алгоритм Дейкстры, и алгоритм Форда-Беллмана.

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1.   Алексеев В.Е., Таланов В.А. - Графы. Модели вычислений. Структуры данных, Глава 3.4 Нахождение кратчайших путей в графе - Нижний Новгород, 2005;

2.      Олифер В.Г. Олифер Н.А. - Основы компьютерных сетей - Питер, 2009;

3.      «Глоссарий теории графов», <http://ru.wikipedia.org/Глоссарий_теории_графов>

.        «Задача о кратчайшем пути», <http://ru.wikipedia.org/Задача_о_кратчайшем_пути;>

.        «Алгоритм Дейкстры»,<http://ru.wikipedia.org/Алгоритм_Дейкстры>

ПРИЛОЖЕНИЯ

ИСХОДНЫЙ КОД РЕАЛИЗАЦИИ АЛГОРИТМА ДЕЙКСТРЫ

#include"stdafx.h"

#include<iostream>;V = 6;(intmatSize[V][V], intst)

{distance[V], count, index, i, u;m = st + 1;visited[V];(i = 0; i<V; i++) {[i] = INT_MAX;[i] = false;

}[st] = 0;(count = 0; count<V - 1; count++)

{min = INT_MAX;(i = 0; i<V; i++)(!visited[i] && distance[i] <= min)

{= distance[i]; index = i;

}= index;[u] = true;(i = 0; i<V; i++)(!visited[i] &&matSize[u][i] && distance[u] != INT_MAX&&[u] + matSize[u][i]<distance[i])[i] = distance[u] + matSize[u][i];

}<<"Стоимость пути из начальной вершины до остальных:\t\n";

for (i = 0; i<V; i++)(distance[i] != INT_MAX)<< m <<" > "<<i + 1 <<" = "<< distance[i] <<endl;<< m <<" > "<<i + 1 <<" = "<<"маршрутнедоступен"<<endl;

}main()

{(LC_ALL, "Rus");start, matSize[V][V] =

{

{ 0, 1, 4, 0, 2, 0 },

{ 0, 0, 0, 9, 0, 0 },

{ 4, 0, 0, 7, 0, 0 },

{ 0, 9, 7, 0, 0, 2 },

{ 0, 0, 0, 0, 0, 8 },

{ 0, 0, 0, 0, 0, 0 }

};<<"Начальнаявершина>> "; cin>> start;(matSize, start - 1);("pause>>void");

ИСХОДНЫЙ КОД РЕАЛИЗАЦИИ АЛГОРИТМА БЕЛЛМАНА-ФОРДА

#include"stdafx.h"

#include<iostream>

#include<list>

#include<stack>

#include<limits.h>;

{v;;:(int_v, int_w) { v = _v; ves = _w; }() { return v; }() { returnves; }

};

{V;<AdjListNode> *adj;:(int V);(int u, int v, intves);_ford(intsrc);

};::Graph(intV)

{>V = V;= newlist<AdjListNode>[V];

}::addEdge(intu, intv, intves)

{(v, ves);[u].push_back(node);

}::bellman_ford(intsrc)

{*dist = newint[V];(inti = 0; i< V; i++)[i] = INT_MAX;[src] = 0;(int u = 0; u < V; u++)

{<AdjListNode>::iteratori;(dist[u] != INT_MAX)

{(i = adj[u].begin(); i != adj[u].end(); ++i)(dist[i->getV()] >dist[u] + i->getves())

{[i->getV()] = dist[u] + i->getves();

}

}

}<<"Вершина\t\tРасстояние"<<endl;(inti = 0; i<V; i++)

{<<i<<"\t\t"<<dist[i] <<"\t\t";<<endl;

}

}main()

{(LC_ALL, "rus");(5);.addEdge(0, 1, -1);.addEdge(0, 2, 4);.addEdge(1, 2, 3);.addEdge(1, 3, 2);.addEdge(1, 4, 2);.addEdge(3, 2, 5);.addEdge(3, 1, 1);.addEdge(4, 3, -3); s = 1;<<"Кратчайшие расстояния от источника "<< s <<" \n";

g.bellman_ford(s);0;

}