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

Краткий обзор задач динамического программирования

Методом динамического программирования решается очень много задач. Вот краткий их перечень:

• 
  Задача о наибольшей общей подпоследовательности: даны две последовательности, требуется найти самую длинную общую подпоследовательность.
  
• 
  Задача поиска наибольшей увеличивающейся подпоследовательности: дана последовательность, требуется найти самую длинную возрастающую подпоследовательность.
  
• 
  Задача о редакционном расстоянии (расстояние Левенштейна): даны две строки, требуется найти минимальное количество стираний, замен и добавлений символов, преобразующих одну строку в другую.
  
• 
  Задача о вычислении чисел Фибоначчи
  
• 
  Задача о порядке перемножения матриц: даны матрицы A_1, …, A_n, требуется минимизировать количество скалярных операций для их перемножения.
  
• 
  Задача о выборе траектории
  
• 
  Задача последовательного принятия решения
  
• 
  Задача об использовании рабочей силы
  
• 
  Задача управления запасами
  
• 
  Задача о ранце: из неограниченного множества предметов со свойствами «стоимость» и «вес» требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную стоимость при ограниченном суммарном весе.
  
• 
  Алгоритм Флойда — Уоршелла: найти кратчайшие расстояния между всеми вершинами взвешенного ориентированного графа.
  
• 
  Алгоритм Беллмана — Форда: найти кратчайший путь во взвешенном графе между двумя заданными вершинами.
  
• 
  Максимальное независимое множество вершин в дереве: дано дерево, найти максимальное множество вершин, никакие две из которых не связаны ребром.
  

4. Реализация на примере задачи о вычислении чисел Фибоначчи

В 1202 г. появилась на свет знаменитая «Книга абака» Леонардо Пизанского (более известного под прозвищем Фибоначчи – сын Боначчи), крупнейшего европейского математика эпохи Средневековья. Этот объемный труд стал настоящей энциклопедией математических знаний того времени и сыграл важную роль в их распространении в странах Западной Европы в следующие несколько столетий. Наиболее известной по сей день остается, конечно же, задача о размножении кроликов, впервые появившаяся в «Liber abaci». Спрашивается, сколько пар кроликов родится за год от одной пары, если кролики начинают приносить потомство со второго месяца и каждая пара через месяц производит на свет еще одну пару? Ее решение привело Фибоначчи к открытию едва ли ни самой знаменитой числовой последовательности 1, 1, 2, 3, 5, 8, 13, ... , названной впоследствии его именем и породившей множество исследований

Числа Фибоначчи являются элементами числовой последовательности, где каждое последующее число образуется посредством суммирования двух предыдущих, например: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…. Как правило, записывается такая последовательность формулой:

Очевидно, что данная задача имеет рекурсивное решение благодаря рекуррентной записи для вычисления элемента:

F(n) = F(n-1) + F(n-2).

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

F(4)=F(3)+F(2) и F(3)=F(2)+F(1)

следует, что для вычисления F(4) значение F(2) приходится вычислять дважды.

Найдем сложность рекурсивного алгоритма вычисления значения n-го числа Фибоначчи.
Пусть T(n) – количество операций, необходимых для вычисления n-го числа Фибоначчи, тогда в соответствии с алгоритмом для T(n) можно записать следующие соотношения

Здесь с₁ и с₂ количество операций для проверки условия и сложения двух чисел.

Будем искать решение в виде T(n) = xⁿ, при n > 1. Это позволяет переписать уравнение в виде

xⁿ = x^n-1 + x^n-2+c₂

Разделим на xⁿ и, переходя к пределу при с учетом того, что , находим