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

Не путать с динамическим языком программирования или динамической проблемой .

Рисунок 1. Поиск кратчайшего пути в графе с использованием оптимальной подструктуры; прямая линия указывает на одно ребро; волнистая линия указывает кратчайший путь между двумя вершинами, которые она соединяет (среди других путей, не показанных, разделяющих одни и те же две вершины); жирная линия — это кратчайший путь от начала до цели.

Динамическое программирование — это одновременно метод математической оптимизации и алгоритмическая парадигма . Метод был разработан Ричардом Беллманом в 1950-х годах и нашел применение во многих областях, от аэрокосмической техники до экономики .

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

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

Обзор

Математическая оптимизация

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

Это делается путем определения последовательности функций ценности V ₁ , V ₂ , ..., V _n, принимающих y в качестве аргумента, представляющего состояние системы в моменты времени i от 1 до n .

Определение V _n ( y ) — это значение, полученное в состоянии y в последний момент времени n .

Значения V _i в более ранние моменты времени i = n −1, n − 2, ..., 2, 1 можно найти, действуя в обратном направлении, используя рекурсивное соотношение, называемое уравнением Беллмана .

Для i = 2, ..., n , V _{i −1} в любом состоянии y вычисляется на основе V _i путем максимизации простой функции (обычно суммы) выигрыша от решения в момент времени i − 1 и функции V _i в новом состоянии системы, если такое решение принято.

Поскольку V _i уже рассчитано для необходимых состояний, описанная выше операция дает V _{i -1} для этих состояний.

Наконец, V ₁ в начальном состоянии системы является значением оптимального решения. Оптимальные значения переменных решения можно восстановить одно за другим, отслеживая уже выполненные вычисления.

Теория управления

В теории управления типичной задачей является поиск допустимого управления. $\mathbf {u} ^{\ast }$ что приводит к тому, что система ${\dot {\mathbf {x} }}(t)=\mathbf {g} \left(\mathbf {x} (t),\mathbf {u} (t),t\right)$ следовать по допустимой траектории $\mathbf {x} ^{\ast }$ на непрерывном временном интервале $t_{0}\leq t\leq t_{1}$ которая минимизирует функцию стоимости

$J=b\left(\mathbf {x} (t_{1}),t_{1}\right)+\int _{t_{0}}^{t_{1}}f\left(\mathbf {x} (t),\mathbf {u} (t),t\right)\mathrm {d} t$

Решением этой проблемы является закон или политика оптимального управления. $\mathbf {u} ^{\ast }=h(\mathbf {x} (t),t)$, что дает оптимальную траекторию $\mathbf {x} ^{\ast }$ и функция себестоимости $J^{\ast }$. Последний подчиняется фундаментальному уравнению динамического программирования:

$-J_{t}^{\ast }=\min _{\mathbf {u} }\left\{f\left(\mathbf {x} (t),\mathbf {u} (t),t\right)+J_{x}^{\ast {\mathsf {T}}}\mathbf {g} \left(\mathbf {x} (t),\mathbf {u} (t),t\right)\right\}$

уравнение в частных производных, известное как уравнение Гамильтона–Якоби–Беллмана , в котором $J_{x}^{\ast }={\frac {\partial J^{\ast }}{\partial \mathbf {x} }}=\left[{\frac {\partial J^{\ast }}{\partial x_{1}}}~~~~{\frac {\partial J^{\ast }}{\partial x_{2}}}~~~~\dots ~~~~{\frac {\partial J^{\ast }}{\partial x_{n}}}\right]^{\mathsf {T}}$ и $J_{t}^{\ast }={\frac {\partial J^{\ast }}{\partial t}}$. Оказывается, что минимизация $\mathbf {u}$ с точки зрения $t$, $\mathbf {x}$, и неизвестная функция $J_{x}^{\ast }$ а затем подставляет результат в уравнение Гамильтона – Якоби – Беллмана, чтобы получить уравнение в частных производных, которое нужно решить с граничным условием $J\left(t_{1}\right)=b\left(\mathbf {x} (t_{1}),t_{1}\right)$. На практике это обычно требует численных методов для некоторой дискретной аппроксимации точного соотношения оптимизации.

Альтернативно, непрерывный процесс может быть аппроксимирован дискретной системой, что приводит к следующему рекуррентному соотношению, аналогичному уравнению Гамильтона – Якоби – Беллмана:

$J_{k}^{\ast }\left(\mathbf {x} _{n-k}\right)=\min _{\mathbf {u} _{n-k}}\left\{{\hat {f}}\left(\mathbf {x} _{n-k},\mathbf {u} _{n-k}\right)+J_{k-1}^{\ast }\left({\hat {\mathbf {g} }}\left(\mathbf {x} _{n-k},\mathbf {u} _{n-k}\right)\right)\right\}$

в $k$-й этап $n$ равноотстоящие дискретные интервалы времени, и где ${\hat {f}}$ и ${\hat {\mathbf {g} }}$ обозначают дискретные аппроксимации $f$ и $\mathbf {g}$. Это функциональное уравнение известно как уравнение Беллмана , которое можно решить для точного решения дискретной аппроксимации уравнения оптимизации.

Пример из экономики: проблема Рэмси об оптимальных сбережениях.

См. Также: модель Рэмси – Касса – Купманса.

В экономике целью обычно является максимизация (а не минимизация) некоторой динамической функции общественного благосостояния . В задаче Рамсея эта функция связывает объемы потребления с уровнями полезности . Грубо говоря, планировщик сталкивается с компромиссом между одновременным потреблением и будущим потреблением (посредством инвестиций в основной капитал , который используется в производстве), известным как межвременной выбор . Будущее потребление дисконтируется по постоянной ставке. $\beta \in (0,1)$. Дискретное приближение к уравнению перехода капитала имеет вид

$k_{t+1}={\hat {g}}\left(k_{t},c_{t}\right)=f(k_{t})-c_{t}$

где $c$ это потребление, $k$ является капиталом, и $f$ — производственная функция, удовлетворяющая условиям Инада . Первоначальный акционерный капитал $k_{0}>0$ предполагается.

Позволять $c_{t}$ быть потреблением в период t и предположим, что потребление приносит полезность $u(c_{t})=\ln(c_{t})$ пока жив потребитель. Предположим, что потребитель нетерпелив и дисконтирует будущую полезность с коэффициентом b каждый период, где $0<b<1$. Позволять $k_{t}$ быть капиталом в период t . Предположим, что первоначальный капитал равен заданной сумме. $k_{0}>0$и предположим, что капитал и потребление этого периода определяют капитал следующего периода как $k_{t+1}=Ak_{t}^{a}-c_{t}$, где A — положительная константа и $0<a<1$. Предположим, что капитал не может быть отрицательным. Тогда задачу принятия решения потребителем можно записать следующим образом:

$\max \sum _{t=0}^{T}b^{t}\ln(c_{t})$ при условии $k_{t+1}=Ak_{t}^{a}-c_{t}\geq 0$ для всех $t=0,1,2,\ldots ,T$

Записанная таким образом задача выглядит сложной, поскольку она требует решения для всех переменных выбора. $c_{0},c_{1},c_{2},\ldots ,c_{T}$. (Столица $k_{0}$ не является переменной выбора — первоначальный капитал потребителя принимается как заданный.)

Подход динамического программирования для решения этой проблемы предполагает разбиение ее на последовательность более мелких решений. Для этого определим последовательность функций стоимости $V_{t}(k)$, для $t=0,1,2,\ldots ,T,T+1$ которые представляют собой стоимость наличия любого размера капитала k в каждый момент времени t . (По предположению) нет никакой пользы от наличия капитала после смерти. $V_{T+1}(k)=0$.

Стоимость любого количества капитала в любой предыдущий момент времени может быть рассчитана методом обратной индукции с использованием уравнения Беллмана . В этой задаче для каждого $t=0,1,2,\ldots ,T$, уравнение Беллмана имеет вид

$V_{t}(k_{t})\,=\,\max \left(\ln(c_{t})+bV_{t+1}(k_{t+1})\right)$ при условии $k_{t+1}=Ak_{t}^{a}-c_{t}\geq 0$

Эта задача намного проще той, которую мы записали ранее, поскольку она включает только две переменные решения: $c_{t}$ и $k_{t+1}$. Интуитивно, вместо того, чтобы выбирать план на всю жизнь при рождении, потребитель может действовать постепенно, шаг за шагом. В момент времени t его текущий капитал $k_{t}$ задано, и ему остается только выбрать ток потребления $c_{t}$ и сохранение $k_{t+1}$.

Чтобы на самом деле решить эту проблему, мы действуем в обратном направлении. Для простоты текущий уровень капитала обозначен как k . $V_{T+1}(k)$ уже известно, поэтому, используя уравнение Беллмана, как только мы сможем вычислить $V_{T}(k)$и так далее, пока не дойдем до $V_{0}(k)$, что представляет собой ценность задачи первоначального решения на протяжении всей жизни. Другими словами, как только мы узнаем $V_{T-j+1}(k)$, мы можем рассчитать $V_{T-j}(k)$, что является максимальным из $\ln(c_{T-j})+bV_{T-j+1}(Ak^{a}-c_{T-j})$, где $c_{T-j}$ является переменной выбора и $Ak^{a}-c_{T-j}\geq 0$.

Возвращаясь назад, можно показать, что функция стоимости во времени $t=T-j$ является

$V_{T-j}(k)\,=\,a\sum _{i=0}^{j}a^{i}b^{i}\ln k+v_{T-j}$

где каждый $v_{T-j}$ является константой и оптимальным количеством, которое можно потреблять за раз $t=T-j$ является

$c_{T-j}(k)\,=\,{\frac {1}{\sum _{i=0}^{j}a^{i}b^{i}}}Ak^{a}$

который можно упростить до

${\begin{aligned}c_{T}(k)&=Ak^{a}\\c_{T-1}(k)&={\frac {Ak^{a}}{1+ab}}\\c_{T-2}(k)&={\frac {Ak^{a}}{1+ab+a^{2}b^{2}}}\\&\dots \\c_{2}(k)&={\frac {Ak^{a}}{1+ab+a^{2}b^{2}+\ldots +a^{T-2}b^{T-2}}}\\c_{1}(k)&={\frac {Ak^{a}}{1+ab+a^{2}b^{2}+\ldots +a^{T-2}b^{T-2}+a^{T-1}b^{T-1}}}\\c_{0}(k)&={\frac {Ak^{a}}{1+ab+a^{2}b^{2}+\ldots +a^{T-2}b^{T-2}+a^{T-1}b^{T-1}+a^{T}b^{T}}}\end{aligned}}$

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

Информатика

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

Оптимальная подструктура означает, что решение данной задачи оптимизации может быть получено путем комбинации оптимальных решений ее подзадач. Такие оптимальные подструктуры обычно описываются с помощью рекурсии . Например, для данного графа G=(V,E) кратчайший путь p от вершины u до вершины v демонстрирует оптимальную подструктуру: возьмите любую промежуточную вершину w на этом кратчайшем пути p . Если p действительно является кратчайшим путем, то его можно разбить на подпути p ₁ от u до w и p ₂ от w до v, так что они, в свою очередь, действительно являются кратчайшими путями между соответствующими вершинами (путем простого аргумент вырезания и вставки, описанный в разделе «Введение в алгоритмы» ). Следовательно, можно легко сформулировать решение для поиска кратчайших путей рекурсивным способом, что и делает алгоритм Беллмана-Форда или алгоритм Флойда-Уоршалла .

Перекрытие подзадач означает, что пространство подзадач должно быть небольшим, то есть любой рекурсивный алгоритм, решающий проблему, должен снова и снова решать одни и те же подзадачи, а не генерировать новые подзадачи. Например, рассмотрим рекурсивную формулировку для генерации последовательности Фибоначчи: F _i = F _{i −1} + F _{i −2} с базовым случаем F ₁ = F ₂ = 1. Тогда F ₄₃ = F ₄₂ + F ₄₁ и F ₄₂ = Ж ₄₁ + Ж ₄₀ . Теперь F ₄₁ решается в рекурсивных поддеревьях как F _43, так и F ₄₂ . Несмотря на то, что общее количество подзадач на самом деле невелико (их всего 43), мы в конечном итоге будем решать одни и те же проблемы снова и снова, если примем такое наивное рекурсивное решение, как это. Динамическое программирование учитывает этот факт и решает каждую подзадачу только один раз.

Рисунок 2. Граф подзадачи для последовательности Фибоначчи. Тот факт, что это не дерево, указывает на перекрывающиеся подзадачи.

Этого можно добиться одним из двух способов:

• Нисходящий подход : это прямое следствие рекурсивной формулировки любой проблемы. Если решение любой проблемы можно сформулировать рекурсивно, используя решение ее подзадач, и если ее подзадачи перекрываются, то можно легко запомнить или сохранить решения подзадач в таблице. Всякий раз, когда мы пытаемся решить новую подзадачу, мы сначала проверяем таблицу, чтобы убедиться, что она уже решена. Если решение записано, мы можем использовать его напрямую, в противном случае решаем подзадачу и добавляем ее решение в таблицу.
• Подход «снизу вверх» : как только мы сформулируем решение проблемы рекурсивно, как в терминах ее подзадач, мы можем попытаться переформулировать проблему восходящим способом: сначала попробуйте решить подзадачи и использовать их решения для построения и прийти к решению более крупных подзадач. Это также обычно делается в табличной форме путем итеративной генерации решений для все более крупных подзадач с использованием решений для небольших подзадач. Например, если мы уже знаем значения F ₄₁ и F ₄₀ , мы можем напрямую вычислить значение F ₄₂ .

Некоторые языки программирования могут автоматически запоминать результат вызова функции с определенным набором аргументов, чтобы ускорить оценку вызова по имени (этот механизм называется вызовом по необходимости ). Некоторые языки делают это возможным (например, Scheme , Common Lisp , Perl или D ). Некоторые языки имеют встроенную функцию автоматического запоминания , например табличный Пролог и J , который поддерживает запоминание с помощью наречия M .. В любом случае это возможно только для ссылочно прозрачной функции. Мемоизация также встречается как легко доступный шаблон проектирования в языках, основанных на переписывании терминов, таких как Wolfram Language .

Биоинформатика

Динамическое программирование широко используется в биоинформатике для таких задач, как выравнивание последовательностей , сворачивание белков , предсказание структуры РНК и связывание белка с ДНК. Первые алгоритмы динамического программирования связывания белка с ДНК были независимо разработаны в 1970-х годах Чарльзом ДеЛизи в США. and Georgii Gurskii and Alexander Zasedatelev in USSR. В последнее время эти алгоритмы стали очень популярны в биоинформатике и вычислительной биологии , особенно в исследованиях позиционирования нуклеосом и связывания факторов транскрипции .

Примеры: компьютерные алгоритмы.

Алгоритм Дейкстры для задачи о кратчайшем пути

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

Фактически, объяснение Дейкстры логики алгоритма а именно

Задача 2. Найти путь минимальной общей длины между двумя заданными узлами. $P$ и $Q$.

Мы используем тот факт, что если $R$ — узел на минимальном пути из $P$ к $Q$, знание последнего предполагает знание минимального пути из $P$ к $R$.

представляет собой перефразирование Беллмана знаменитого принципа оптимальности в контексте задачи о кратчайшем пути .

Последовательность Фибоначчи

Использование динамического программирования при вычислении n- го члена последовательности Фибоначчи значительно повышает его производительность. Вот наивная реализация, основанная непосредственно на математическом определении:

function fib(n)
    if n <= 1 return n
    return fib(n − 1) + fib(n − 2)

Обратите внимание, что если мы вызовем, скажем, fib(5), мы создаем дерево вызовов, которое вызывает функцию с одним и тем же значением много раз:

1. fib(5)
2. fib(4) + fib(3)
3. (fib(3) + fib(2)) + (fib(2) + fib(1))
4. ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
5. (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

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

Теперь предположим, что у нас есть простой карты объект m , который отображает каждое значение fib оно уже вычислено до результата, и мы модифицируем нашу функцию, чтобы использовать его и обновлять. Полученная функция требует только времени O ( n ) вместо экспоненциального времени (но требует пространства O ( n ):

var m := map(0 → 0, 1 → 1)
function fib(n)
    if key n is not in map m 
        m[n] := fib(n − 1) + fib(n − 2)
    return m[n]

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

При восходящем подходе мы вычисляем меньшие значения fib сначала, а затем создайте на их основе более крупные ценности. Этот метод также использует время O( n ), поскольку он содержит цикл, который повторяется n - 1 раз, но занимает только постоянное пространство (O(1)) в отличие от нисходящего подхода, который требует пространства O( n ) для сохраните карту.

function fib(n)
    if n = 0
        return 0
    else
        var previousFib := 0, currentFib := 1
        repeat n − 1 times // loop is skipped if n = 1
            var newFib := previousFib + currentFib
            previousFib := currentFib
            currentFib  := newFib
        return currentFib

В обоих примерах мы вычисляем только fib(2) один раз, а затем использовать его для расчета обоих fib(4) и fib(3), вместо того, чтобы вычислять его каждый раз, когда оценивается любой из них.

Тип сбалансированной матрицы 0–1.

Рассмотрим задачу присвоения значений (нуля или единицы) позициям матрицы размера n × n , причем n четное, так, чтобы каждая строка и каждый столбец содержали ровно n /2 нулей и n /2 единиц. Мы спрашиваем, сколько существует различных заданий для данного $n$. Например, когда n = 4 , пять возможных решений:

${\begin{bmatrix}0&1&0&1\\1&0&1&0\\0&1&0&1\\1&0&1&0\end{bmatrix}}{\text{ and }}{\begin{bmatrix}0&0&1&1\\0&0&1&1\\1&1&0&0\\1&1&0&0\end{bmatrix}}{\text{ and }}{\begin{bmatrix}1&1&0&0\\0&0&1&1\\1&1&0&0\\0&0&1&1\end{bmatrix}}{\text{ and }}{\begin{bmatrix}1&0&0&1\\0&1&1&0\\0&1&1&0\\1&0&0&1\end{bmatrix}}{\text{ and }}{\begin{bmatrix}1&1&0&0\\1&1&0&0\\0&0&1&1\\0&0&1&1\end{bmatrix}}.$

Существует как минимум три возможных подхода: грубая сила , возврат и динамическое программирование.

Перебор состоит из проверки всех присвоений нулей и единиц и подсчета тех, у которых сбалансированы строки и столбцы ( n /2 нулей и n /2 единиц). Как есть $2^{n^{2}}$ возможные задания и ${\tbinom {n}{n/2}}^{n}$ разумные задания, эта стратегия непрактична, за исключением, возможно, до $n=6$.

Возврат для этой задачи состоит в выборе некоторого порядка элементов матрицы и рекурсивном размещении единиц или нулей, при этом проверяя, что в каждой строке и столбце количество элементов, которые не были назначены, а также количество единиц или нулей не менее n / 2 . Хотя этот подход более сложен, чем грубая сила, этот подход будет проверять каждое решение один раз, что делает его непрактичным для n число решений уже равно 116 963 796 250 для n больше шести, поскольку , как мы увидим, = 8.

Динамическое программирование дает возможность подсчитать количество решений, не посещая их все. Представьте себе возврат значений для первой строки: какая информация нам потребуется об остальных строках, чтобы иметь возможность точно подсчитать решения, полученные для каждого значения первой строки? Мы рассматриваем доски размера k × n , где 1 ⩽ k ⩽ n , у которых $k$ строки содержат $n/2$ нули и $n/2$ те. Функция f , к которой мемоизация применяется , отображает векторы из n пар целых чисел в количество допустимых досок (решений). Для каждого столбца существует одна пара, и ее два компонента указывают соответственно количество нулей и единиц, которые еще не помещены в этот столбец. Мы ищем ценность $f((n/2,n/2),(n/2,n/2),\ldots (n/2,n/2))$ ( $n$ аргументы или один вектор $n$ элементы). Процесс создания подзадачи включает в себя перебор каждой из ${\tbinom {n}{n/2}}$ возможные назначения для верхней строки доски и проходя по каждому столбцу, вычитая единицу из соответствующего элемента пары для этого столбца, в зависимости от того, содержит ли назначение для верхней строки ноль или единицу в этой позиции. Если какой-либо из результатов отрицательный, то присвоение недействительно и не вносит вклад в множество решений (рекурсия останавливается). В противном случае у нас есть задание для верхней строки доски k × n , и мы рекурсивно вычисляем количество решений для оставшейся доски ( k − 1) × n , складывая числа решений для каждого допустимого назначения верхней строки и возвращая сумма, которая запоминается. Базовый случай — это тривиальная подзадача, которая возникает для доски размером 1 × n . Количество решений для этой доски равно нулю или одному, в зависимости от того, является ли вектор перестановкой n /2. $(0,1)$ и н /2 $(1,0)$ пары или нет.

Например, на первых двух досках, показанных выше, последовательности векторов будут такими:

((2, 2) (2, 2) (2, 2) (2, 2))       ((2, 2) (2, 2) (2, 2) (2, 2))     k = 4
  0      1      0      1              0      0      1      1

((1, 2) (2, 1) (1, 2) (2, 1))       ((1, 2) (1, 2) (2, 1) (2, 1))     k = 3
  1      0      1      0              0      0      1      1

((1, 1) (1, 1) (1, 1) (1, 1))       ((0, 2) (0, 2) (2, 0) (2, 0))     k = 2
  0      1      0      1              1      1      0      0

((0, 1) (1, 0) (0, 1) (1, 0))       ((0, 1) (0, 1) (1, 0) (1, 0))     k = 1
  1      0      1      0              1      1      0      0

((0, 0) (0, 0) (0, 0) (0, 0))       ((0, 0) (0, 0), (0, 0) (0, 0))

Количество решений (последовательность A058527 в OEIS ) равно

$1,\,2,\,90,\,297200,\,116963796250,\,6736218287430460752,\ldots$

Ссылки на реализацию подхода динамического программирования в MAPLE можно найти среди внешних ссылок .

шахматная доска

Рассмотрим шахматную доску с клетками n × n и функцией стоимости c(i, j) который возвращает стоимость, связанную с квадратом (i,j) ( i быть рядом, j это столбец). Например (на шахматной доске 5×5):

5	6	7	4	7	8
4	7	6	1	1	4
3	3	5	7	8	2
2	–	6	7	0	–
1	–	–	5	–	–
	1	2	3	4	5

Таким образом c(1, 3) = 5

Допустим, есть шашка, которая может начинаться с любой клетки первого ряда (т. е. ряда), и вы хотите знать кратчайший путь (сумму минимальных затрат на каждом посещенном ряду), чтобы добраться до последнего ряда; при условии, что шашка может двигаться только по диагонали влево вперед, по диагонали вправо вперед или прямо вперед. То есть шашка на (1,3) может переехать в (2,2), (2,3) или (2,4).

5
4
3
2		х	х	х
1			тот
	1	2	3	4	5

Эта задача демонстрирует оптимальную подструктуру . То есть решение всей проблемы зависит от решения подзадач. Определим функцию q(i, j) как

q ( ​​i , j ) = минимальная стоимость достижения квадрата ( i , j ).

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

Функция q(i, j) равна минимальной стоимости перехода к любому из трех квадратов ниже него (поскольку это единственные квадраты, которые могут его достичь) плюс c(i, j). Например:

5
4			А
3		Б	С	Д
2
1
	1	2	3	4	5

$q(A)=\min(q(B),q(C),q(D))+c(A)\,$

Теперь давайте определим q(i, j) в несколько более общих терминах:

$q(i,j)={\begin{cases}\infty &j<1{\text{ or }}j>n\\c(i,j)&i=1\\\min(q(i-1,j-1),q(i-1,j),q(i-1,j+1))+c(i,j)&{\text{otherwise.}}\end{cases}}$

Первая строка этого уравнения относится к доске, смоделированной в виде клеток, индексированных по 1 на нижней границе и n на самой высокой границе. Вторая строка определяет, что происходит на первом ранге; предоставление базового варианта. Третья строка, рекурсия, является важной частью. Он представляет собой A,B,C,D термины в примере. Из этого определения мы можем вывести простой рекурсивный код для q(i, j). В следующем псевдокоде n размер доски, c(i, j) - функция стоимости, и min() возвращает минимум из нескольких значений:

function minCost(i, j)
    if j < 1 or j > n
        return infinity
    else if i = 1
        return c(i, j)
    else
        return min( minCost(i-1, j-1), minCost(i-1, j), minCost(i-1, j+1) ) + c(i, j)

Эта функция вычисляет только стоимость пути, а не сам путь. Фактический путь мы обсудим ниже. Это, как и пример с числами Фибоначчи, ужасно медленное, потому что оно также демонстрирует атрибут перекрывающихся подзадач . То есть он снова и снова пересчитывает одни и те же затраты на путь. Однако мы можем вычислить его гораздо быстрее восходящим способом, если будем хранить стоимость пути в двумерном массиве. q[i, j] вместо использования функции. Это позволяет избежать повторных вычислений; все значения, необходимые для массива q[i, j] вычисляются заранее только один раз. Предварительно рассчитанные значения для (i,j) просто просматриваются при необходимости.

Нам также необходимо знать, каков на самом деле кратчайший путь. Для этого воспользуемся другим массивом p[i, j]; массив -предшественник . Этот массив записывает путь к любому квадрату s. Предшественник s моделируется как смещение относительно индекса (в q[i, j]) предварительно вычисленной стоимости пути s. Чтобы восстановить полный путь, мы ищем предшественника s, затем предшественник этого квадрата, затем предшественник этого квадрата и так далее рекурсивно, пока мы не достигнем начального квадрата. Рассмотрим следующий псевдокод:

function computeShortestPathArrays()
    for x from 1 to n
        q[1, x] := c(1, x)
    for y from 1 to n
        q[y, 0]     := infinity
        q[y, n + 1] := infinity
    for y from 2 to n
        for x from 1 to n
            m := min(q[y-1, x-1], q[y-1, x], q[y-1, x+1])
            q[y, x] := m + c(y, x)
            if m = q[y-1, x-1]
                p[y, x] := -1
            else if m = q[y-1, x]
                p[y, x] :=  0
            else
                p[y, x] :=  1

Теперь все остальное — просто найти минимум и распечатать его.

function computeShortestPath()
    computeShortestPathArrays()
    minIndex := 1
    min := q[n, 1]
    for i from 2 to n
        if q[n, i] < min
            minIndex := i
            min := q[n, i]
    printPath(n, minIndex)

function printPath(y, x)
    print(x)
    print("<-")
    if y = 2
        print(x + p[y, x])
    else
        printPath(y-1, x + p[y, x])

Выравнивание последовательности

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

Проблему можно сформулировать естественным образом как рекурсию: последовательность A оптимально редактируется в последовательность B одним из следующих способов:

1. вставка первого символа B и выполнение оптимального выравнивания A и хвоста B
2. удаление первого символа A и оптимальное выравнивание хвоста A и B
3. замену первого символа A первым символом B и выполнение оптимального выравнивания хвостов A и B.

Частичные выравнивания можно свести в таблицу в виде матрицы, где ячейка (i,j) содержит стоимость оптимального выравнивания A[1..i] по B[1..j]. Стоимость в ячейке (i,j) можно рассчитать, сложив стоимость соответствующих операций со стоимостью соседних ячеек и выбрав оптимум.

Существуют разные варианты, см. Алгоритм Смита-Уотермана и алгоритм Нидлмана-Вунша .

Пазл Ханойская башня

Набор моделей Ханойских башен (из 8 дисков)

Анимированное решение головоломки Ханойской башни для T(4,3) .

или Ханойская башня Ханойские — башни это математическая игра или головоломка . Он состоит из трех стержней и нескольких дисков разного размера, которые могут надвигаться на любой стержень. Головоломка начинается с аккуратной стопки дисков в порядке возрастания размера на одном стержне, самый маленький вверху, образуя таким образом коническую форму.

Цель головоломки — переместить всю стопку на другой стержень, соблюдая следующие правила:

• Одновременно можно перемещать только один диск.
• Каждое движение состоит в том, чтобы снять верхний диск с одного из стержней и надвинуть его на другой стержень поверх других дисков, которые уже могут присутствовать на этом стержне.
• Ни один диск не может быть помещен поверх диска меньшего размера.

Решение динамического программирования состоит из решения функционального уравнения

S(n,h,t) = S(n-1,h, not(h,t)); С(1,ч,т) ; S(n-1,not(h,t),t)

где n обозначает количество дисков, которые необходимо переместить, h обозначает исходный стержень, t обозначает целевой стержень, not(h,t) обозначает третий стержень (ни h, ни t), ";" обозначает конкатенацию, а

S(n, h, t) := решение задачи, состоящей из n дисков, которые нужно переместить со стержня h на стержень t.

Для n=1 задача тривиальна, а именно S(1,h,t) = «переместить диск со стержня h на стержень t» (остался только один диск).

Число ходов, необходимое для этого решения, равно 2. ^н − 1. Если цель состоит в максимизации количества ходов (без циклирования), тогда функциональное уравнение динамического программирования немного сложнее и 3 ^н − Требуется 1 ход.

Загадка с падением яиц

Ниже приводится описание примера этой знаменитой головоломки с участием N=2 яиц и здания H=36 этажей:

Предположим, мы хотим знать, с каких этажей 36-этажного здания безопасно ронять яйца, а с каких яйца разобьются при приземлении (используя английскую терминологию США , согласно которой первый этаж находится на уровне земли). Сделаем несколько предположений:

• Яйцо, пережившее падение, можно использовать снова.
• Разбитое яйцо необходимо выбросить.
• Эффект падения одинаков для всех яиц.
• Если яйцо разбилось при падении, оно разобьется и при падении из окна повыше.
• Если яйцо выдержит падение, то оно выдержит и более короткое падение.
• Не исключено, что яйца разбиваются из окон первого этажа, и не исключено, что яйца могут выжить в окнах 36-го этажа.

Если в наличии только одно яйцо и мы хотим быть уверены в получении правильного результата, опыт можно провести только одним способом. Выбросьте яйцо из окна первого этажа; если он выживет, выбросьте его из окна второго этажа. Продолжайте идти вверх, пока он не сломается. В худшем случае для этого метода может потребоваться 36 пометов. Предположим, имеются 2 яйца. Какое наименьшее количество яичного помета гарантированно сработает во всех случаях?

динамического программирования Чтобы вывести функциональное уравнение для этой головоломки, пусть состояние модели динамического программирования будет парой s = (n,k), где

n = количество доступных тестовых яиц, n = 0, 1, 2, 3, ..., N − 1.

k = количество (последовательных) этажей, которые еще предстоит проверить, k = 0, 1, 2, ..., H − 1.

Например, s = (2,6) указывает, что доступны два тестовых яйца и еще предстоит протестировать 6 (последовательных) этажей. Начальное состояние процесса: s = ( N , H ), где N обозначает количество тестовых яиц, доступных в начале эксперимента. Процесс завершается либо когда тестовых яиц больше нет ( n = 0), либо когда k = 0, в зависимости от того, что произойдет раньше. Если завершение происходит в состоянии s = (0, k ) и k > 0, то тест не пройден.

Теперь позвольте

W ( n , k ) = минимальное количество испытаний, необходимое для определения значения критического минимума при наихудшем сценарии, учитывая, что процесс находится в состоянии s = ( n , k ).

Тогда можно показать, что

W ( п , k ) знак равно 1 + min {max ( W ( n - 1, x - 1), W ( n , k - x )): x = 1, 2, ..., k }

причем W ( n ,0) = 0 для всех n > 0 и W (1, k ) = k для всех k . Это уравнение легко решить итеративно, систематически увеличивая значения n и k .

Более быстрое решение DP с использованием другой параметризации

Обратите внимание, что приведенное выше решение принимает $O(nk^{2})$ время с решением DP. Это можно улучшить до $O(nk\log k)$ время бинарным поиском оптимального $x$ в приведенном выше повторении, поскольку $W(n-1,x-1)$ увеличивается в $x$ пока $W(n,k-x)$ уменьшается в $x$, таким образом, локальный минимум $\max(W(n-1,x-1),W(n,k-x))$ является глобальным минимумом. Кроме того, сохраняя оптимальные $x$ для каждой ячейки таблицы DP и исходя из ее значения для предыдущей ячейки, оптимальное $x$ для каждой ячейки можно найти за постоянное время, улучшая ее до $O(nk)$ время. Однако есть еще более быстрое решение, предполагающее другую параметризацию задачи:

Позволять $k$ — общее количество этажей, на которых яйца разбиваются при падении с $k$этаж (пример выше эквивалентен взятию $k=37$).

Позволять $m$ быть минимальным полом, с которого нужно уронить яйцо, чтобы оно разбилось.

Позволять $f(t,n)$ быть максимальным количеством значений $m$ которые различимы с помощью $t$ пытается и $n$ яйца.

Затем $f(t,0)=f(0,n)=1$ для всех $t,n\geq 0$.

Позволять $a$ быть полом, с которого падает первое яйцо в оптимальной стратегии.

Если первое яйцо разбилось, $m$ из $1$ к $a$ и различимы с использованием не более $t-1$ пытается и $n-1$ яйца.

Если первое яйцо не разбилось, $m$ из $a+1$ к $k$ и различимы с помощью $t-1$ пытается и $n$ яйца.

Поэтому, $f(t,n)=f(t-1,n-1)+f(t-1,n)$.

Тогда задача эквивалентна нахождению минимума $x$ такой, что $f(x,n)\geq k$.

Для этого мы могли бы вычислить $\{f(t,i):0\leq i\leq n\}$ в порядке возрастания $t$, что заняло бы $O(nx)$ время.

Таким образом, если отдельно рассмотреть случай $n=1$, алгоритм примет $O(n{\sqrt {k}})$ время.

Но рекуррентное соотношение на самом деле можно решить, дав $f(t,n)=\sum _{i=0}^{n}{\binom {t}{i}}$, который можно вычислить в $O(n)$ время с использованием личности ${\binom {t}{i+1}}={\binom {t}{i}}{\frac {t-i}{i+1}}$ для всех $i\geq 0$.

С $f(t,n)\leq f(t+1,n)$ для всех $t\geq 0$, мы можем выполнить двоичный поиск по $t$ найти $x$, давая $O(n\log k)$ алгоритм.

Умножение цепочки матриц

Основная статья: Умножение матричной цепочки

Умножение цепочки матриц — хорошо известный пример, демонстрирующий полезность динамического программирования. Например, в инженерных приложениях часто приходится перемножать цепочку матриц. Неудивительно, что можно встретить матрицы больших размеров, например 100×100. Поэтому наша задача — перемножить матрицы ⁠ $A_{1},A_{2},....A_{n}$⁠ . Умножение матриц не коммутативно, а ассоциативно; и мы можем перемножать только две матрицы одновременно. Итак, мы можем умножить эту цепочку матриц разными способами, например:

((А ₁ × А ₂ ) × А ₃ ) × ... А _н

А ₁ ×(((А ₂ ×А ₃ )× ... ) × А _н )

(А ₁ × А ₂ ) × (А ₃ × ... А _п )

и так далее. Существует множество способов умножения этой цепочки матриц. Все они дадут один и тот же окончательный результат, однако их вычисление займет больше или меньше времени, в зависимости от того, какие конкретные матрицы умножаются. Если матрица A имеет размеры m×n, а матрица B имеет размеры n×q, то матрица C=A×B будет иметь размеры m×q и потребует скалярных умножений m*n*q (с использованием упрощенного алгоритма умножения матриц для целей иллюстрации).

Например, перемножим матрицы A, B и C. Предположим, что их размеры равны m×n, n×p и p×s соответственно. Матрица A×B×C будет иметь размер m×s и может быть рассчитана двумя способами, показанными ниже:

1. Ax(B×C) Этот порядок умножения матриц потребует скалярных умножений nps + mns.
2. (A×B)×C Этот порядок умножения матриц потребует скалярных вычислений mnp + mps.

Предположим, что m = 10, n = 100, p = 10 и s = 1000. Итак, первый способ умножения цепочки потребует 1 000 000 + 1 000 000 вычислений. Второй способ потребует всего 10 000+100 000 вычислений. Очевидно, что второй способ быстрее, и нам следует перемножать матрицы, используя такое расположение круглых скобок.

Таким образом, мы пришли к выводу, что порядок скобок имеет значение и что наша задача — найти оптимальный порядок скобок.

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

Назовем m[i,j] минимальным количеством скалярных умножений, необходимых для умножения цепочки матриц от матрицы i до матрицы j (т. е. A _i × .... × A _j , т. е. i<=j). Мы разделяем цепочку на некоторой матрице k, такой, что i <= k < j, и пытаемся выяснить, какая комбинация дает минимум m[i,j].

Формула:

       if i = j, m[i,j]= 0
       if i < j, m[i,j]= min over all possible values of k (m[i,k]+m[k+1,j] + $p_{i-1}*p_{k}*p_{j}$) 

где k варьируется от i до j - 1.

• ⁠ $p_{i-1}$⁠ — размерность строки матрицы i,
• ⁠ $p_{k}$⁠ — размерность столбца матрицы k,
• ⁠ $p_{j}$⁠ — размерность столбца матрицы j.

Эту формулу можно закодировать, как показано ниже, где входной параметр «цепочка» — это цепочка матриц, т.е. ⁠ $A_{1},A_{2},...A_{n}$⁠ :

function OptimalMatrixChainParenthesis(chain)
    n = length(chain)
    for i = 1, n
        m[i,i] = 0    // Since it takes no calculations to multiply one matrix
    for len = 2, n
        for i = 1, n - len + 1
            j = i + len -1
            m[i,j] = infinity      // So that the first calculation updates
            for k = i, j-1
                q = m[i, k] + m[k+1, j] + $p_{i-1}*p_{k}*p_{j}$
                if q < m[i, j]     // The new order of parentheses is better than what we had
                    m[i, j] = q    // Update
                    s[i, j] = k    // Record which k to split on, i.e. where to place the parenthesis

На данный момент мы вычислили значения для всех возможных m [ i , j ] , минимального количества вычислений для умножения цепочки от матрицы i до матрицы j , и мы записали соответствующую «точку разделения» s [ i , j ] . Например, если мы перемножаем цепочку A ₁ ×A ₂ ×A ₃ ×A ₄ , и получается, что m [1, 3] = 100 и s [1, 3] = 2 , это означает, что оптимальное размещение скобка для матриц от 1 до 3 равна ⁠ $(A_{1}\times A_{2})\times A_{3}$⁠ и для умножения этих матриц потребуется 100 скалярных вычислений.

Этот алгоритм создаст «таблицы» m [, ] и s [, ], в которых будут записи для всех возможных значений i и j. Окончательное решение для всей цепочки — m[1, n] с соответствующим разделением в точке s[1, n]. Раскрытие решения будет рекурсивным, начиная сверху и продолжая до тех пор, пока мы не достигнем базового случая, то есть умножения одиночных матриц.

Поэтому следующим шагом будет фактическое разделение цепочки, т.е. размещение скобок там, где они (оптимально) принадлежат. Для этой цели можно использовать следующий алгоритм:

function PrintOptimalParenthesis(s, i, j)
    if i = j
        print "A"i
    else
        print "(" 
        PrintOptimalParenthesis(s, i, s[i, j]) 
        PrintOptimalParenthesis(s, s[i, j] + 1, j) 
        print ")"

Конечно, этот алгоритм бесполезен для фактического умножения. Этот алгоритм — всего лишь удобный способ увидеть, как выглядит результат.

Чтобы фактически умножить матрицы с использованием правильного разделения, нам нужен следующий алгоритм:

   function MatrixChainMultiply(chain from 1 to n)       // returns the final matrix, i.e. A1×A2×... ×An
      OptimalMatrixChainParenthesis(chain from 1 to n)   // this will produce s[ . ] and m[ . ] "tables"
      OptimalMatrixMultiplication(s, chain from 1 to n)  // actually multiply

   function OptimalMatrixMultiplication(s, i, j)   // returns the result of multiplying a chain of matrices from Ai to Aj in optimal way
      if i < j
         // keep on splitting the chain and multiplying the matrices in left and right sides
         LeftSide = OptimalMatrixMultiplication(s, i, s[i, j])
         RightSide = OptimalMatrixMultiplication(s, s[i, j] + 1, j)
         return MatrixMultiply(LeftSide, RightSide) 
      else if i = j
         return Ai   // matrix at position i
      else 
         print "error, i <= j must hold"

    function MatrixMultiply(A, B)    // function that multiplies two matrices
      if columns(A) = rows(B) 
         for i = 1, rows(A)
            for j = 1, columns(B)
               C[i, j] = 0
               for k = 1, columns(A)
                   C[i, j] = C[i, j] + A[i, k]*B[k, j] 
               return C 
      else 
          print "error, incompatible dimensions."

История названия

Термин «динамическое программирование» первоначально был использован в 1940-х годах Ричардом Беллманом для описания процесса решения проблем, в котором необходимо одно за другим находить лучшие решения. К 1953 году он уточнил это до современного значения, конкретно имея в виду вложение меньших проблем принятия решений в более крупные решения. и впоследствии эта область была признана IEEE как тема системного анализа и инженерии . Вклад Беллмана запомнился названием уравнения Беллмана , центрального результата динамического программирования, который переформулирует задачу оптимизации в рекурсивной форме.

Беллман объясняет причину термина «динамическое программирование» в своей автобиографии «Глаз урагана: автобиография» :

Осенний квартал 1950 года я провел в РЭНД . Моей первой задачей было найти название для многоэтапных процессов принятия решений. Интересный вопрос: «Откуда взялось название динамическое программирование?» 1950-е годы были не лучшими годами для математических исследований. У нас в Вашингтоне был очень интересный джентльмен по имени Уилсон . Он был министром обороны, и у него действительно был патологический страх и ненависть к слову «исследования». Я не отношусь к этому термину легкомысленно; Я использую его точно. Его лицо покраснело бы, он покраснел и стал бы агрессивным, если бы люди использовали термин «исследование» в его присутствии. Вы можете себе представить, что он тогда чувствовал по поводу термина «математический». Корпорация RAND работала в ВВС, и, по сути, ВВС возглавляли Уилсона. Следовательно, я чувствовал, что должен что-то сделать, чтобы оградить Вильсона и ВВС от того факта, что я действительно занимался математикой внутри корпорации RAND. Какой титул, какое имя я мог бы выбрать? В первую очередь меня интересовало планирование, принятие решений, мышление. Но планирование – нехорошее слово по разным причинам. Поэтому я решил использовать слово «программирование». Я хотел донести до вас мысль, что это было динамично, многоэтапно и менялось во времени. Я подумал: давайте убьем двух зайцев одним выстрелом. Возьмем слово, имеющее абсолютно точное значение, а именно динамический в классическом физическом смысле. У него также есть очень интересное свойство как прилагательного: невозможно использовать слово «динамический» в уничижительном смысле. Попробуйте придумать какую-нибудь комбинацию, которая, возможно, придаст этому уничижительному значению. Это невозможно. Поэтому я подумал, что динамическое программирование — хорошее название. Это было то, против чего не мог возражать даже конгрессмен. Поэтому я использовал его как прикрытие для своей деятельности.

- Ричард Беллман, Глаз урагана: автобиография (1984, стр. 159)

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

Приведенное выше объяснение происхождения этого термина может быть неточным: по мнению Рассела и Норвига, приведенная выше история «не может быть строго правдивой, поскольку его первая статья, использующая этот термин (Беллман, 1952), появилась до того, как Вильсон стал министром обороны в 1953 году. " Кроме того, Гарольд Дж. Кушнер , заархивированный 1 марта 2017 г. в Wayback Machine, заявил в своей речи: «С другой стороны, когда я задал [Беллману] тот же вопрос, он ответил, что пытается отодвинуть на второй план линейное программирование Данцига с помощью добавление динамики. Возможно, обе мотивации были правдой».

См. также

• Выпуклость в экономике - важная тема в экономике.
• Жадный алгоритм – последовательность локально оптимальных вариантов.
• Невыпуклость (экономика) - Нарушения предположений выпуклости элементарной экономики.
• Стохастическое программирование - основа моделирования задач оптимизации, связанных с неопределенностью.
• Стохастическое динамическое программирование - метод 1957 года для моделирования проблем принятия решений в условиях неопределенности.
• Обучение с подкреплением - Область машинного обучения

Дальнейшее чтение

• Адда, Джером; Купер, Рассел (2003), Динамическая экономика , MIT Press, ISBN  9780262012010 . Доступное введение в динамическое программирование в экономике. Код MATLAB для книги. Архивировано 9 октября 2020 г. в Wayback Machine .
• Беллман, Ричард (1954), «Теория динамического программирования», Бюллетень Американского математического общества , 60 (6): 503–516, doi : 10.1090/S0002-9904-1954-09848-8 , MR   0067459 . Включает обширную библиографию литературы в этой области до 1954 года.
• Беллман, Ричард (1957), Динамическое программирование , Издательство Принстонского университета . Дуврское издание в мягкой обложке (2003 г.), ISBN   0-486-42809-5 .
• Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001), Введение в алгоритмы (2-е изд.), MIT Press & McGraw – Hill, ISBN  978-0-262-03293-3 . Особенно стр. 323–69.
• Дрейфус, Стюарт Э.; Закон, Аверилл М. (1977), Искусство и теория динамического программирования , Academic Press, ISBN  978-0-12-221860-6 .
• Гигерих, Р.; Мейер, К.; Штеффен, П. (2004), «Дисциплина динамического программирования над данными последовательностей» (PDF) , Science of Computer Programming , 51 (3): 215–263, doi : 10.1016/j.scico.2003.12.005 .
• Мейн, Шон (2007), Методы управления сложными сетями , Cambridge University Press, ISBN  978-0-521-88441-9 , заархивировано из оригинала 19 июня 2010 г.
• Шритаран, СС (1991). «Динамическое программирование уравнений Навье-Стокса». Системы и контрольные письма . 16 (4): 299–307. дои : 10.1016/0167-6911(91)90020-ф .
• Стоки, Нэнси ; Лукас, Роберт Э .; Прескотт, Эдвард (1989), Рекурсивные методы экономической динамики , Гарвардский университет. Пресса, ISBN  978-0-674-75096-8 .

Внешние ссылки

• Учебник по динамическому программированию
• Курс MIT по алгоритмам - включает 4 видеолекции по DP, лекции 15–18.
• Прикладное математическое программирование Брэдли, Хакса и Маньянти, глава 11
• Дополнительные примечания DP
• Кинг, Ян, 2002 (1987), « Простое введение в динамическое программирование в макроэкономических моделях ». Введение в динамическое программирование как важный инструмент экономической теории.
• Динамическое программирование: от новичка до продвинутого. Статья Думитру на TopCoder.com о динамическом программировании.
• Алгебраическое динамическое программирование - формализованная основа динамического программирования, включая курс начального уровня для DP, Университет Билефельда.
• Дрейфус, Стюарт, « Ричард Беллман о зарождении динамического программирования. Архивировано 13 октября 2020 г. в Wayback Machine ».
• Учебник по динамическому программированию
• Нежное введение в динамическое программирование и алгоритм Витерби
• Табличный Пролог BProlog , XSB , SWI-Prolog
• Онлайн-модули интерактивного динамического программирования IFORS, включая кратчайший путь, коммивояжера, рюкзак, фальшивую монету, падение яиц, мост и факел, замену, продукты с цепной матрицей и задачу критического пути.