Изменения

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

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

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

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

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

Важнейшее свойство задач, которое позволяет решать их с помощью динамического программирования, это оптимальность для подзадач. В зависимости от формулировки задачи, будь то динамическое программирование на отрезке, на префиксе, на дереве, термин оптимальности для подзадач может быть различным, но, в целом, формулируется так:{{Определение|definition = «Если если есть оптимальное решение для некоторой подзадачи, которая возникает в процессе решения задачи, то именно его нужно использовать для решения задачи в целом»целом. ===Принцип оптимальности на префиксе===[[Файл:ST.jpg|200px|thumb|right]]Рассмотрим некий необратимый процесс производства и представим его в виде ориентированного и ациклического графа. Процесс проходит некий ряд состояний. Началом производства (первым состоянием) обозначим вершину графа $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$. Принцип оптимальности для подзадач выполняется. Т.е. чтобы получить оптимальный путь из одной вершины графа в другую, префиксы меньших путей должны быть оптимальными. В качестве примера рассмотрим следующую задачу: пусть дан ациклический ориентированный взвешенный граф, требуется найти вес кратчайшего пути из u в v. Воспользуемся принципом оптимальности на префиксе.<br />Пусть <tex>d</tex> — функция, где <tex>d(i)</tex> — вес кратчайшего пути из <tex>u</tex> в <tex>i</tex>. Ясно, что <tex>d(u)</tex> равен <tex>0</tex>. Пусть <tex>w(i, j)</tex> {{---}} вес ребра из <tex>i</tex> в <tex>j</tex>. Будем обходить граф в порядке [[Использование_обхода_в_глубину_для_топологической_сортировки | топологической сортировки]]. Получаем следующие соотношения: <br />: <tex> d(i) = \min\limits_{\mathop{j:j \rightsquigarrow i}}(d(j) + w(j, i)) </tex> Так как мы обходим граф в порядке [[Использование_обхода_в_глубину_для_топологической_сортировки |топологической сортировки]], то на <tex>i</tex>-ом шаге всем <tex>d(j)</tex> (<tex>j</tex> такие, что существует ребро из <tex>j</tex> в <tex>i</tex>) уже присвоены оптимальные ответы, и, следовательно, <tex>d(i)</tex> также будет присвоен оптимальный ответ.==== Примеры задач ====:* [[Кратчайший путь в ациклическом графе]]:* [[Задача о числе путей в ациклическом графе]]  === Принцип оптимальности на подотрезках===Требуется посчитать функцию $f(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)$.  ==== Примеры задач ====:* [[Задача о расстановке знаков в выражении ]]:* [[Задача о порядке перемножения матриц]]:* [[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]:* [[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]:* [[Задача о наибольшей общей подпоследовательности]]:* [[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]:* [[Задача о расстоянии Дамерау-Левенштейна]]:* [[Задача о наибольшей общей подпоследовательности]]

===Принцип оптимальности на префиксеподмножествах ===[[Файл:STТребуется посчитать функцию <math>f(A)</math>, где <math>A</math> {{---}} некоторое множество.jpg|200px|thumb|left]]Рассмотрим некий необратимый процесс производства, например, производство консервов и представим его Принцип состоит в виде ориентированного и ациклического графа. Предположим, что есть свиноферма и свиньи, которые выращиваются и отправляются на завод, чтобы стать консервами. Началом производства обозначим вершину графа $S$, а конец производства $T$. Процесс требует оптимизации, т.е. требуется найти наиболее оптимальный путь $S \rightsquigarrow T$. Он проходит через вершину графа $U$. Префикс оптимального пути $S \rightsquigarrow U$ является оптимальным путём $S \rightsquigarrow U$. Теперь рассмотрим принцип оптимальности следующем: пусть для динамического программирования на префиксе. Итак, имеем некоторый оптимальный путь $S \rightsquigarrow T$, который проходит через $U$. Пусть префикс $ \Delta U$, т.е. путь от $S \rightsquigarrow U$, не оптимален. Тогда заменим неоптимальную часть $S всех множеств <math>B</math> (где <math>B \rightsquigarrow U$ пути $S \rightsquigarrow T$ оптимальной, а путь $U \rightsquigarrow T$ добавим в конец. Получим более in A</math>) известен оптимальный путь $S \rightsquigarrow T$. Принцип оптимальности ответ для подзадач выполняетсяфункции <math>f(B)</math>. ТТогда будем вычислять <math>f(A)</math> через такие <math>f(B)</math>.е. чтобы получить оптимальный путь из одной вершины графа в другую, префиксы меньших путей должны быть оптимальнымиВ качестве примера рассмотрим задачу о коммивояжере.

{{Определение|definition === Примеры задач ==='''Мемоизация''' (англ. memoization) — сохранение результатов выполнения функций для предотвращения повторных вычислений.}} Это один из способов оптимизации, применяемый для увеличения скорости выполнения компьютерных программ. Перед вызовом функции проверяется, вызывалась ли функция ранее:* [[Кратчайший путь в ациклическом графе]]если не вызывалась, функция вызывается и результат её выполнения сохраняется;*если вызывалась, используется сохранённый результат.В качестве примера рассмотрим задачу о нахождении числа Фибоначчи под номером <math>n</math>. Без мемоизации:

== Принцип оптимальности на подотрезках==Пусть нужно посчитать функцию f '''int''' Fibonacci(i, j'''int''' n). Принцип состоит в том, что мы пересчитываем f(i, j) через такие f(i1, j1), что i : '''if''' n <= i1 <= j1 <1 '''return''' 1 a = j. Для примера рассмотрим следующую задачу: пусть дан ориентированный взвешенный ациклический граф без кратных ребер, где вес ребер <math> \in Z </math>. Требуется найти кратчайший путь от каждой вершины до каждой. Пусть вершины пронумерованы в порядке топологической сортировки и dFibonacci(i, j) n - ответ на задачу. Ясно, что d(i, i1) b = 0 и dFibonacci(i, j) = infinity, если не существует путь от i до j. Пусть нам требуется посчитать путь от вершины i до j, при чем чем для любого k (k = [i..j]), d(i, k) и d(k, jn - 2) посчитаны, тогда: <br />: <tex> d(i, j) = \min\limits_{\mathop{k:i \rightsquigarrow k \rightsquigarrow j}} (d(i, k) '''return''' a + d(k, j)) </tex>b

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

==СсылкиИсточники информации==*Лекция 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 Википедия {{---}} Мемоизация]