Источник: Nuances of Programming
Предыдущая часть: “Структуры данных: подход «разделяй и властвуй»”
Подход динамического программирования схож с подходом «разделяй и властвуй»: тоже разбивает задачи на как можно более мелкие подзадачи. Отличие в том, что здесь подзадачи решаются не независимо. Результаты этих более мелких подзадач запоминаются и используются для аналогичных или перекрывающихся подзадач.
Динамическое программирование применяется там, где есть задачи, которые можно разделить на похожие подзадачи, а их результаты использовать повторно. Эти алгоритмы в основном применяются для оптимизации. Прежде чем решать текущую подзадачу, динамическим алгоритмом изучаются результаты ранее решенных подзадач. Решения подзадач комбинируются для получения лучшего решения.
Таким образом, мы можем сказать, что:
- задача должна разделяться на более мелкие перекрывающиеся подзадачи;
- оптимальное решение достигается при использовании оптимального решения более мелких подзадач;
- В динамических алгоритмах применяется мемоизация (сохранение результатов).
Сравнение
В отличие от «жадных» алгоритмов, нацеленных на локальную оптимизацию, динамические алгоритмы устремлены к общей оптимизации задачи.
В отличие от алгоритмов с подходом «разделяй и властвуй» (где решения комбинируются для получения общего решения), в динамических алгоритмах используются результаты меньших подзадач, чтобы затем пытаться оптимизировать крупную подзадачу. В динамических алгоритмах применяется мемоизация для запоминания результатов уже решенных подзадач.
Пример
С использованием подхода динамического программирования решаются следующие задачи:
- вычисление ряда Фибоначчи;
- задача о ранце;
- ханойская башня;
- поиск кратчайшего пути между всеми парами вершин (алгоритм Флойда-Уоршелла);
- поиск кратчайших путей от одной из вершин графа до всех остальных (алгоритм Дейкстры);
- планирование проектов.
Динамическое программирование применяется как сверху вниз, так и снизу вверх. И, конечно, обращение к результату предыдущего решения чаще всего обходится дешевле с точки зрения количества циклов центрального процессора, чем повторное вычисление.
Читайте также: