Решение графов динамическое программирование

Динамическое программирование в решении задач на теорию графов

Граф – это совокупность двух множеств: множества точек (вершин графа) и множества рёбер. Соответственное, можно сказать, что вершины графа соединены тем или иным образом между собой рёбрами графа.

Графы делятся на конечные и бесконечные.

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

Что такое динамическое программирование?

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

Какая связь у динамического программирования и графов?

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

Конкретный пример: необходимо найти количество путей из пункта А в пункт Ж.

Катастрофическое ошибкой школьников является то, что они начинают считать количество путей вручную, не пользуясь “золотым правилом графа”. На самом деле, при сложном построении графа, количество путей может преодолеть и отметку в тысячу путей. Мы же так опрометчивы не будем, а воспользуемся правилом, только решать мы будем не с конца, а с начала. Построим табличку, размеры которой: 2 столбца и N строк, где N – количество вершин графа

Заполняется таблица следующим образом: в левом столбце записываются все вершины, в правом – количество путей до каждой из них. Принято считать, что количество путей до стартовой вершины (в нашем случае до вершины А) равно единице. Далее наша задача заключается в поиске вершин, в которые ведёт дорога только из найденных (по числу путей) вершин. Пока что мы знаем только вершину А, значит ищем вершины, в которые ведет дорога только из вершины А. В нашем случае это вершины: Б, В, Г. Напомню: количество путей, по которым можно добраться из начальной вершины графа до конечной, равно сумме количеств путей, по которым можно добраться до каждой из вершин графа, ведущих в конечный пункт. Значит, в вершины Б, В, Г ведет всего один путь. Запишем это в таблицу. Теперь нам известны вершины А, Б, В, Г, значит ищем неизвестные вершины, в которые ведет дорога только из этих пунктов. В нашем случае это вершина Д. В нее ведут дороги из известных нам Б и В, значит количество путей до пункта Д равно сумме количеств путей до пунктов Б и Г, т.е. до Д мы можем добраться двумя способами. Так же занесем это в таблицу. Следующий пункт – пункт Е. В него ведут дороги из В и Д, значит в пункт Е можно добраться 3 способами (В + Д). Аналогично в пункт Ж, т.к. в него ведет дорога только из известного нам пункта Е.

Конечная таблица должна выглядеть следующим образом:

Наблюдая за тенденциями в сфере ЕГЭ и ОГЭ можно обратить внимание на то, что задание по нашей сегодняшней теме из года в год усложняется и знания этого алгоритма недостаточно для получения балла за это задание, так как вы можете столкнуться с дополнительными условиями.

Условие непроходимости через какую-то вершину

Задача: найти количество путей из пункта А в пункт З, не проходящих через пункт Д.

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

В нашем случае нужно избавиться от рёбер АД, БД, ГД, ДЕ, ДЖ, ДЗ. Тогда граф примет такой вид:

Дело за малым – нужно повторить уже известный нам алгоритм. Строим табличку и заполняем её.

Источник

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₉.

Источник