АЛГОРИТМЫ НАХОЖДЕНИЯ КРАТЧАЙШИХ ПУТЕЙ НА ГРАФАХ.

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

Метод динамического программирования. Метод рассматривает многостадийные процессы принятия решения. При постановке задачи динамического программирования формируется некоторый критерий. Процесс разбивается на стадии (шаги), в которых принимаются решения, приводящие к достижению общей поставленной цели. Таким образом, метод динамического программирования - метод пошаговой оптимизации. Введем функцию f i, определяющую минимальную длину пути из начальной в вершину i. Обозначим через S i j длину пути между вершинами i и j, а f j - наименьшую длину пути между вершиной j и начальной вершиной. Выбирая в качестве i такую вершину, которая минимизирует сумму (S i j + f j ), получаем уравнение f i = min {S i j + f j }

Трудность решения данного уравнения заключается в том, что неизвестная функция входит в обе части равенства. В такой ситуации приходится прибегать к классическому методу последовательных приближений( итераций), используя рекуррентную формулу: f i (k+1) = min {S i j + f j (k) }, где f j (k) - k -е приближение функции. Возможен другой подход к решению поставленной задачи с помощью метода стратегий. При движении из начальной точки i в конечную k получается приближение f i (0) = S ik, где S ik - длина пути между точками i и k. Следующее приближение – поиск решения в классе двухзвенных ломаных. Дальнейшие приближения ищутся в классе трехзвенных, четырехзвенных и других ломаных.

Пример 1. Определить кратчайший путь из вершины 1 в вершину 10 для графа, представленного на рис. 1.

Решение задачи: Начальные условия: f 1 = 0, S 11 = 0. Находим последовательно значения функции f i (в условных единицах) для каждой вершины ориентированного графа: Длина кратчайшего пути составляет 14 условных единиц. Для выбора оптимальной траектории движения следует осуществить просмотр функций f i в обратном порядке, то есть с f 10.

Пусть f i = f 10. В данном случае Получаем, что (3 + f 8 ) = 14, то есть fj = f 8. Значит, из вершины 10 следует перейти к вершине 8. Имеем fi = f 8. Рассмотрим функцию: то есть fj = f 6 и т.д. Таким образом, получаем кратчайший путь от вершины 1 к вершине 10: (1, 4, 6, 8, 10) Рассмотренный метод определения кратчайшего пути может быть распространен и на неориентированные графы (используется метод подстановок и предположений).

АЛГОРИТМ ДЕЙКСТРЫ ПРЕДНАЗНАЧЕН ДЛЯ НАХОЖДЕНИЯ КРАТЧАЙШЕГО ПУТИ МЕЖДУ ВЕРШИНАМИ В НЕОРИЕНТИРОВАННОМ ГРАФЕ. ИДЕЯ АЛГОРИТМА СЛЕДУЮЩАЯ, СНАЧАЛА ВЫБЕРЕМ ПУТЬ ДО НАЧАЛЬНОЙ ВЕРШИНЫ РАВНЫМ НУЛЮ, И ЗАНОСИМ ЭТУ ВЕРШИНУ ВО МНОЖЕСТВО УЖЕ ВЫБРАННЫХ, РАССТОЯНИЕ ОТ КОТОРЫХ ДО ОСТАВШИХСЯ НЕВЫБРАННЫХ ВЕРШИН ОПРЕДЕЛЕНО. НА КАЖДОМ СЛЕДУЮЩЕМ ЭТАПЕ НАХОДИМ СЛЕДУЮЩУЮ НЕВЫБРАННУЮ ВЕРШИНУ, РАССТОЯНИЕ ДО КОТОРОЙ НАИМЕНЬШЕЕ И СОЕДИНЁННУЮ РЕБРОМ С КАКОЙ- НИБУДЬ ВЕРШИНОЙ ИЗ МНОЖЕСТВА ВЫБРАННЫХ (ЭТО РАССТОЯНИЕ БУДЕТ РАВНО РАССТОЯНИЮ ДО УЖЕ ВЫБРАННОЙ ВЕРШИНЫ ПЛЮС ДЛИНА РЕБРА). НАЙТИ КРАТЧАЙШИЙ ПУТЬ НА ГРАФЕ ОТ ВЕРШИНЫ L ДО ВЕРШИНЫ D (РИС.2). Метод Дейкстры.

Рис. 2. Взвешенный неориентированный граф

Запишем алгоритм в виде последовательности шагов. Шаг 1. Определяются расстояния от начальной вершины L до всех остальных Длина пути до выбранной вершины Выбранная вершина Невыбранные вершины BGNRDSMA 0L710 7B

Шаг 2. Выбираем наименьшее расстояние от L до B, найденная вершина В принимается за вновь выбранную. Найденное наименьшее расстояние добавляется к длинам ребер от новой вершины В до всех остальных. Выбирается минимальное расстояние от В до N. Новая вершина N принимается за выбранную. Длина пути до выбранно й вершины Выбранн ая вершина Невыбранные вершины BGNRDSMA 0L710 7B N

Шаг 3. Определяются расстояния от вершины N до всех оставшихся (за исключением L и B). Длина пути до выбранно й вершины Выбранн ая вершина Невыбранные вершины BGNRDSMA 0L710 7B N G Для наглядности в дальнейшем вместо знака будем ставить знак -. Расстояние от вершины L через вершину N до вершины G равно 18. Это расстояние больше, чем расстояние LB+BG= 16, поэтому оно не учитывается в дальнейшем. Продолжая аналогичные построения, построим таблицу.

Длина пути до выбранно й вершины Выбранн ая вершина Невыбранные вершины B G N R D S M A 0 L B N G = = S = = = =42 34 A [34+15] - 41 R [41+32] M [42+21] - - -

Таким образом, найдена длина кратчайшего пути между вершинами L и D (44 условных единицы). Траектория пути определяется следующим образом. Осуществляем обратный просмотр от конечной вершины к начальной. Просматриваем столбец, соответствующий вершине, снизу вверх и фиксируем первое появление минимальной величины. В столбце, соответствующем вершине D, впервые минимальная длина 44 появилась снизу в четвертой строке. В этой строке указана вершина S, к которой следует перейти, то есть следующим нужно рассматривать столбец, соответствующий вершине S. В этом столбце минимальная длина, равная 27, указывает следующую вершину G, к которой следует перейти, и т.д. Таким образом, получаем траекторию пути: ( L, B, G, S, D ).