Изменения
Нет описания правки
<wikitex>
''Динамическое программирование — это когда у нас есть задача, которую непонятно как решать, и мы разбиваем ее на меньшие задачи, которые тоже непонятно как решать. (с) А.Кумок''
==Процесс разработки алгоритмов динамического программирования==
В процессе составления алгоритмов динамического программирования, требуется следовать последовательности из четырёх действий:
Важнейшее свойство задач, которое позволяет решать их с помощью динамического программирования, это оптимальность для подзадач. В зависимости от формулировки задачи, будь то динамическое программирование на отрезке, на префиксе, на дереве, термин оптимальности для подзадач может быть различным, но, в целом, формулируется так: если есть оптимальное решение для некоторой подзадачи, которая возникает в процессе решения задачи, то именно его нужно использовать для решения задачи в целом.
===Принцип оптимальности на префиксе===
[[Файл: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$. Принцип оптимальности для подзадач выполняется. Т.е. чтобы получить оптимальный путь из одной вершины графа в другую, префиксы меньших путей должны быть оптимальными.
Так как мы обходим граф в порядке [[Использование_обхода_в_глубину_для_топологической_сортировки |топологической сортировки]], то на <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 \le leqslant i \le leqslant j \le 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 \le leqslant l \le leqslant r \le leqslant 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 />
Доказательство:<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>-ю, при необходимости посетить все вершины.
* [[Задача коммивояжера, ДП по подмножествам]]
'''int''' Fibonacci('''int''' n):
'''if''' n<=1
'''return''' 1
a=Fibonacci(n-1) b=Fibonacci(n-2) '''return''' a+b
С мемоизацией:
'''int''' Fibonacci('''int''' n):
'''if''' n<=1
'''return''' 1
'''if''' Fibfib[n]!=-1 <font color=green>// проверка на то, не посчитали ли мы это число раньше; посчитанные числа хранятся в массиве fib</font> '''return''' Fibfib[n] Fibfib[n-1]=Fibonacci(n-1) Fibfib[n-2]=Fibonacci(n-2) '''return''' Fibfib[n-1]+Fibfib[n-2]
==См.также==
* [[<math>\mathrm{NP}</math>-полнота задач о гамильтоновом цикле и пути в графах]] ==Источники информации==*Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 15*T. H. Cormen. «Introduction to Algorithms» third edition, Chapter 15
==Ссылкии источники информации==* Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 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]
