Графы. Поиск оптимального маршрута по городам Беларуси

УЧЕРЕЖДЕНИЕ ОБРАЗОВАНИЯ

«БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ  ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ ИМЕНИ  МАКСИМА ТАНКА»

Кафедра прикладной математики и информатики

 

 

 

 

 

 

 

 

 

 

 

«Графы. Поиск оптимального маршрута по городам Беларуси»

 

Пояснительная записка

 

к курсовому проекту по информатике

 

 

 

 

 

 

 

 

 

 

 

 

 

Выполнил

студент математического  факультета

Макаронок Сергей, 304 гр.

 

Руководитель:

ст. преподаватель кафедры

прикладной математики

и информатики

Шутько Е.И.

 

 

 

 

Минск, 2010

Содержание

 

Введение                               4

1. Разработка модели

1.1 Сущность задачи                                       6

1.2 Организация данных                                                8

1.3 Инструменты разработки               10

2. Проектирование программы

2.1 Описание основных алгоритмов                                               11

2.2 Описание структуры                                                12

3. Тестирование

3.1 Технические требования                                     14

3.2 Полное тестирование                                                14

4. Применение

4.1 Назначение программы                                    20

Заключение                                         21

Литература                                         22

Приложение  А                                                23

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

 

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

Нахождение кратчайшего  пути – жизненно необходимо и используется практически везде, начиная от нахождения оптимального маршрута между двумя  объектами на местности (например, кратчайший путь от дома до университета), в системах автопилота, для нахождения оптимального маршрута при перевозках, коммутации информационного пакета в Internet и  т.п.

Кратчайший путь рассматривается  при помощи некоторого математического  объекта, называемого графом.

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

Наиболее эффективными алгоритмами нахождения кратчайшего пути являются следующие:

• алгоритм Дейкстры (используется для нахождения оптимального маршрута между двумя вершинами);
• алгоритм Флойда (для нахождения оптимального маршрута между всеми парами вершин);

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

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

С помощью алгоритма Флойда-Уоршола  можно найти кратчайшие пути между всему парами вершин за O (N3), где N - количество вершин в графе.

Основной задачей данного  курсового проекта под названием «Графы. Поиск оптимального маршрута по городам Беларуси»,  является программная реализация алгоритма поиска кратчайшего пути между двумя любыми вершинами графа.

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

Данная программа может  использоваться в дискретной математике для исследования графов или в  качестве наглядного пособия, демонстрирующего применение алгоритма Флойда на практике.

Пояснительная записка состоит  из четырех разделов содержащих информацию по составлению и применению программы.

В первом разделе «Разработка  модели» описывается сущность задачи, применяемая математическая модель. Также описываются способы организации  исходных данных. Рассматриваются инструменты  реализации алгоритма.

Во втором разделе «Проектирование программы» рассматриваются разрабатываемые функции их структура и реализация.

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

В четвертом разделе «Применение» описывается назначение программы, рассматривается практический пример использования программы.

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

Приложение должно содержать текст программы.

 

 

 

1 Разработка модели

 

1.1 Сущность задачи

 

Кратчайший путь рассматривается  при помощи некоторого математического  объекта, называемого графом.

Граф G (рис.2.1.1) задается множеством точек (вершин) х₁, х₂,...,х_n. (которое обозначается через Х) и множеством линий (ребер) а₁, а₂,...,а_m. (которое обозначается символом А), соединяющих между собой все или часть этих точек. Таким образом, граф G полностью задается (и обозначается) парой (Х, А). Если ребра из множества А ориентированы, что обычно показывается стрелкой, то они называются дугами, и граф с такими ребрами называется ориентированным графом.

Например, если дорога имеет  не двух-, а одностороннее движение то направление этого движения будет показано стрелкой.

Если ребра не имеют  ориентации, то граф называется неориентированным, (двухстороннее движение).

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

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

При рассмотрении пути µ  представленного последовательностью  дуг (ä₁, ä₂,..., ä_q), за его вес принимается число l(µ), равное сумме весов всех дуг, входящих в µ, т.е.

         (1)

Метод Флойда позволяет найти  кратчайшие пути между всеми парами вершин графа.

Обозначим l_ij длину дуги (x_i, x_j), если таковой не существует примем l_ij = ¥, кроме того, положим l_ii = 0. Обозначим длину кратчайшего из путей из x_i в x_j с промежуточными вершинами из множества {x₁, …, x_m}. Тогда можно получить следующие уравнения

, (2)

. (3)

Уравнение (2) очевидно. Обоснуем уравнение (3).

Рассмотрим кратчайший путь из x_i в x_j с промежуточными вершинами из множества {x₁, …, x_m, x_m+1}. Если этот путь не содержит x_m+1, то . Если же он содержит x_m+1, то деля путь на отрезки от x_i до x_m+1 и от x_m+1 до x_j, получаем равенство .

Уравнения (2) и (3) позволяют  легко вычислить матрицу расстояний [d_ij] между всеми парами вершин графа G(X, E). На первом этапе согласно (2) составляем n´n матрицу равную матрице [l_ij] весов ребер (n – число вершин G(X, E)). n раз производим вычисление по итерационной формуле (3), после чего имеем – матрицу расстояний.

Отметим, что алгоритм Флойда непосредственно не указывает сам  кратчайший путь между вершинами, а  только его длину.

Алгоритм Флойда можно  модифицировать таким образом, чтобы  можно было находить и сами пути. Для этого получим вспомогательную  матрицу [R_ij], которая будет содержать наибольший номер вершины некоторого кратчайшего пути из x_i в x_j (R_ij=0, если этот путь не содержит промежуточных вершин).

Эта матрица вычисляется  параллельно с  по следующим правилам

           (4)

Последнее выражение следует  из обоснования (3).

Теперь кратчайший путь выписывается из следующего рекурсивного алгоритма:

Кратчайший путь из x_i в x_j:

1°. Если R_ij = 0  то выполнить 2°,

иначе выполнить 3°.

2°. Если i=j  то выписать x_i и закончить,

иначе выписать x_i и x_j закончить.

3°. Выписать кратчайший путь между x_i и .

4°. Выписать кратчайший путь между и x_j.

Пункты 3° и 4° предполагают рекурсивное обращение к рассмотренному алгоритму.

Для вывода кратчайшего пути для заданных двух вершин, необходимо еще модифицировать алгоритм Флойда. В рассмотренный алгоритм необходимо вставить проверку: совпадает ли текущая  вершина x_i с начальной, а x_j с конечной вершиной искомого пути.

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

Компьютерные средства и  информационные технологии повысили возможности  такого всеохватывающего метода изучения и создания, как моделирования  объектов, явлений и процессов  – как тех, что существуют в  природе, так и тех, что создаются  человеком искусственно.

Количество объектов усложнялись, увеличивались, и  натурное моделирование (макеты сооружений) стало невыгодным, неэкономным. Поэтому для изучения начали применять математику. Использование математических моделей – уравнения, неравенства,  формулы  и тому подобное называется математическим моделированием, для развития и приспособления которого нужны были эффективные численные методы.

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

 

1.2 Организация данных

Для удобства, все данные целесообразно записать в стандартный блокнот.

Рассмотрим это на примере:

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

Рассмотрим пример организации файла для графа, представленного на рисунке 1:

рисунок 1 - ориентированный  граф

 

Для данного графа файл выглядит следующим образом:

 

Таблица 1.2.1–Описание  переменных

Переменная	Тип	Описание
SizeMatrix	int	Количество точек (вершин) грифа
i,j	int	Счётчики
ot	int	Номер начальной точки (вершины)
do	int	Номер конечной точки (вершины)
MatrixWeight [i,j]	int	Массив i-j элемент которого содержит расстояние между i-й и j-й точками (вершинами) Замечание: с[i][i]=0; c[i][j]=c[j][i].
MatrixPath [i,j]	int	Массив строк, который  содержит пути Замечание: После прохождения обработки  по алгоритму Флойда p-й элемент массива содержит кратчайший путь.
WeightPath	int	Длина пути между двумя  вершинами. Замечание: После прохождения обработки  по алгоритму Флойда - содержит длину  кратчайшего  пути.
cont	int	Переменная служит для  определения выбранного варианта вывода информации.