Динамическое программирование

2020-10-24T14:14:26Z

128.69.233.190: исправил мемоизацию Fibonacci. запоминать нужно текущее значение, а не предыдущие

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

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

==Оптимальная подструктура==
Задача имеет оптимальную подструктуру, если её оптимальное решение может быть рационально составлено из оптимальных решений её подзадач. [[Файл: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. Воспользуемся принципом оптимальности на префиксе. 
Пусть <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>. Будем обходить граф в порядке [[Использование_обхода_в_глубину_для_топологической_сортировки | топологической сортировки]]. Получаем следующие соотношения: 
: <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> уже посчитаны и они оптимальны. Рассмотрим два случая: 
# <tex> s(i) \neq s(j) </tex>, тогда <tex> d(i, j) = \max(d(i, j - 1), d(i + 1, j)) </tex> 
# <tex> s(i) = s(j) </tex>, тогда <tex> d(i, j) = d(i + 1, j - 1) + 2 </tex> 
Доказательство: 
# Так <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]$). 
# Данное равенство следует из факта, что выгодно включить в максимальный подпалиндром символы $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) — сохранение результатов выполнения функций для предотвращения повторных вычислений.
}}

Это один из способов оптимизации, применяемый для увеличения скорости выполнения компьютерных программ. Перед вызовом функции проверяется, вызывалась ли функция ранее:
*если не вызывалась, функция вызывается и результат её выполнения сохраняется;
*если вызывалась, используется сохранённый результат.
В качестве примера рассмотрим задачу о нахождении числа Фибоначчи под номером <math>n</math>. Без мемоизации:

'''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''' fib[n] == -1 // проверка на то, не посчитали ли мы это число раньше; посчитанные числа хранятся в массиве fib
fib[n] = Fibonacci(n - 1) + Fibonacci(n - 2)
'''return''' fib[n]

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

==Источники информации==
* Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 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 Википедия {{---}} Мемоизация]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]
</wikitex>

Викиконспекты - Вклад участника [ru]

Динамическое программирование