2.1 Существующие методы нахождения кратчайшего расстояния
Благодаря своему широкому применению, теория о нахождении кратчайших путей в последнее время интенсивно развивается.
Нахождение кратчайшего пути - жизненно необходимо и используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности (например, кратчайший путь от дома до университета), в системах автопилота, для нахождения оптимального маршрута при перевозках, коммутации информационного пакета в Internet.
Применение различных вычислений, производимых с помощью методов нахождения кратчайшего расстояния на графах, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут прокладки кабеля. Если рассматривать существующие или вновь проектируемые дома, сооружения, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередачи и т. п. — как рёбра.
Путем (или ориентированным маршрутом) ориентированного графа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей.
Дуги, имеющие общие концевые вершины, называются смежными.
Ориентированной цепью (орцепью) называется такой путь, в котором каждая дуга используется не больше одного раза. Простой орцепью называется такой путь, в котором каждая вершина используется не более одного раза. Очевидно, что простая орцепь является также орцепью, но обратное утверждение неверно. Маршрут есть неориентированный «двойник» пути, и это понятие рассматривается в тех случаях, когда можно пренебречь направленностью дуг в графе. Иногда дугам графа сопоставляются числа называемые весом, или длиной, или стоимостью (ценой) дуги. Тогда граф называется графом со взвешенными дугами. Иногда веса приписываются вершинам графа, и тогда получается граф с взвешенными вершинами. Если в графе веса приписаны и дугам, и вершинам, то он называется просто взвешенным. Вес пути в графе определяется как сумма весов ребер этого пути. Кратчайшим путем между двумя вершинами называется путь наименьшего веса, соединяющий эти вершины.
Кратчайший путь рассматривается при помощи некоторого математического объекта, называемого графом.
Существуют три наиболее эффективных алгоритма нахождения кратчайшего пути:
− алгоритм Дейкстры (используется для нахождения оптимального маршрута между двумя вершинами);
− алгоритм Флойда (для нахождения оптимального маршрута между всеми парами вершин);
− алгоритм Йена (для нахождения k-оптимальных маршрутов между двумя вершинами).
2.2 Алгоритмы решения оптимизационных задач на графах
Путем (или ориентированным маршрутом) ориентированного графа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей.
Дуги, имеющие общие концевые вершины, называются смежными.
Ориентированной цепью (орцепью) называется такой путь, в котором каждая дуга используется не больше одного раза. Простой орцепью называется такой путь, в котором каждая вершина используется не более одного раза. Очевидно, что простая орцепь является также орцепью, но обратное утверждение неверно. Маршрут есть неориентированный «двойник» пути, и это понятие рассматривается в тех случаях, когда можно пренебречь направленностью дуг в графе. Иногда дугам графа сопоставляются числа называемые весом, или длиной, или стоимостью (ценой) дуги. Тогда граф называется графом со взвешенными дугами. Иногда веса приписываются вершинам графа, и тогда получается граф с взвешенными вершинами. Если в графе веса приписаны и дугам, и вершинам, то он называется просто взвешенным. Вес пути в графе определяется как сумма весов ребер этого пути. Кратчайшим путем между двумя вершинами называется путь наименьшего веса, соединяющий эти вершины.
Кратчайший путь можно найти с помощью следующих алгоритмов:
− волновой алгоритм;
− алгоритм Дейкстры;
− алгоритм Беллмана – Форда;
− алгоритм Флойда – Уоршелла;
− алгоритм Йена.
Выбор алгоритма нахождения кратчайшего пути зависит от вида графа в котором требуется найти кратчайший путь.
2.2.1 Волновой алгоритм
Волновой алгоритм - алгоритм, позволяющий найти минимальный путь в графе с рёбрами единичной длины. Основан на алгоритме поиска в ширину. Применяется для нахождения кратчайшего пути в графе, в общем случае находит лишь его длину.
Суть алгоритма заключается в следующем. На двумерной клетчатой карте (матрице), состоящей из "проходимых" и "непроходимых" клеток, обозначена клетка старта и клетка финиша. Цель алгоритма - проложить кратчайший путь от клетки старта к клетке финиша, если это, конечно, возможно. От старта во все направления распространяется волна, причем каждая пройденная волной клетка помечается как "пройденная". Волна, в свою очередь, не может проходить через клетки помеченные как "пройденные" или "непроходимые". Волна движется, пока не достигнет точки финиша или пока не останется не пройденных клеток. Если волна прошла все доступные клетки, но так и не достигла клетку финиша, значит, путь от старта до финиша проложить невозможно. После достижения волной финиша, от старта прокладывается путь до финиша и сохраняется в массиве.
Волновой алгоритм состоит из двух этапов.
На первом этапе моделируется процесс распространения волны от ячейки А по свободным ячейкам ДРП (Дискретного Рабочего Поля).
При распространении волны от ячейки А, алгоритм последовательно строит f1 (А) - первый, f2 (А) - второй,., fk (А) - k-ый ее фронты. Если проведение пути возможно, то на k+1-ом шаге окажется, что ячейка В є Оk+1 (А). Если в следующий фронт не удается включить ни одной свободной ячейки, т.е. Оk (А) = Оk+1 (А), то при данных условиях путь провести невозможно.
Т.о. первый этап волнового алгоритма определяет возможность проведения пути между А и В.
На втором этапе, начиная с ячейки В, по определенным правилам, выполняется переход от ячейки k-ого фронта к ячейке k-1 фронта до ячейки А. Пройденные ячейки - искомый путь.
Условия, которые нужно выполнить для проведения пути и оценки его оптимальности должны быть заложены в правила, по которым движется фронт волны.
Распространение волны заключается в присваивании ячейкам, соседним с ячейкой предыдущего фронта, значения весовой функции. Вес ячейки k-ого фронта Pk является функцией веса ячейки k-1-ого фронта.
Метод кодирования ячеек по mod3 базируется на основном требовании к весам: Pk-1 ≠ Pk ≠ Pk+1. Ячейкам, включенным в последующие фронты, можно присваивать не сами веса, а их значения по mod3 (1,2,3,1,2,3,.). Проведение пути заключается в отслеживании отметок (1,2,3). Если ячейка имеет несколько соседних ячеек с одинаковыми метками, то используется правило приоритетных направлений.
При движении от ячейки В к ячейке А используется следующее правило приоритетов: ←, ↑, →, ↓.
2.2.2 Алгоритм Дейкстры
Алгори́тм Де́йкстры (Dijkstra’s algorithm) - алгоритм находит кратчайшее расстояние от одной из вершин графа до всех остальных (если таковые имеются). Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его использует протокол OSPF для устранения кольцевых маршрутов.
В процессе работы алгоритма последовательно помечаются рассмотренные вершины графа. Причем вершина, помеченная последней (на данный момент) расположена ближе к исходной вершине, чем все непомеченные, но дальше, чем все помеченные.
Сначала помечается исходная вершина; следующей, очевидно, будет помечена вершина, ближайшая к исходной, и смежная с ней.
Пусть на каком-то шаге уже помечено несколько вершин. Известны кратчайшие пути, ведущие из исходной вершины к помеченным. Для каждой из непомеченных вершин проделаем следующее:
1) Рассмотрим все дуги, ведущие из помеченных вершин в одну непомеченную. Каждая такая дуга является последней дугой на пути из исходной вершины в эту непомеченную.
2) Выберем из этих путей кратчайший. А затем выберем среди них самый короткий ко всем непомеченным вершинам, и пометим вершину, к которой он ведет.
Алгоритм завершится, когда будут помечены все достижимые вершины.
В результате работы алгоритма Дейкстры строится Дерево кратчайших путей.
2.2.3 Алгоритм Беллмана-Форда
Алгоритм Беллмана - Форда применяется для нахождения кратчайшего расстояния от вершины [s] до остальных вершин. Одна из его ключевых особенностей, отличающая его от алгоритма Дейкстры, заключается в том, что он способен работать на графах, где вес ребер может быть задан отрицательным числом. Алгоритм может обнаруживать побочное явление таких графов - циклы отрицательной величины по которым можно вечно крутиться, уменьшая расстояние до вершин. Процесс не закончится. Поэтому, цикл проверки вершин ограничен числом N (числом самих вершин). Этого достаточно для того, чтобы просчитать минимальное расстояние до любой вершины, а главное алгоритм в любом случае завершится.
Так же особенностью алгоритма является то, что в одну и туже вершину мы можем попасть несколько раз.
2.2.4 Алгоритм Флойда – Уоршелла
Алгоритм Флойда - Уоршелла - динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа.
Процедура находит пути минимального веса в графе G= (V,E) заданном весовой матрицей W у которой элемент W [i, j] равен весу ребра соединяющего i-ую и j-ую вершины. При этом полагаем, что W [i, i] =0 для всех i. Путь ищется для всех пар вершин графа. Для бесконечности используется число GM его можно задавать в зависимости от конкретной задачи.
Следует заметить, что если в графе существует контур отрицательной сумарной длины, то вес любого пути, проходящего через вершину из этого контура, можно сделать сколь угодно малой, "прокрутившись" в контуре необходимое количество раз. Поэтому поставленная задача разрешима не всегда. В случае описанном выше, алгоритм Флойда прекращает свою работу. Останавливаясь подробнее надо заметить, что если граф неориентированный (W [i,j] - симметрична), то ребро с отрицательным весом является как раз таким контуром (туда-сюда можно бегать пока не сделаем вес достаточно малым)
Алгоритм Флойда предполагает последовательное преобразование матрицы весов W. В конечном итоге получаем матрицу, элементы d [i,j] которой представляют из себя вес минимального пути соединяющего i и j вершины.
На выходе получаем матрицу D минимальных весов и матрицу P при помощи которой можно восстановить путь минимального веса следующим образом: значение p [i,j] будет равно номеру последней вершины в пути между i и j. Переменная s на выходе равна 1, если алгоритм отработал полностью, и нулю, если в ходе работы алгоритма найден контур отрицательного веса.
2.2.5 Алгоритм Йена
Алгоритм предназначен для нахождения К путей минимальной длины во взвешенном графе соединяющих вершины u1,u2. Ищутся пути, которые не содержат петель.
Работа алгоритма начинается с нахождения кратчайшего пути, для этого будем использовать уже описанный алгоритм Дейкстры. Второй путь ищем перебирая кратчайшие отклонения от первого, третий кратчайшие отклонения от второго и т.д.
Пошаговое описание:
1. Найти минимальный путь P1= (v11,.,v1L [1]). Положить k = 2. Включить P1 в результирующий список.
2. Положить MinW равным бесконечности. Найти отклонение минимального веса, от (k-1) - го кратчайшего пути Pk-1 для всех i=1,2,.,L [k-1], выполняя для каждого i шаги с 3-го по 6-й.
3. Проверить, совпадает ли подпуть, образованный первыми i вершинами пути Pk-1, с подпутем, образованным первыми i вершинами любого из путей j=1,2,.,k-1). Если да, положить W [vk-1i,vji+1] равным бесконечности в противном случае ничего не изменять (чтобы в дальнейшем исключить получение в результат одних и тех же путей).
4. Используя алгоритм нахождения кратчайшего пути, найти пути от vk-1i к u2, исключая из рассмотрения корни (vk-11,.,vk-1i) (чтобы исключить петли), для этого достаточно положить равными бесконечности элементы столбцов и строк матрицы W, соответствующие вершинам входящим в корень.
5. Построить путь, объединяя корень и найденное кратчайшее ответвление, если его вес меньше MinW, то запомнить его.
6. Восстановить исходную матрицу весов W и возвратиться к шагу 3.
7. Поместить путь минимального веса (MinW), найденный в результате выполнения шагов с 3 по 6, в результирующий список. Если k = K, то алгоритм заканчивает работу, иначе увеличить k на единицу и вернуться к шагу 2.
Алгоритм использует массив p для результирующего списка путей, и массив l для хранения соответствующих длин, при этом если начиная с некоторого i элементы l [i] равны - 1, значит существует только i-1 кратчайших путей без петель.
2.2.6 Вывод
В ходе рассмотрения этих методов были сделаны такие выводы:
Преимущество алгоритма Уоршелла-Флойда состоит в том, что он годен для большинства графов с ребрами неотрицательной длины, отличный вариант для решения задачи в общем случае, без особых условий. Недостатком алгоритма является необходимость несколько раз анализировать одну и ту же вершину, что приводит к лишним итерациям, а следовательно – к затратам времени и ресурсов ПК. Кроме того, нет проверки на возможность наличия в графе отрицательных ребер, что может привести к затруднениям в программной реализации.
Эффективность метода Дейкстры существенно зависит от того, как организован поиск вершины с наименьшим текущим расстоянием.
Несмотря на очень высокую эффективность метода Дейкстры-Грибова, в практических задачах с «географической» системой расстояний эще более эффективен метод, принаблежащий Б.Ю.Левиту... В сравнении с методом Дейкстры метод Левита проигрывает на том, что некоторые вершины приходится обрабатывать повторно, а выигрывает на более простых алгоритмах включения и исключения вершин из множества М1. Эксперименты показывают, что для графов с «геометрическим» происхождением, т.е. для графов, построенных на основе транспортных сетей и реальных расстояний, метод Левита оказывается наиболее быстрым. Он выигрывает и по размеру программы. Метод Левита обладает еще и тем преимуществом перед методом Дейкстры, что он применим в случае отрицательных длин дуг (ведь «длина дуги» - это просто название, которое дает нам полезные ассоциации с реальностью).
Алгоритм Флойда наиболее подходящий для решения задач оптимизации путей между всеми парами вершин в сети, алгоритм Йена наилучший для нахождения нескольких кратчайших путей между двумя вершинами транспортной сети. Алгоритм Флойда – Уоршелла помогает последовательно вычислить все значения длин кратчайших путей между вершинами. На каждом шаге алгоритм генерирует две двумерные матрицы, одна из которых содержит длины кратчайших путей между всеми вершинами графа, а другая содержит сами пути. Названные алгоритмы могут найти свое применение в программах для транспортных и коммуникационных сетей, таких как коммутация информационного пакета в Internet, где вершины - роутеры, а ребра это связи между роутерами. Таким образом, чем короче будет путь, тем быстрее пакет достигнет пункта назначения и меньше будут информационные потери.
Можно сделать вывод, что при проведении исследований нельзя охватить сразу все существующие алгоритмы решения задачи. Чаще всего выполняется сравнение нескольких наиболее популярных и наиболее простых методов для решения тех или иных видов задач при заданных условиях.