Реферат Алгоритм Дейкстры
Работа добавлена на сайт bukvasha.net: 2015-10-28Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
от 25%
Подписываем
договор
СОДЕРЖАНИЕ
Введение …………………………………………………………………………..3
1. Формализация исходных данных……….…………………………………......5
1.1. Анализ современного состояния проблемы поиска кратчайшего
пути………………………………………………………………………….5
1.2. Анализ существующих методов…………………………………………..7
1.2.1. Метод Форда………………………………………………………….7
1.2.2. Метод Флойда………………………………………………………...8
1.2.3. Метод Дейкстры……………………………………………………...9
1.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.1
Анализ современного состояния проблемы поиска
кратчайшего пути.
Теория графов - это область дискретной математики, особенностью которой является геометрический подход к изучению объектов. Обычно её относят к топологии (потому что во многих случаях рассматриваются лишь топологические свойства графов), однако она пересекается со многими разделами теории множеств, комбинаторной математики, алгебры, геометрии, теории матриц, теории игр, математической логики и многих других математических дисциплин. Основной объект теории графов - граф и его обобщения.
Первые задачи теории графов были связаны с решением математических развлекательных задач и головоломок (задача о Кенигсбергских мостах, задача о расстановке ферзей на шахматной доске, задачи о перевозках, задача о кругосветном путешествии и другие). Одним из первых результатов в теории графов явился критерий существования обхода всех ребер графа без повторений, полученный Л. Эйлером при решении задачи о Кенигсбергских мостах.
Родившись при решении головоломок и занимательных игр теория графов стала в настоящее время простым, доступным и мощным средством решения вопросов, относящихся к широкому кругу проблем. Графы буквально вездесущи. В 20 в. задачи, связанные с графами, начали возникать не только в физике, химии, электротехнике биологии, экономике, социологии и т.д., но и внутри математики, в таких разделах, как топология, алгебра, теория вероятностей, теория чисел. Не обошла она и Вооружённые Силы.
Так как охрана государственной границы, учебные мероприятия и проведение боевых операций требуют частой перегруппировки войск, совершения маршей, а время и ресурсы на их проведение ограничены, то теория графов с её богатым математическим аппаратом пришлась как нельзя кстати для решения поставленных задач. Правильно составленный маршрут движения будь то боевой техники или подразделений в пешем порядке позволяет выполнить поставленную задачу не только быстро, но и качественно. При выполнении поставленной задачи это позволяет расходовать меньше горючего, способствует уменьшению количества техники, вышедшей из строя при совершении марша из-за больших нагрузок, экономии сил и времени, что позволяет поднять моральный дух личного состава. Особенно это важно в боевых условиях.
Значительно расширились исследования по теории графов в конце 40-х - начале 50-х годов, прежде всего в силу развития кибернетики и вычислительной техники. Благодаря развитию вычислительной техники, изучению сложных кибернетических систем, интерес к теории графов возрос, а проблематика теории графов существенным образом обогатилась. Кроме того, использование ЭВМ позволило решать возникающие на практике конкретные задачи, связанные с большим объемом вычислений, прежде не поддававшиеся решению. Для ряда экстремальных задач теории графов были разработаны методы их решения, например, один из таких методов позволяет решать задачи о построении максимального потока через сеть. Для отдельных классов графов (деревья, плоские графы и т. д.), которые изучались и ранее, было показано, что решения некоторых задач для графов из этих классов находятся проще, чем для произвольных графов (нахождение условий существования графов с заданными свойствами, установление изоморфизма графов и др.).
За последние три десятилетия теория графов превратилась в один из наиболее бурно развивающихся разделов математики. Это вызвано запросами стремительно расширяющейся области приложений. В теоретико- графовых терминах формулируется большое число задач, связанных с дискретными объектами. Такие задачи возникают при проектировании интегральных схем и схем управления, при исследовании автоматов, логических цепей, блок - схем программ, в экономике и статистике, химии и биологии, в теории расписании и дискретной оптимизации. Таким образом, теория графов становится одной из существенных частей математического аппарата кибернетики, языком дискретной математики.
На практике часто встречается задача определения кратчайшего маршрута по заданной сети из начального пункта до конечного пункта маршрута. Транспортная сеть может быть представлена в виде графа (рисунок 1.1.1), дуги которого - транспортные магистрали, а узлы - пункты отправления и назначения.
Рисунок 1.1.1 Ориентированный граф.
Графически транспортная сеть изображается в виде совокупности n пунктов P1,P2,...,Pn, причем некоторые упорядоченные пары (Pi, Pj) пунктов назначения соединены дугами заданной длинны r(Pi,Pj)=lij. Некоторые или все дуги могут быть ориентированы, т.е. по ним возможно движение только в одном направлении, указанном стрелками.
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.
По окончанию второго этапа метки вершин позволяют нам
определить значение минимального пути из исходной в конечную
вершину;
3) На третьем этапе происходит определение минимального пути при
помощи обратного хода от конечной вершины к начальной, причем для
вершины Xj предшествующей будет вершина Xi, если для этой пары
выполняется Hj - Hi = Lij. Если существует несколько таких пар, то
выбирается любая из них.
1.2.2. Метод Флойда.
Существует два случая:
1) В графе нет циклов отрицательного веса.
В основе алгоритма Флойда ([3] стр. 150) лежит метод динамического программирования. Пусть A
2) В графе есть циклы отрицательного веса.
В этом случае между некоторыми парами вершин может быть сколь угодно короткий путь. Найти такие пары несложно по матрице "кратчайших" путей, построенных алгоритмом Флойда.
Если в графе много ребер отрицательного веса, то вес найденного алгоритмом Флойда цикла отрицательного веса будет очень быстро уменьшаться. Это может привести к нескольким последствиям:
а) произойдет переполнение типа (при данных ограничения вес цикла может достигать -10
б) вес цикла станет по абсолютной величине больше "бесконечности".
1.2.3. Алгоритм Дейкстры.
Рассмотрим задачу в общем виде. Пусть дан граф G=(X,Г), дугам которого приписаны веса (стоимости), задаваемые матрицей С=||с
Элементы с
Из общей задачи о кратчайшем пути вытекают две подзадачи:
а) для заданной начальной вершины s найти кратчайшие пути между s и всеми другими вершинами x
б) найти кратчайшее расстояние между всеми парами вершин.
Рассмотрим задачу определения кратчайшего пути между заданными вершинами s и t для случая c
1.3 Перспективы развития методов поиска кратчайших путей
Как уже говорилось, при использовании электронной карты имеет место достаточно большая размерность множества, определяющего пространство поиска, что, в свою очередь, проявляет один из недостатков данных алгоритмов: подобного рода поиск траектории связан с большими временными затратами и не может позволить решать задачу в реальном масштабе времени. В виду того, что для ряда практических задач важное значение имеет одновременное выполнение требования минимизации времени поиска и учета некоторого множества ограничивающих факторов, возникает вывод о невозможности использования названных выше алгоритмов. Решая вопрос преодоления этих трудностей, становится очевидной необходимость разработки нового метода, в основу которого можно было бы положить достоинства существующих алгоритмов.
Проблему перечисленных методов Дейкстры, форда и Флойда нахожу в том, что они не способны учитывать ряд ограничений в выборе траектории , связанных с преодолением естественных препятствий, таких как складки местности, водные преграды, обрывы. Из-за этого и из-за сравнительно больших временных затрат нет возможности решать проблему поиска кратчайшего и оптимального пути в реальном масштабе времени.
Необходима разработка новых методов, которые основывались бы на уже известных, но включали дополнительный набор параметров, которые необходимо учитывать при отыскании кратчайшего пути.
Выводы:
1) Произведён анализ современного состояния проблемы поиска кратчайшего
расстояния;
2) Рассмотрены существующие методы поиска кратчайшего расстояния;
3) Выявлены их недостатки;
4) Предложен путь дальнейшего развития методов поиска кратчайшего расстояния.
2. Разработка алгоритма и программы поиска кратчайшего
расстояния.
2.1 Разработка алгоритма.
Алгоритм Дейкстры включает следующие основные шаги:
Пусть t(x
Присвоение начальных значений
Шаг 1. Положить l(s) = 0 и считать эту пометку постоянной.
Положить l(x
Обновление пометок
Шаг 2. Для всех x
l(x
Превращение пометок в постоянные
Шаг 3. Среди всех вершин с временными пометками найти такую, для которой:
l(x
Шаг 4. Считать пометку вершины x* постоянной и положить p=x*.
Шаг 5.
а) если надо найти лишь путь от s к t. Если p=t, то l(p) является длиной кратчайшего пути. Останов. Если p ≠ t, то переход к шагу 2.
б) если требуется найти пути от s ко всем остальным вершинам. Если все вершины отмечены как постоянные, то эти пометки дают длины кратчайших путей. Останов. Если некоторые пометки являются временными, то переход к шагу 2.
Как только длины кратчайших путей от s будут найдены, сами пути можно получить при помощи рекурсивной процедуры с помощью соотношения:
l(x
Где вершина x
Если кратчайший путь от s до любой вершины x
Если существует несколько кратчайших путей от s к какой- либо другой вершине, то при некоторой фиксированной вершине x
Блок - схема алгоритма будет состоять из одиннадцати блоков [приложение А]:
1) начало;
2) ввод данных;
3) обработка данных;
4) открытие цикла перебора строк;
5) поиск элементов;
6) поиск расстояния до вершины;
7) закрытие цикла перебора строк;
8) выбор минимального расстояния;
9) вывод полученной информации на дисплей;
10) проверка на завершение программы;
11) конец.
Во втором блоке программы производится инициализация массива имеющимися данными. Далее данная информация следует в блок «обработка данных». В данном блоке определяются исходные данные для данной итерации. В зависимости от полученных данных программа задаёт перебор строки массива (блок «перебор строк»). Данная процедура позволяет программе производить поиск элементов в столбце (блок «поиск элементов»). Если программа находит элемент, то производится расчет расстояния до этой вершины от начальной. После перебора всех строк массив закрывается. После этой процедуры программа из полученных расстояний до вершин выбирает наименьшее. После обработки всех соответствующих этой величине данных, программа производит вывод информации на дисплей (блок «вывод информации»).
После вывода полученной информации на дисплей, программа производит проверку на окончание. Если данное условие наступило, то программа заканчивает свою работу. В противном случае программа с новыми данными возвращается к блоку 3 и все действия повторяются заново.
Предложенный алгоритм является простым и быстрым приближенным способом поиска оптимального маршрута.
2.2 Выбор языка программирования.
Прогресс компьютерных технологий определил процесс появления новых разнообразных знаковых систем для записи алгоритмов – языков программирования. Смысл появления такого языка – оснащённый набор вычислительных формул дополнительной информации, превращает данный набор в алгоритм. Язык программирования служит двум связанным между собой целям: он даёт программисту аппарат для задания действий, которые должны быть выполнены, и формирует концепции, которыми пользуется программист, размышляя о том, что делать.
Си ++ - это универсальный язык программирования, задуманный так, чтобы сделать программирование более приятным для серьёзного программиста. За исключением второстепенных деталей Си ++ является надмножеством языка программирования Си. Помимо возможностей, которые дает Си, Си ++ предоставляет гибкие и эффективные средства определения новых типов. Используя определения новых типов, точно отвечающих концепциям приложения, программист может разделять разрабатываемую программу на легко поддающиеся контролю части. Такой метод построения программ часто называют абстракцией данных. Информация о типах содержится в некоторых объектах типов, определённых пользователем. Такие объекты просты и надёжны в использовании в тех ситуациях, когда их тип нельзя установить на стадии компиляции. Программирование с применением таких объектов часто называют объектно-ориентированным. При правильном использовании этот метод даёт более короткие, проще понимаемые и легче контролируемые программы.
Си ++ обеспечивает полный набор операторов структурного программирования. Он также предлагает необычно большой набор операций. Многие операции Си ++ соответствуют машинным командам, и поэтому допускают прямую трансляцию в машинный код. Разнообразие операций позволяет выбирать их различные наборы для минимизации результирующего поля.
Си ++ поддерживает указатели не переменные и функции. Указатель на объект программы соответствует машинному адресу этого объекта. Посредством разумного использования указателей можно создавать эффективно-выполняемые программы, так как указатели позволяют ссылаться на объекты тем же самым путём, как это делает машина. Си ++ поддерживает арифметику указателей, и тем самым позволяет осуществлять непосредственный доступ и манипуляции с адресами памяти.
В своём составе Си ++ содержит препроцессор, который обрабатывает текстовые файлы перед компиляцией. Среди его наиболее полезных приложений при написании программ на Си ++ являются: определение программных констант, замена вызова функций аналогичными, но более быстрыми макросами, условная компиляция. Препроцессор не ограничен процессированием только исходных текстовых файлов Си ++, он может быть использован для любого текстового файла.
Си ++ - гибкий язык, позволяющий принимать в конкретных ситуациях самые разные решения.
Исходя из вышеизложенного для написания программы, был выбран язык программирования Borland С ++ Builder версии 6.0, стандарта ISO/IEC 144882.
2.3 Разработка программы.
Основываясь на разработанном алгоритме и выбранном языке программирования Borland С ++ Builder версии 6.0, стандарта ISO/IEC 144882, была написана программа.
Тело программы состоит из главной функции и четырех впомогательных.
Программа начинается с подключения стандартных библиотек (iostream и conio).
Далее в программе определяется максимальная размерность массива. После определения данной величины, производится определение глобальных массивов:
-mass;
-TempMass.
Далее производится объявление вспомогательных функций:
- void Vvod(float a[n][n],float b[n][n],int n) - данная функция преднащначена для инициализации массива;
-void Vivod(float a[n][n],int n) – данная функция выводит массив с результатами вычислений;
- void Obnul(float a[n][n],int n,int I) - функция предназначенная для отбрасывания пройденных верщин;
-void ZapTempMass(float a[n],int I,int J,int n) – данная функция записывает данные во временный массив.
Далее следует главная функция. Данная функция начинается с определения величин необходимых в ходе решения:
int Otvet[n] - данный массив предназначен для записи в него найденных вершин, которые будут являться ответом.
int size; - величина инициализирующаяся числом количества вершин
float L[n] - массив, содержащий данные о расстояния между определяемыми вершинами;
float min(0) - временная величина, предназначенная для отыскания минимального расстояния между вершинами;
int i=1- исходная вершина по умолчанию;
int j - величина используемая для перебора в массиве;
int s(0) - счетчик итераций.
Далее программа предлогает пользователю ввести количетво вершин.
Посде получения программой данной величины, она создает массив, который далее будет инициализироваться величиной расстояния между вершинами.
После получения программой всех начальных данных, ей будет предложено ввести начальную вершину. После получения программой данной величины, она приступает к решению поставленной ей задачи. Организуется счётчик итераций. На каждой из них происходит вычисление промежуточных значений, которые потом заносятся в массив TempMass и выводятся на экран. После этого массив обнуляется. На каждой итерации выбирается минимальное значение расстояния TempMin, которое определяет дальнейшую строку, по которой будем работать.
while(s<size) – операция будет продолжаться до тех пор, пока количество итераций не станет равным количеству вершин. При выполнении последнего условия выводится конечный результат. Для завершения надо нажать кнопку Ввод. В конце программного кода идёт определение всех четырёх вспомогательных функций.
Выводы:
1) Произведённые в предыдущих главах исследования позволили составить
алгоритм поиска кратчайшего расстояния;
2) Обоснован выбор языка программирования;
3) На основе составленного алгоритма составлена программа поиска
расстояния.
3. Экспериментальное исследование алгоритма и
программы.
3.1 Решение задачи методом Дейкстры.
Рассмотрим действие алгоритма на примере. Пусть дан граф G, показанный на рисунке 3.1.1, где каждое неориентированное ребро рассматривается как пара противоположно ориентированных дуг равного веса. Матрица смежности весов С приведена ниже. Требуется найти все кратчайшие пути от вершины x, ко всем остальным вершинам. Для решения задачи воспользуемся алгоритмом Дейкстры, который является одним из самых быстрых для поиска кратчайшего расстояния от некоторой вершины до всех остальных.
Рисунок 3.1.1- Смешанный граф
Решение.
Постоянные пометки будем снабжать знаком +, остальные пометки рассматриваются как временные.
Шаг 1.
l(x
p = x
Первая итерация
Шаг 2.
Г( p) = Г(x
Применяя (2) , получим
l(x
Так как на первой итерации вершина только одна , то шаг 3 по выбору минимума опускается.
Шаг 4.
l(x
Шаг 5.
Не все вершины имеют постоянные пометки.
Переход к следующей итерации.
| i / j | x | x | x | x | x | x |
| x | --------- | 4 | | | | |
| x | 4 | --------- | 3 | | 2 | 3 |
| x | | 3 | --------- | 5 | 1 | 4 |
| x | | | 5 | --------- | | 3 |
| x | | 2 | 1 | | --------- | 2 |
| x | | 3 | 4 | 3 | 2 | --------- |
Таблица 3.1.1- Матрица смежности весов .
Вторая итерация.
Шаг 2.
Г( p) = Г(x
l(x
l(x
l(x
Шаг 3.
min{l(x
Шаг 4.
l(x
Шаг 5. Переход к следующей итерации.
Третья итерация.
Шаг 2.
Г( p) = Г(x
l(x
l(x
Шаг 3.
min{l(x
Выбираем любую вершину.
Шаг 4.
l(x
Шаг 5. Переход к следующей итерации.
Четвёртая итерация.
Шаг 2.
Г( p) = Г(x
l(x
l(x
Шаг 3.
min{ l(x
Шаг 4.
l(x
Шаг 5. Переход к следующей итерации.
Пятая итерация.
Шаг 2.
Г( p) = Г(x
l(x
Шаг 3.
min(x
Шаг 4.
l(x
Шаг 5. Все вершины имеют постоянные пометки. Остановка. Окончательная расстановка пометок приведена на рис.3
Для нахождения кратчайшего пути между вершиной x
l(x
Одной из таких вершиной является х
Продолжая аналогичные рассуждения, получим :
l(х
l(x
l(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г.
