Изменения

<wikitex>''Динамическое программирование — это когда у нас есть задача, которую непонятно как решать, и мы разбиваем ее на меньшие задачи, которые тоже непонятно как решать. (с) А.Кумок'' 

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

Задача имеет оптимальную подструктуру, если её оптимальное решение может быть рационально составлено из оптимальных решений её подзадач. [[Файл:FG.png|150px|thumb|Граф подзадач для чисел Фибоначчи]]ЗадачиНаличие оптимальной подструктуры в задаче используется для определения применимости динамического программирования и жадных алгоритмов для решения оной. Например, задача по нахождению кратчайшего пути между некоторыми вершинами графа содержит в себе оптимальное решение подзадач. Многие задачи, решаемые динамическим программированием, можно определить как поиск в заданном ориентированном ациклическом графе [[Кратчайший_путь_в_ациклическом_графе|кратчайшего пути]] от одной вершины к другой.[[Файл:ULP.JPG|thumb|right|150px|Задача о самом длинном невзвешенном пути]] 

Задача по нахождению кратчайшего пути между некоторыми вершинами графа содержит в себе оптимальное решение подзадач. Это свойство называется      ===Отсутствие оптимальной подструктурой. Наличие у задачи этого свойства определяет её решаемость динамическим программированием.[[Файл:ULP.JPG|thumb|left|150px|Задача о самом длинном невзвешенном пути]]подструктуры===Иногда оптимальная структура подструктура может отсутствовать в задаче.

Таким образом, в задаче о поиске самого длинного невзвешенного пути не возникает никаких оптимальных подструктур. Для этой задачи до сих пор не найдено ни одного эффективного алгоритма, работающего по принципу динамического программирования. Фактически, это [[Классы NP, coNP, Σ₁, Π₁|NP-полная задача]], т.е. вряд ли ее можно решить в течение полиномиального времени.

Важнейшее свойство задач, которое позволяет решать их с помощью динамического программирования, это оптимальность для подзадач. В зависимости от формулировки задачи, будь то динамическое программирование на отрезке, на префиксе, на дереве, термин оптимальности для подзадач может быть различным, но, в целом, формулируется так:{{Определение|definition = «Если если есть оптимальное решение для некоторой подзадачи, которая возникает в процессе решения задачи, то именно его нужно использовать для решения задачи в целом»}}целом.

===Принцип оптимальности на префиксе===[[Файл: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$. Принцип оптимальности для подзадач выполняется. Т.е. чтобы получить оптимальный путь из одной вершины графа в другую, префиксы меньших путей должны быть оптимальными.

Так как мы обходим граф в порядке [[Использование_обхода_в_глубину_для_топологической_сортировки |топологической сортировки]], то на <tex>i</tex>-ом шаге всем <tex>d(j)</tex> (<tex>j</tex> такие, что существует ребро из <tex>j</tex> в <tex>i</tex>) уже присвоены оптимальные ответы, и, следовательно, <tex>d(i)</tex> также будет присвоен оптимальный ответ.==== Примеры задач ====

Ответ будет равен === Принцип оптимальности на подотрезках===Требуется посчитать функцию $df(1, n)$. Принцип состоит в следующем: пусть для всех отрезков $i$, $j$ (где <tex> u \leqslant i \leqslant j \leqslant 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 \leqslant l \leqslant r \leqslant j </tex> уже посчитаны и они оптимальны. Рассмотрим два случая: <br /># <tex> s(i) \neq s(j) </tex>, тогда <tex> d(i, j) = \max(d(i, j - 1), d(i + 1, j)) </tex> <br /># <tex> s(i) = s(j) </tex>, тогда <tex> d(i, j) = d(i + 1, j - 1) + 2 </tex> <br />Доказательство:<br /># Так <tex>s(i) \neq s(j)</tex>, символы $s(i)$ и $s(j)$ не могут входить в максимальный подпалиндром одновременно, то есть либо $s(i)$ входят в максимальный подпалиндром(тогда его длина $d[i, j - 1]$), либо $s(j)$ входит в максимальный подпалиндром (тогда его длина $d[i + 1, j]$), либо оба не входят в максимальный подпалиндром (тогда его длина $= d[i, j - 1] = d[i + 1, j]$). <br /># Данное равенство следует из факта, что выгодно включить в максимальный подпалиндром символы $s(i)$ и $s(j)$.

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

== Принцип оптимальности на подмножествах См.также==:* [[Задача коммивояжера, ДП Динамическое программирование по подмножествампрофилю]]* [[Динамика по поддеревьям]]

==СсылкиИсточники информации==*Лекция 10.11.2011*Т. Кормен. «Алгоритмы. Построение и анализ» (второе издание, Глава 15)*T. H. Cormen. «Introduction to Algorithms» (third edition, Chapter 15)* [http://en.wikipedia.org/wiki/Optimal_substructure Wikipedia {{---}} Optimal substructure ]* [http://en.wikipedia.org/wiki/Greedy_algorithm Wikipedia {{---}} Greedy algorithm]* [https://en.wikipedia.org/wiki/Dynamic_programming Wikipedia {{---}} Dynamic programming]* [https://en.wikipedia.org/wiki/Memoization Wikipedia {{---}} Memoization]* [https://ru.wikipedia.org/wiki/%D0%96%D0%B0%D0%B4%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC Википедия {{---}} Жадный алгоритм]* [http://ru.wikipedia.org/wiki/%C4%E8%ED%E0%EC%E8%F7%E5%F1%EA%EE%E5_%EF%F0%EE%E3%F0%E0%EC%EC%E8%F0%EE%E2%E0%ED%E8%E5 Википедия {{---}} Динамическое программирование]* [https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D0%BC%D0%BE%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F Википедия {{---}} Мемоизация]