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

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

Skillfactory.ru

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

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

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

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

Сравнение

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

Skillfactory.ru

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

Пример

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

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

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

Читайте также:

Читайте нас в TelegramVK и Яндекс.Дзен

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