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

Оглавление

Введение…………………………………………………………………………4

     1. Сетевые модели.............................................................................................5

1.1. Основные определения.........................................................................5

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

1.3. Алгоритмы определения кратчайшего пути......................................6

1.4. Примеры................................................................................................12

      2. Программа и руководство пользователя...................................................15

2.1. Модульная организация программы..................................................15

2.2. Текст программы..................................................................................16

2.3. Руководство пользователя...................................................................18

Приложение. Тестовый пример...........................................................................19

Заключение............................................................................................................21

Список литературы...............................................................................................22

 

 

 

 

 

 

 

 

Введение

Тема моей курсовой работы: Поиск кратчайшего пути.

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

Задачи курсовой работы:

1.Изучить основные алгоритмы поиска кратчайшего пути;

2.Выбрать один алгоритм из изученных и написать приложение для автоматизации поиска этого пути и расчета его стоимости. 

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

 

 

 

 

 

 

 

 

 

 

 

 

1. Сетевые модели

1.1. Основные определения

Сеть состоит из множества  узлов, связанных дугами (или ребрами). Таким  образом, сеть описывается парой множеств (N, А), где N— множество узлов,  а А — множество ребер. Например, сеть, показанная на рис. 1, описывается следующим образом.

N={1,2,3,4},

А = {(1,2), (1,3), (2,3), (2,4), (3,4)}.

 

 

 

Рисунок 1 - Пример ориентированной сети.

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

Путем называется последовательность различных ребер, соединяющих два  узла, независимо от направления потока в каждом ребре. Путь формирует цикл, если начальный и конечный узлы совпадают. Например, на рис. 1 дуги (1,2), (2,3) И (3,4) составляют цикл. Ориентированный цикл — это цикл, в котором все дуги ориентированы в определенном направлении.

 

 

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

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

• замена оборудования;
• составление расписания движения транспортных средств;
• размещение пунктов скорой помощи;
• размещение телефонных станций;
• поиск самого надежного маршрута;
• планирование производства.

1.3. Алгоритмы определения кратчайшего пути

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

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

2. Алгоритм Флойда.

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

В процессе выполнения этого алгоритма  при переходе от узла i к следующему узлу j используется специальная процедура пометки ребер. Обозначим через кратчайшее расстояние от исходного узла 1 до узла i, через — длину ребра (i, j), — длины ребер (i, j) задают матрицу весов сети как квадратную матрицу n * n,  элемент   которой равен весу ребра.

Тогда для узла j определим метку [i] следующим образом.

[i] = [ +], ≥ 0.

Метки узлов в алгоритме  Дейкстры могут быть двух типов: временные  и постоянные. Временная метка  впоследствии может быть заменена на другую временную, если будет найден более короткий путь к данному узлу. Когда же станет очевидным, что не существует более короткого пути от исходного узла к данному, статус временной метки изменяется на постоянный.

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

Этап 0. Исходному узлу (узел 1) присваивается постоянная метка [0, —]. Полагаем i = 1.

Этап 1. а) Вычисляются временные  метки  [ +],для всех узлов j, которые можно достичь непосредственно из узла i и которые не имеют постоянных меток.  Если узел j уже имеет метку [, k], полученную от другого узла k, и,

если  + <  тогда метка [k] заменяется на [ +].

  b) Если все узлы имеют постоянные метки, процесс вычислений заканчивается. В противном случае выбирается метка [, s] с наименьшим значением расстояния среди всех временных меток (если таких меток несколько, то выбор произволен). Полагаем i = r и повторяем этап i.

 — длины  ребер (i, j) задают матрицу весов сети как квадратную матрицу n * n,  элемент   которой равен весу ребра.

Пример алгоритма:

for x Є X do begin

     Mark[x] = FALSE;

    Dist[x] = ∞;

      end;

y = x0;

Mark[x0] = TRUE;

Dist[x0] = 0;

while not Mark[z] do begin

       for x Є X do

              if  not Mark[x] and dist[x]>dist[y]+w[y,x] then begin

                      Dist[x] = dist[y]+w[y,x];

                     Prev[x] = y;

             end;

    {Поиск  новой вершины y Є X с минимальной временной меткой}

   Dist[y] = min     dist[x];

                 x Є X  and Mark[x] = FALSE

  Mark[y] = TRUE;

       end.

В алгоритме использованы операторы:

Mark[x] – вектор меток вершин устанавливает принадлежность вершины x Є X  постоянной (TRUE) или временной (FALSE) метке.

Dist[x] – вектор, фиксирующий в алгоритме текущие значения меток вершин.

Prev[x] – вектор, позволяющий восстановить в обратной последовательности вершины кратчайшего пути.

Prev[x] указывает на вершину с окончательной меткой, ближайшую к вершине x. Последовательность вершин кратчайшего пути будет иметь следующий вид:

z, prev[z], prev[prev[z]], prev[prev[prev[z]]], …, x0,

а значение dist[z] составит длину пути из х0  и z. Очередная новая вершина, претендующая на постоянную метку, обозначается через y.

Алгоритм Флойда. Этот алгоритм более общий по сравнению с алгоритмом Дейкстры, так как он находит кратчайшие пути между любыми двумя узлами сети. Конечно эта задача может быть решена и многократным применением алгоритма Дейкстры (каждый раз последовательно выбираем вершину от первой до N-ной, пока не получим кратчайшие пути от всех вершин графа).

Покажем сначала основную идею метода Флойда. Пусть есть три  узла i, j и k и заданы расстояния между ними (рис. 2). Если выполняется неравенство d_ij + d_jk < d_ik,  то целесообразно заменить путь i -> k путем i -> j -> k. Такая замена (далее ее будем условно называть треугольным оператором) выполняется систематически в процессе выполнения алгоритма Флойда.

 
Рисунок 2 - Треугольный оператор.

Алгоритм Флойда требует  выполнения следующих действий.

Шаг 0. Определяем начальную матрицу расстояния D₀ и матрицу последовательности узлов S₀. Диагональные элементы обеих матриц помечаются знаком "-", показывающим, что эти элементы в вычислениях не участвуют. Полагаем k = 1:

 
                                      Рисунок 3 - Начальная ситуация.

Основной шаг k. Задаем строку k и столбец k как ведущую строку и ведущий столбец. Рассматриваем возможность применения треугольного оператора ко всем элементам d_ij матрицы D_k-1. Если выполняется неравенство d_ik + d_kj < d_ij, (i <> k, j <> k, i <> j), тогда выполняем следующие действия:

• создаем матрицу D_k путем замены в матрице D_k-1 элемента d_ij на сумму d_ik + d_kj,
• создаем матрицу S_k путем замены в матрице S_k-1 элемента s_ij на k. Полагаем k = k + 1 и повторяем шаг k.

Поясним действия, выполняемые  на k-м шаге алгоритма, представив матрицу D_k-1 так, как она показана на рисунке 4. На этом рисунке строка k и столбец k являются ведущими. Строка i - любая строка с номером от 1 до k - 1, а строка p - произвольная строка с номером от k + 1 до n. Аналогично столбец j представляет любой столбец с номером от 1 до k - 1, столбец q - произвольный столбец с номером от k + 1 до n. Треугольный оператор выполняется следующим образом. Если сумма элементов ведущих строки и столбца (показанных в квадратах) меньше элементов, находящихся в пересечении столбца и строки (показанных в кружках), соответствующих рассматриваемым ведущим элементам, то расстояние (элемент в кружке) заменяется на сумму расстояний, представленных ведущими элементами:

 
Рисунок 4 - Иллюстрация алгоритма Флойда.

После реализации n шагов алгоритма определение по матрицам D_n и S_n кратчайшего пути между узлами i и j выполняется по следующим правилам.

1. Расстояние между узлами i и j равно элементу d_ij в матрице D_n.
2. Промежуточные узлы пути от узла i к узлу j определяем по матрице S_n. Пусть s_ij = k, тогда имеем путь i -> k -> j. Если далее s_ik = k и s_kj = j, тогда считаем, что весь путь определен, так как найдены все промежуточные узлы. В противном случае повторяем описанную процедуру для путей от узла i к узлу k и от узла k к узлу j.

 

1.4. Примеры

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

                                                          15

                

              100   20             10                          50

30                                              60

Рисунок 5 – Пример 1.

Решение.

1. Узлу 1 присваиваем постоянную метку [0, —]. Полагаем i = 1 (просматриваемая вершина).

2.   2 узел: 0+100< ∞ => [100;1] -  временая  метка;

      3 узел: 0+30 < ∞ => [30;1] - постоянная метка.

3.   i = 3.

    4 узел: 30+10 < ∞  => [40; 3]- постоянная метка;

    5 узел: 30+60  < ∞  => [90; 3]- постоянная метка.

4. i = 4.

    5 узел: 40+50 < 90 - нет.

5. i = 5. Путь найден. (1, 3, 5). Расстояние = 90 миль. Выход.

2.  Дана транспортная сеть (рис. 6), состоящая из пяти городов (расстояния между городами (в милях) приведены возле соответствующих дуг сети). Необходимо найти кратчайшие расстояния от города 1 (узел 1) до города 5 (узел 5). Решим задачу, применяя алгоритм Дейкстры.

                                                        1

 

 20 700    15

100                                    300

 

Рисунок 6 - Пример 2.

 

Решение.

1.  Узлу 1 присваиваем постоянную  метку [0, —]. Полагаем i = 1 (просматриваемая вершина).

2.   3 узел: 0+100 < ∞ => [100;1] - постоянная метка.

3.   i = 3.

    1 узел: метка не  присваивается, т.к. есть постоянная  метка

    2 узел: 100+700  < ∞ => [800; 3]- временная метка.

    4 узел: 100+20 < ∞ => [120; 3]- постоянная метка.

    5 узел: 100+300 < ∞ => [400; 3]- временная метка.

4. i = 4.

    2 узел: 120+1  < 800 => [121; 4]- постоянная метка.

    4 узел: метка не  присваивается, т.к. есть уже  постоянная.

5. i =2 .

    3 узел: метка не  присваивается, т.к. есть постоянная  метка.

    4 узел: метка не  присваивается, т.к. есть постоянная  метка.

    5 узел: 121+15 < 400 => [136; 2] - кратчайший путь найден.

6. i = 5. Путь найден. (1, 3, 4, 2, 5). Расстояние = 136 миль. Выход.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Программа и руководство пользователя

2.1. Модульная организация программы

Реализация проекта выполнена  в рамках двух модулей. Каждый из них выполняет определенные для него функции. Разделение функций модулей выполнено в соответствии с задачами проекта. В общем случае разделение выполняется на две составные части: проведение расчетов и визуализация  полученных данных.

Каждый из модулей реализует  свой класс. Описание модулей призываются  к описанию классов (их назначения) и методов классов (решения определенных задач класса).