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

<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). Принцип состоит в том, что мы пересчитываем $f(u, v)$ через такие $f(i, j)$, что [math] u \le i \le j \le v [/math]. Данную задачу можно свести к следующей задаче: пусть дан ориентированный взвешенный ациклический граф без кратных ребер, где вес ребер - любое вещественное число. Требуется найти кратчайший путь от вершины $u$ до $v$. Пусть вершины пронумерованы в порядке топологической сортировки $w(i, j)$ - величина ребра от $i$ до $j$(если ребра не существует, то данное значение равно $\infty$) и $d(i, j)$ - ответ на задачу. Ясно, что $d(i, i) = 0$. Путь от вершины $i$ до $j$ пересчитывается следующим образом: пусть для любого $k$ $(k = [i..j])$, $d(i, k)$ и $d(k, j)$ посчитаны, тогда:

[math] d(i, j) = \min(w(i, j), \min\limits_{\mathop{k:i \rightsquigarrow k \rightsquigarrow j}} [d(i, k) + d(k, j)]) [/math]

Ответ будет равен $d(u, v)$.

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

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

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

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

Ссылки

• Лекция 10.11.2011
• Т. Кормен. «Алгоритмы. Построение и анализ» (второе издание, Глава 15)
• T. H. Cormen. «Introduction to Algorithms» (third edition, Chapter 15)

</wikitex>