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

Попробуем воспользоваться динамическим программированием для решения зада- чи поиска кратчайшего пути из 5 в t при наличии отрицательных стоимостей ребер, но без отрицательных циклов. Также можно опробовать идею, которая работала в прошлом: подзадача i может искать кратчайший путь с использованием только первых i узлов.
Эта идея не работает немедленно, но ее можно заставить работать ценой некоторых усилий. А здесь мы рассмотрим более простое и эффективное ре- шение — алгоритм Беллмана-Форда. Разработку динамического программирования как общей алгоритмической методологии часто приписывают работе Беллмана, опубликованной в 1950-х годах; а алгоритм нахождения кратчайшего пути Белл- мана-Форда стал одним из ее первых практических применений.

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

Рис. 6.22. Путь с минимальной стоимостью P из v в t, использующий не более i ребер


(6.22) Если граф G не содержит отрицательных циклов, то существует кратчай- ший путь из 5 в t, который является простым (то есть не содержит повторяющихся узлов), а следовательно, содержит не более n-1 ребер.

Доказательство. Так как каждый цикл имеет неотрицательную стоимость, в кратчайшем пути P из 5 в t с наименьшим числом ребер не повторяется никакая вершина v. Если бы в P повторялась вершина v, то мы могли бы удалить часть P между последовательными посещениями v, что привело бы к построению пути с не большей стоимостью и меньшим количеством ребер.

Воспользуемся OPT(i, v) для обозначения минимальной стоимости пути v-t с использованием не более i ребер. Согласно (6.22), исходная задача заключается в вычислении OPT(n - 1, 5). (Также алгоритм можно спроектировать так, чтобы подзадачи соответствовали минимальной стоимости пути 5-v, использующего не более i ребер. Такая форма образует более естественную параллель с алгоритмом Дейкстры, но она не столь естественна в контексте протоколов маршрутизации, о которых речь пойдет позднее.)

Теперь нужно найти простой способ выражения OPT(i, v) с использованием мень- ших подзадач. Как вы увидите, в наиболее естественном решении задействовано много разных параметров; это еще один пример принципа «многовариантного выбора», представленного в алгоритме сегментированной задачи наименьших квадратов.

Зафиксируем оптимальный путь P, представляющий OPT(i, v) на рис. 6.22.

♦ Если путь P содержит не более i - 1 ребер, то OPT(i, v) = OPT(/ - 1, v).

♦ Если путь P содержит i ребер и первым является ребро (v, w), то OPT(i, v) = = cvw + OPT(i - 1, w).

Так мы приходим к следующей рекурсивной формуле.

(6.23) Если i > 0, то

ОРТ (/, v) = miп(ОРТ(/ - 1, v), miп (OPT(; - 1, w) + сj).

Используя это рекуррентное соотношение, получаем следующий алгоритм ди- намического программирования для вычисления значения OPT(n - 1, 5).

Shortest-Path{G, s, t)

n = количество узлов в G Массив M[0... n - 1, V]

Определить M[0, t] = 0 и M[0, v] = ∞ для всех остальных v е V

For i = 1............. n - 1

For v e v в произвольном порядке

Вычислить M[i, v] с использованием рекуррентного отношения (6.23)

End For End For

Вернуть M[n - 1,5]

Правильность метода доказывается индукцией напрямую из (6.23). Время выполнения можно ограничить следующим образом: таблица M состоит из n2 эле- ментов; на вычисление каждого элемента может потребоваться время O(n), так как нам придется рассмотреть максимум n узлов w V. ■

(6.24) Метод кратчайшего пути правильно вычисляет минимальную стои- мость пути 5-t в графе, не содержащем отрицательных циклов, и выполняется за время O(n3).

Для таблицы M, coдержащей оптимальные значения подзадач, кратчайший путь, содержащий не более i ребер, может быть получен за время O(in) посредством обратного отслеживания по меньшим подзадачам.

В качестве примера рассмотрим граф на рис. 6.23, а, в котором требуется найти кратчайший путь от каждого узла до t. В таблице на рис. 6.23, b представлен мас- сив M, элементы которого соответствуют значениям M [i, v] из алгоритма. Одна строка таблицы соответствует кратчайшему пути из конкретного узла в t, так как количество ребер в пути может увеличиться. Например, кратчайший путь из узла d в t обновляется четыре раза: из d-t в d-a-t, d-a-b-e-t и, наконец, d-a-b-e-c-t.

а



b

Рис. 6.23. Для направленного графа в (a) алгоритм кратчайшего пути строит таблицу динамического программирования (b)

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Решение методом динамического программирования:

  1. В динамических методах
  2. Метод решения проблем«2»
  3. § 2. МЕТОДОЛОГИЧЕСКИЕ ОРИЕНТАЦИИ В ВЫБОРЕ МЕТОДОВ ПРАКТИЧЕСКИХ РЕШЕНИЙ
  4. СТЕРЕОТИП ДИНАМИЧЕСКИЙ
  5. Иванова Г.С. Основы программирования, 2002
  6. ПСИХОЛОГИЯ ДИНАМИЧЕСКАЯ
  7. ПСИХИКА: ПОНИМАНИЕ ДИНАМИЧЕСКОЕ
  8. АНАЛИЗ КАУЗАЛЬНО-ДИНАМИЧЕСКИЙ
  9. § 3. Исправление недостатков решения арбитражного суда. Дополнительное решение
  10. Динамическая медитация
  11. Динамический смысл аспектов
  12. Эстетика программирования
  13. ПРОЦЕСС ПСИХИЧЕСКИЙ: ХАРАКТЕРИСТИКА ДИНАМИЧЕСКАЯ
  14. Основной курс (Программирование)
  15. Г.С.Иванова, Т.Н.Ничушкина, Е.К.Пугачев. Объектно- ориентированное программирование, 2001
  16. О. Л. Голицына, Т. Л. Партыка, И. И. Попов. ЯЗЫКИ ПРОГРАММИРОВАНИЯ, 2008
  17. Часть вторая Родительское программирование