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

stify">     определить   значение  минимального    пути  из  исходной в конечную

     вершину;

3) На  третьем этапе  происходит  определение минимального  пути  при 

     помощи  обратного хода от конечной  вершины к начальной, причем   для

     вершины  Xj предшествующей   будет вершина  Xi, если   для  этой  пары  

     выполняется  Hj -   Hi  = Lij. Если существует   несколько таких пар,  то 

     выбирается любая   из них.          

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

            Существует два случая:

1) В графе нет циклов отрицательного веса.

            В основе алгоритма Флойда ([3] стр. 150) лежит метод динамического программирования. Пусть A - матрица размера NxN с элементами a , где a - длина кратчайшего пути между вершинами i и j, проходящего через вершины с номерами меньше либо равными k (не считая начальной и конечной вершин). Тогда A - матрица смежности нашего графа, A - искомая матрица кратчайших расстояний. Найдем a , зная A . Заметим, что в кратчайшем пути между вершинами i и j, содержащем вершины с номерами от 1 до k (т.е. соответсвующем a ) вершина k может либо встречаться, либо нет. Значит a , = min(a , a + a ).

2) В графе есть циклы отрицательного веса.

            В этом случае между некоторыми парами вершин может быть сколь угодно короткий путь. Найти такие пары несложно по матрице "кратчайших" путей, построенных алгоритмом Флойда.

            Если в графе много ребер отрицательного веса, то вес найденного алгоритмом Флойда цикла отрицательного веса будет очень быстро уменьшаться. Это может привести к нескольким последствиям:

а) произойдет переполнение типа (при данных ограничения вес цикла может достигать -10 .

б) вес цикла станет по абсолютной величине больше "бесконечности".

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

            Рассмотрим задачу в общем виде. Пусть дан граф G=(X,Г), дугам которого приписаны веса (стоимости), задаваемые матрицей С=||с ||. Задача о кратчайшем пути состоит в нахождении кратчайшего пути от заданной вершины s X до заданной конечной вершины t X., при условии, что такой путь существует, т.е. при условии t R(s). Здесь R(s)- множество вершин, достижимых из вершины s.

            Элементы с могут быть положительными, отрицательными или нулями. Единственное ограничение состоит в том, чтобы в G не было циклов с суммарным отрицательным весом.

            Из общей задачи о кратчайшем пути  вытекают две подзадачи:

            а) для заданной начальной вершины s найти кратчайшие пути между s и всеми другими вершинами x   X;

            б) найти кратчайшее расстояние между всеми парами вершин.

Рассмотрим задачу определения кратчайшего пути между заданными вершинами s и t для случая c   >0, i , j . Наиболее эффективный алгоритм решения задачи о кротчайшем (s-t) пути первоначально дал Дейкстра. В общем случае этот метод основан на приписывании вершинам временных пометок, причём пометка вершины даёт верхнюю границу длины пути от s к этой вершине. Эти пометки (их величины) постепенно уменьшаются с помощью итерационной процедуры, и на каждом шаге итерации только одна из временных пометок становиться постоянной. Последнее указывает на то, что пометка уже не является верхней границей, а даёт точную длину кратчайшего пути от s к рассматриваемой вершине.

        

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

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

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

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

 

            

Выводы:

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

     расстояния;

2) Рассмотрены существующие методы поиска кратчайшего расстояния;

3) Выявлены их недостатки;

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

 
 

            
 

            

            
 
 
 
 
 
 
 
 
 
 
 

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

                 расстояния. 

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

            Алгоритм Дейкстры включает следующие основные шаги:

            Пусть t(x )- пометка вершины x .

            Присвоение начальных значений

            Шаг 1. Положить l(s) = 0 и считать эту пометку постоянной.

Положить  l(x ) = ∞ для всех x ≠ s и считать эти пометки временными. Положить p=s.

            Обновление пометок

            Шаг 2. Для всех x Г(p), пометки которых временные, изменить пометки в соответствии со следующим выражением:

                                       l(x ) = min {l(x ); l(p) + c(p, x )}                                   (2.1)

            Превращение пометок в постоянные

            Шаг 3. Среди всех вершин с временными пометками найти такую, для которой:

                                       l(x *) = min { l(x )}.

             Шаг 4. Считать пометку вершины x* постоянной и положить p=x*.

            Шаг 5.

              а) если надо найти лишь путь от s к t. Если p=t, то l(p) является длиной кратчайшего пути. Останов. Если p ≠ t, то переход к шагу 2.

              б) если требуется найти пути от s ко всем остальным вершинам. Если все вершины отмечены как постоянные, то эти пометки дают длины кратчайших путей. Останов. Если некоторые пометки являются временными, то переход к шагу 2.

            Как только длины кратчайших путей от s будут найдены, сами пути можно получить при помощи рекурсивной процедуры с помощью соотношения:

                                       l(x ’) + c(x ’,x ) = l(x ),                                             (2.2)

Где вершина  x ’ непосредственно предшествует вершине x в кратчайшем пути от s к x .

            Если кратчайший путь от s до любой вершины x является единственным, то дуги (x ’, x) этого пути образуют ориентированное дерево с корнем s.

            Если существует несколько кратчайших путей от s к какой- либо другой вершине, то при некоторой фиксированной вершине x ’ соотношение (2.2) будет выполнятся для более чем одной вершины x . В этом случае  выбор может быть либо произвольным (если нужен хотя бы один кратчайший путь), либо таким, что рассматриваются все дуги (x ’, x), входящие в какой-либо из кратчайших путей, и при этом совокупность всех таких дуг образует неориентированное дерево, а общий граф, называемый базой относительно S или просо S-базой.

            Блок - схема алгоритма будет состоять из одиннадцати блоков [приложение А]:

             1) начало;

             2) ввод данных;

             3) обработка данных;

             4) открытие цикла перебора строк;

             5) поиск элементов;

             6) поиск расстояния до вершины;

             7) закрытие цикла перебора строк;

             8) выбор минимального расстояния;

             9) вывод полученной информации  на дисплей;

             10) проверка на завершение программы;

             11) конец.

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

                         После вывода полученной информации на дисплей, программа производит проверку на окончание. Если данное условие наступило, то программа заканчивает свою работу. В противном случае программа с новыми данными возвращается к блоку 3 и все действия повторяются заново.

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

            2.2 Выбор языка программирования. 

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

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