Структуры данных - динамическое программирование

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

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

Итак, мы можем сказать, что -

• Проблема должна быть разделена на более мелкие частично совпадающие подзадачи.

• Оптимального решения можно достичь, используя оптимальное решение небольших подзадач.

• В динамических алгоритмах используется мемоизация.

Сравнение

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

В отличие от алгоритмов «разделяй и властвуй», где решения объединяются для достижения общего решения, динамические алгоритмы используют выходные данные меньшей подзадачи, а затем пытаются оптимизировать более крупную подзадачу. Динамические алгоритмы используют мемоизацию для запоминания результатов уже решенных подзадач.

пример

Следующие компьютерные проблемы могут быть решены с использованием подхода динамического программирования -

• Числовой ряд Фибоначчи
• Задача о рюкзаке
• Ханойская башня
• Кратчайший путь для всех пар от Флойда-Уоршалла
• Кратчайший путь от Дейкстры
• Планирование проекта

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