Изменения
Нет описания правки
{{Определение
|definition =
'''Динамическое программирование''' (англ. dynamic programming) — это когда у нас есть задача, которую непонятно как решать, и мы разбиваем ее на меньшие задачи, которые тоже непонятно как решать. <br />
A.Кормак
}}
<wikitex>
==Процесс разработки алгоритмов динамического программирования==
==Оптимальная подструктура==
Задача имеет оптимальную подструктуру, если её оптимальное решение может быть рационально составлено из оптимальных решений её подзадач.[[Файл:FG.png|150px|thumb|Граф подзадач для чисел Фибоначчи]] Наличие оптимальной подструктуры в задаче используется для определения применимости динамического программирования и жадных алгоритмов для решения оной. Например, задача по нахождению кратчайшего пути между некоторыми вершинами графа содержит в себе оптимальное решение подзадач.[[Файл:FG.png|150px|thumb|Граф подзадач для чисел Фибоначчи]]
Многие задачи, решаемые динамическим программированием, можно определить как поиск в заданном ориентированном ациклическом графе [[Кратчайший_путь_в_ациклическом_графе|кратчайшего пути]] от одной вершины к другой.
[[Файл:ULP.JPG|thumb|leftright|150px|Задача о самом длинном невзвешенном пути]]
===Отсутствие оптимальной подструктуры===
Рассмотрим путь $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-полная задача, т.е. вряд ли ее можно решить в течение полиномиального времени.
==Принцип оптимальности на префиксе==
[[Файл:ST.jpg|200px|thumb|leftright]]
Рассмотрим некий необратимый процесс производства и представим его в виде ориентированного и ациклического графа. Процесс проходит некий ряд состояний. Началом производства (первым состоянием) обозначим вершину графа $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$ (где <tex> u \le i \le j \le v </tex>) известен оптимальный ответ для функции $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$, таких что <tex> i \le l \le r \le j </tex> уже посчитаны и они оптимальны. Рассмотрим два случая: <br />
# <tex> s(i) \neq s(j), тогда d(i, j) = max(d(i, j - 1), d(i + 1, j)) </tex> <br />
# <tex> s(i) = s(j), тогда d(i, j) = d(i + 1, j - 1) + 2 </tex> <br />
== Принцип оптимальности на подмножествах ==
==СсылкиИсточники информации==
*Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 15
*T. H. Cormen. «Introduction to Algorithms» third edition, Chapter 15
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]
</wikitex>
----
