Материал: АиСД. Практикум (in dev)

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

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

В настоящее время известны десятки алгоритмов решения поставленной задачи.

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

36. Метод динамического программирования.

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

Введем функцию 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⁽⁰⁾ = S_ik, где S_ik - длина пути между точками i и k. Следующее приближение – поиск решения в классе двухзвенных ломаных. Дальнейшие приближения ищутся в классе трехзвенных, четырехзвенных и других ломаных.

37. Пример определения кратчайшего пути №1

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

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

Начальные условия: f₁ = 0, S₁₁ = 0.

Находим последовательно значения функции f_i (в условных единицах) для каждой вершины ориентированного графа:

f₂ = min{S₂₁ + f₁} = {3 + f₁} = {3 + 0} = 3;

f₃ = min{S₃₁ + f₁} = {4 + f₁} = {4 + 0} = 4;

f₄ = min{S₄₁ + f₁} = {2 + f₁} = {2 + 0} = 2;

S₆₄ + f₄ 2 + 2

f₆ = min S₆₃ + f₃ = min 6 + 4 = 4;

S₆₂ + f₂ 3 + 3

S₅₄ + f₄ 5 + 2

f₅ = min = min = 5;

S₅₆ + f₆ 1 + 4

S₇₅ + f₅ 6 + 5

f₇ = min = min = 11;

S₅₅ + f₆ 8 + 4

f₉ = min {S₈₅ + f₅} = min = {12 + 5} = 17;

_S86 + f₆ 7 + 4

f₈ = min S₈₉ + f₉ = min 6+17 = 11;

S_10,7 + f₄ 4 + 11

f₁₀ = min S_10,8 + f₈ = min 3 + 11 = 14.

S_10,9 + f₁₀ 11 + 17

Длина кратчайшего пути составляет 14 условных единиц. Для выбора оптимальной траектории движения следует осуществить просмотр функций f_i в обратном порядке, то есть с f_10. Пусть f_i = f₁₀. В данном случае

4 + f₁ 4 + 11

f₁₀ = min 3 + f₈ = min 3 + 11 = 14.

11 + f₉ 11 + 17

Получаем, что (3 + f₈) = 14, то есть fj = f₈. Значит, из вершины 10 следует перейти к вершине 8. Имеем fi = f₈. Рассмотрим функцию

7 + f₆ 7 + 4

f₈ = min = min = 11,

6 + f₉ 6 + 17

то есть fj = f₆ и т.д.

Таким образом, получаем кратчайший путь от вершины 1 к вершине 10:

(1, 4, 6, 8, 10)

Рассмотренный метод определения кратчайшего пути может быть распространен и на неориентированные графы.

38. Пример нахождения кратчайшего пути при условии, что граф неориентированный№2

Для графа (рис. 1) найти кратчайший путь от вершины 1 до вершины 10, рассматривая граф как неориентированный. Матрица смежности весов графа в этом случае имеет вид: