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

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

ОГЛАВЛЕНИЕ

Введение

.     Общие сведения о графах

2.      Постановка задачи

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

.        Алгоритм Беллмана-Форда

.        Алгоритм А*

.        Практическое применение

Заключение

Список использованной литературы

Приложения

ВВЕДЕНИЕ

«Задача поиска кратчайшего пути» (задача о минимальном пути, задача о дилижансе), в последнее время получила широкое распространение, благодаря своему применению для решения множества других задач.

В настоящее время она применяется в алгоритмах поиска оптимального пути между двумя объектами (GPS-навигация), в системах автоматического пилотирования, для нахождения кратчайшего пути прохождения Internet-пакета по сети, и множества других.

Задача о кратчайшем пути является одной из важнейших классических задач теории графов. На сегодняшний день известно множество алгоритмов для ее решения.

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

1. ОБЩИЕ СВЕДЕНИЯ О ГРАФАХ

алгоритм задача путь граф

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

ВИДЫ ГРАФОВ И МЕТОДЫ ИХ ЗАДАНИЯ

Каждая пара вершин, имеющих связь, называется ребром графа. Ребра, имеющие направления, называются ориентированными. В связи с наличием/отсутствием ориентированных ребер в графе, графы делятся на:

·        Ориентированные графы- содержат только ориентированные ребра;

·        Неориентированные графы-содержат только неориентированные ребра;

·        Смешанные графы - содержат как ориентированные ребра, так и неориентированные.

Ребро и вершина, которой оно принадлежит считаются инцидентными.

Подграф исходного графа - это граф, содержащий некое подмножество вершин данного графа и некое подмножество инцидентных им рёбер.Граф с p вершинами и q ребрами называется (p, q)-графом. Обычно граф представляется с помощью подобной диаграммы:

Ориентированный граф, с 6-ю вершинами

Данная диаграмма наглядно отображает имеющиеся вершины, и связи между ними,однако для решения некоторых задач применяютсяи другие способы задания графа:

Матрица смежности

Матрица смежности графа G(V, E), где V-множество вершин, E- множество ребер данного графа это квадратная матрица A размера n, в которой значение элемента aij равно числу рёбер из i-й вершины графа в j-ю вершину.

Матрица смежности выглядит следующим образом:

Матрица смежности

Граф, соответствующий данной матрице

Матрица инцидентности

Матрица инцидентности - форма представления графа, в которой указываются связи между инцидентными элементами графа (ребро(дуга) и вершина). Столбцы матрицы соответствуют ребрам, строки - вершинам. Ненулевое значение в ячейке матрицы указывает связь между вершиной и ребром (их инцидентность). Пример матрицы инцидентности:

Матрица инцидентности

Граф, соответствующий данной матрице

Также существуют другие способы, но приведенные являются наиболее емкими и популярными.

МАРШРУТЫ, ПУТИ, СВЯЗНОСТЬ

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

Путь это такая последовательность рёбер в графе, что конец одного ребра является началом другого. Путь можно считать частным случаем маршрута.

Связность - это одно из наиболее простых свойств, которым может обладать граф.

Граф называется связным, если любая пара его вершин соединена простой цепью. Максимальный связный подграф графа G называется компонентой связности, или просто компонентой графа G. Таким образом, несвязный граф имеет по меньшей мере 2 компоненты.

Связный граф

На рисунке 4 приведен пример связного графа, с простыми цепями, соединяющими все вершины графа. Так, в данном графе вершины Aи Bсоединены простой цепью {A,B}, вершины B иD простой цепями {B,E,D}, {B,C,D}, {B,A,D}.

Простейшим примером несвязного графа является граф с изолированнойвершиной. Вершина называется изолированной, если она не имеет инцидентных ей ребер. Пример такого графа, с изолированной вершиной D приведен на рис. 5:

ВЕС И ДЛИНА ПУТИ

В некоторых задачах, ребрам ставят в соответствие числа, (обозначаемые ai ->ci) которые называютвесом (длиной)ребра.

Тогда граф G можно описать как 3 множества:

X- множество вершин, A - множество дуг, C - множество весов.

X = {x1,x2,x3…xi}= {a1,a2,a3…ai,}= {c1,c2,c3…ci,}

Несвязный граф

Взвешенный граф

Из рисунка видно, что вес ребра (4,5) равен 15. Вес пути принимается равным сумме весов входящих в него ребер. Вес пути A = (2,4,5), в данном случае равен сумме весов ребер (2,4) и (4,5) = 12+15 = 27.

2. ПОСТАНОВКА ЗАДАЧИ

Задача поиска кратчайшего пути это задача, в которой необходимо найти кратчайший путь между двумя точками (вершинами), на графе, уменьшая сумму весов ребер, составляющих этот путь.

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

Существуют различные постановки задачи о кратчайшем пути:

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

·        Задача о кратчайшем пути между заданной парой вершин. Требуется найти кратчайший путь из заданной вершины u в заданную вершину v.

·        Задача о кратчайшем пути между всеми парами вершин. Требуется найти кратчайший путь из каждой вершины u в каждую вершину v. Эту задачу тоже можно решить с помощью алгоритма, предназначенного для решения задачи об одной исходной вершине, однако обычно она решается быстрее.

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

Находит кратчайшее расстояние от одной из вершин графа до всех остальных, работает только для графов без рёбер отрицательного веса.

ЗАДАЧА

Дан взвешенный ориентированный граф G(V, E) без петель и дуг отрицательного веса. Найти кратчайшие пути от некоторой вершины a графа G до всех остальных вершин этого графа.

АЛГОРИТМ

.        Каждой вершине из V сопоставим метку - минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово - на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

.        Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин - бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как не посещённые.

.        Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, в которые ведут рёбра из u, назовем соседями этой вершины. Для каждого соседа вершины u, кроме отмеченных как посещённые, рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг алгоритма

ПРИМЕР

В качестве примера возьмем неориентированный граф, и найдем минимальные расстояния от первой вершины до всех остальных:

При инициализации алгоритма, метка искомой вершины помечается 0, метки остальных вершин - бесконечностью:

Шаг №1: минимальную метку имеет вершина 1, её соседями являются 6, 3, 2. Рассмотрим их. Первый по очереди сосед вершины 1 - вершина 2, потому что длина пути до неё минимальна. Длина пути в неё через вершину 1 равна сумме кратчайшего расстояния до вершины 1, значению её метки, и длины ребра, идущего из 1-й в 2-ю, то есть 0 + 7 = 7. Это меньше текущей метки вершины 2, бесконечности, поэтому новая метка 2-й вершины равна 7.

Аналогичную операцию проделываем с двумя другими соседями 1-й вершины - 3-й и 6-й.

Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит. Вычеркнем её из графа, чтобы отметить, что эта вершина посещена.

Шаг №2. Снова находим «ближайшую» из не посещённых вершин. Это вершина 2 с меткой 7.

Соседями вершины 2 являются 1, 3 и 4, первая по очереди - уже вычеркнутая вершина 1, поэтому ее в рассмотрение не берем, вторая по очереди - вершина 3, путь до нее через вершину 2: 7 + 10 = 17, но 17 больше текущей метки этой вершины (9), поэтому метка не меняется. Также сосед 2-ой вершины - вершина 4, расстояние до нее через вершину 2: 7 + 15 = 22, 22 <, присваиваем вершине 4 метку 22.

Непросмотренных соседей вершины 2 не осталось, расстояние до нее можно считать окончательным, вершину помечаем как посещенную.

Шаг №3. Повторяем шаг алгоритма, выбрав вершину 3. После проверки всех её соседей получаем следующее:

Дальнейшие шаги. Повторяем шаг алгоритма для оставшихся вершин. Это будут вершины 6, 4 и 5, соответственно порядку.

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

До 2-ой - 7;

До 3-ей - 9;

До 4-ой - 20;

До 5-ой - 20;

До 6-ой - 11.

. АЛГОРИТМ БЕЛЛМАНА-ФОРДА

Находит кратчайшие пути от одной вершины графа до всех остальных во взвешенном графе. Вес ребер может быть отрицательным.

ЗАДАЧА

Дан ориентированный или неориентированный граф G со взвешенными рёбрами. Требуется найти кратчайшие пути от выделенной вершины s до всех вершин графа.

АЛГОРИТМ

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

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

.        Если текущая метка вершины больше чем метка нового пути, то она изменяется в его сторону, иначе остается неизменной.

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

ПРИМЕР

Инициализация алгоритма. Метка истока приравнивается 0, остальные - бесконечности.

Шаг № 1. В цикле производится перебор всех ребер, начинаем с ребра 1-3. Для этого проверим не входит ли оно в путь более оптимальный, чем уже найденный. ∞> 0 +6. Найден более короткий путь, метка вершины 3 меняется на значение 6 (проведена релаксация).

Шаг №2. Проверяем ребро 2-1. Для этого проверяем - не является ли оно частью более короткого пути, чем уже найденный. 0<∞ + 2.Релаксация не нужна, метка остается неизменной.

Шаг № 3. Проверяем ребро 3-2. Для этого проверяем - не является ли оно частью более короткого пути, чем уже найденный. ∞> 6 + 48.Найден более короткий путь, метка вершины меняется на значение 54 (проведена релаксация).

Шаг 5-7. Снова проверяем ребра 1-3, 2-1, 3-2, в данном случае релаксация не требуется, минимальные расстояния уже найдены.

Шаг 8. Осталось проверить граф на наличие цикла отрицательного веса, достижимого из стартовой вершины. Для ребра 1-3 проверяется - может ли оно еще улучшить текущий найденный путь. Т.к. 1-3 не его не улучшает, оно не входит в цикл отрицательного веса.

Шаг 9-10. Аналогично ребру 1-3 проверяются ребра 2-1 и 3-2.

В графе нет циклов отрицательного веса, работа алгоритма закончена.

. АЛГОРИТМ А*

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

ЗАДАЧА

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

АЛГОРИТМ

Добавляем стартовую клетку в открытый список;

Повторяем следующее:

Ищем в открытом списке клетку с наименьшей стоимостью F. Делаем ее текущей клеткой;

Помещаем ее в закрытый списоки удаляем с открытого;

Для каждой из соседних 8-ми клеток:

Если клетка непроходимая или она находится в закрытом списке, игнорируем ее. В противном случае делаем следующее:

Если клетка еще не в открытом списке, то добавляем ее туда. Делаем текущую клетку родительской для этой клетки. Рассчитываем стоимости F, G и H клетки(пояснение в примере);

Если клетка уже в открытом списке, то проверяем, не дешевле ли будет путь в неё через эту клетку. Для сравнения используем стоимость G. Более низкая стоимость G указывает на то, что путь будет дешевле. Если это так, то меняем родителя клетки на текущую клетку и пересчитываем для нее стоимости G и F.

Останавливаемся если:

Открытый список пуст и мы не дошли до целевой клетки. В этом случае путь отсутствует;

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

ПРИМЕР

Инициализация. Имеются две точки, зеленая - стартовая, красная - конечная, синяя - стена (непроходимые клетки). Сама область поиска разделена на сетку с квадратными клетками, упрощая таким образом её до квадратного массива. Для нахождения пути необходимо определить, какие клетки нужно пройти для перемещения из стартовой клетки в конечную.