Изменения

<wikitex>''Динамическое программирование — это когда у нас есть задача, которую непонятно как решать, и мы разбиваем ее на меньшие задачи, которые тоже непонятно как решать. (с) А.Кумок'' ==Процесс разработки алгоритмов динамического программирования==В процессе составления алгоритмов динамического программирования, требуется следовать последовательности из четырёх действий:# Описать структуру оптимального решения.# Рекурсивно определить значение оптимального решения.# Вычислить значение оптимального решения с помощью метода восходящего анализа.# Составить оптимальное решение на основе полученной информации. ==Оптимальная подструктура==Задача имеет оптимальную подструктуру, если её оптимальное решение может быть рационально составлено из оптимальных решений её подзадач. [[Файл:FG.png|150px|thumb|Граф подзадач для чисел Фибоначчи]] Наличие оптимальной подструктуры в задаче используется для определения применимости динамического программирования и жадных алгоритмов для решения оной. Например, задача по нахождению кратчайшего пути между некоторыми вершинами графа содержит в себе оптимальное решение подзадач. Многие задачи, решаемые динамическим программированием, можно определить как поиск в заданном ориентированном ациклическом графе [[Кратчайший_путь_в_ациклическом_графе|кратчайшего пути]] от одной вершины к другой.[[Файл:ULP.JPG|thumb|right|150px|Задача о самом длинном невзвешенном пути]]        ===Отсутствие оптимальной подструктуры===Иногда оптимальная подструктура может отсутствовать в задаче. Рассмотрим задачу, в которой имеется ориентированный граф $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, coNP, Σ₁, Π₁|NP-полная задача]], т.е. вряд ли ее можно решить в течение полиномиального времени.     

Важнейшее свойство задач, которое позволяет решать их с помощью динамического программирования , это оптимальность для подзадач. В зависимости от формулировки задачи, будь то динамическое программирование на отрезке, на префиксе, на дереве, термин оптимальности для подзадач может быть различным, но, в целом, он формулируется так:если есть оптимальное решение для некоторой подзадачи, которая возникает в процессе решения задачи, то именно его нужно использовать для решения задачи в целом. ===Принцип оптимальности на префиксе===[[Файл: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)$.  ==== Примеры задач ====:* [[Задача о расстановке знаков в выражении ]]:* [[Задача о порядке перемножения матриц]]:* [[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]:* [[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]:* [[Задача о наибольшей общей подпоследовательности]]:* [[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]:* [[Задача о расстоянии Дамерау-Левенштейна]]:* [[Задача о наибольшей общей подпоследовательности]] === Принцип оптимальности на подмножествах ===Требуется посчитать функцию <math>f(A)</math>, где <math>A</math> {{---}} некоторое множество. Принцип состоит в следующем: пусть для всех множеств <math>B</math> (где <math>B \in A</math>) известен оптимальный ответ для функции <math>f(B)</math>. Тогда будем вычислять <math>f(A)</math> через такие <math>f(B)</math>. В качестве примера рассмотрим задачу о коммивояжере. Обозначим <tex>d[i][mask]</tex> как наименьшую стоимость пути из вершины <tex>i</tex> в вершину <tex>0</tex>, проходящую (не считая вершины <tex>i</tex>) единожды по всем тем и только тем вершинам <tex>j</tex>, для которых <tex>mask_j = 1</tex> (т.е. <tex>d[i][mask]</tex> уже найденный оптимальный путь от <tex>i</tex>-ой вершины до <tex>0</tex>-ой, проходящий через те вершины, где <tex>mask_j=1</tex>. Если <tex>mask_j=0</tex>,то эти вершины еще не посещены). Тогда воспользуемся принципом оптимальности на подмножествах. Стоимостью минимального гамильтонова цикла в исходном графе будет значение <tex> d[0][2^n-1]</tex> — стоимость пути из <tex>0</tex>-й вершины в <tex>0</tex>-ю, при необходимости посетить все вершины. ==== Примеры задач ====* [[Задача коммивояжера, ДП по подмножествам]] ==Мемоизация== 

|definition = «Если есть оптимальное решение '''Мемоизация''' (англ. memoization) — сохранение результатов выполнения функций для некоторой подзадачи, которая возникает в процессе решения задачи, то именно его нужно использовать для решения задачи в целом»предотвращения повторных вычислений.}} ==Оптимальная подструктура==Задачи, решаемые динамическим программированием, можно определить как поиск в заданном ориентированном ациклическом графе [[Кратчайший_путь_в_ациклическом_графе|кратчайшего пути]] от одной вершины к другой.

Задача по нахождению кратчайшего пути до некоторой вершины графа (напримерЭто один из способов оптимизации, $S$_{$iприменяемый для увеличения скорости выполнения компьютерных программ. Перед вызовом функции проверяется, вызывалась ли функция ранее:*если не вызывалась,j$}) содержит в себе оптимальное решение подзадач (кратчайший путь до $S$_{$1функция вызывается и результат её выполнения сохраняется;*если вызывалась,j-1$} или $S$используется сохранённый результат.В качестве примера рассмотрим задачу о нахождении числа Фибоначчи под номером <submath>$2,j-2$n</submath>). Это свойство называется оптимальной подструктурой. Наличие у задачи этого свойства определяет её решаемость динамическим программированием.Без мемоизации:

'''int''' Fibonacci('''int''' n): '''if''' n <=1 '''return''' 1 a =Принцип оптимальности для динамического программирования на префиксе=Fibonacci(n - 1) b =Fibonacci(n - 2)[[Файл:ST.jpg|320px]] '''return''' a + b

Рассмотрим принцип оптимальности для динамического программирования С мемоизацией: '''int''' Fibonacci('''int''' n): '''if''' n <= 1 '''return''' 1 '''if''' fib[n] != -1 <font color=green>// проверка на префиксе.то, не посчитали ли мы это число раньше; посчитанные числа хранятся в массиве fib</font> '''return''' fib[n] fib[n - 1] = Fibonacci(n - 1) fib[n - 2] = Fibonacci(n - 2) '''return''' fib[n - 1] + fib[n - 2]

Задан граф. Требуется дойти от $S$ до $T$. Префикс оптимального пути $S \rightsquigarrow U$ является оптимальным путём $S \rightsquigarrow U$. Есть какой-то префикс, оптимальный путь проходит через $U$. Рассмотрим префикс $\Delta U$ (т.е. путь $S \rightsquigarrow U$ ), пусть он неоптимальный. Это значит, что есть более оптимальный путь. Тогда заменим этот префикс на более оптимальный путь до $U$, а путь $U \rightsquigarrow T$ добавим в конец. Получится более оптимальный путь $S \rightsquigarrow T$. Принцип оптимальности для подзадач выполняется==См.также==* [[Динамическое программирование по профилю]]</wikitex>* [[Динамика по поддеревьям]]

==СсылкиИсточники информации==*Лекция 10Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 15* T. H.11Cormen.2011«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.D0wikipedia.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.9Ewikipedia.org/wiki/%D0.BF.D1.82.%9C%D0.B8.%B5%D0.%BC.%D0.B0.D0.BB.D1.8C.D0.BD.D0.%BE.D1.81.D1.82.D1.8C_.%D0.B4.%B8%D0.BB.D1.8F_.D0.BF.D0.BE.D0.B4.D0.%B7.%D0.%B0.%D1%86%D0.B4.D0.B0.%B8%D1.87|%8F Википедия, Жадный алгоритм{{---}} Мемоизация]*Т. Кормен. «Алгоритмы. Построение и анализ» (2^оеиздание, Глава 15)