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