Динамическое программирование
<wikitex>
Процесс разработки алгоритмов динамического программирования
В процессе составления алгоритмов динамического программирования, требуется следовать последовательности из четырёх действий:
- Описать структуру оптимального решения
- Рекурсивно определить значение оптимального решения
- Вычислить значение оптимального решения с помощью метода восходящего анализа
- Составить оптимального решения на основе полученной информации
Оптимальная подструктура
Задачи, решаемые динамическим программированием, можно определить как поиск в заданном ориентированном ациклическом графе кратчайшего пути от одной вершины к другой.
Задача по нахождению кратчайшего пути между некоторыми вершинами графа содержит в себе оптимальное решение подзадач. Это свойство называется оптимальной подструктурой. Наличие у задачи этого свойства определяет её решаемость динамическим программированием.
Иногда оптимальная структура может отсутствовать в задаче. Рассмотрим задачу, в которой имеется ориентированный граф $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)$, что . Данную задачу можно свести к следующей задаче: пусть дан ориентированный взвешенный ациклический граф без кратных ребер, где вес ребер - любое вещественное число. Требуется найти кратчайший путь от вершины $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)$ посчитаны, тогда:
Ответ будет равен $d(u, v)$.
Примеры задач
Принцип оптимальности на подмножествах
Ссылки
- Лекция 10.11.2011
- Т. Кормен. «Алгоритмы. Построение и анализ» (второе издание, Глава 15)
- T. H. Cormen. «Introduction to Algorithms» (third edition, Chapter 15)
</wikitex>
