Принципы и подходы к динамическому программированию, сферы его использования, приемы и принципы. Решение задачи теста для написания и отладки программы, используемые входные и выходные данные. Тестирование заданной программы и инструкция пользователя.
Задача о кратчайшем пути - задача поиска самого короткого пути (цепи) между двумя точками (вершинами) на графе, в которой минимизируется сумма весов ребер, составляющих путь. Такой путь P называется путем длиной n из вершины v1 в vn (i указывает на номер вершины пути и не имеет никакого отношения к нумерации вершин на графе). В связи с тем, что существует множество различных постановок данной задачи, есть наиболее популярные алгоритмы для решения задачи поиска кратчайшего пути на графе: - Алгоритм Дейкстры находит кратчайший путь от одной из вершин графа до всех остальных. Предположим, что нам известны m вершин, ближайших к вершине s (близость любой вершины x к вершине s определяется длиной кратчайшего пути, ведущего из s в x). Это обусловливается тем, что кратчайший путь из вершины s в (m 1)-ю ближайшую вершину при положительном значении длин всех дуг должен содержать в качестве промежуточных лишь окрашенные вершины, т.е. вершины, входящие в число m вершин, ближайших к вершине s.В данном курсовом проекте выполнена постановка задачи нахождения кратчайшего пути. Задача о кратчайшем пути - задача поиска самого короткого пути (цепи) между двумя точками (вершинами) на графе, в которой минимизируется сумма весов ребер, составляющих путь. Алгоритм Флойда - Уоршелла находит кратчайшие пути между всеми вершинами взвешенного ориентированного графа. Находит путь между вершинами s и t графа (s не совпадает с t), содержащий минимальное количество промежуточных вершин (ребер). Алгоритм Дейкстры позволяет находить в графе кратчайший путь между двумя выделенными вершинами s и t при положительных длинах дуг.
Введение
«Задача поиска кратчайшего пути » (задача оминимальном пути, задача о дилижансе), в последнее время получилаширокое распространение, благодаря своему применению для решения множества других задач.
В настоящее время она применяется в алгоритмах поиска оптимального пути между двумя объектами (GPS-навигация), в системах автоматического пилотирования, для нахождения кратчайшего пути прохождения Internet-пакета по сети, и множества других.
Задача о кратчайшем пути является одной из важнейших классических задач теории графов. На сегодняшний день известно множество алгоритмов для ее решения.
Кратчайший путь рассматривается с помощью математической модели, называемой графом.
Похожие задачи: - Задача коммивояжера. Требуется найти кратчайший маршрут, проходящий через указанные города (вершины) хотя бы по одному разу с последующим возвратом в исходный город. Данная задача относится к классу NP-трудных задач в отличие от задачи поиска кратчайшего пути, которая может быть решена за полиномиальное время в графах без циклов. Задача коммивояжера решается неэффективно для больших наборов данных.
- Задача канадского путешественника и задача стохастического поиска кратчайшего пути являются обобщением рассматриваемой задачи, в которых обходимый граф заранее полностью неизвестен и изменяется во времени или следующий проход по графу вычисляется на основе вероятностей.
Целью курсового проекта является разработка приложения для решения задачи нахождения кратчайшего пути.
Задачи курсового проекта: - Выполнить постановку задачи нахождения кратчайшего пути;
- Выполнить обзор существующих решений задачи нахождения кратчайшего пути;
- Рассмотреть решение задачи теста для написания и отладки программы;
- Выполнить входные и выходные данные работы программы;
- Выполнить организацию диалога;
- Выполнить разработку алгоритма;
- Обосновать выбор средств разработки;
- Протестировать программу;
- Составить инструкцию пользователю;
- Выполнить заключение;
- Рассмотреть список использованной литературы;
- Оформить приложения;
- Выполнить презентацию для защиты курсового проекта.
1. Общая часть
1.1 Постановка задачи
Задача о кратчайшем пути - задача поиска самого короткого пути (цепи) между двумя точками (вершинами) на графе, в которой минимизируется сумма весов ребер, составляющих путь.
Кратчайшая (простая) цепь часто называется геодезической.
Задача о кратчайшем пути является одной из важнейших классических задач теории графов.
Сегодня известно множество алгоритмов для ее решения.
У данной задачи существуют и другие названия: задача о минимальном пути или, в устаревшем варианте, задача о дилижансе.
Значимость данной задачи определяется ее различными практическими применениями. Например, в GPS-навигаторах, где осуществляется поиск кратчайшего пути между двумя перекрестками. В качестве вершин выступают перекрестки, а дороги являются ребрами, которые лежат между ними. Сумма расстояний всех дорог между перекрестками должна быть минимальной, тогда найден самый короткий путь.
Задача поиска кратчайшего пути на графе может быть определена для неориентированного, ориентированного или смешанного графа. Далее будет рассмотрена постановка задачи в самом простом виде для неориентированного графа. Для смешанного и ориентированного графа дополнительно должны учитываться направления ребер.
Граф представляет собой совокупность непустого множества вершин и ребер (наборов пар вершин). Две вершины на графе смежные, если они соединяются общим ребром. Путь в неориентированном графе представляет собой последовательность вершин P = (v1,v2,...,vn) € V x V x … x V, таких что vi смежная с vi 1 для . Такой путь P называется путем длиной n из вершины v1 в vn (i указывает на номер вершины пути и не имеет никакого отношения к нумерации вершин на графе).
Существуют различные постановки задачи о кратчайшем пути: - Задача о кратчайшем пути в заданный пункт назначения. Требуется найти кратчайший путь в заданную вершину назначения t, который начинается в каждой из вершин графа (кроме t). Поменяв направление каждого принадлежащего графу ребра, эту задачу можно свести к задаче о единой исходной вершине (в которой осуществляется поиск кратчайшего пути из заданной вершины во все остальные).
- Задача о кратчайшем пути между заданной парой вершин. Требуется найти кратчайший путь из заданной вершины u в заданную вершину v.
- Задача о кратчайшем пути между всеми парами вершин. Требуется найти кратчайший путь из каждой вершины u в каждую вершину v. Эту задачу тоже можно решить с помощью алгоритма, предназначенного для решения задачи об одной исходной вершине, однако обычно она решается быстрее.
В различных постановках задачи, роль длины ребра могут играть не только сами длины, но и время, стоимость, расходы, объем затрачиваемых ресурсов (материальных, финансовых, топливно-энергетических и т.п.) или другие характеристики, связанные с прохождением каждого ребра. Таким образом, задача находит практическое применение в большом количестве областей (информатика, экономика, география и др.).
1.2 Обзор существующих решений
В связи с тем, что существует множество различных постановок данной задачи, есть наиболее популярные алгоритмы для решения задачи поиска кратчайшего пути на графе: - Алгоритм Дейкстры находит кратчайший путь от одной из вершин графа до всех остальных. Алгоритм работает только для графов без ребер отрицательного веса.
- Алгоритм Беллмана - Форда находит кратчайшие пути от одной вершины графа до всех остальных во взвешенном графе. Вес ребер может быть отрицательным.
- Алгоритм поиска А* находит маршрут с наименьшей стоимостью от одной вершины (начальной) к другой (целевой, конечной), используя алгоритм поиска по первому наилучшему совпадению на графе.
- Алгоритм Флойда - Уоршелла находит кратчайшие пути между всеми вершинами взвешенного ориентированного графа.
- Алгоритм Джонсона находит кратчайшие пути между всеми парами вершин взвешенного ориентированного графа.
- Алгоритм Ли (волновой алгоритм) основан на методе поиска в ширину. Находит путь между вершинами s и t графа (s не совпадает с t), содержащий минимальное количество промежуточных вершин (ребер). Основное применение - трассировки электрических соединений на кристаллах микросхем и на печатных платах. Так же используется для поиска кратчайшего расстояния на карте в стратегических играх.
- Поиск кратчайшего пути на основе алгоритма Килдала.
- Задача о поиске кратчайшего пути на графе может быть интерпретирована по-разному и применяться в различных областях. Далее приведены примеры различных применений задачи. Другие применения изучаются в дисциплине, которая занимается исследованием операций.
Картографические сервисы
Алгоритмы нахождения кратчайшего пути на графе применяются для нахождения путей между физическими объектами на таких картографических сервисах, как карты Google или OPENSTREETMAP.
Недетерминированная машина
Если представить недетерминированную абстрактную машину как граф, где вершины описывают состояния, а ребра определяют возможные переходы, тогда алгоритмы поиска кратчайшего пути могут быть применены для поиска оптимальной последовательности решений для достижения главной цели. Например, если вершинами являются состояния кубика рубика, а ребром представляет собой одно действие над кубиком, тогда алгоритм может быть применен для поиска решения с минимальным количеством ходов.
Сети дорог
Задача поиска кратчайшего пути на графе широко используется при определении наименьшего расстояния в сети дорог.
Сеть дорог можно представить в виде графа с положительными весами. Вершины являются дорожными развязками, а ребра дорогами, которые их соединяют. Веса ребер могут соответствовать протяженности данного участка, времени необходимому для его преодоления или стоимости путешествия по нему. Ориентированные ребра можно использовать для представления односторонних улиц. В таком графе можно ввести характеристику, которая указывает на то, что одни дороги важнее других для длительных путешествий (например, автомагистрали). Она была формализована в понятии (идее) о магистралях.
Для реализации подхода, где одни дороги важнее других, существует множество алгоритмов. Они решают задачу поиска кратчайшего пути намного быстрее, чем аналогичные на обычных графах. Подобные алгоритмы состоят из двух этапов: 1) этап предобработки. Производится предварительная обработка графа без учета начальной и конечной вершины (может длиться до нескольких дней, если работать с реальными данными). Обычно выполняется один раз и потом используются полученные данные.
2) этап запроса. Осуществляется запрос и поиск кратчайшего пути, при этом известны начальная и конечная вершина.
2.Технологическая часть
2.1 Динамическое программирование
Под динамическим программированием понимают некоторый специальный метод оптимизации, суть которого состоит в отыскании оптимального решения путем выполнения вычислений в несколько шагов (этапов).
Вся задача оптимизации разделяется на несколько шагов, причем вес шагов могут быть уникальными или одинаковыми и чередоваться друг с другом. Некоторые задачи оптимизации легко разделяются на шаги естественным способом, а для других - вводится искусственное разделение на шаги.
Примерами задач, решаемых динамическим программированием могут быть: распределение ресурсов (финансовых, сырьевых, материальных и т.д.) между предприятиями, замена (или ремонт) промышленного оборудования, прокладка коммуникаций (трубопроводов, дорог и т.д.) и пр. В этих задачах, как правило, в качестве шагов (этапов) выступают отрезки времени (годы, кварталы и т.д.), которые явно задаются в условии задачи.
Большинство методов исследования операций связано в первую очередь с задачами вполне определенного содержания. Классический аппарат математики оказался малопригодным для решения многих задач оптимизации, включающих большое число переменных и / или ограничений в виде неравенств. Несомненна привлекательность идеи разбиения задачи большой размерности на подзадачи меньшей размерности, включающие всего по нескольких переменных, и последующего решения общей задачи по частям. Именно на этой идее основан метод динамического программирования.
Динамическое программирование (ДП) представляет собой математический метод, заслуга создания и развития которого принадлежит прежде всего Беллману. Метод можно использовать для решения весьма широкого круга задач, включая задачи распределения ресурсов, замены и управления запасами, задачи о загрузке.
Характерным для динамического программирования является подход к решению задачи по этапам, с каждым из которых ассоциирована одна управляемая переменная. Набор рекуррентных вычислительных процедур, связывающих различные этапы, обеспечивает получение допустимого оптимального решения задачи в целом при достижении последнего этапа.
Происхождение названия динамическое программирование, вероятно, связано с использованием методов ДП в задачах принятия решений через фиксированные промежутки времени (например, в задачах управления запасами). Однако методы ДП успешно применяются также для решения задач, в которых фактор времени не учитывается. По этой причине более удачным представляется термин многоэтапное программирование, отражающий пошаговый характер процесса решения задачи.
Фундаментальным принципом, положенным в основу теории ДП, является принцип оптимальности. По существу, он определяет порядок поэтапного решения допускающей декомпозицию задачи (это более приемлемый путь, чем непосредственное решение задачи в исходной постановке) с помощью рекуррентных вычислительных процедур.
Динамическое программирование позволяет осуществлять оптимальное планирование управляемых процессов. Под «управляемыми» понимаются процессы, на ход которых мы можем в той или другой степени влиять.
Пусть предполагается к осуществлению некоторое мероприятие или серия мероприятий («операция»), преследующая определенную цель. Спрашивается: как нужно организовать (спланировать) операцию для того, чтобы она была наиболее эффективной? Для того, чтобы поставленная задача приобрела количественный, математический характер, необходимо ввести в рассмотрение некоторый численный критерий W, которым мы будем характеризовать качество, успешность, эффективность операции. Критерий эффективности в каждом конкретном случаи выбирается исходя из целевой направленности операции и задачи исследования (какой элемент управления оптимизируется и для чего).
Сформулируем общий принцип, лежащий в основе решения всех задач динамического программирования («принцип оптимальности»): «Каково бы ни было состояние системы S перед очередным шагом, надо выбрать управление на этом шаге так, чтобы выигрыш на данном шаге плюс оптимальный выигрыш на всех последующих шагах был максимальным».
Динамическое программирование - это поэтапное планирование многошагового процесса, при котором на каждом этапе оптимизируется только один шаг. Управление на каждом шаге должно выбираться с учетом всех его последствий в будущем.
Рассмотрим пример задачи динамического программирования.
Для двух предприятий выделено 1400 единиц денежных средств. Как распределить все средства в течение 4 лет, чтобы доход был наибольшим, если известно, что доход от х единиц, вложенных в первое предприятие равен f1(x) = 3x, а доход от у единиц, вложенных в первое предприятие равен f2(y) = 4y. Остаток средств, к концу года составляет g1(x) = 0,5x - для первого предприятия, g2(y) = 0,3y - для второго предприятия. Решить задачу методом динамического программирования.
Решение: Процесс распределения средств разобьем на 4 этапа - по соответствующим годам.
Обозначим ak = xk yk - средства, которые распределяются на к-ом шаге как сумма средств по предприятиям.
Суммарный доход от обоих предприятий на к-ом шаге: zk = f1(xk) f2(ak - xk) = 3xk 4(ak - xk) = 4ak - xk
Остаток средств от обоих предприятий на к-ом шаге: ak 1 = g1(xk) g2(ak - xk) = 0,5xk 0,3(ak - xk) = 0,3ak 0,2xk
Обозначим z k (ak) - максимальный доход, полученный от распределения средств ak между двумя предприятиями с к-го шага до конца рассматриваемого периода.
Рекуррентные соотношения Беллмана для этих функций
Z 4 (a4) =
Z 4 (a4) =
Проведем оптимизацию, начиная с четвертого шага: 4-й шаг.
Оптимальный доход равен: Z 4 (a4) = , т.к. линейная убывающая функция достигает максимума в начале рассматриваемого промежутка, т.е. при x4 = 0.
3-й шаг.
Z 3(a3)= т.к. линейная убывающая функция достигает максимума в начале рассматриваемого промежутка, т.е. при x3 = 0.
2-й шаг.
Z 2(a2)= т.к. линейная возрастающая функция достигает максимума в конце рассматриваемого промежутка, т.е. при x2 = a2.
1-й шаг. z 1(a1)= т.к. линейная возрастающая функция достигает максимума в конце рассматриваемого промежутка, т.е. при x1 = a1.
Результаты оптимизации: z 1(a1) = 6,8a1; x 1 = a1;
z 2(a2) = 5,6?2; x 2 = a2;
z 3(a3) = 5,2a3; x 3 = 0;
z 4(a4) = 4a4; x 4 = 0;
Определим количественное распределение средств по годам: Т.к. a1 = a = 1400, x 1 = 1400, получаем a2 = 0,3a1 0,2x1 = 700 a3=0,3a2 0,2x2=350 a4=0,3a3 0,2x3=105
Представим распределение средств в виде таблицы: Таблица 1 предприятие год
1 2 3 4
1 1400 700 0 0
2 0 0 350 105
При таком распределении средств за 4 года будет получен доход, равный
3.Специальная часть
3.1 Описание метода решения
Алгоритм Дейкстры позволяет находить в графе кратчайший путь между двумя выделенными вершинами s и t при положительных длинах дуг. Этот алгоритм, предложенный в 1959 г. Дейкстрой, считается одним из наиболее эффективных алгоритмов решения задачи.
Главная идея, лежащая в основе алгоритма Дейкстры, предельно проста. Предположим, что нам известны m вершин, ближайших к вершине s (близость любой вершины x к вершине s определяется длиной кратчайшего пути, ведущего из s в x). Пусть также известны сами кратчайшие пути, соединяющие вершину s с выделенными m вершинами. Покажем теперь, как может быть определена (m 1)-я ближайшая к s вершина.
Окрасим вершину s и m ближайших к ней вершин. Построим для каждой неокрашенной вершины y пути, непосредственно соединяющие с помощью дуг (х, у) каждую окрашенную вершину х с у. Выберем из этих путей кратчайший, и будем считать его условно кратчайшим путем из вершины s в вершину y.
Какая же из неокрашенных вершин является (m 1)-й ближайшей к s вершиной? Та, для которой условно кратчайший путь имеет наименьшую длину. Это обусловливается тем, что кратчайший путь из вершины s в (m 1)-ю ближайшую вершину при положительном значении длин всех дуг должен содержать в качестве промежуточных лишь окрашенные вершины, т.е. вершины, входящие в число m вершин, ближайших к вершине s.
Итак, если известны m ближайших к s вершин, то (m 1)-я ближайшая к s вершина может быть найдена так, как это описано выше. Начиная с m = 0, описанная процедура может повторяться до тех пор, пока не будет получен кратчайший путь, ведущий из вершины s к вершине t.
Имея в виду приведенные соображения, мы можем теперь формально описать алгоритм Дейкстры.
Каждой вершине X в ходе алгоритма присваивается число d(x), равное длине кратчайшего пути из вершины S в вершину X и включающем только окрашенные вершины. Положить d(s)=0 и d(x)=? для всех остальных вершин графа. Окрашиваем вершину S и полагаем y=S, где y - последняя окрашенная вершина.
1. Для каждой неокрашенной вершины X пересчитывается величина d(x) последующей формуле: d(x)=min{d(x); d(y) ay,x}, ay,x - ребро.
2. Если d(x)=? для всех неокрашенных вершин, то алгоритм заканчивается т.к. отсутствуют пути из вершины S в неокрашенные вершины. Иначе окрашивается та вершина, для которой величина d(x) является минимальной. Окрашивается и дуга, ведущая в эту вершину в соответствии с выражением (1) и полагаем y=x.
3. Если y=t, кратчайший путь из s в t найден. Иначе переходим к шагу 2.
Каждый раз окрашивается вершина и дуга, заходящая в эту вершину. Окрашенные дуги не могут образовывать цикл, а образуют в исходном графе дерево с корнем (началом) в вершине s. Это дерево называют ориентированным деревом кратчайших путей. Путь из s в t принадлежит этому дереву. При поиске одного кратчайшего пути процедура наращивания завершается при достижении конечной вершины этого пути. Нам же необходимо получить все кратчайшие пути начинающиеся в вершине №1. Для этого процедуру наращивания ориентированного дерева продолжается до тех пор, пока все вершины не будут включены. Таким образом, мы получаем ориентированное дерево кратчайших путей, которое является покрывающим деревом графа.
Иногда в графе имеются несколько кратчайших путей. Кратчайший путь будет единственным, если в алгоритме ни разу не возникает неоднозначность при окрашивании дуги.
Отметим, что главным условием успешного применения алгоритма Дейкстры к задаче на графе является не отрицательность длин дуг этого графа.
3.2 Решение задачи теста для написания и отладки программы
Рассмотрим работу алгоритма на примере графа, показанного на рисунке 1. Пусть требуется найти расстояния от 1-й вершины до 6-й.
Рисунок 1
Кружками обозначены вершины, линиями - пути между ними (ребра графа). В кружках обозначены номера вершин, над ребрами обозначена их «цена» - длина пути. Рядом с каждой вершиной красным обозначена метка - длина кратчайшего пути в эту вершину из вершины 1.
Рисунок 2
Первый шаг. Рассмотрим шаг алгоритма Дейкстры для примера. Минимальную метку имеет вершина 1. Ее соседями являются вершины 2, 3 и 6.
Рисунок 3
Первый по очереди соседней вершины 1 - вершина 2, потому что длина пути до нее минимальна. Длина пути в нее через вершину 1 равна кратчайшему расстоянию до вершины 1 длина ребра, идущего из 1 в 2, то есть 0 7 = 7. Это меньше текущей метки вершины 2, поэтому новая метка 2-й вершины равна 7.
Рисунок 4
Аналогичную операцию проделываем с двумя другими соседями 1-й вершины - 3-й и 6-й.
Таблица 2 узел метка статус
1 [0;-] постоянная
2 [7;1] временная
3 [9;1] временная
6 [14;1] временная
Наименьшее расстояние имеет вершина 2, поэтому она принимает статус постоянная.
Рисунок 5
Рисунок 6
Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит. Вычеркнем ее из графа, чтобы отметить, что эта вершина посещена.
Рисунок 7
Второй шаг. Шаг алгоритма повторяется. Снова находим «ближайшую» из не посещенных вершин. Это вершина 2 с меткой 7, которая получила статус постоянная. Рассматриваем вершины, которые можно достичь из вершины 2.
Таблица 3 узелметкастатус
1 [0;-] постоянная
2 [7;1] постоянная
3 [9;1] временная
6 [14;1] временная
4 [22;2] временная
3 [17;2] временная
Рисунок 8
Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 2-ю. Соседями вершины 2 являются 1, 3, 4.
Первый (по порядку) соседней вершины 2 - вершина 1. Но она уже посещена, поэтому с 1-й вершиной ничего не делаем.
Следующий сосед вершины 2 - вершины 4 и 3. Если идти в нее через 2-ю, то длина такого пути будет = кратчайшее расстояние до 2 расстояние между вершинами 2 и 4 = 7 15 = 22. Поскольку 22<?, устанавливаем метку вершины 4 равной 22.
Рисунок 9
Еще один сосед вершины 2 - вершина 3. Если идти в нее через 2, то длина такого пути будет = 7 10 = 17. Но текущая метка третьей вершины равна 9<17, поэтому метка не меняется. И получается таблица.
Таблица 4 узелметкастатус
1 [0;-] постоянная
2 [7;1] постоянная
3 [9;1] временная
6 [14;1] временная
4 [22;2] временная
Наименьшее расстояние имеет вершина 3, поэтому она принимает статус постоянная.
Рисунок 10
Все соседи вершины 2 просмотрены, замораживаем расстояние до нее и помечаем ее как посещенную.
Третий шаг. Повторяем шаг алгоритма, выбрав вершину 3.
Таблица 5 узелметкастатус
1 [0;-] постоянная
2 [7;1] постоянная
3 [9;1] постоянная
6 [14;1] временная
4 [22;2] временная
4 [20;3] временная
6 [11;3] временная
Дальнейшие шаги. Повторяем шаг алгоритма для оставшихся вершин (Это будут по порядку 6, 4 и 5).
Вершина 4 имеет две метки, оставляем меньшую [20;3]. Вершина 6 имеет две метки, оставляем меньшую [11;3].
Получаем таблицу: Таблица 6 узелметкастатус
1 [0;-] постоянная
2 [7;1] постоянная
3 [9;1] постоянная
4 [20;3] временная
6 [11;3] временная
Наименьшее расстояние имеет вершина 6, поэтому она принимает статус постоянная. Но из вершины 6 нет путей до других вершин, поэтому статус постоянная принимает и вершина 4.
Рассматриваем вершины, которые можно достичь из вершины 4.
Таблица 7 узелметкастатус
1 [0;-] постоянная
2 [7;1] постоянная
3 [9;1] постоянная
4 [20;3] постоянная
6 [11;3] постоянная
5 [26;4] постоянная
Завершение выполнения алгоритма. Алгоритм заканчивает работу, когда вычеркнуты все вершины. Результат его работы: кратчайший путь от вершины 1 до 6-й составляет 11.
Поскольку алгоритм Дейкстры всякий раз выбирает для обработки вершины с наименьшей оценкой кратчайшего пути, можно сказать, что он относится к жадным алгоритмам.
Ответ: Путь: 1-3-6, длина = 11
3.3 Входные и выходные данные работы программы
На входе вводится вес ребер в матрице смежности.
На выходе будет отображаться пройденный самый короткий путь и его длина.
3.4 Организация диалога
При запуске программы открывается окно, показанное на рисунке 11.
Рисунок 11. Стартовое окно программы
На данной форме присутствуют: 2 label, 1 button и 1 PICTUREBOX.
Элемент button используется для перехода к следующей форме, показанной на рисунке 12.
Элемент label используется для отображения информации.
Элемент PICTUREBOX используется для изображения картинки на форме.
Рисунок 12.Главная форма программы
На данной форме присутствуют: 16 label, 36 TEXTBOX для ввода пользователем веса ребер. Также на форме размещены 2 PICTUREBOX для отображения картинок на форме.
Элементы label используются для нумерации строк и столбцов, а так же для вывода пути и его длины.
Элемент MENUSTRIP используется для просмотра «О программе», показанной на рисунке 13, а так же для выхода из программы рисунок 14.
Рисунок 13. О программе
На данной форме присутствуют: 4 label, 2 PICTUREBOX для отображения картинок.
Элемент label используется для получения информации
Диалоговое окно
Рисунок 14.Окно выхода из программы
При нажатии на кнопку «Да» выходит из программы.
3.5 Разработка алгоритма
Программа выводит минимальный путь между двумя указанными вершинами в графе и его длину.
При запуске программы пользователем на экран выводится окно приветствия. При нажатии пользователем кнопки «Ок» программа открывает другую форму, где отображается матрица, в которой нужно ввести вес ребер исследуемого графа. Данные, введенные пользователем, отображаются в виде матрицы смежности, в которой не существующие ребра обозначаются 999999.
Совпадающие начальная и конечная вершины обозначены прочерком. Вес ребер должен быть не отрицательным числом.
После нажатия пользователем кнопки «Рассчитать», программа запускает вычислительный процесс и выводит на экран маршрут и его длину.
Результатом программы является вывод на экран вершин, через которые проходит минимальный путь, а также вывод длины маршрута.
Например, 1 - 3 - 6 - это путь, 1 => 3 = 4, 3 => 6 = 2; Длина пути равна 6;
Если пользователю требуется получить информацию о программе, то он нажимает кнопку «О программе».
Программа открывает форму «О программе».
Если пользователю требуется закрыть программу, то он нажимает кнопку выход. Программа закрывается.
3.6 Обоснование выбора средств разработки
При написании программы использовалась среда Microsoft Visual C#. Данная среда позволяет писать приложения на языке C#.
В ходе написания программы все операторы и служебные слова языка С# выделяются другим цветом, чтобы отличать их от переменных, заданных программистом. Среда Microsoft Visual C# содержит встроенный компилятор.
Окно программы разделено на несколько частей. Вверху находится стандартная панель - Standart, с которой можно сохранить исходный текст программы на диск, открыть новый документ, скопировать или вставить текст, отменить последнее действие, или найти текст. Слева находятся панели Object TREEVIEW и Object Inspector, на которых показаны объекты, которые используются в данной программе, и их свойства. В центре окна программы расположен текстовый редактор, в котором следует писать программу. Внизу - панель Output, в которой показывается сообщения, если в программе содержатся ошибки - компилятор сообщает вид ошибки и строку, в которой она допущена, достаточно сделать двойной клик левой клавишей мыши на описании ошибки в Output, чтобы переместиться на строку, содержащую ошибки. Программа создана в Windows Form режиме.
В C# входит много полезных особенностей - простота, объектная ориентированность, типовая защищенность, "сборка мусора", поддержка совместимости версий и многое другое. Данные возможности позволяют быстро и легко разрабатывать приложения, особенно COM приложения и Web сервисы. При создании C#, его авторы учитывали достижения многих других языков программирования: C , C, Java, SMALLTALK, Delphi, Visual Basic и т.д. Надо заметить, что по причине того, что C# разрабатывался с чистого листа, у его авторов была возможность оставить в прошлом все неудобные и неприятные особенности (существующие, как правило, для обратной совместимости), любого из предшествующих ему языков. В результате получился действительно простой, удобный и современный язык, по мощности не уступающий С .
Microsoft.NET - это новая технология, ориентированная на разработку обычных (автономных) приложений и приложений для Интернета. В рамках Microsoft.NET первоначально были доступны всего несколько языков программирования: - Microsoft C#;
- Managed C ;
- Microsoft Visual Basic.NET;
- Microsoft Visual J#.NET;
- JSCRIPT.NET.
Сейчас число таких языков исчисляется десятками. Но основным языком считается язык C# (по-русски читается «Си-Шарп»), разработанный специально для Microsoft.NET. Именно на C# доступны все возможности новой технологии от Microsoft.
Достоинства и недостатки технологии Microsoft.NET: Относительно недавно появившаяся технология Microsoft.NET имеет много достоинств по сравнению с более ранними технологиями. Но ничего не дается даром, новая технология имеет и ряд недостатков. Рассмотрим и то, и другое немного подробнее.
Достоинства: 1. Единые средства API для разработки программ на разных языках.
2. Простота стыковки разно языковых модулей.
3. Многие тысячи готовых к употреблению классов, реализующие различные алгоритмы, сокращают сроки разработки новых программ и повышают надежность этих программ.
4. Установка программ под.NET не требует программ-инсталляторов, делается простое копирование программы в нужную папку. Как следствие, при установке не вносятся ни какие записи в реестр Windows, поэтому после удаления таких программ в реестре не остается «мусор».
Недостатки: 1. Заметно снижается скорость работы программ. По моим наблюдениям, процентов на 40-50 даже для чисто счетных алгоритмов. Это немало. Но с учетом постоянного роста производительности новых образцов вычислительной техники это не смертельно. Хотя на старенькой технике такие программы могут очень медленно работать.
2. Требуется больше оперативной памяти. Программы под.NET обычно невелики, самые простые имеют размер в несколько килобайт. Но при запуске таких программ запускаются и средства Microsoft.NET Framework, а это «весит» порядка 20 Мбайт в зависимости от версии Framework.
3. На компьютере должна быть установлена среда выполнения программ Microsoft.NET Framework. В операционных системах Windows Vista и Windows 7 эта среда имеется по умолчанию, но в предшествующих операционных системах Framework необходимо устанавливать самим. Кроме того, возможно, потребуется обновить операционную систему Windows. Для Windows 2000 нужен четвертый сервис-пак, для Windows XP - второй. А о линейке Windows 95/98 нужно забыть.
3.7 Тестирование программы
После запуска программы и введения пользователем весов ребер, программа выводит результат: вершины, через которые проходит минимальный путь, а также вывод длины маршрута.
Рисунок 15
Результат работы программы совпадает с результатом решенной задачи теста, значит программа работоспособна.
3.8 Инструкция пользователю
1) Данная программа предназначена для нахождения кратчайшего пути в графе. Эта программа находит наикратчайший путь от начальной до конечной вершины.
2) Системные программные средства, используемые программой, должны быть представлены локализованной версией операционной системы Windows xp, vista, 7 или Windows 8.
Программа должна быть установлена в каталог C:\Program Files. Для установки данной программы достаточно установить exe файл.
В состав используемых технических средств должны входить: - Современный процессор частотой 1.6МГЦ и выше
- ОЗУ более 1 Гбайт
- 2 ГБ видеопамяти и выше
- Наличие свободного места на жестком диске более 100 Мбайт.
Программа не предназначена для работы под управлением ОС Windows 2000 и Windows 98, так как это очень древние системы.
3) Дистрибутив программы находится на диске. Для установки программы на ПК требуется открыть диск, выбрать ярлык, который называется «Setup» и открыть его. Далее выбираем язык и нажимаем кнопку «Ок», потом откроется окно «Мастер установки» нажимаем далее, откроется окно, где можно выбрать место, куда можно установить программу путем нажатием кнопки «Обзор». После того как выбрали место для установки программы, нажимаем кнопку далее. Следующим шагом будет окно, где можно поставить галочку для создания ярлыка на рабочем месте, потом нажимаем кнопку далее. Затем идет завершающее окно, где нужно нажать на кнопку «Установить». После нажатия на кнопку идет процесс установки программы на ПК. После того как установка будет завершена высветится окно, где предложат поставить галочку, что бы сразу запустить программу. Нажимаем кнопку «Готово» и запускаем ярлык на рабочем столе.
4) При запуске программы (с помощь ехе файла или инсталятора), открывается окно приветствия (рис. 11), в этом окне нужно нажать кнопку «Ок». Далее откроется форма на которой присутствует матрица размером 6 Х 6.(рис. 12) Нужно ввести в свободные ячейки положительные числа т.е. ввести вес ребер. В программе не существующие ребра автоматически пронумерованы числом 999999, а в ячейках в которых начальная вершина совпадает с конечной стоит прочерк.
После того как числа введены нужно нажать на кнопку «рассчитать» и в правом верхнем углу окна программы выведется путь и длина пути. Что бы выйти из программы нужно нажать на кнопку выход в левом верхнем углу программы, высветится окно (рис. 14) в котором нужно нажать кнопка «Да» и программа будет закрыта. Для того что бы посмотреть информацию о программе нужно нажать кнопку «О программе».
Вывод
В данном курсовом проекте выполнена постановка задачи нахождения кратчайшего пути. Задача о кратчайшем пути - задача поиска самого короткого пути (цепи) между двумя точками (вершинами) на графе, в которой минимизируется сумма весов ребер, составляющих путь.
Выполнен обзор существующих решений задачи нахождения кратчайшего пути.
- Алгоритм Дейкстры находит кратчайший путь от одной из вершин графа до всех остальных. Алгоритм работает только для графов без ребер отрицательного веса.
- Алгоритм Беллмана - Форда находит кратчайшие пути от одной вершины графа до всех остальных во взвешенном графе. Вес ребер может быть отрицательным.
- Алгоритм Флойда - Уоршелла находит кратчайшие пути между всеми вершинами взвешенного ориентированного графа.
- Алгоритм Ли (волновой алгоритм) основан на методе поиска в ширину. Находит путь между вершинами s и t графа (s не совпадает с t), содержащий минимальное количество промежуточных вершин (ребер).
Рассмотрен вопрос: Динамическое программирование.
Под динамическим программированием понимают некоторый специальный метод оптимизации, суть которого состоит в отыскании оптимального решения путем выполнения вычислений в несколько шагов (этапов).
Вся задача оптимизации разделяется на несколько шагов, причем вес шаги могут быть уникальными или одинаковыми и чередоваться друг с другом. Некоторые задачи оптимизации легко разделяются на шаги естественным способом, а для других - вводится искусственное разделение на шаги.
Выполнено описание метода решения.
Алгоритм Дейкстры позволяет находить в графе кратчайший путь между двумя выделенными вершинами s и t при положительных длинах дуг. Этот алгоритм, предложенный в 1959 г. Дейкстрой, считается одним из наиболее эффективных алгоритмов решения задачи.
Рассмотрено решение задачи теста для написания и отладки программы.
Рассмотрим работу алгоритма на примере графа, показанного на рисунке 1. Пусть требуется найти расстояния от 1-й вершины до 6-й.
Задача рассмотрена и полностью решена.
Выполнены входные и выходные данные работы программы.
На входе вводится вес ребер в матрице смежности.
На выходе будет отображаться пройденный самый короткий путь и его длина.
Выполнена организация диалога;
Сделаны скриншоты форм и рассмотрены свойства элементов.
Выполнена Разработка алгоритма.
Расписан и разобран алгоритм.
Обоснован выбор средств разработки.
В C# входит много полезных особенностей - простота, объектная ориентированность, типовая защищенность, "сборка мусора", поддержка совместимости версий и многое другое. Данные возможности позволяют быстро и легко разрабатывать приложения, особенно COM приложения и Web сервисы.
Выполнено тестирование программы.
Результат работы программы совпадает с результатом решенной задачи теста, значит программа работоспособна.
Составлена инструкция пользователю.
Инструкция рассмотрена и расписана.
В процессе выполнения данного курсового проекта, цель была достигнута, поставленные задачи выполнены.
Была рассмотрена теория графов в общем, изучены понятия путей и маршрутов, рассмотрены такие алгоритмы нахождения кратчайших путей в графе, как волновой алгоритм, алгоритм Дейкстры, алгоритм Белламна-Форда, алгоритм Флойда-Уоршелла, Алгоритм поиска А*, Алгоритм Джонсона. Названные алгоритмы могут найти свое применение в программах для транспортных и коммуникационных сетей, таких как коммутация информационного пакета в Internet, где вершины - роутеры, а ребра это связи между роутерами. Таким образом, чем короче будет путь, тем быстрее пакет достигнет пункта назначения и меньше будут информационные потери.
Были реализованы поставленные задачи. С помощью Microsoft Visual был разработан программный продукт "Алгоритм Дейкстры" для нахождения кратчайших путей графа между всеми его вершинами. Преимуществом данной программы является то, что в ней реализованы принципы динамического программирования, то есть, пользователь сам определяет количество вершин графа, количество ребер (дуг) и их вес.
