Изменения
Нет описания правки
==Оптимальность для подзадач==
Важнейшее свойство задач, которое позволяет решать их с помощью динамического программирования, это оптимальность для подзадач. В зависимости от формулировки задачи, будь то динамическое программирование на отрезке, на префиксе, на дереве, термин оптимальности для подзадач может быть различным, но, в целом, формулируется так: если есть оптимальное решение для некоторой подзадачи, которая возникает в процессе решения задачи, то именно его нужно использовать для решения задачи в целом.
==Принцип оптимальности на префиксе==
=== Примеры задач ===
:* [[Кратчайший путь в ациклическом графе]]
:* [[Задача о числе путей в ациклическом графе]]
== Принцип оптимальности на подотрезках==
:* [[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]
:* [[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]
:* [[Задача о наибольшей общей подпоследовательности]]
:* [[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]
:* [[Задача о расстоянии Дамерау-Левенштейна]]
:* [[Задача о наибольшей общей подпоследовательности]]
== Принцип оптимальности на подмножествах ==
Требуется посчитать функцию <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>.
=== Примеры задач ===
* [[Задача коммивояжера, ДП по подмножествам]]
==Мемоизация==
{{Определение
|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[]''' Fib=-1 <font color=green>// массив, в котором под номером <math>i</math> хранится число Фибоначчи с номером <math>i</math></font>
'''int''' Fibonacci('''int''' n):
'''if''' n<=1
'''return''' 1
'''if''' Fib[n]!=-1 <font color=green>// проверка на то, не посчитали ли мы это число раньше</font>
'''return''' Fib[n]
Fib[n-1]=Fibonacci(n-1)
Fib[n-2]=Fibonacci(n-2)
'''return''' Fib[n-1]+Fib[n-2]
==Источники информации==
* [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 Википедия {{---}} Мемоизация]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]
