Числа Фибоначчи и динамическое программирование
Попросите компьютер найти 40-е число Фибоначчи самым очевидным способом, и он сделает больше 331 миллиона вызовов. Попросите сделать это с таблицей, и ему хватит 39 сложений. Разница — это динамическое программирование, и почти все впервые знакомятся с ним именно на числах Фибоначчи.
Задача
Числа Фибоначчи начинаются с 0, 1, а каждое следующее число — сумма двух предыдущих: 0, 1, 1, 2, 3, 5, 8, 13, 21 и так далее. В виде правила: F(0) = 0, F(1) = 1 и F(n) = F(n − 1) + F(n − 2). Правило рекурсивное, и превратить его прямо в рекурсивную программу легко, но такая программа оказывается очень медленной.
Почему рекурсия повторяется
Чтобы найти F(5), программа запрашивает F(4) и F(3). F(4) запрашивает F(3) и F(2), так что F(3) вычисляется дважды, F(2) — трижды, а F(1) — пять раз. Если нарисовать вызовы деревом, на каждом уровне их становится почти вдвое больше, и всего для F(n) получается 2·F(n + 1) − 1 вызовов. Меньшие задачи перекрываются: одни и те же возвращаются снова и снова. Это верный признак того, что поможет динамическое программирование.
Два способа запоминать
Мемоизация сохраняет рекурсию, но записывает каждый ответ в таблицу, и каждый вызов, прежде чем что-то делать, заглядывает в таблицу. Табуляция заполняет таблицу снизу вверх: сначала F(0) и F(1), затем из них F(2), из F(2) и F(1) — F(3) и так далее до F(n). В обоих случаях каждый член вычисляется один раз, поэтому F(n) стоит n − 1 сложений вместо экспоненциального числа вызовов.
Пример
Снизу вверх для F(7): начинаем с 0 и 1. Затем 0 + 1 = 1, 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8 и 5 + 8 = 13, так что F(7) = 13 после шести сложений. Обычная рекурсия сделала бы для того же ответа 2·F(8) − 1 = 41 вызов. Сверху вниз первые вызовы спускаются до F(1) по левому краю дерева; на обратном пути почти каждый второй вызов находит свой ответ уже в таблице.
Откуда взялось название
Ричард Беллман дал динамическому программированию это название в начале 1950-х годов, когда работал в корпорации RAND. Позже он писал, что выбрал слово «программирование» в старом смысле — «планирование», а «динамическое» — потому что оно звучало внушительно и против него было трудно возразить. Сам метод — решать задачу через ответы для ее меньших версий — сегодня работает в проверке орфографии, планировщиках маршрутов и сравнении ДНК.
Попробуйте сами
Откройте приложение и нажмите Шаг. В режиме снизу вверх оранжевая ячейка заполняется, а две синие ячейки — это члены, которые она складывает. Переключитесь на сверху вниз и посмотрите, как стек вызовов под таблицей растет до n, а потом уменьшается по мере возвращения ответов; подсказка под плиткой Сложения считает, сколько вызовов получили ответ прямо из таблицы.
Часто задаваемые вопросы
Что такое перекрывающиеся подзадачи?
Меньшие задачи, которые нужны решению больше одного раза. И F(n), и F(n − 1) нужно F(n − 2), поэтому обычная рекурсия вычисляет его дважды, а ниже по дереву потери умножаются. Динамическое программирование решает каждую подзадачу один раз и запоминает ответ.
Мемоизация быстрее табуляции?
Они делают одни и те же сложения. Табуляция обычно немного быстрее, потому что не делает вызовов, и ей не может не хватить места в стеке; мемоизация удобна, когда нужны только некоторые меньшие ответы, потому что она вычисляет только их.
Можно ли вычислять числа Фибоначчи еще быстрее?
Да. Метод быстрого удвоения, использующий F(2k) = F(k)·(2·F(k + 1) − F(k)) и F(2k + 1) = F(k)² + F(k + 1)², требует всего около log₂ n шагов. Формула Бине с золотым сечением дает те же числа, но из-за ошибок округления она ненадежна при больших n.
Сколько памяти нужно таблице?
Полная таблица хранит n + 1 чисел, но каждому новому члену нужны только два предыдущих, поэтому цикл, который хранит два числа, делает ту же работу с постоянной памятью. Хранить всю таблицу полезно, когда нужны все члены или когда хочется увидеть, как работает метод.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Попробовать: числа Фибоначчи и динамическое программирование