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

 

 

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% менее трудоемок, чем применение алгоритма Дейкстры для всех пар вершин.

 

 

Литература

 

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

 

 

Приложение A

 

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

 

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

 

unit Unit1;

 

interface

 

uses

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