2014-02-02
590Лекция 7
Как уже отмечалось, в некоторых случаях рекурсивное решение может оказаться очень трудоемким, так как в процессе его выполнения одна и та же задача может решаться несколько раз. Простой анализ примера вычисления дистанции Левенштейна позволяет выявить такие повторные вычисления. Например, функция 
вычислялась в шагах 7, 8, 7, 16 алгоритма.
Если в процессе выполнения рекурсивного алгоритма одна и та же задача решается несколько раз, то говорят, что алгоритм содержит перекрывающиеся подзадачи. Например, задача вычисления функции , рассмотренная выше, является перекрывающейся подзадачей задачи вычисления функции 
Метод решения задачи оптимизации, реализующей рекурсивный алгоритм с перекрывающимися подзадачами, в котором каждая такая подзадача решается один раз, а ее результат сохраняется для последующего применения, называется динамическим программированием.
На рис. 1 приведен пример реализации алгоритма вычисления члена последовательности Фибоначчи методом динамического программирования.
|
|
|
Рис. 1. Функция вычисления члена последовательности Фибоначчи, реализующая алгоритм динамического программирования
Обратите внимание, что новой реализацией функции fib для хранения промежуточных значений используется статический массив. Применение массива позволяете избежать повторных рекурсивных вычислений, которые были в реализации, представленной в пред. лекции.
Заметим, что задачи вычисления факториала и наибольшего общего делителя не имеет смысла решать методом динамического программирования, так как при их рекурсивном решении не образуются перекрывающиеся подзадачи и, следовательно, нет необходимости запоминать промежуточные вычисления.
Следует отметить, что рассматриваемый здесь метод является частью более общей теории динамического программирования, основы которой разработаны Р. Беллманом. Эта теория исследует процесс пошагового решения задач оптимизации, в котором на каждом шаге из множества допустимых решений выбирается одно, оптимизирующее заданную целевую функцию.
