 |
Лекция. Задача нахождения кратчайших путей
|
|
|
|
Цель лекции: изучить основные алгоритмы поиска кратчайшего пути и научиться решать задачи поиска кратчайшего пути на основе алгоритмов Дейкстры, Флойда и переборных алгоритмов.
Содержание: алгоритм Дейкстры; алгоритм Флойда; переборные алгоритмы.
Нахождение кратчайшего пути на сегодняшний день является жизненно необходимой задачей и используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности (например, кратчайший путь от дома до университета), в системах автопилота, для нахождения оптимального маршрута при перевозках, коммутации информационного пакета в сетях и т.п.
Рассмотрим три наиболее эффективных алгоритма нахождения кратчайшего пути:
1) алгоритм Дейкстры;
2) алгоритм Флойда;
3) переборные алгоритмы.
Указанные алгоритмы легко выполняются при малом количестве вершин в графе. При увеличении их количества задача поиска кратчайшего пути усложняется.
Алгоритм Дейкстры.
Данный алгоритм является алгоритмом на графах, который изобретен нидерландским ученым Э. Дейкстрой в 1959 году. Алгоритм находит кратчайшее расстояние от одной из вершин графа до всех остальных и работает только для графов без ребер отрицательного веса.
Каждой вершине приписывается вес – это вес пути от начальной вершины до данной. Также каждая вершина может быть выделена. Если вершина выделена, то путь от нее до начальной вершины кратчайший, если – нет, то временный. Обходя граф, алгоритм считает для каждой вершины маршрут, и, если он оказывается кратчайшим, выделяет вершину. Весом данной вершины становится веc пути. Для всех соседей данной вершины алгоритм также рассчитывает вес, при этом ни при каких условиях не выделяя их. Алгоритм заканчивает свою работу, дойдя до конечной вершины, и весом кратчайшего пути становится вес конечной вершины.
|
|
|
Алгоритм Дейкстры
Шаг1. Всем вершинам, за исключением первой, присваивается вес равный бесконечности, а первой вершине – 0.
Шаг 2. Все вершины не выделены.
Шаг 3. Первая вершина объявляется текущей.
Шаг 4. Вес всех невыделенных вершин пересчитывается по формуле: вес невыделенной вершины есть минимальное число из старого веса данной вершины, суммы веса текущей вершины и веса ребра, соединяющего текущую вершину с невыделенной.
Шаг 5. Среди невыделенных вершин ищется вершина с минимальным весом. Если таковая не найдена, то есть вес всех вершин равен бесконечности, то маршрут не существует. Следовательно, выход. Иначе, текущей становится найденная вершина. Она же выделяется.
Шаг 6. Если текущей вершиной оказывается конечная, то путь найден, и его вес есть вес конечной вершины.
Шаг 7. Переход на шаг 4.
Для определения самого кратчайшего пути введем массив P вершин, где P[v] будет содержать вершину, непосредственно предшествующую вершине v в кратчайшем пути (см. рисунок 10.1).
Рисунок 10.1-Демонстрация алгоритма Дейкстры
Сложность алгоритма Дейкстры зависит от способа нахождения вершины, а также способа хранения множества непосещенных вершин и способа обновления длин.
Алгоритм Флойда.
Рассматриваемый алгоритм иногда называют алгоритмом Флойда-Уоршелла. Алгоритм Флойда-Уоршелла является алгоритмом на графах, который разработан в 1962 году Робертом Флойдом и Стивеном Уоршеллом. Он служит для нахождения кратчайших путей между всеми парами вершин графа.
Метод Флойда непосредственно основывается на том факте, что в графе с положительными весами ребер всякий неэлементарный (содержащий более 1 ребра) кратчайший путь состоит из других кратчайших путей.
|
|
|
Основная идея алгоритма. Пусть есть три вершины i, j, k и заданы расстояния между ними. Если выполняется неравенство A[i,k]+A[k,j]<A[i,j], то целесообразно заменить путь i->j путем i->k->j. Такая замена выполняется систематически в процессе выполнения данного алгоритма.
Шаг 0. Определяем начальную матрицу расстояния A0 и матрицу последовательности вершин S0. Каждый диагональный элемент обеих матриц равен 0, таким образом, показывая, что эти элементы в вычислениях не участвуют. Полагаем k = 1.
Основной шаг k. Задаем строку k и столбец k как ведущую строку и ведущий столбец. Рассматриваем возможность применения замены описанной выше, ко всем элементам A[i,j] матрицы Ak-1. Если выполняется неравенство 
, тогда выполняем следующие действия:
- создаем матрицу Ak путем замены в матрице Ak-1 элемента A[i,j] на сумму A[i,k]+A[k,j];
- создаем матрицу Sk путем замены в матрице Sk-1 элемента S[i,j] на k. Полагаем k = k + 1 и повторяем шаг k.
Таким образом, алгоритм Флойда делает n итераций, после I -й итерации матрица А будет содержать длины кратчайших путей между любыми двумя парами вершин при условии, что эти пути проходят через вершины от первой до I -й. На каждой итерации перебираются все пары вершин, и путь между ними сокращается при помощи I -й вершины (см. рисунок 10.2).
Рисунок 10.2 -Демонстрация алгоритма Флойда
Заметим, что если граф неориентированный, то все матрицы, получаемые в результате преобразований, симметричны, и следовательно, достаточно вычислять только элементы, расположенные выше главной диагонали.
Переборные алгоритмы.
Переборные алгоритмы, по сути своей, являются алгоритмами поиска, как правило, поиска оптимального решения. При этом решение конструируется постепенно. В этом случае обычно говорят о переборе вершин дерева вариантов. Вершинами такого графа будут промежуточные или конечные варианты, а ребра будут указывать пути конструирования вариантов.
Лабиринт, состоящий из проходимых и непроходимых клеток, задан матрицей A размером mxn. Элемент матрицы A[i,j]=0, если клетка (i, j) проходима. В противном случае 
.
Требуется найти длину кратчайшего пути из клетки (1, 1) в клетку (m, n).
Фактически дана матрица смежности (только в ней нули заменены бесконечностями, а единицы – нулями). Лабиринт представляет собой граф.
|
|
|
Вершинами дерева вариантов в данной задаче являются пути, начинающиеся в клетке (1, 1). Ребра показывают ход конструирования этих путей и соединяют два пути длины k и k +1, где второй путь получается из первого добавлением к пути еще одного хода.
|
|
|
