kabobo.ru Поиск минимального пути проезда
страница 1
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ СРЕДНЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ 
"ВОЛГОГРАДСКИЙ ТЕХНОЛОГИЧЕСКИЙ КОЛЛЕДЖ"
КАФЕДРА ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ АВТОМАТИЗИРОВАННЫХ СИСТЕМ И ВЫЧИСЛТЕЛЬНОЙ ТЕХНИКИ

КУРСОВОЙ ПРОЕКТ


По дисциплине: Математические методы
Тема: Поиск минимального пути проезда

                                                              Выполнила:


                                                              Студентка группы ВТ 3-1
                                                              Матвиенко Э.В.

                                                              Научный руководитель:


                                                              Теткин А.А.

Волгоград   2011


СОДЕРЖАНИЕ

1. Введение


2. Алгоритмы для нахождения минимальных путей
2.1. Алгоритм Флойда
2.2. Алгоритм Форда-Беллмана
2.3. Алгоритм Дейкстры
3.   Программная реализация алгоритма Дейкстры 
3.1. Описание алгоритма и структуры программы
3.2. Инструкция пользователя
3.3. Текст программы
3.4. Результат работы программы
4.   Заключение
5.   Список литературы

  1. ВВЕДЕНИЕ

    Теория графов находит применение в разных областях современной математики и ее многочисленных приложений, особенно это относится к экономике, в частности, когда надо выбрать наилучшие варианты развозки грузов.
    Нахождение кратчайшего пути - жизненно необходимо и используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности, заканчивая системами автопилота, коммутации информационного пакета в Internet и т.п.
      Кратчайший путь рассматривается при помощи некоторого математического объекта, называемого графом.
    Существует много алгоритмов для нахождения кратчайшего пути. Вот самые популярные   из них:
  * алгоритм Дейкстры (используется для нахождения оптимального маршрута между двумя вершинами);
  * алгоритм Флойда (для нахождения оптимального маршрута между всеми парами вершин);
  * Алгоритм Форда-Белламана

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


Для реализации компьютерной модели, большое значение имеет такое научное направление, как программирование. 
      Из всех языков программирования, язык С++ является наиболее широко используемым. И именно с его помощью в данном курсовом проекте находится длина минимального пути проезда.
  2. АЛГОРИТМЫ ДЛЯ НАХОЖДЕНИЯ МИНИМАЛЬНЫХ ПУТЕЙ

        В этой главе будут рассмотрены алгоритмы Флойда, Форда-Беллмана и алгоритм Дейкстры.

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

      Рассматриваемый алгоритм иногда называют алгоритмом Флойда-Уоршелла. Алгоритм Флойда-Уоршелла является алгоритмом на графах. Этот алгоритм был одновременно опубликован в статьях Роберта Флойда (Robert Floyd) и Стивена Уоршелла (Stephen Warshall) в 1962 г., хотя в 1959 г. Бернард Рой (Bernard Roy) опубликовал практически такой же алгоритм, но это осталось незамеченным.


      В отличие от алгоритма Дейкстры, рассмотренного далее, он находит все кратчайшие пути в графе, к тому же, допускает наличие отрицательных весов (расстояний) на ребрах графа, при условии, что в графе не образуется циклов отрицательной длины (т. е. невозможно бесконечно уменьшать расстояние между некоторыми точками).
    Метод Флойда непосредственно основывается на том факте, что в графе с положительными весами ребер всякий неэлементарный (содержащий более 1 ребра) кратчайший путь состоит из других кратчайших путей.
По алгоритму Флойда-Уоршелла сначала ищется кратчайший путь от одной вершины ко всем вершинам, доступным из нее, затем проводятся те же действия, но пытаясь пройти от этой вершины ко всем доступным из нее, проходя каждый раз через новую вершину (сначала через первую, затем – через вторую и т.д.). Таким образом обрабатываются все вершины. 
      Алгоритм Флойда требует O(N3) времени для работы и O(N2) памяти для хранения матрицы C. Для корректной работы алгоритма необходимо, чтобы в графе отсутствовали циклы отрицательной длины (в этом случае понятие кратчайшего пути не определено).

      3.2. Алгоритм Беллмана-Форда

      Алгоритм Беллмана -Форда — алгоритм поиска кратчайшего пути во взвешенном графе. За время O(|V| × |E|) алгоритм находит кратчайшие пути от одной вершины графа до всех остальных. 
      Алгоритм носит имя двух американских учёных: Ричарда Беллмана (Richard Bellman) и Лестера Форда (Lester Ford). Форд фактически изобрёл этот алгоритм в 1956 г. при изучении другой математической задачи, подзадача которой свелась к поиску кратчайшего пути в графе, и Форд дал набросок решающего эту задачу алгоритма. Беллман в 1958 г. опубликовал статью, посвящённую конкретно задаче нахождения кратчайшего пути, и в этой статье он чётко сформулировал алгоритм в том виде, в котором он известен нам сейчас.

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

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

      Алгоритм Дейкстры (Dijkstra’s algorithm) — алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса.         Алгоритм широко применяется в программировании и технологиях, например, его использует протокол OSPF для устранения кольцевых маршрутов.

      Пусть задан простой неориентированный граф G = ( V , E ), как конечное множество вершин V и множество E неупорядоченных пар { v i , v j } - ребер. Каждому ребру в алгоритме Дейкстры предписано действительное число a [ i ][ j ] > 0, которое называется длиной этого ребра. Требуется найти кратчайший путь между заданными вершинами s и q , то есть такую последовательность вершин u 1 , u 2 ,…, u n , что u 1 = s , u n = q , { u i, u i+1 } принадлежит E для всех 1 <= i <= n -1, и сумма длин ребер { u i ,u i+1 } минимальна.
  Каждой вершине из V сопоставим метку — минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.
      Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые.
    
      Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, в которые ведут рёбра из u, назовем соседями этой вершины. Для каждого соседа вершины u, кроме отмеченных как посещённые, рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг алгоритма.
Сложность алгоритма Дейкстры зависит от способа нахождения вершины v, а также способа хранения множества непосещенных вершин и способа обновления меток. Обозначим через n количество вершин, а через m  количество ребер в графе G.
  * В простейшем случае, когда для поиска вершины с минимальным d[v] просматривается все множество вершин, а для хранения величин d — массив, время работы алгоритма есть O(n2+ m). Основной цикл выполняется порядка n раз, в каждом из них на нахождение минимума тратится порядка n операций, плюс количество релаксаций (смен меток), которое не превосходит количества ребер в исходном графе.
  * Для разреженных графов (то есть таких, для которых m много меньше n2) непосещенные вершины можно хранить в двоичной куче, а в качестве ключа использовать значения d[i], тогда время извлечения вершины из U станет log n, при том, что время модификации d[i] возрастет до log n. Так как цикл выполняется порядка n раз, а количество релаксаций не больше m, скорость работы такой реализации O(n*log n + m*log n)
  * Если для хранения непосещенных вершин использовать фибоначчиеву кучу, для которой удаление происходит в среднем за O(log n), а уменьшение значения в среднем за O(1), то время работы алгоритма составит O(n*log n + m)

Пример


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

Кружками обозначены вершины, линиями — пути между ними (ребра графа). В кружках обозначены номера вершин, над ребрами обозначена их «цена» — длина пути. Рядом с каждой вершиной красным обозначена метка — длина кратчайшего пути в эту вершину из вершины 1.

Первый шаг. Рассмотрим шаг алгоритма Дейкстры для нашего примера. Минимальную метку имеет вершина 1. Её соседями являются вершины 2, 3 и 6

Первый по очереди сосед вершины 1 — вершина 2, потому что длина пути до неё минимальна. Длина пути в неё через вершину 1 равна сумме кратчайшего расстояния до вершины 1, значению её метки, и длины ребра, идущего из 1-ой в 2-ую, то есть 0 + 7 = 7. Это меньше текущей метки вершины 2, бесконечности, поэтому новая метка 2-й вершины равна 7.

Аналогичную операцию проделываем с двумя другими соседями 1-й вершины — 3-й и 6-й.

Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит (то, что это действительно так, впервые доказал Э. Дейкстра). Вычеркнем её из графа, чтобы отметить, что эта вершина посещена.

Второй шаг. Шаг алгоритма повторяется. Снова находим «ближайшую» из непосещенных вершин. Это вершина 2 с меткой 7.
Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 2-ю вершину. Соседями вершины 2 являются вершины 1, 3 и 4.Первый (по порядку) сосед вершины 2 — вершина 1. Но она уже посещена, поэтому с 1-й вершиной ничего не делаем.

Следующий сосед вершины 2 — вершина 3, так как имеет минимальную метку из вершин, отмеченных как не посещённые. Если идти в неё через 2, то длина такого пути будет равна 17 (7 + 10 = 17). Но текущая метка третьей вершины равна 9<17, поэтому метка не меняется.

Ещё один сосед вершины 2 — вершина 4. Если идти в неё через 2-ю, то длина такого пути будет равна сумме кратчайшего расстояния до 2-ой вершины и расстояния между вершинами 2 и 4, то есть 22 (7 + 15 = 22). Поскольку 22<, устанавливаем метку вершины 4 равной 22.

Все соседи вершины 2 просмотрены, замораживаем расстояние до неё и помечаем её как посещенную.

Третий шаг. Повторяем шаг алгоритма, выбрав вершину 3. После её «обработки» получим такие результаты:

Дальнейшие шаги. Повторяем шаг алгоритма для оставшихся вершин. Это будут вершины 6, 4 и 5, соответственно порядку.

Завершение выполнения алгоритма. Алгоритм заканчивает работу, когда вычеркнуты все вершины. Результат его работы виден на последнем рисунке: кратчайший путь от вершины 1 до 2-й составляет 7, до 3-й — 9, до 4-й — 20, до 5-й — 20, до 6-й — 11.

  3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА ДЕЙКСТРЫ 

      4.4. Описание алгоритма и структуры программы

      Программа выводит минимальный путь между двумя указанными вершинами в графе и его длину.


      При запуске программы на экран выводится запрос о вводе весов рёбер исследуемого графа. Данные, введённые пользователем, отображаются в виде матрицы смежности, в которой не существующие рёбра обозначаются нулями. После указанным рёбрам присваивается значение 65535, которое принимается за бесконечность.
      Следующим этапом выполнения программы является запрос о вводе номеров вершин, между которыми необходимо узнать путь. В случае, если начальная и конечная вершины совпадают, отображается соответствующее сообщение и работа программы завершается. В противном случае   выполняется непосредственно алгоритм Дейкстры.
      Результатом программы является вывод на экран вершин, через которые проходит минимальный путь, а также вывод длины маршрута. Если пути между заданными точками не существует - выводится соответствующее сообщение.

|
Переменная | | Тип | Описание | |


n | |         int | Количество точек (вершин) графа | |
i,j | |         int | Счётчики | |
p | |         int | Номер кратчайшего пути и наименьшей длины пути | |
xn | |         int | Номер начальной точки (вершины) | |
xk | |         int | Номер конечной точки (вершины) | |
flag[11] | |         int | Массив, i-й элемент которого имеет значение 0, когда i-й путь и расстояние временные, и принимает значение 1, когда i-й путь и расстояние становятся постоянными | |
c[11][11] | |         word (unsigned int) | Массив i-j элемент которого содержит расстояние между i-й и j-й точками (вершинами)Замечание:1. с[i][i]=2. c[i][j]=c[j][i] | |
s[80] | |       char | Строчная переменная, которая содержит промежуточные значения пути | |
path[80][11] | |       char | Массив строк, который содержит путиЗамечание:После прохождения обработки по алгоритму Дейкстры p-й элемент массива содержит кратчайший путь. | |
l[11] | |         word (unsigned int) | Массив, который содержит длины путей (path)Замечание:После прохождения обработки по алгоритму Дейкстры p-й элемент массива содержит длину кратчайшего пути. | |
| | | |
      Кроме стандартных функций из библиотек   iostream,   string,   stdio.h,   conio.h,   stdlib.h   были использованы также следующие функции:
· word minim(word x, word y) - функция, которая возвращает минимальное из x и y.
· int min(int n) - функция, которая возвращает номер элемента массива l[i] минимальной «неотмеченной» длиной пути(flag[i]=0).
      Программа создана в консольном режиме – в режиме, не имеющем графического интерфейса.

      4.5. Инструкция пользователя

При запуске программы выполняйте эти инструкции:
1. Введите количество вершин исследуемого графа.
2. Введите веса рёбер (положительное число). В программе расстояния от хi до xi+1 и xi+1 до хi считаются равными, а расстояния от хiдо хi - не существующими. Если ребра между указанными вершинами не существует, введите 0 (ноль).
На экран выводится матрица смежности, отображающая введённую информацию.
3. Введите номер вершины, от которой начинается искомый путь.
4. Введите номер вершины, в которой путь заканчивается.
5. Чтоб завершить работу программы после получения результата нажмите Enter.

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

#include
#include
#include
#include
#define word unsigned int
using namespace std;

int i, j, n, p, xn, xk;


int flag[11];
word c[11][11], l[11];
char s[80], path[80][11];

int min(int n)


{
int i, result;
for(i=0;iif(!(flag[i])) result=i;
for(i=0;iif((l[result]>l[i])&&(!flag[i])) result=i;
return result;
}

word minim(word x, word y) //функция возвращающая минимальное X или Y


{
if(xreturn y;
}

void main()


{
setlocale(LC_ALL,"Russian"); //русская кодировка
cout<<"Введите количество точек: ";
cin>>n;
for(i=0;ifor(j=0;jfor(i=0;ifor(j=i+1;j{
cout<<"Введите расстояние от x"<cin>>c[i][j];
}

for(i=0;i
cout<for(i=0;i{
cout<<"X"<for(j=0;j{
printf("%4d",c[i][j]);
c[j][i]=c[i][j];
}
printf("nn");
}
for(i=0;ifor(j=0;jif(c[i][j]==0) c[i][j]=65535; //бесконечность
cout<<"Введите точку отправления: ";
cin>>xn;
cout<<"Введите точку прибытия: ";
cin>>xk;
xk--;
xn--;
if(xn==xk)
{
cout<<"Начальная и конечная точки совпадают!!!"<getch();
return;
}

for(i=0;i
{
flag[i]=0;
l[i]=65535; 
}
l[xn]=0;
flag[xn]=1;
p=xn;
itoa(xn+1,s,10);/*Преобразует целое число (xn+1) в строку символов (s). 
Цифра 10 означает использование 10-ой системы счисления*/
for(i=1;i<=n;i++)
{
strcpy(path[i],"X");//копирует строку
strcat(path[i],s);//присоединяет одну строку к другой
}

/*цикл для поиска минимального маршрута*/


do 
{
for(i=0;iif((c[p][i]!=65535)&&(!flag[i])&&(i!=p))
{
if(l[i]>l[p]+c[p][i])
{
itoa(i+1,s,10); 
strcpy(path[i+1],path[p+1]);
strcat(path[i+1],"-X");
strcat(path[i+1],s);
}
l[i]=minim(l[i],l[p]+c[p][i]);
}
p=min(n);
flag[p]=1;
}
while(p!=xk);//пока не дойдем до конечной точки
/*цикл для поиска минимального маршрута*/

if(l[p]!=65535)//если длина пути не равна бесконечности...


{
cout<<"Минимальный путь: "<
cout<<"Длина пути: "<}
else
cout<<"Такого пути не существует!!!"<getch();
}

      4.7. Результат работы программы:

  4. ЗАКЛЮЧЕНИЕ

      Таким образом, в процессе создания данного проекта разработана программа, реализующая алгоритм Дейкстры в Microsoft Visual Studio 2010 Express. Её недостатком является примитивный пользовательский интерфейс. Это связано с тем, что программа работает в консольном режиме, не добавляющем к сложности языка сложность программного оконного интерфейса.


      Также были углублены знания по предмету «Программирование» и «Математические методы».

  5. СПИСОК ЛИТЕРАТУРЫ



  * Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд Алгоритмы: построение и анализ, 2-е издание. Пер. с англ. — М.,   "Вильямс", 2010
  * http://algolib.narod.ru/Graph/Path.html   Алгоритм поиска кратчайшего пути
  * http://www.lotos-khv.narod.ru/algoritm/diikstra.htm Алгоритм Дейкстры
  * http://www.inattack.ru/article/606.html Алгоритм Флойда - Уоршелла
  * http://gr5381.blog.tut.by/2008/06/26/kratchayshie-puti-algoritm-deykstryi/ Кратчайшие пути. Алгоритм Дейкстры.
  * http://medicine.adetiplus.ru/?title=Diikstra_algoritm Сложность алгоритма
  * http://ru.wikipedia.org/wiki/ Алгоритм_Беллмана_—_Форда   Алгоритм Беллмана — Форда
  * О. Оре., Теория графов. М., «Либроком», 2010
  * С. Д. Шапорев.,   Дискртеная математика. Курс лекций и практических занятий., СПб., БХВ-Петербург., 2005
  * Р. Хаггарти.,   Дискретная математика для программистов., М., Техносфера, 2005
  * Н. И. Костюкова.,   Графы и их применение. Комбинаторные алгоритмы для программистов., Интернет-университет информационных технологий, Бином. Лаборатория знаний., 2007
  * Шевелев Ю. П., Дискретная математика., Лань., 2008
  * Лафоре Р., Объектно-ориентированное программирование в С++., СПб., 2011
  * Культин Н.Б., Основы программирования в Microsoft Visual C++ 2010., М., BHV., 2010
  * Джесс Либерти., Освой самостоятельно С++ за 21 день., М., Вильямс., 2005
страница 1
скачать файл

Смотрите также:
Поиск минимального пути проезда
95.65kb. 1 стр.

Пензенский поисковый отряд «Поиск-Вездеход»
72kb. 1 стр.

Алис Миллер. Драма одаренного ребенка и поиск собственного Я
1271.04kb. 6 стр.

© kabobo.ru, 2017