Динамическое программирование

Выводы

Динамическое программирование действительно оказалось очень мощным методом. Его применение существенно облегчает решение многих сложных задач, которые нельзя решить другими методами. Укажем два признака, характерных для задач, решаемых методами динамического программирования.

• 
  Задача обладает свойством оптимальности для подзадач, т. е. оптимальное решение задачи содержит оптимальные решения ее подзадач.
  
• 
  Задача имеет перекрывающиеся подзадачи, т. е. при рекурсивном решении мы многократно выходим на одни и те же подзадачи.
  

При этом, наши исследования показали, что решение перекрывающихся подзадач значительно эффективнее именно динамическим программирование, а не вычислением рекурсии, хоть для написания первой программы понадобилось больше строк кода.

Список литературы

1. 
   Р. Беллман «Динамическое программирование». Изд-во иностранной литературы, 1690.
   
2. 
   Р. Беллман, С. Дрейфус «Прикладные задачи динамического программирования». М., Наука. Главная редакция Физико-математической литературы, 1965.
   
3. 
   С М. Окулов, О. А. Пестов «Динамическое программирование». Москва БИНОМ. Лаборатория знаний 2012.
   
4. 
   Вентцель Е. С. Исследование операций. М., «Советское радио», 1972.
   
5. 
   Х. Абельсон, Д. Д. Сассман «Структура и интерпретация компьютерных программ», Добросвет, 2006.