Ирина Эланс

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

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

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

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

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

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

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

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

Выполнил

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

Макаронок Сергей, 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₊₁}. Если этот путь не содержит x_m₊₁, то . Если же он содержит x_m₊₁, то деля путь на отрезки от x_i до x_m₊₁ и от x_m₊₁ до 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	Переменная служит для определения выбранного варианта вывода информации.

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

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

Для реализации алгоритма Флойда была выбрана система программирования Delphi версии 7 фирмы Enterprise (Borland), так как она предоставляет наиболее широкие возможности для программирования приложений ОС Windows.

Delphi – это продукт Borland International для быстрого создания приложений. Высокопроизводительный инструмент визуального построения приложений включает в себя настоящий компилятор кода и предоставляет средства визуального программирования, несколько похожие на те, что можно обнаружить в Microsoft Visual Basic или в других инструментах визуального проектирования. В основе Delphi лежит язык Object Pascal, который является расширением объектно-ориентированного языка Pascal. В Delphi также входят локальный SQL-сервер, генераторы отчетов, библиотеки визуальных компонентов, и прочее хозяйство, необходимое для того, чтобы чувствовать себя совершенно уверенным при профессиональной разработке информационных систем или просто программ для Windows-среды.

Прежде всего Delphi предназначен для профессиональных разработчиков, желающих очень быстро разрабатывать приложения в архитектуре клиент-сервер. Delphi производит небольшие по размерам (до 15-30 Кбайт) высокоэффективные исполняемые модули (.exe и .dll), поэтому в Delphi должны быть прежде всего заинтересованы те, кто разрабатывает продукты на продажу. С другой стороны небольшие по размерам и быстро исполняемые модули означают, что требования к клиентским рабочим местам существенно снижаются – это имеет немаловажное значение и для конечных пользователей.

Преимущества Delphi по сравнению с аналогичными программными продуктами.

– быстрота разработки приложения;

– высокая производительность разработанного приложения;

– низкие требования разработанного приложения к ресурсам компьютера;

– наращиваемость за счет встраивания новых компонент и инструментов в среду Delphi;

– возможность разработки новых компонент и инструментов собственными средствами Delphi (существующие компоненты и инструменты доступны в исходных кодах);

– удачная проработка иерархии объектов.

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

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

Для реализации, поставленной в курсовой работе задачи, была разработана программа Floid; которая включает 7 процедурных функций согласно обрабатываемым темам:

procedure ClearGrid;

procedure GetWeightsMatrix;

procedure FirstCountStep;

procedure GoCount;

procedure ShowResults;

function AllAreReady: boolean;

function GetMinPath: word;

Рассмотрим назначение каждой функции:

1. procedure ClearGrid; - производит очистку интерфейсной таблицы весов.

2. procedure GetWeightsMatrix; - переносит данные из TstringGrid в таблицу весов.

3. procedure FirstCountStep; - инициализация расчета.

4. procedure GoCount; - запуск расчета.

5. procedure ShowResults; - результаты расчета переносим в Memo

6. function AllAreReady: boolean; - идет проверка: все ли вершины обсчитаны?

7. function GetMinPath: word; - получаем вершину с наименьшем путем.

В процессе выполнения главной программы происходит перерасчет, по формулам, матрицы весов и матрицы путей. Также проводиться проверка корректности ввода информации.

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

Общая структура алгоритма программы представлена в виде

блок-схемы на рисунке 2.

Да

Нет

Да

Нет Нет

Рисунок 2

Описание действия программы представлено ниже.

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

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

Далее, по исходной матрице весов, создается матрица путей. Затем выполняется непосредственно алгоритм Флойда.

Следующим этапом выполнения программы является запрос о выборе вывода результата. Если выбран город из списка, то запускается соответствующая процедура и выводятся все доступные пути и его длины.

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

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

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

Минимальные системные требования к данному приложению представлены в таблице 3.1.1.

Таблица 3.1.1 – Минимальные системные требования

Элементы конфигурации	Описание характеристик
Процессор	AMD/Intel 200Ghz +
Оперативная память	32mb +
Видео адаптер	16mb +
Дисковой накопитель	3Мб
Клавиатура	Совместимая с персональным компьютером
Мышь	Совместимая с персональным компьютером
Блок питания	200W +
Монитор	15 +
Операционная система	98\2000\XP\Vista\Seven

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

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

Протестируем программу на примере, рассмотренном в пункте 1.2.

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

рисунок 3

Если была нажата кнопка «Показать вычисления», то открывается еще одно окно:

рисунок 4

При нажатии на кнопку «Заполнить города», в поле StringGrid помещаются все доступные города:

рисунок 5

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

рисунок 6

Также есть кнопка «Случайные пути», она создана для того, чтобы расстояния брались не настоящими величинами, а случайным образом. Это не основная функция программы, а дополнение.

Далее при нажатии кнопки «Рассчитать значения» в области Memo появляются все доступные пути от выбранного города до других доступных городов и расстояние между ними. Через символ «=>» указаны города, через которые лежит путь в конечный город; в скобках (…) указано расстояние между выбранным городом и конечным.

рисунок 7

Если ни один из городов не выбран, то при нажатии на кнопку «Рассчитать значения» появляется окно предупреждения:

рисунок 8

Теперь, после просмотра результатов и закрытия окна

«Расчет значений», попадаем на главное окно.

Далее для просмотра географической карты Беларуси, а также схематической карты (с известными расстояниями), нажимаем на кнопку «Показать графически»:

рисунок 9

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

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

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

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

Заключение

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

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

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

Теория графов находит применение, например, в геоинформационных системах (ГИС). Существующие или вновь проектируемые дома, сооружения, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередачи и т. п. — как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут.

Достоинства программы:

- В программе используется красочный графический интерфейс.

- В списке отображаются все доступные маршруты.

- Одновременная видимость списка городов и карты Беларуси.

Недостатки программы:

- Не разработан алгоритм поиска маршрута через требуемый город.

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

Литература

Архангельский А.Я. Программирование в Delphi 6 ––М.: ЗАО «Издательство БИНОМ», 2002
Архангельский А. Программирование в Delphi. Учебник по классическим версиям Delphi - М.: ЗАО «Издательство БИНОМ», 2006
Ахо А.В., Хопкрофт Д.Э., Ульман Д.Д. Построение и анализ вычислительных алгоритмов. Москва: Мир, 1979
Вирт Никлаус, Алгоритмы+структуры данных= программы. — М.: «Мир», 1985
Емеличев В.А., Мельников О.И. Лекции по теории графов. – М.: Наука, 1990
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. – М: МЦНМО, 2001
Кристофидес Н. Теория графов. – М.: Мир, 1978
Носов В.А. Комбинаторика и теория графов, МГТУ, 1999
Фаронов В.В. Delphi 6. Учебный курс. Издательство Молгачев С.В., 2001
Хаханов В.И., Чумаченко С.В. Дискретная математика (теоретическое и практическое содержание курса).–Кафедра АПВТ, 2002

Приложение A

(обязательное)

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

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Графы. Поиск оптимального маршрута по городам Беларуси 📙 Курсовая → 🆔 66702