Динамическое программирование (Динамическое планирование)

Динамическое программирование

(Динамическое планирование)

Динамическое программирование

Динамическое программирование было открыто известным американским математиком Ричардом Беллманом (Richard Bellman) в 1950-х годах как общий метод оптимизации многостадийных процессов принятия решения. Динамическое программирование представляет собой метод решения задач с перекрывающимися подзадачами. Вместо того чтобы решать перекрывающиеся подзадачи снова и снова, динамическое программирование предлагает решить каждую из меньших подзадач только один раз, записав при этом результат в таблицу, из которой затем можно будет получить решение исходной задачи.

Динамическое программирование

Пример. Числа Фибоначчи. F(0) = 0, F(1) = 1, …, F(n) = F(n-1) + F(n-2) при n ≥ 2. Если мы попытаемся использовать для вычисления n-го числа Фибоначчи F(n) рекуррентное соотношение непосредственно, т.е. через рекурсию, то придется много раз вычислять одни и те же значения данной функции. Заметим, что задача вычисления F(n) выражается через перекрывающиеся подзадачи меньшего размера – вычисления F(n-1) и F(n-2). Таким образом, мы можем просто заполнить элементы одномерного массива n+1 последовательными значениями F(n), начиная с начальных значений.

Динамическое программирование

Пример. Числа Фибоначчи.

F(5)

F(4)

F(3)

F(3)

F(2)

F(2)

F(1)

F(2)

F(1)

F(1)

F(0)

F(1)

F(0)

F(1)

F(0)

Динамическое программирование

Пример. Числа Фибоначчи. Заметим, что можно обойтись и без запоминания дополнительного массива, ограничившись запоминанием только двух последних элементов последовательности Фибоначчи. Такая ситуация не является чем-то необычным, мы встретимся с ней еще в нескольких примерах. Хотя непосредственное применение динамического программирования можно рассматривать, как частный случай экономии времени за счет памяти, зачастую алгоритмы динамического программирования можно усовершенствовать, избежав использования излишней памяти.

Динамическое программирование

Пример. Биномиальные коэффициенты. Вычисление биномиальных коэффициентов – стандартный пример применения динамического программирования к задаче, не являющейся задачей оптимизации. Биномиальные коэффициенты удовлетворяют следующим рекуррентным соотношениям Сnk = Cn-1k-1 + Cn-1k, Сn0 = Cnn = 1 т.е. решение задачи сводится к решению меньших перекрывающихся задач, подводит нас к решению задачи с использованием метода динамического программирования.

Динамическое программирование

Пример. Биномиальные коэффициенты. Запишем значения биномиальных коэффициентов в таблицу с n+1 строками и k+1 столбцами, пронумерованными, соответственно, от 0 до n и от 0 до k. Мы заполняем таблицу строка за строкой, начиная со строки 0 и заканчивая строкой n. Каждая строка i заполняется слева направо, начиная с 1. На главной диагонали таблицы в строках от 0 по k-ую также находятся 1. Остальные элементы таблицы вычисляются путем сложения элементов предыдущей строки – из того же и предшествующего столбца (треугольник Паскаля).

Динамическое программирование

Пример. Биномиальные коэффициенты. 0 1 2 3 … k 0 1 1 1 1 2 1 2 1 3 1 3 3 1 … … k 1 k ……….. 1 … ……………… n-1 1 n-1 ……… n 1 n ……….

Динамическое программирование

Пример. Биномиальные коэффициенты. Какова временная эффективность данного алгоритма? Очевидно, что базовой операцией алгоритма является сложение, так что обозначим через А(n, k) общее количество сложений. Заметим, что вычисление каждого элемента требуется только одно сложение. Кроме того, поскольку первые k+1 строк таблицы образуют треугольник, а остальные n-k строк – прямоугольник, можно разбить сумму на две части A(n,k) = ½*(k-1)*k + k*(n-k) = Θ(n*k).

Динамическое программирование

Алгоритм Уоршалла. Транзитивным замыканием (transitive closure) ориентированного графа с n вершинами можно определить как булеву матрицу T={tij} размером n*n, в которой элемент на пересечении i-ой строки и j-го столбца равен 1, если существует нетривиальный ориентированный путь (т.е. ориентированный путь положительной длины) из вершины i в вершину j; в противном случае значение tij равно 0. Транзитивное замыкание ориентированного графа можно построить с помощью поиска в глубину или в ширину. Однако это можно сделать более эффективно.

Динамическое программирование

Алгоритм Уоршалла. Алгоритм Уоршалла строит транзитивное замыкание ориентированного графа с n вершинами как последовательность булевых матриц размером n*n: R(0), … , R(k-1), R(k), … , R(n). Элемент на пересечении i-ой строки и j-го столбца матрицы R(k) равен 1 тогда и только тогда, когда существует ориентированный путь из i-ой в j-ую вершину такой, что все промежуточные вершины, если таковые имеются, имеют номер не выше k. Таким образом, R(0) – просто матрица смежности, а R(n) – транзитивное замыкание.