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

Нахождение кратчайшего пути на сегодняшний день является жизненно необходимой задачей и используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности (например, кратчайший путь от дома до университета), в системах автопилота, для нахождения оптимального маршрута при перевозках, коммутации информационного пакета в сетях и т.п. Метод Флойда непосредственно основывается на том факте, что в графе с положительными весами ребер всякий неэлементарный (содержащий более 1 ребра) кратчайший путь состоит из других кратчайших путей. A[i,j] равен расстоянию от вершины i к вершине j, которое имеет конечное значение, если существует ребро (i,j), и равен бесконечности в противном случае. Таким образом, алгоритм Флойда делает n итераций, после i-й итерации матрица А будет содержать длины кратчайших путей между любыми двумя парами вершин при условии, что эти пути проходят через вершины от первой до i-й. Теперь на первом шаге известна «стоимость» решения задачи от второго шага до последнего шага и, следовательно, можно указать оптимальное решение на первом шаге (снизить «стоимость» первого шага).В данном курсовом проекте была рассмотрена проблема решения задач методом динамического программирования, нахождения кратчайшего пути. Существует три алгоритма решения такого типа задач: алгоритм Дейкстры, алгорит Флойда, переборные алгоритмы. В качестве языка программирования был выбран С .#include "stdafx.h" #include #include #include #includeВидовые экраны работы программы Рис.

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

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

Наиболее эффективными алгоритмами нахождения кратчайшего пути являются: 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]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 и т.д. шаги, вплоть до первого шага. Таким образом, будут найдены условно-оптимальные решения на каждом шаге. Далее выполняется переход от условно-оптимального решения к безусловно-оптимальному решению на каждом шаге, т.е. выполняются решения о первого шага к последнему, ориентируясь на полученные условно-оптимальные решения. Теперь на первом шаге известна «стоимость» решения задачи от второго шага до последнего шага и, следовательно, можно указать оптимальное решение на первом шаге (снизить «стоимость» первого шага). Далее выполняются аналогично второй, третий и т.д. шаги.

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

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

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

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

Каждой вершине приписывается вес - это вес пути от начальной вершины до данной. Также каждая вершина может быть выделена. Если вершина выделена, то путь от нее до начальной вершины кратчайший, если нет - то временный. Алгоритм считает для каждой вершины маршрут, и, если он оказывается кратчайшим, выделяет вершину. Весом данной вершины становится вес пути. Для всех соседей данной вершины алгоритм также рассчитывает вес, при этом ни при каких условиях не выделяя их. Алгоритм заканчивает свою работу, дойдя до конечной вершины, и весом кратчайшего пути становится вес конечной вершины. Алгоритм Дейкстры: Шаг 1. Всем вершинам, за исключением первой, присваивается вес равный бесконечности, а первой вершине - 0.

Шаг 2. Все вершины не выделены.

Шаг 3. Первая вершина объявляется текущей.

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

Шаг 5. Среди невыделенных вершин ищется вершина с минимальным весом. Если таковая не найдена, то есть вес всех вершин равен бесконечности, то маршрут не существует. Следовательно, выход. Иначе, текущей становится найденная вершина. Она же выделяется.

Шаг 6. Если текущей вершиной оказывается конечная, то путь найден, и его вес есть вес конечной вершины.

Шаг 7. Переход на шаг 4.

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

Шаг 1: исходному узлу присваивается метка [0;-], полагаем i=1.

Шаг 2: вычисляются временные метки [ , i] для всех узлов, которые можно достичь непосредственно из узла 1(i) и которое не имеет постоянных меток.

Рис. 2

Таблица 2

Узел Метка Статус метки

1 [0;-] постоянная

2 [2;1] временная

5 [6;1] временная

6 [8;1] временная

9 [7;1] временная

Среди узлов 2, 5, 6, и 9 наименьшее значение расстояния имеет узел 2, поэтому статус узла меняется на постоянный.

Рис. 3

Таблица 3

Узел Метка Статус метки

1 [0;-] постоянная

2 [2;1] постоянная

5 [6;1] временная

6 [8;1] временная

9 [7;1] временная

3 [8;2] временная

7 [13;2] временная

Среди узлов 3, 5, 6,7 и 9 наименьшее значение расстояния имеет узел 5, поэтому статус узла меняется на постоянный.

Шаг 3: если узел j уже имеет метку j[ k], полученную из другого узла k и если < , тогда метка меняется на новую.

Рис. 4

Просматриваются все узлы, достижимые из узла 5.

Таблица 4

Узел Метка Статус метки

1 [0;-] постоянная

2 [2;1] постоянная

5 [6;1] постоянная

6 [8;1][9;5] временная

9 [7;1] временная

3 [8;2] временная

7 [13;2] временная

10 [11;5] временная

Среди узлов 3, 6,7,10 и 9 наименьшее значение расстояния имеет узел 9, поэтому статус узла меняется на постоянный.

Рис.5

Таблица 5

Узел Метка Статус метки

1 [0;-] постоянная

2 [2;1] постоянная

5 [6;1] постоянная

6 [8;1] временная

9 [7;1] постоянная

3 [8;2] временная

7 [13;2] временная

10 [11;5][11;9] временная

8 [16;9] временная

Среди узлов 3, 6,7,10 и 8 наименьшее значение расстояния имеет узел 6, поэтому статус узла меняется на постоянный.

Рис. 6

Таблица 6

УЗЕЛМЕТКАСТАТУС метки

1 [0;-] постоянная

2 [2;1] постоянная

5 [6;1] постоянная

6 [8;1] постоянная

9 [7;1] постоянная

3 [8;2] временная

7 [13;2] временная

10 [11;5] временная

8 [16;9][15;6] временная

Среди узлов 3,7,10 и 8 наименьшее значение расстояния имеет узел 3, поэтому статус узла меняется на постоянный.

Рис. 7

Таблица 7

Узел Метка Статус метки

1 [0;-] постоянная

2 [2;1] постоянная

5 [6;1] постоянная

6 [8;1] постоянная

9 [7;1] постоянная

3 [8;2] постоянная

7 [13;2] временная

10 [11;5] временная

8 [15;6] временная

4 [11;3] временная

Среди узлов 4,7,10 и 8 наименьшее значение расстояния имеет узел 10, поэтому статус узла меняется на постоянный.

Рис.8

Таблица 8

УЗЕЛМЕТКАСТАТУС метки

1 [0;-] постоянная

2 [2;1] постоянная

5 [6;1] постоянная

6 [8;1] постоянная

9 [7;1] постоянная

3 [8;2] постоянная

7 [13;2] временная

10 [11;5] постоянная

8 [15;6] временная

4 [11;3] временная

Среди узлов 4,7, и 8 наименьшее значение расстояния имеет узел 4, поэтому статус узла меняется на постоянный.

Рис.9

Таблица 9

Узел Метка Статус метки

1 [0;-] постоянная

2 [2;1] постоянная

5 [6;1] постоянная

6 [8;1] постоянная

9 [7;1] постоянная

3 [8;2] постоянная

7 [13;2] временная

10 [11;5] постоянная

8 [15;6] временная

4 [11;3] постоянная

Среди узлов 7, и 8 наименьшее значение расстояния имеет узел 7, поэтому статус узла меняется на постоянный.

Рис.10

Таблица 10

УЗЕЛМЕТКАСТАТУС метки

1 [0;-] постоянная

2 [2;1] постоянная

5 [6;1] постоянная

6 [8;1] постоянная

9 [7;1] постоянная

3 [8;2] постоянная

7 [13;2] постоянная

10 [11;5] постоянная

8 [15;6] временная

4 [11;3] постоянная

Узел 8 меняет свой статус на постоянный.

Шаг 4: если все узлы имеют постоянные метки, процесс вычисления заканчивается, в противном случае выбирается метка с наименьшим значением расстояния среди всех временных меток.

Рис.11

Таблица 11

Узел Метка Статус метки

1 [0;-] постоянная

2 [2;1] постоянная

5 [6;1] постоянная

6 [8;1] постоянная

9 [7;1] постоянная

3 [8;2] постоянная

7 [13;2] постоянная

10 [11;5] постоянная

8 [15;6] постоянная

4 [11;3] постоянная

Так как все узлы имеют статус «постоянная», то процесс вычисления закончен.

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

Расстояние от 1 до 2: 2[2;1]1[0;1]

1->2

L=2 км

Расстояние от 1 до 3: 3[8;2]2[2;1]1[0;1]

1->2->3

L=8 км

Расстояние от 1 до 4: 4[11;3]3[8;2]2[2;1]1[0;1]

1->2->3->4

L=11км

Расстояние от 1 до 5: 5[6;1]1[0;1]

1->5

L=6 км

Расстояние от 1 до 6: 6[8;1]1[0;1]

1->6

L=8 км

Расстояние от 1 до 7: 7[13;2]2[2;1]1[0;1]

1->2->7

L=13 км

Расстояние от 1 до 8: 8[15;6]6[8;1]1[0;1]

1->6->8

L=15 км

Расстояние от 1 до 9: 9[7;1]1[0;1]

1->9

L=7 км

Расстояние от 1 до 10: 10[11;5]5[6;1]1[0;1]

1->5->10

L=11км

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

В качестве входных данных программа получает количество точек графа, список длин путей графа и для расчета пути: начальную и конечную точку.

Выходными данными являются запись пути графа из матрицы инцидентности и длина пути.

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

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

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

Сначала в программу задается конечное число точек в задаче и записывается в память.

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

После ввода данных, выводится матрица инцедентности. Которая указывается в массиве.

После указания начальной точки пути и конечной, начинается выполнения цикла на поиск минимального расстояния от начального до конечного графа. И затем выводит сумму пути.

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

Для разработки программы будет использоваться язык С#.

С# или «си шарп» - это язык программирования, который является объектно-ориентированным и применяется для разработки модулей и компонентов для Windows NET платформы.

На данный момент язык программирования C# набирает очень большой темп, и нет столь простого и многофункционального языка, как Си шарп. В нем собраны все достоинства разных языков. Быстродействие выполнения приближается к языку Assembler.

Язык Си шарп имеет 300 000 библиотек разных функций, которые работают с максимальным быстродействием.

C# относится к семье языков с С-подобным синтаксисом, из них его синтаксис наиболее близок к C и Java. Язык имеет статическую типизацию, поддерживает полиморфизм, перегрузку операторов (в том числе операторов явного и неявного приведения типа), делегаты, атрибуты, события, свойства, обобщенные типы и методы, итераторы, анонимные функции с поддержкой замыканий, LINQ, исключения, комментарии в формате XML.

Переняв многое от своих предшественников - языков C , Java, Delphi, Модула и Smalltalk - С#, опираясь на практику их использования, исключает некоторые модели, зарекомендовавшие себя как проблематичные при разработке программных систем, например, C# не поддерживает множественное наследование классов (в отличие от C ).

C# разрабатывался как язык программирования прикладного уровня для CLR и, как таковой, зависит, прежде всего, от возможностей самой CLR. Это касается, прежде всего, системы типов C#, которая отражает BCL. Присутствие или отсутствие тех или иных выразительных особенностей языка диктуется тем, может ли конкретная языковая особенность быть транслирована в соответствующие конструкции CLR. Так, с развитием CLR от версии 1.1 к 2.0 значительно обогатился и сам C#; подобного взаимодействия следует ожидать и в дальнейшем. (Однако эта закономерность была нарушена с выходом C# 3.0, представляющим собой расширения языка, не опирающиеся на расширения платформы .NET.) CLR предоставляет C#, как и всем другим .NET-ориентированным языкам, многие возможности, которых лишены «классические» языки программирования. Например, сборка мусора не реализована в самом C#, а производится CLR для программ, написанных на C# точно так же, как это делается для программ на VB.NET, J# и др.

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

Программа решения задачи написанная на языке программирования C содержит в себе 3 вида переменных, цикл для строк и столбцов, команды для вывода результатов на экран.

Int - тип переменной, которая может принимать только целые значения.

Типы данных word и char

For - этот цикл действует различным образом в разных частях кода. Изначально инициализируя часть цикла. Программа вычисляет условие. Заданное условием if. Если это значение истинно, программа выполняет тело цикла. Высчитывает и выводит ответ.

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

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

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

Данный программный продукт является способом решения задач линейного программирования симплекс - метода. Программа не предполагает установки и работает при запуске .exe файла. Программа работает в операционной системе Windows, для запуска требуется двойной клик по исполняемому файлу. Откроется окно командной строки, в котором осуществляется диалог с программой. Ввод данных, происходит по средствам клавиатуры.

В данном курсовом проекте была рассмотрена проблема решения задач методом динамического программирования, нахождения кратчайшего пути. Существует три алгоритма решения такого типа задач: алгоритм Дейкстры, алгорит Флойда, переборные алгоритмы.

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

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

Таким образом, поставленные задачи выполнены и цель курсового проекта достигнута.

1. Агальцов В.П., Валдайская И.В. Математические методы в программировании: Учебник. - М.: ИД «ФОРУМ»: ИНФРА-М, 2006. - 224 с.: ил. - (Профессиональное образование).

2. Голицына О.Л., Попов И.И. Основы алгоритмизации и программирования: Учебное пособие. - М.: Форум: Инфра-М, 2004

3. Орлов В.В. Технологии разработки программных продуктов. - СПБ.: Питер, 2003. - 437 с.

4. Партыка Т.Л., Попов И.И. Математические методы: Учебник. - М.: ФОРУМ: ИНФРА-М, 2005. - 464с.: ил. - ( Профессиональное образование)