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

            Шаг 3.

                                                      min(x ) =10.

            Шаг 4.

                                                    l(x ) = 10 ; p= x .           

            Шаг 5. Все вершины имеют постоянные пометки. Остановка. Окончательная расстановка пометок приведена на рис.3

Для нахождения кратчайшего пути между вершиной x (например) и начальной вершиной применяем последовательно (2.2). Таким образом, полагая x =x , находим вершину x ’ , непосредственно предшествующую x в кратчайшем пути  от x к x ; вершина должна удовлетворять соотношению 

                                   l(x ’)+ C(x ’, x ’ )= l(x ’ )= 10.

Одной из таких вершиной является х = x ’.

Продолжая аналогичные рассуждения, получим :

                                l(х ’) + C(х ’, х ) = l(х ) = 7 х ’ = x .

                                l(x ’) + C(x ’, x ) = l(x ) = 6 x ’ = x .

                                l(x ’) + C(x ’, x )= l(x ) = 4 x ’ = x

Таким образом, кратчайший путь от вершины  x к вершине x   проходит через вершины x , x и х . То есть ( x , x ) = (x , x , x , х , x ). Путь на рисунке   выделен черным цветом.     

Рисунок 3.1.2- Окончательные пометки вершин графа.

            

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

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

 

Рисунок 3.2.1.- Интерфейс программы.

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

            Протестировав программу на примере, рассмотренном предыдущем пункте, мы получаем одинаковые данные. Это свидетельствует о её работоспособности. Задача решена верно.

           

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

            Для того чтобы программа работала быстро и эффективно не требуется мощных компьютеров и современных операционных систем. Ниже приведены минимальные параметры компьютера, которые нужны для работы:  

• Центральный процессор: Intel Pentium 166 MHz  (рекомендуется P2 400 MHz)
• Операционные системы: Microsoft Windows 98, Windows Millennium (Me), Windows 2000, Windows ХР
• Оперативная память: 128 Mb (рекомендуемая 256 Mb)
• Памяти на жестком диске: 115 Mb (при компактной установке),

   675 Mb (при полной установке), 580 Mb (при профессиональной установке), 
   480 Mb (при персональной установке)

• CD-ROM drive
• Монитор с разрешением VGA и выше

 

Выводы:

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

вершины;

2. Произведено решение тестового примера с помощью составленной

программы;

3. На основании совпадения результатов сделан вывод о работоспособности   

     программы.

4. Указаны необходимые требования для пользования программой.

                                         

                                               ЗАКЛЮЧЕНИЕ

 

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

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

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

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

                            

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

1. Н. Кристофидес, Теория графов. М.: «Мир» 1978г. ;
2. Вялых Б. И,, Сукманов С. А. Дискретная математика. ТАИИ 2004г;
3. О. Оре  Графы и их применение. Пер. с англ. под ред. И.М. Яглома. - М., “Мир”, 1965г;
4. Е. П. Липатов. Теория графов и её применения. - М., Знание, 1986г.