Разработка алгоритма кратчайшего пути

СОДЕРЖАНИЕ

 

ВВЕДЕНИЕ                                                                                                                3

1 ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ И СООТВЕТСТВИЯ                                         5

1.1 Теория  графов как математическия аппарат для решения задач                    5

1.2 Алгоритм  нахождения кратчайшего пути между двумя точками                  9

2 РАЗРАБОТКА И АПРОБАЦИИ АЛГОРИТМА                                                 12

2.1 Составление блок-схемы                                                                                    12

2.2 Апробация работы алгоритма                                                                            15

ЗАКЛЮЧЕНИЕ                                                                                                          21

СПИСКА  ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ                                                22

ПРИЛОЖЕНИЕ                                                                                                         23

 

 

 

 

 

 

 

 

 

 

 

 

ВВЕДЕНИЕ

 

Данная курсовая работа будет  содержать в себе разработку студентом  собственного алгоритма нахождения кратчайшего пути между вершинами  графа. Алгоритм будет написан в  среде быстрой разработке приложений Borland Developed Studio на языке программирования производного от Object Pascal, реализованного в среде разработки Delphi.

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

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

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

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

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

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

Объект исследования –  методы теории графов кратчайшего пути между двумя точками.

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

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

Задачи исследования – 1) анализ применения теории графов для решения задач; 2) описание алгоритма нахождения кратчайшего пути между двумя точками; 3) разработка алгоритма нахождения кратчайшего пути между вершинами графа; 4) разработка программного приложения и апробация алгоритма на графах для нахождения кратчайшего пути между его вершинами.

Методы исследования –  анализ научно-методической, учебно-дидактической  литературы, учебников и учебных  пособий по информатике и программированию; изучение опыта по составлению вычислительных алгоритмов; вычислительный эксперимент.

Данная пояснительная записка состоит из двух частей: теоретической и практической, и содержит 22 страницы, 9 рисунков и 1 приложениеф.

 

 

 

 

 

 

 

 

1. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ И СООТВЕТСТВИЯ

 

1. Теория графов как математический аппарат для решения задач

 

Теория графов - это область дискретной математики, особенностью которой является геометрический подход к изучению объектов. Основной объект теории графов - граф и его обобщения.

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

Одним из первых результатов  в теории графов явился критерий существования  обхода всех ребер графа без повторений, полученный Л. Эйлером при решении задачи о Кенигсбергских мостах. Вот пересказ отрывка из письма Эйлера от 13 марта 1736 году: «Мне была предложена задача об острове, расположенном в городе Кенигсберге и окруженном рекой, через которую перекинуто 7 мостов[4].

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

Вопрос этот, хотя и банальный, показался мне, однако, достойным  внимания тем, что для его решения  недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство. После  долгих размышлений я нашел лёгкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое  угодно число и как угодно расположенных мостов или не может»[3].

 

                                              Рисунок 1.1 - Кенигсбергские мосты на карте, и в виде графа                    

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

В 20 веке задачи, связанные с графами, начали возникать не только в физике, химии, электротехнике биологии, экономике, социологии и т.д., но и внутри математики, в таких разделах, как топология, алгебра, теория вероятностей, теория чисел. В начале 20 века графы стали использоваться для представления некоторых математических объектов и формальной постановки различных дискретных задач; при этом наряду с термином «граф» употреблялись и другие термины, например, карта, комплекс, диаграмма, сеть, лабиринт. После выхода в свет в 1936 году монографии Д. Кёнига термин «граф» стал более употребительным, чем другие. В этой работе были систематизированы известные к тому времени факты. В 1936 году вышла небольшая брошюра Ойстена Оре, содержащая блестящее элементарное введение в теорию графов. В 1962 году в Англии была издана книга французского математика Клода Бержа «Теория графов и её приложение». Обе книги, безусловно, представляют интерес для любителей занимательной математики. Сотни известных головоломок, на первый взгляд не имеющих ничего общего друг с другом, легко решаются с помощью теории графов.

В 20-30-х годах 20 в. появились первые результаты, относящиеся к изучению свойств связности, планарности, симметрии графов, которые привели к формированию ряда новых направлений в теории графов[5].

Значительно расширились  исследования по теории графов в конце 40-х - начале 50-х годов, прежде всего  в силу развития кибернетики и вычислительной техники. Благодаря развитию вычислительной техники, изучению сложных кибернетических систем, интерес к теории графов возрос, а проблематика теории графов существенным образом обогатилась. Кроме того, использование ЭВМ позволило решать возникающие на практике конкретные задачи, связанные с большим объемом вычислений, прежде не поддававшиеся решению. Для ряда экстремальных задач теории графов были разработаны методы их решения, например, один из таких методов позволяет решать задачи о построении максимального потока через сеть. Для отдельных классов графов (деревья, плоские графы и т.д.), которые изучались и ранее, было показано, что решения некоторых задач для графов из этих классов находятся проще, чем для произвольных графов (нахождение условий существования графов с заданными свойствами, установление изоморфизма графов и др.).

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

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

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

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

Графы нашли применение практически  во всех отраслях научных знаний: физике, биологии, химии, математике, истории, лингвистике, социальных науках, технике  и т.п. Наибольшей популярностью  теоретико-графовые модели используются при исследовании коммуникационных сетей, систем информатики, химических и генетических структур, электрических  цепей и других систем сетевой структуры[1].

  

 

 

 

 

 

2. Алгоритм нахождения кратчайшего пути между вершинами

 

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

Алгоритм нахождение кратчайшего пути решает задачу о кратчайших путях из одной вершины для взвешенного ориентированного графа G = (V, E) с исходной вершиной s, в котором веса всех рёбер неотрицательны и не равны друг другу ( (u, v) ≥ 0 для всех (u, v) E).

Алгоритм будет состоять в следующем: Имеется граф. Некоторая его вершина обозначена как вершина 1. Необходимо найти минимальные пути от вершины 1 до определенно заданной вершины графа пользователем. Минимальным путём будем называть путь с минимальной суммой цен вдоль пути. Ценой назовем неотрицательное число являющееся весом ребра.

Идея алгоритма основывается на следующем: Пусть построен минимальный путь из вершины А в вершину B. И пусть вершина B связана с некоторым количеством вершин i. Обозначим через Ci - цену пути из вершины B в вершину i. Выберем из Ci минимальную величину. Тогда минимальное продолжение пути из точки B пойдёт через выбранную величину.

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

Главная процедура в алгоритме  состоит в том, что  добавление еще одной вершины к множеству выделенных. Эта процедура состоит из двух шагов:

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

Procedure 1;

Begin

S:={1);

For i:=2  to n do

D[i]:=C[1,i]; {инициализация D}

For i:=1 to n-1 do

Begin

Выбор из множества V\S такой вершины w, что значение D[w] минимально;

Добавить w к множеству S;

For каждая вершина v из множества V\S do

D[v]:=min(D[v], D[w]+C[w,v])

End;

End;

Листинг 1.2 – Процедура алгоритма нахождения кратчайшего пути.

 

1. Строим множество вершин  инцидентных выделенным и находим  среди их вершину с наименьшей  ценой. Найденная вершина добавляется  в множество выделенных.