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

Предыдущая часть: “Структуры данных: подход «разделяй и властвуй»”

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

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

Таким образом, мы можем сказать, что:

• задача должна разделяться на более мелкие перекрывающиеся подзадачи;
• оптимальное решение достигается при использовании оптимального решения более мелких подзадач;
• В динамических алгоритмах применяется мемоизация (сохранение результатов).

Сравнение

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

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

Пример

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

• вычисление ряда Фибоначчи;
• задача о ранце;
• ханойская башня;
• поиск кратчайшего пути между всеми парами вершин (алгоритм Флойда-Уоршелла);
• поиск кратчайших путей от одной из вершин графа до всех остальных (алгоритм Дейкстры);
• планирование проектов.

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