Решение задач методами динамического программирования, нахождение кратчайшего пути

КОМИТЕТ ОБРАЗОВАНИЯ, НАУКИ И МОЛОДЕЖНОЙ ПОЛИТИКИ НОВГОРОДСКОЙ ОБЛАСТИ

Боровичский техникум строительной индустрии и экономики

Специальность: 230105 «Программное обеспечение вычислительной техники и автоматизированных систем»

 

КУРСОВОЙ ПРОЕКТ

По дисциплине: Математические  методы

Тема: Решение задач методами динамического программирования, нахождение  кратчайшего пути.

КП 02 СД.01 11 00 00

 

Выполнил студент:

Группы П-41

Новикова Д.А.

Руководитель  работы:

Преподаватель

Винокурова Е.В.

 

 

 

Боровичи

2013

 

КОМИТЕТ ОБРАЗОВАНИЯ, НАУКИ И МОЛОДЕЖНОЙ ПОЛИТИКИ НОВГОРОДСКОЙ ОБЛАСТИ

Боровичский техникум строительной индустрии и экономики

 

 

 

 

 

ЗАДАНИЕ

на курсовое проектирование

 

По предмету _______Математические   методы                  ___________

Студенту группы                                    П-41                                             .

                                   Новиковой Дарье Андреевне      

 

Тема: Решение задач методами динамического программирования, нахождение  кратчайшего пути.

                  

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

      Введение

1. Общая часть
1. Постановка задачи
1. Экономическая постановка задачи
2. Математическая постановка задачи
2. Обзор существующих решений
2. Технологическая часть

2.1. Динамическое программирование

3. Специальная часть
1. Описание  метода решения.
2. Решение задачи теста  для написания и отладки программы
3. Анализ полученных результатов
4. Входные и выходные данные работы программы
5. Организация диалога
6. Разработка алгоритма
7. Обоснование выбора средств  разработки
8. Описание программных модулей
9. Тестирование программы
10. Инструкция пользователю

      Заключение

      Приложение  А. Глоссарий понятий

      Приложение  Б. Текст программы

      Приложение  В. Видовые экраны работы программы

      Приложение  Г. Алгоритм решения задачи

 

РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА

 

1. Агальцов В.П., Валдайская И.В. Математические методы в программировании: Учебник. – М.: ИД «ФОРУМ»: ИНФРА-М, 2006. – 224 с.: ил. – (Профессиональное образование).
2. Голицына О.Л., Попов И.И. Основы алгоритмизации и программирования: Учебное пособие. - М.: Форум: Инфра-М, 2004
3. Орлов В.В. Технологии разработки программных продуктов. - СПб.: Питер, 2003. - 437 с.
4. Партыка Т.Л., Попов И.И. Математические методы: Учебник. – М.: ФОРУМ: ИНФРА-М, 2005. – 464с.: ил. – ( Профессиональное образование)

 

 

Дата выдачи «28» ____01_____2013 г.

Срок окончания  «16» ___03_____2013 г.

 

Преподаватель-руководитель курсового

проектирования_______________________

Председатель  цикловой комиссии_______________________

 

 

Содержание

      Введение

1.Общая часть

1.1.Постановка задачи

1.1.1.Экономическая постановка задачи

1.1.2.Математическая постановка задачи

1.2.Обзор существующих решений

2.Технологическая часть

2.1. Динамическое программирование

3.Специальная часть

3.1.Описание  метода решения.

3.2.Решение задачи теста  для написания и отладки программы

3.3.Анализ полученных результатов

3.4.Входные и выходные данные работы программы

3.5.Организация диалога

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

3.7.Обоснование выбора средств  разработки

3.8.Описание программных модулей

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

3.10.Инструкция пользователю

      Заключение

      Приложение  А. Глоссарий понятий

      Приложение  Б. Текст программы

      Приложение  В. Видовые экраны работы программы

      Приложение  Г. Алгоритм решения задачи

     

 
Введение

 

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

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

Наиболее  эффективными алгоритмами нахождения кратчайшего пути являются:

1. алгоритм Дейкстры;
2. алгоритм Флойда;
3. переборные алгоритмы.

Указанные алгоритмы легко выполняются  при малом количестве вершин в  графе. При увеличении их количества задача поиска кратчайшего пути усложняется.

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

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

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

 

1.Общая  часть

1.1.Постановка задачи

1.1.1.Экономическая постановка задачи

 

В данной  задаче нужно будет подключить  по кратчайшему пути все 10 сельских населенных пунктов к телефонной станции. Числа указывают расстояние  в километрах. (рис.1)

 

 

 

Рис.1

 

 

 

 

1.1.2.Математическая постановка  задачи

 

Задан неориентированный граф  G (V,X) , состоящий из 10 вершин V={1, 2, 3, 4, 5, 6, 7, 8, 9, 10} и 14 рёбер (X). Длины рёбер указаны в километрах и приведены ниже в таблице 1:

Таблица 1

Ребро	Длина ребра
X1	2
X2	6
X3	8
X4	7
X5	6
X6	11
X7	3
X8	5
X9	3
X10	7
X11	5
X12	9
X13	4
X14	5

 

Найти кратчайшее расстояние от вершины V1 ко всем остальным вершинам.

1.2.Обзор существующих решений

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

1. алгоритм Флойда;
2. переборные алгоритмы.

Метод Флойда непосредственно основывается на том факте, что в графе с положительными весами ребер всякий неэлементарный (содержащий более 1 ребра) кратчайший путь состоит из других кратчайших путей.

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

В алгоритме Флойда используется матрица A размером nxn, в которой вычисляются длины кратчайших путей. Элемент A[i,j] равен расстоянию от вершины i к вершине j, которое имеет конечное значение, если существует ребро (i,j), и равен бесконечности в противном случае.

Основная  идея алгоритма. Пусть есть три вершины  i, j, k и заданы расстояния между ними. Если выполняется неравенство A[i,k]+A[k,j]<A[i,j], то целесообразно заменить путь i->j путем i->k->j. Такая замена выполняется систематически в процессе выполнения данного алгоритма.

Шаг 0. Определяем начальную матрицу  расстояния A0 и матрицу последовательности вершин S0. Каждый диагональный элемент обеих матриц равен 0, таким образом, показывая, что эти элементы в вычислениях не участвуют. Полагаем k = 1.

Основной  шаг k. Задаем строку k и столбец k как ведущую строку и ведущий столбец. Рассматриваем возможность применения замены описанной выше, ко всем элементам A[i,j] матрицы Ak-1. Если выполняется неравенство, тогда выполняем следующие действия:

1. создаем матрицу Ak путем замены в матрице Ak-1 элемента A[i,j] на сумму A[i,k]+A[k,j] ;
2. создаем матрицу Sk путем замены в матрице Sk-1 элемента S[i,j] на k. Полагаем k = k + 1 и повторяем шаг k.

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

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

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

Лабиринт, состоящий из проходимых и непроходимых клеток, задан матрицей A размером mxn. Элемент матрицы A[i,j]=0, если клетка (i,j) проходима. В противном случае  A[i,j]=∞.

Требуется найти длину кратчайшего пути из клетки (1, 1) в клетку (m, n).Фактически дана матрица смежности (только в ней нули заменены бесконечностями, а единицы – нулями). Лабиринт представляет собой граф.

Вершинами дерева вариантов в данной задаче являются пути, начинающиеся в клетке (1, 1). Ребра – показывают ход конструирования этих путей и соединяют два пути длины k и k+1, где второй путь получается из первого добавлением к пути еще одного хода. 

2.Технологическая  часть

2.1.Динамическое программирование.

Под динамическим программированием понимают некоторый специальный метод оптимизации, суть которого  состоит в отыскании оптимального решения путем выполнения вычислений  в несколько шагов(этапов). Вся задача оптимизации разделяется на несколько шагов, причем все шаги могут быть уникальными или одинаковыми и чередоваться друг с другом. Некоторые задачи оптимизации легко разделяются на шаги естественным способом, а для других- вводится искусственное разделение на шаги.

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

Оптимальное решение задачи в целом  складывается из оптимальных решений  на каждом шаге

 

 

Где - оптимальное решение на i-м шаге.

В этом случае говорят, что целевая  функция L обладает  «аддитивным критерием качества».

Нахождение  кратчайшего пути.

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

Учитывая вышесказанное, выполнить  вычисления в задачах динамического  программирования удобнее от конца к началу. Действительно легко можно планировать последний, m-1. Выполняя вычисления по последнему шагу, надо сделать ряд предположений: как закончился предыдущий, m-1, шаг и для каждого предположения найти условно-оптимальное решение на m-м шаге. Аналогично выполняются m-1, m-2 и т.д. шаги, вплоть до первого шага. Таким образом, будут найдены условно-оптимальные решения на каждом шаге. Далее выполняется переход от условно-оптимального решения к безусловно-оптимальному решению на каждом шаге, т.е. выполняются решения о первого шага к последнему, ориентируясь на полученные условно-оптимальные решения. Теперь на первом шаге известна «стоимость» решения задачи от второго шага до последнего шага и, следовательно, можно указать оптимальное решение на первом шаге  (снизить «стоимость» первого шага). Далее выполняются аналогично второй, третий и т.д. шаги.