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

                                                      СОДЕРЖАНИЕ 
 

Введение  …………………………………………………………………………..3 

1. Формализация исходных данных……….…………………………………......5

    1.1. Анализ современного состояния проблемы поиска кратчайшего          

      пути………………………………………………………………………….5

1.2. Анализ существующих методов…………………………………………..7

      1.2.1. Метод Форда………………………………………………………….7

      1.2.2. Метод Флойда………………………………………………………...8

      1.2.3. Метод Дейкстры……………………………………………………...9

3. Перспективы развития методов поиска кратчайших путей  .…………...10

    Выводы   ………………………………………………………………………..11 

2. Разработка алгоритма и программы поиска кратчайшего расстояния....…...12

    2.1 Разработка алгоритма………………………………………………………12

    2.2 Обоснование выбора языка программирования……………………….....14

    2.3 Разработка программы…………………………………………………….16

    Выводы………………………………………………………………………….17 

3.Экспериментальное исследование алгоритма и программы ….……………..18 

    3.1 Решение задачи методом Дейкстры………………………………………18

    3.2 Тестирование программы……………………………………………….....22

    3.3 Руководство программисту………………………………………………..23

    Выводы………………………………………………………………………….23  

Заключение.……………………………………………………………………….24 

Список  литературы ……………………………………………………………....25 

Приложения

А

Б 
 
 
 

                                                

                                                      

                                                         ВВЕДЕНИЕ 

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

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

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

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

             Работа состоит из трёх глав.

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

              Во второй главе разрабатывается алгоритм поиска кратчайшего расстояния. Производится выбор языка программирования. Разрабатывается программа.                              

            В третьей главе проводятся экспериментальные  исследования метода Дейкстры. Тестируется программа и приводятся результаты работы.

            
 

           1.  Формализация исходных данных. 

1. Анализ  современного состояния  проблемы поиска             

      кратчайшего пути. 

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

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

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

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

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

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

            На практике часто встречается задача определения кратчайшего маршрута по заданной сети из начального пункта до конечного пункта маршрута. Транспортная сеть может быть представлена в виде графа (рисунок 1.1.1), дуги которого - транспортные магистрали, а узлы - пункты отправления и назначения.

    

    Рисунок 1.1.1 Ориентированный граф.

     

Графически  транспортная сеть изображается в виде совокупности n пунктов P₁,P₂,...,P_n, причем некоторые упорядоченные пары (P_i, P_j) пунктов назначения соединены дугами заданной длинны r(P_i,P_j)=l_ij. Некоторые или все дуги могут быть ориентированы, т.е. по ним возможно движение только в одном направлении, указанном стрелками.  

            1.2 Анализ существующих методов.

            1.2.1. Метод Форда.

        Алгоритм  Форда позволяет   от какой-либо  исходной  вершины  Х определить минимальный путь до произвольной вершины Xj графа G.

            Алгоритм Форда состоит из  следующих шагов:

1)  Каждой   вершине   Xi  графа  G    ставятся  в  соответствие максимально

     возможные для данной задачи  числа Hi;                       

2)  На  втором   шаге вычисляются   разности  Hj  - Hi  для каждой  вершины    

     Xi, где  Hj -  вес вершины,  в которую  ведет дуга (Xi,Xj). Здесь возможны  

    три случая : Hj  - Hi < Lij,  Hj - Hi = Lij, Hj - Hi >  Lij, где Lij   - вес дуги,        

     ведущей   из вершины Xi в   вершину Xj.

    Случай,   когда Hj  -  Hi   >  Lij  позволяет нам уменьшить расстояние       

     между вершинами  Xi  и  Xj благодаря  следующим преобразованиям: 

     Hj  -  Hi  >   Lij , Hj >   Lij + Hi, отсюда принимаем:  Hj = Hi + Lij.

     Второй   шаг выполняется  до тех   пор, пока  еще существуют пары     

     (i,j),  для которых выполняется   неравенство Hj - Hi > Lij.

     По  окончанию   второго  этапа  метки   вершин позволяют нам