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

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

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. Разработка алгоритма.

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

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