Задача динамического программирования граф

1.5. Метод динамического программирования

Предполагается, что граф G =(X, U) не содержит контуров. Такие графы часто используются при решении задач автоматизированного проектирования, а также управления выполнением проектов с использованием методов PERT и CPM. В основе этих методов лежит построение ориентированного бесконтурного графа (сети PERT или CPM), дуги которого соответствуют некоторым элементарным задачам (этапам или операциям), составляющим проект, а их веса указывают на время, необходимое для решения отдельных задач. Кроме того, предполагается, что для любых (x_i, x_j) U и (x_i, x_k) U задача, соответствующая дуге (x_i, x_j) должна быть закончена до начала решения задачи, изображаемой дугой (x_i, x_k). Очевидно, что ориентированный граф, который строится по указанным правилам, всегда является бесконтурным.

Алгоритмы поиска кратчайших путей в бесконтурных орграфах, основанные на методе динамического программирования, используют следующий принцип оптимальности Беллмана: «любой подпуть минимального пути является минимальным путем между соответствующими вершинами» [3].

Алгоритм поиска кратчайших путей [s, x_i] от источника s=x₁ до всех других вершин x_i (), представленный ниже, подобно алгоритмам 1.1 и 1.2 также использует пометки (x_i) вершин графа.

Алгоритм 1.3. (вычисление длин кратчайших путей [s, x_i] методом динамического программирования)

Данные: бесконтурный орграф G=(X, U) с n вершинами, имеющими правильную нумерацию; выделенный источник s = x₁; произвольные веса дуг l(x_i, x_j).

Результаты: длины   (x_i) кратчайших путей [s, x_i] от источника s до вершин x_i ().

Шаг 1 (присвоение начальных значений)

Задать пометки  (x_i)= вершинам  (x_i)X\s и   (x₁)=0 для x₁=s. Присвоить j =1.

Шаг 2 (изменение пометок)

Присвоить j=j+1 и для вершины x_j вычислить окончательное значение пометки:

. (1.4)

где T = Г -1 (x_j) . При T =  пометка вершины x_j не изменяется.

Шаг 3 (проверка условия окончания)

Если j=n, то конец алгоритма. Иначе переход к шагу 2.

При решении задачи поиска кратчайшего пути [s, t] от источника s = x₁ до стока tX\s процесс изменения пометок завершается при достижении вершины t. В этом случае последний шаг имеет вид.

Шаг 3′ (условие окогчания алгоритма 1.3. при поиске пути [s, t])

Если x_j=t, то конец алгоритма. Иначе переход к шагу 2.

Таким образом, для определения пометок  * (x_i) достаточно один раз просмотреть список вершин графа в порядке возрастания их номеров. При этом выражение (1.4) обеспечивает получение корректного результата только при правильной нумерации вершин. В целом вычислительная сложность алгоритма оценивается как O(m) операций (m — число дуг), так как каждая дуга (x_i, x_j)U анализируется на шаге 2 в точности один раз. Построение кратчайших путей может быть выполнено любым из способов, указанных в разделе 1.2.

Использование метода динамического программирования позволяет легко построить еще одну модификацию алгоритма поиска кратчайших путей для бесконтурных орграфов, в которой решается задача вычисления минимальных расстояний (x_i) от каждой вершины x_i X\t до стока t = x_n.

Алгоритм 1.4. (вычисление длин кратчайших путей [s, t] методом динамического программирования)

Данные: бесконтурный орграф G=(X, U) с n вершинами, имеющими правильную нумерацию; выделенный сток t = x_n; произвольные веса дуг l(x_i, x_j).

Результаты: длины   (x₁) кратчайших путей [s, x_i] от вершин x_i () до стока t.

Шаг 1 (присвоение начальных значений)

Задать пометки (x_j)= вершинам x_jX\t и   (x_n)=0 для x_n=t. Присвоить i=n.

Шаг 2 (изменение пометок)

Присвоить i=i-1 и для вершины x_i вычислить окончательное значение пометки:

(1.5)

где S = Г(x_i) . При S = Ø пометка вершины x_i не изменяется.

Шаг 3 (проверка условия окончания)

Если i=n, то конец алгоритма. Иначе переход к шагу 2.

Чтобы использовать алгоритм 1.4 для поиска пути [s, t], где t=x_n и sX\t, необходимо изменить условие окончания следующим образом.

Шаг 3′ (условие окончания алгоритма 1.4 при поиске [s, t]

Если x_i=s, то конец алгоритма. Иначе переход к шагу 2.

Трудоемкость алгоритма 1.4 определяется аналогично и также составляет O (m) операций. Эта же оценка является предельной при поиске пути [s, t] и достигается в случае s = x₁.

Существенное отличие алгоритма 1.4 состоит в обратном порядке просмотра вершин графа при расстановке пометок от стока к источнику. Для некоторой вершины x_i X величина  * (x_i) определяет длину кратчайшего пути [x_i, t], в отличие от пометки  * (x_i), соответствующей длине пути [s, x_i]. Поэтому при построении пути не удается использовать соотношение (1.2), так как значения  * (x_i) предполагают получение последовательности вершин

[s, t] = ( s, x (1) , x (2) , . , x ( k ) , t)

в направлении от источника s к стоку t в соответствии с выражением вида

 * (x_j)=  * (x_i) — l(x_i, x_j), (1.6)

которое должно выполняться для любой дуги (x_i, x_j)[s, t].

Сначала определяется вершина x (1) Г(s), удовлетворяющая условию (1.6), затем x (2) Г(x (1) ) и т.д.

При построении кратчайшего пути также возможно применение двойных пометок вида [ * (x_i), m_i], где m_i — вершина графа, из которой помечена x_iX. Вторая часть пометки обновляется при изменении  * (x_i) по формуле (1.5) и получает значение m_i=x_j. В итоге источник s=x₁ с пометкой [ * (x₁), m₁] указывает вторую вершину x (1) = m₁ пути [s, t], пометка [(x (1) ), m₂] определяет вершину x (2) = m₂ и т.д.

Пример 1.3. Пусть ориентированный граф, в котором отсутствуют контуры, имеет вид, показанный на рис. 1.7. Необходимо определить кратчайший путь [x₁, x₉].

Рис. 1.7. Представление графа для примера 1.3

Результаты работы алгоритма 1.3 показаны в виде вектора пометок  * (x_i), который имеет вид:

Значения  * (x_i), полученные по алгоритму 1.4, представлены вектором

Кратчайший путь [x₁, x₉] может быть построен по любому из этих векторов с помощью соотношения (1.2) или (1.6) соответственно и имеет вид:

В заключение следует отметить важное свойство пометок  * (x_i) и  * (x_i). Для любой вершины x_i, принадлежащей кратчайшему пути [s, t] в бесконтурном орграфе, всегда справедливо соотношение

 * (x_i) +  * (x_i)=L([s, t]), x_i[s, t], (1.7)

где L([s,t]= * (t)= * (s) — длина кратчайшего пути от истока к стоку. Условие (1.7) и требование правильной нумерации вершин позволяют построить кратчайший путь, так как в последовательности [s, t] вершины x_i[s, t] всегда располагаются в порядке возрастания индексов i  n>.

1.30. Обосновать необходимость правильной нумерации вершин графа при поиске кратчайшего пути методом динамического программирования.

1.31. Что показывают пометки (x_i), приписываемые вершинам графа в алгоритме 1.4.

1.32. Составить подпрограмму построения кратчайшего пути на графе по известным значениям пометок  * (x_i).

1.33. Разработать формальную схему алгоритма топологической сортировки вершин бесконтурного ориентированного графа.

1.34. Написать программу построения правильной нумерации вершин графа на основе алгоритма топологической сортировки.

1.35. Модифицировать алгоритм 1.3 для поиска кратчайших путей с использованием пометок вида (x_i), m_i].

1.36. Модифицировать алгоритм 1.4 для поиска кратчайших путей с использованием пометок вида (x_i), m_i].

1.37. Решить задачу поиска кратчайших путей [x_i, x₉], , для графа из примера 1.3 по алгоритму, в котором применяются двойные пометки.

1.38. Разработать процедуру построения кратчайшего пути из источника в сток на основе соотношения (1.7).

1.39. Определить кратчайший путь из вершины x₁ в вершину x₉ для графа, показанного на рис. 1.8.

Ответ: значения  * (x_i) представлены вектором (0, 6, 4, 7, 9, 13, 15, 14, 20).

Рис. 1.8. Представление графа для упражнения 1.39

1.40. Для графа на рис. 1.8 вычислить значения  * (x_i).при условии, что стоком является вершина x₉.

Источник

Занятие 5. Решение задач ДП: Задача поиска кратчайшего пути (о поиске минимального расстояния)

Представим граф, представляющий собой воображаемую карту дорог, вершинами которого являются точки пересечения дорог или перекрестки (A11, A21, A31, A12, A22, A31, A13, A23…), см. рис. 5.1.

Необходимо добраться из дома на работу, сделать это следует за минимальное время или другими словами — с помощью маршрута минимальной длины.

Рис. 5.1. Граф для задачи поиска кратчайшего пути

Итак, наша цель:

1. определить путь минимальной длины;
2. определить минимальное расстояние от дома до работы.

Введем условные дополнения:

Как решить задачу без использования методов ДП?

Наивное решение

Наивным решением может быть метод перебора.

Граф имеет структуру — порядок слева направо.

• взять 1-й путь и найти его длину d1
• взять 2-й путь и найти его длину d2
• …
• взять k -й путь и найти его длину dk

После этого определить минимальный путь посредством процедуры argmin (d_i) , i=1. k

Т.е. решить такую задачу можно перебором.

Минус:
Посчитаем количество путей (из каждой вершины) — получим 18 путей.
Это не так мало, задача ведь простая.

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

Такие алгоритмы считаются не эффективными.

Другой вариант:
Можно воспользоваться так называемыми алгоритмами на графах, например, алгоритмом Дейкстра. О них поговорим на другой лекции.

Использование методов динамического программирования

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

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

Рис. 5.2. Количество уровней перекрестков, которые надо пересечь, доехав до работы

Получилось 4 уровня перекрестков от Дома до Работы.

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

Предположим, что мы находимся на последнем уровне перекрестков от Работы.
На последнем уровне перекрестков минимальная длина пути из каждого перекрестка до работы известна (из таблицы) — это 4 и 3.

Зная минимальную длину пути из этого уровня перекрестков до Работы, можно ли найти минимальную дину пути из следующего уровня (A21, A22, A23) до Работы? — да можно. Например, из точки А21 нужно посмотреть всего два варианта: А21 -> A31 и A21 -> A32 . Затем выбрать минимальный из них, воспользовавшись процедурой argmin .

Теперь, зная минимальную длину пути из перекрестков второго уровня до Работы, можно найти минимальную длину пути из перекрестков третьего уровня до Работы.

И так и продолжим, пока не найдем минимальную длину пути от Дома до Работы.

Словесный алгоритм мы разработали. Теперь приступим к решению.

F_Aij — минимальная длина пути из перекрестка Aij до работы.
Запишем формулу. Начнем с последнего уровня перекрестков, двигаясь влево.

F_{3,j (j)=1,2} F_3,1 — минимальная длина пути из перекрестка A₃₁ до Работы = 4
F_3,2 — минимальная длина пути из перекрестка A₃₂ до Работы = 3

F_3,1 = 4
F_3,2 = 3

F_2,2 — это второй уровень, состоящий из перекрестков А₂₁, А₂₂, А₂₃

Рассмотрим перекресток А₂₂, из которого есть два пути:

А₂₂ argmin : 6 F_2,2 = min[A22 -> A31 -> Работа; A22 -> A32 -> Работа] = min[3 + 4; 3 + 3] = 6 (А_3,2)

Рассчитываем следующую ветвь второго уровня:

F_2,1 = min[A21 -> A31 -> Работа; A21 -> A32 -> Работа] = min(3 + 4; 2 + 3) = 5 (А₃₂)

Рассчитываем последнюю оставшуюся ветвь второго уровня:

Рассматриваем третий уровень перекрестков:

F_1,1 (перекресток A₁₁) = min[A11 -> A21 -> F_2,1;A11 -> A22 -> F_2,2;A11 -> A23 -> F_2,3] = min[2 + 5;1 + 6;1 + 5] = 6 (A₂₃) (А₃₁)

F_1,2 (перекресток A₁₂) = min[1 + 5;2 + 6;1 + 5] = 6 (A₂₃) (А₂₁), можно взять любой минмимум из двух

F_1,3 (перекресток A₁₃)= min[2 + 5;3 + 6;2 + 5] = 7 (A₂₃) (А₂₁), можно взять любой минмимум из двух

F3	F2	F1
1	4	5 (A32)	6 (A23)
2	3	6 (A32)	5 (A21)
—	—	5 (A31)	7 (A21)

Осталось найти цель — из Дома:

F_Дом = min[1 -> A11 -> F11; 2 -> A12 -> F12; 3 -> A13 -> F13] = min[1 + 6;2 + 6;3 + 7] = 7 (A₁₁)

Длина минимального пути из Дома до Работы = 7
Восстановим минимальный путь: A11 -> A23 -> A31 — > Работа

Сложность решения: решая задачу с перебором, приходилось умножать ( 3 * 3 * 2 ), а в данной задаче нам необходимо складывать. Т.е. мы получаем вместо экспоненциальной функции эффективное полеомиальное решения.

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

Источник

Читайте также:  Alutech rto 500 программирование