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

<wikitex>

Процесс разработки алгоритмов динамического программирования

В процессе составления алгоритмов динамического программирования, требуется следовать последовательности из четырёх действий:

1. Описать структуру оптимального решения
2. Рекурсивно определить значение оптимального решения
3. Вычислить значение оптимального решения с помощью метода восходящего анализа
4. Составить оптимального решения на основе полученной информации

Оптимальная подструктура

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

Граф подзадач для чисел Фибоначчи

Многие задачи, решаемые динамическим программированием, можно определить как поиск в заданном ориентированном ациклическом графе кратчайшего пути от одной вершины к другой.

Задача о самом длинном невзвешенном пути

Отсутствие оптимальной подструктуры

Иногда оптимальная подструктура может отсутствовать в задаче. Рассмотрим задачу, в которой имеется ориентированный граф $G = (V, E)$ и вершины $u, v \in V$, задачу по определению простого пути от вершины $u$ к вершине $v$, состоящий из максимального количества рёбер.

Рассмотрим путь $q \rightarrow r \rightarrow t$, который является самым длинным простым путем $q \rightsquigarrow t$. Является ли путь $q \rightarrow r$ самым длинным путем $q \rightsquigarrow r$? Нет, поскольку простой путь $q \rightarrow s \rightarrow t \rightarrow r$ длиннее. Является ли путь $r \rightarrow t$ самым длинным путем $r \rightsquigarrow t$? Снова нет, поскольку простой путь $r \rightarrow q \rightarrow s \rightarrow t$ длиннее. Таким образом, в задаче о поиске самого длинного невзвешенного пути не возникает никаких оптимальных подструктур. Для этой задачи до сих пор не найдено ни одного эффективного алгоритма, работающего по принципу динамического программирования. Фактически, это NP-полная задача, т.е. вряд ли ее можно решить в течение полиномиального времени.

Оптимальность для подзадач

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

Принцип оптимальности на префиксе

Рассмотрим некий необратимый процесс производства и представим его в виде ориентированного и ациклического графа. Процесс проходит некий ряд состояний. Началом производства (первым состоянием) обозначим вершину графа $S$, а конец производства (последнее состояние) $T$. Процесс требует оптимизации, т.е. требуется найти оптимальный путь $S \rightsquigarrow T$. Он проходит через вершину графа $U$. Префикс оптимального пути $S \rightsquigarrow U$ является оптимальным путём $S \rightsquigarrow U$. Теперь рассмотрим принцип оптимальности для динамического программирования на префиксе. Итак, имеем некоторый оптимальный путь $S \rightsquigarrow T$, который проходит через $U$. Пусть префикс $ \Delta U$, т.е. путь от $S \rightsquigarrow U$, неоптимален. Тогда заменим неоптимальную часть $S \rightsquigarrow U$ пути $S \rightsquigarrow T$ оптимальной, а путь $U \rightsquigarrow T$ добавим в конец. Получим оптимальный путь $S \rightsquigarrow T$. Принцип оптимальности для подзадач выполняется. Т.е. чтобы получить оптимальный путь из одной вершины графа в другую, префиксы меньших путей должны быть оптимальными.

Примеры задач

• Кратчайший путь в ациклическом графе

Принцип оптимальности на подотрезках

Требуется посчитать функцию $f(1, n)$. Принцип состоит в следующем: пусть на для всех отрезков $i$, $j$ (где [math] u \le i \le j \le v [/math]) известен оптимальный ответ для функции $f(i, j)$. Тогда мы будем вычислять $f(u, v)$ через такие $f(i, j)$. В качестве примера рассмотрим следующую классическую задачу: дана строка длины n, нужно найти максимальный подпалиндром (подпоследовательность максимальной длины, которая является палиндромом). Пусть $d(i, j)$ - ответ на задачу для подстроки, начинающаяся с символа $i$ и заканчивающаяся в символе $j$. Ясно, что $d(i, j) = 0$ для всех $i, j,$ что $i > j$ и $d(i, i) = 1$ для всех $i$. Пусть нам нужно посчитать значение для $d(i, j)$, причем значение $d$ для всех $l, r$, что [math] i \le l \le r \le j [/math] уже посчитаны и они оптимальны. Рассмотрим два случая:

1. [math] s(i) \neq s(j), тогда d(i, j) = max(d(i, j - 1), d(i + 1, j)) [/math]
   
2. [math] s(i) = s(j), тогда d(i, j) = d(i + 1, j - 1) + 2 [/math]
   

Доказательство:

1. Так [math]s(i) \neq s(j)[/math], символы $s(i)$ и $s(j)$ не могут входит в максимальный подпвлиндром одновременно, то есть либо $s(i)$ входят в максимальный подпвлиндром (тогда его длина $d[i, j - 1]$), либо $s(j)$ входи в максимальный подпвлиндром (тогда его длина $d[i + 1, j]$), либо оба не входят в максимальный подпвлиндром (тогда его длина $= d[i, j - 1] = d[i + 1, j]$).
   
2. Данное равенство следует из факта, что выгодно включить в мп символы $s(i)$ и $s(j)$.

Примеры задач

• Задача о расстановке знаков в выражении
• Задача о порядке перемножения матриц
• Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами
• Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза

Принцип оптимальности на подмножествах

• Задача коммивояжера, ДП по подмножествам

Ссылки

• Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 15
• T. H. Cormen. «Introduction to Algorithms» third edition, Chapter 15
• Wikipedia
  • Optimal substructure
  • Greedy algorithm
  • Динамическое программирование

</wikitex>