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

Оглавление

Введение…………………………………………………………………………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. Модульная организация программы

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

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

1) Unit1 — модуль реализации класса TForm1 проведения всех вычислений нахождения кратчайшего пути.

Методы класса TForm.

procedure Button1Click - реализация алгоритма поиска кратчайшего пути;

procedure StringGrid1DrawCell - процедура закрашивания нулевых элементов.

2) Unit3 — модуль реализации класса TForm3 - О программе.

 

 

 

 

 

 

 

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

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

procedure TForm1.Button1Click(Sender: TObject); // поиск кратчайшего пути

var

Put:array [1..NVertex] of Integer;

i,j,x,m:integer;

weight:Longint;

begin

  If StrToInt(Edit2.Text)>CountPerSpinEdit.Value then begin

   MessageDlg('Такой вершины нет!', mtWarning,[mbOK],0);

  exit;

end;

x0:=StrToInt(Edit1.Text)-1;

z:=StrToInt(Edit2.Text)-1;

Nx:=CountPerSpinEdit.Value;

Nx:=nX-1;

for i:=0 to Nx do begin

  for j:=0 to Nx do begin

   We[i,j]:=StrToInt( StringGrid1.Cells[i+1,j+1]);

    if We[i,j]=0 then We [i,j]:=$7fff;

  end;

end;

for x:=0 to NX do begin

Mark[x]:=False;

Dist[x]:=$7ffffff;

end;

y:=x0;         // просматриваемая вершина

Mark[y]:=True;

Dist[y]:=0;

      Prev[x0]:=x0;

while not Mark [z] do begin

for x:=0 to Nx do

if not Mark[x] and (Dist[x]>Dist[y]+We[y,x]) then begin

  Dist[x]:=Dist[y]+We[x,y];

  Prev[x]:=y;

end;

  // Поиск новой вершины  y принадлежащей Х с минимальной  временной  меткой

  weight:=$7fffff;

    for x:=0 to Nx do if not Mark[x] then

      if weight>Dist[x] then begin

       weight:=Dist[x];

       y:=x;

      end;

     Mark[y]:=True;

    end;

x:=z;

RichEdit1.Text:='Вершины пути=  ';

while x<>x0 do begin

RichEdit1.Lines.Strings[0]:=RichEdit1.Lines.Strings[0]+('x'+IntToStr(x+1)+'('+IntToStr(weight)+')'+' ; ');

x:=Prev[x];

end;

RichEdit1.Lines.Strings[0]:=RichEdit1.Lines.Strings[0]+('x'+IntToStr(x+1)+'('+IntToStr(weight)+')'+'. ');

Edit3.Text:='Длина кратчайшего пути='+IntToStr(Dist[z]);

end;

 

 

 

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

При разработке программы  применялся принятый в среде Delphi объектно-ориентированный  подход для разработки интерфейса. При реализации алгоритмов обработки  данных использовался структурный  подход. В рабочем окне программы  поле для ввода данных и вывода результатов решения, а именно, матрица весов , поле для ввода начальных и конечных вершин пути и поле результатов - вершины пути и стоимость кратчайшего маршрута. Управление программой выполняется посредством кнопок управления, расположенное в главном окне.

Назначение кнопок.

• О программе — нажатие сопровождается вызовом диалога сообщения о разработчике приложения.
• Новые параметры — сброс ранее введенных данных.
• Решение — решает введенную задачу.
• Выход — выход из программы.

Если путь найден, то он выводится в поле Ответ, а если такого пути нет, то выводятся нулевые результаты.

 

 

 

 

 

 

 

 

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

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

                                                           15

                

              100   20             10                          50

30                                              60

      Рисунок 7 - Тестовый пример.

 

На рисунке 8 показан тестовый пример решения в программе.

Вводим количество переменных (вершин) - 5. В матрицу весов вводим значения расстояний между вершинами, их 7. Задаем начальную и конечную вершину. Нажимаем кнопку Решение. В  поле результат выводятся вершины найденного кратчайшего пути и длина этого пути.

Рисунок 8 - Тестовый пример.

 

 

 

 

 

 

 

 

Заключение

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Список использованных источников

 

1. Белов. Теория Графов. -М. : Наука,1968.
2. Емеличев В.А., Мельников О.И.  Лекции по теории графов. - М.: Наука, 1990.

3. Иванов Б.Н. Дискретная математика. Алгоритмы и программы: Учеб. Пособие. – Владивосток: Изд-во ДВГТ,  2000. – 288с.

4. Кук Д., Бейз Г. Компьютерная математика. – М.: Наука, 1990.

5. Молчанова Л.А., Прудникова Л.И. Delphi в примерах и задачах: Учеб. пособие. Владивосток: Изд-во ТГЭУ, 2006. – 92с.

6. Hечепуpенко М.И. Алгоритмы и программы решения задач на гpафах  и сетях.- Hовосибиpск: Hаука, 1990

7. Смольяков Э.Р. Введение в теоpию гpафов. М.: МГТУ, 1992

8. Таха Хемди А. Введение в исследование операций. - М.: Изд-во "Вильямс", 2005. - 903с.

9. http://works.tarefer.ru

10. http://www.bibliofond.ru

11. http://www.coolreferat.com