Мемоизация рекурсии
Вообще говоря, до алгоритма с полиномиальным временем не так уж далеко.
Фундаментальный факт, который становится вторым критическим компонентом решения методом динамического программирования, заключается в том, что наш рекурсивный алгоритм Compute-Opt в действительности решает n + 1 разных подзадач: Compute-Opt(0), Compute-Opt(1), …, Compute-Opt(n).
Тот факт, что он выполняется за экспоненциальное время, приведен просто из-за впечатляющей избыточности количества выдач каждого из этих вызовов.
Метод сохранения ранее вычисленных значений называется мемоизацией (memoization). Описанная стратегия будет реализована в более «умной» процедуре M-Compute- Opt.
Процедура использует массив M [0... n]; элемент M [ j] изначально содержит «пустое» значение, но принимает значение Compute-Opt( j) после первого вычисления. Чтобы определить OPT(n), мы вызываем M-Compute-Opt(n).
M-Compute-Opt( j)
Если j = 0
Вернуть 0
Иначе Если M [ j] не пусто Вернуть M [ j]
Иначе
Определить M [ j] = max(vj + M-Compute-Opt(p( j)), M-Compute-Opt( j − 1))
Вернуть M [ j]
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу