Мемоизация рекурсии

Вообще говоря, до алгоритма с полиномиальным временем не так уж далеко. Фундаментальный факт, который становится вторым критическим компонентом решения методом динамического программирования, заключается в том, что наш рекурсивный алгоритм Compute-Opt в действительности решает n + 1 разных подза- дач: Compute-Opt(0), Compute-Opt(1), ..., Compute-Opt(n).
Тот факт, что он выполняется за экспоненциальное время, приведен просто из-за впечатляющей избыточности количества выдач каждого из этих вызовов.

Как устранить всю эту избыточность? Можно сохранить значение Compute-Opt в глобально-доступном месте при первом вычислении и затем просто использовать заранее вычисленное значение вместо всех будущих рекурсивных вызовов. Метод сохранения ранее вычисленных значений называется мемоизацией (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]

Конец Если

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Мемоизация рекурсии:

  1. Л.О. Доліненко, В.О. Доліненко, С.О. Сарновська. Цивільне право України, 2006
  2. ЦИВІЛЬНЕ ПРАВО УКРАЇНИ
  3. ПЕРЕДМОВА
  4. Частина І ПРОГРАМА КУРСУ «ЦИВІЛЬНЕ ПРАВО УКРАЇНИ»
  5. Розділ І. Загальні положення цивільного права
  6. Тема 1. Поняття цивільного права. Предмет та метод, система цивільного права. Функції та принципи цивільного права
  7. Тема 2. Цивільне законодавство України
  8. Тема 3. Поняття, елементи та види цивільних правовідносин
  9. Тема 4. Здійснення цивільних прав і виконання обов’язків
  10. Тема 5. Захист цивільних прав та інтересів
  11. Тема 6. Об’єкти цивільних прав
  12. Тема 7.ФІЗИЧНІ особи як суб’єкти цивільного права
  13. Тема 8. Юридичні особи
  14. Тема 9. Держава як суб’єкт цивільного права. Територіальні громади та Автономна Республіка Крим як суб’єкти цивільного права
  15. Тема 10. Правочини: поняття, види. Умови чинності правочину
  16. Тема 11. Представництво і довіреність
  17. Тема П.Строки. Позовна давність
  18. Нормативний матеріал:
  19. Література