Принципы динамического программирования: мемоизация или итерации с подзадачами

Теперь мы воспользуемся алгоритмом задачи взвешенного интервального плани- рования, разработанным в предыдущем разделе, для обобщения базовых принци-

пов динамического программирования. Кроме того, он поможет понять принцип, который играет ключевую роль в оставшейся части главы: итерации с подзадачами вместо рекурсивного вычисления решений.

В предыдущем разделе для построения решения задачи взвешенного интер- вального планирования с полиномиальным временем мы сначала разработали рекурсивный алгоритм с экспоненциальным временем, а затем преобразовали его (посредством мемоизации) в эффективный рекурсивный алгоритм, который обращался к глобальному массиву M за оптимальными решениями подзадач. Но чтобы понять, что здесь на самом деле происходит, желательно сформулировать практически эквивалентную версию алгоритма. Именно эта новая формулировка наиболее явно отражает суть метода динамического программирования и служит общим шаблоном для алгоритмов, которые будут разработаны в последующих разделах.

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

Еще по теме Принципы динамического программирования: мемоизация или итерации с подзадачами:

  1. Второй принцип - принцип аналогии или соответствия Макрокосма (Вселенной) и Микрокосма (человека).
  2. 4.5. Цикличность и итерация
  3. Принцип уважения чести и достоинства личности, недопустимости жестоких, бесчеловечных или унижающих человеческое достоинство видов обращения или наказания
  4. Бог — это личность или принцип?
  5. Первый закон или принцип ментализма
  6. ОКОНЧАТЕЛЬНЫЙ СПИСОК, или Принципы отбора кадров
  7. СТЕРЕОТИП ДИНАМИЧЕСКИЙ
  8. ПСИХОЛОГИЯ ДИНАМИЧЕСКАЯ
  9. ПСИХИКА: ПОНИМАНИЕ ДИНАМИЧЕСКОЕ
  10. АНАЛИЗ КАУЗАЛЬНО-ДИНАМИЧЕСКИЙ
  11. Динамическая медитация
  12. В динамических методах
  13. Иванова Г.С. Основы программирования, 2002
  14. Динамический смысл аспектов