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

МЕНЮ


Искусственный интеллект
Поиск
Регистрация на сайте
Помощь проекту

ТЕМЫ


Новости ИИРазработка ИИВнедрение ИИРабота разума и сознаниеМодель мозгаРобототехника, БПЛАТрансгуманизмОбработка текстаТеория эволюцииДополненная реальностьЖелезоКиберугрозыНаучный мирИТ индустрияРазработка ПОТеория информацииМатематикаЦифровая экономика

Авторизация



RSS


RSS новости


Динамическое программирование — это в основном оптимизация простой рекурсии. Везде, где мы видим рекурсивное решение, которое имеет повторяющиеся вызовы для одних и тех же входов, мы можем оптимизировать его с помощью динамического программирования. Идея состоит в том, чтобы просто сохранить результаты подзадач, чтобы нам не приходилось повторно вычислять их, когда это понадобится позже. Эта простая оптимизация сокращает временные сложности от экспоненциального до полиномиального. Например, если мы напишем простое рекурсивное решение для чисел Фибоначчи, мы получим экспоненциальную временную сложность, а если мы оптимизируем его, сохранив решения подзадач, временная сложность уменьшится до линейной.

Числа Фибоначчи

Числа Фибоначчи — это числа следующей целочисленной последовательности:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

Строго математически, эти числа определяются с помощью рекуррентного соотношения

с начальными значениями

Задача

Для заданного натурального числа n выведите n-ый член последовательности Фибоначчи.

Примеры

Вход  : 2 Выход : 1  Вход  : 9 Выход : 34

Рекурсивный метод

Простой метод, который использует математическое рекурсивное определение.

Рекурсивная реализация на C++

Вывод программы:

34

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

Дерево рекурсии

Метод динамического программирования

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

Реализация динамического программирования на C++

Вывод программы:

34

В этом методе вычислительная сложность будет линейной, в отличие от предыдущего метода, в котором экспоненциальная сложность.


Источник: www.geeksforgeeks.org

Комментарии: