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

Метод оптимизации задачи

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

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

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

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

Обзор

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

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

Это делается путем определения последовательности функций ценности 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 ₁ в начальном состоянии системы является значением оптимального решения. Оптимальные значения переменных решения могут быть восстановлены одно за другим путем отслеживания уже выполненных вычислений.

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

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

${\displaystyle 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}$

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

${\displaystyle -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\}}$

уравнение в частных производных , известное как уравнение Гамильтона-Якоби-Беллмана , в котором и . Находят эту минимизацию с точки зрения , и неизвестной функции , а затем подставляют результат в уравнение Гамильтона-Якоби-Беллмана, чтобы получить уравнение в частных производных, которое нужно решить с граничными условиями . ^[2] На практике это обычно требует численных методов для некоторой дискретной аппроксимации точного соотношения оптимизации. ${\displaystyle 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}}}$ ${\displaystyle J_{t}^{\ast }={\frac {\partial J^{\ast }}{\partial t}}}$ ${\displaystyle \mathbf {u} }$ ${\displaystyle t}$ ${\displaystyle \mathbf {x} }$ ${\displaystyle J_{x}^{\ast }}$ ${\displaystyle J\left(t_{1}\right)=b\left(\mathbf {x} (t_{1}),t_{1}\right)}$

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

${\displaystyle 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\}}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle {\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 , последний период жизни.

Информатика

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

Оптимальная подструктура означает, что решение данной задачи оптимизации может быть получено путем комбинации оптимальных решений ее подзадач. Такие оптимальные подструктуры обычно описываются с помощью рекурсии . Например, для данного графа 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 ₄₃ , так и F ₄₂ . Несмотря на то, что общее количество подзадач на самом деле невелико (их всего 43), мы в конечном итоге будем решать одни и те же проблемы снова и снова, если примем такое наивное рекурсивное решение, как это. Динамическое программирование учитывает этот факт и решает каждую подзадачу только один раз.

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

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

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

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

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

Динамическое программирование широко используется в биоинформатике для таких задач, как выравнивание последовательностей , сворачивание белков , предсказание структуры РНК и связывание белка с ДНК. Первые алгоритмы динамического программирования связывания белок-ДНК были независимо разработаны в 1970-х годах Чарльзом ДеЛизи в США ^[5] и Георгием Гурским и Александром Заседателевым в СССР. ^[6] В последнее время эти алгоритмы стали очень популярными в биоинформатике и вычислительной биологии , особенно в исследованиях позиционирования нуклеосом и связывания факторов транскрипции .

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

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

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

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

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

Мы воспользуемся тем, что если – узел на минимальном пути от до , то знание последнего подразумевает знание минимального пути от до . ${\displaystyle R}$ ${\displaystyle P}$ ${\displaystyle Q}$ ${\displaystyle P}$ ${\displaystyle R}$

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

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

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

функция fib(n) , если n <= 1, возвращает n, возвращает 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или подзадач , что приводит к алгоритму экспоненциального времени.

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

var m := map (0 → 0, 1 → 1) функция fib(n) , если ключ n отсутствует на карте m m[n] := fib(n - 1) + fib(n - 2) вернуть м[н]

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

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

функция fib(n) if n = 0 возвращает 0 else  var previousFib := 0, currentFib := 1 повторить n − 1 раз  // цикл пропускается, если n = 1  var newFib := previousFib + currentFib предыдущаяфиб := текущаяфиб текущая Фиб : = новая Фиб вернуть ток Фиб

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

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

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

${\displaystyle {\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 единиц). Поскольку существуют возможные назначения и разумные назначения, эта стратегия непрактична, за исключением, возможно, до . ${\displaystyle 2^{n^{2}}}$ ${\displaystyle {\tbinom {n}{n/2}}^{n}}$ ${\displaystyle n=6}$

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

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

${\displaystyle 1,\,2,\,90,\,297200,\,116963796250,\,6736218287430460752,\ldots }$

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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()возвращающая минимальное из нескольких значений:

функция minCost(i, j), если j < 1 или j > n , возвращает бесконечность , иначе, если i = 1 , возвращает c(i, j) , иначе  возвращает  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моделируется как смещение относительно индекса (in q[i, j]) предварительно вычисленной стоимости пути s. Чтобы восстановить полный путь, мы ищем предшественника s, затем предшественника этого квадрата, затем предшественника этого квадрата и так далее рекурсивно, пока не достигнем начального квадрата. Рассмотрим следующий псевдокод:

функция ComputeShortestPathArrays() для x от 1 до n q[1, x] := c(1, x) для y от 1 до n q[y, 0] := бесконечность q[y, n + 1] := бесконечность для y от 2 до n для x от 1 до n m := min(q[y-1, x-1], q[y-1, x], q[y-1, x+1]) q[y, x] := m + c(y, x) если m = q[y-1, x-1] p[y, x] := -1 иначе, если m = q[y-1, x] р[у, х] := 0 еще р[у, х] := 1

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

функция вычисленияShortestPath() вычислитьШортестПатАррайс() мининдекс := 1 мин := q[n, 1] для i от 2 до n , если q[n, i] < min мининдекс := я мин := q[n, i] printPath(n, minIndex)

функция printPath(y, x) print (x) print ("<-") if y = 2 print (x + p[y, x]) else printPath(y-1, x + p[y, x])

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

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

Проблему можно сформулировать естественным образом как рекурсию: последовательность 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 ^{n - 1 ходов. [12]}

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

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

Предположим, мы хотим знать, с каких этажей в 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 ).

Тогда можно показать, что ^[14]

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 с использованием другой параметризации

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

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

Пусть — минимальный этаж, с которого нужно уронить яйцо, чтобы оно разбилось. ${\displaystyle m}$

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

Тогда для всех . ${\displaystyle f(t,0)=f(0,n)=1}$ ${\displaystyle t,n\geq 0}$

Пусть это пол, с которого упало первое яйцо в оптимальной стратегии. ${\displaystyle a}$

Если первое яйцо разбилось, это можно определить с помощью максимум попыток и яиц. ${\displaystyle m}$ ${\displaystyle 1}$ ${\displaystyle a}$ ${\displaystyle t-1}$ ${\displaystyle n-1}$

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

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

Тогда задача эквивалентна поиску минимума такого, что . ${\displaystyle x}$ ${\displaystyle f(x,n)\geq k}$

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

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

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

Поскольку для всех мы можем найти бинарный поиск , давая алгоритм. ^[15] ${\displaystyle f(t,n)\leq f(t+1,n)}$ ${\displaystyle t\geq 0}$ ${\displaystyle t}$ ${\displaystyle x}$ ${\displaystyle O(n\log k)}$

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

Умножение цепочки матриц — хорошо известный пример, демонстрирующий полезность динамического программирования. Например, в инженерных приложениях часто приходится перемножать цепочку матриц. Неудивительно, что можно встретить матрицы больших размеров, например 100×100. Поэтому наша задача — перемножить матрицы . Умножение матриц не коммутативно, а ассоциативно; и мы можем перемножать только две матрицы одновременно. Итак, мы можем умножить эту цепочку матриц разными способами, например: ${\displaystyle 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].

Формула:

 если i = j, m[i,j]= 0, если i < j, m[i,j]= min по всем возможным значениям k (m[i,k]+m[k+1,j] + ) ${\displaystyle p_{i-1}*p_{k}*p_{j}}$ 

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

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

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

функция OptimalMatrixChainParentesis(цепочка) n = длина (цепочка) для я = 1, п m[i,i] = 0 // Так как для умножения одной матрицы не требуется никаких вычислений  для len = 2, n для i = 1, n - len + 1 j = я + len -1 m[i,j] = бесконечность // Чтобы первое вычисление обновлялось  для k = i, j-1 q = m[i, k] + m[k+1, j] +  ${\displaystyle p_{i-1}*p_{k}*p_{j}}$ if q < m[i, j] ] // Новый порядок скобок лучше, чем тот, который был у нас m[i, j] = q // Обновляем s[i, j] = k // Записываем, по какому k нужно разбить, т.е. где разместить скобки

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

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

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

функция PrintOptimalParentesis(s, i, j), если i = j напечатайте "А"и еще Распечатать "(" PrintOptimalParentesis(s, i, s[i, j]) PrintOptimalParentesis(s, s[i, j] + 1, j) Распечатать ")"

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

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

 function MatrixChainMultiply ( цепочка от 1 до n ) // возвращает итоговую матрицу, т.е. A1×A2×... ×An OptimalMatrixChainParentesis ( цепочка от 1 до n ) // это создаст s[ . ] И м[ . ] "tables" OptimalMatrixMultiplication ( s , цепочка от 1 до n ) // собственно умножение                    function OptimalMatrixMultiplication ( s , i , j ) // возвращает результат умножения цепочки матриц от Ai до Aj оптимальным способом, если i < j // продолжаем разбивать цепочку и умножать матрицы в левой и правой частях LeftSide = OptimalMatrixMultiplication ( s , i , s [ i , j ]) RightSide = OptimalMatrixMultiplication ( s , s [ i , j ] + 1 , j ) return MatrixMultiply ( LeftSide , RightSide ) else if i = j вернуть Ai // матрицу в позиции i else напечатайте «ошибка, я <= j должен удерживаться»                                        function MatrixMultiply ( A , B ) // функция, которая умножает две матрицы , если столбцы ( A ) = строки ( B ) для i = 1 , строки ( A ) для j = 1 , столбцы ( B ) C [ i , j ] = 0 для k = 1 столбцы ( A ) C [ i , j ] = C [ i , j ] + A [ i , k ] * B [ k , j ] возвращают C иначе напечатайте «ошибка , несовместимые размеры».                                            

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

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

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

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

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

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

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

Смотрите также

• Портал системных наук
• Математический портал

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

Рекомендации

1. Кормен, TH; Лейзерсон, CE; Ривест, РЛ; Штейн, К. (2001), Введение в алгоритмы (2-е изд.), MIT Press & McGraw – Hill, ISBN  0-262-03293-7 . стр. 344.
2. Камен, Мичиган ; Шварц, Нидерланды (1991). Динамическая оптимизация: вариационное исчисление и оптимальное управление в экономике и менеджменте (второе изд.). Нью-Йорк: Эльзевир. п. 261. ИСБН 978-0-444-01609-6.
3. Кирк, Дональд Э. (1970). Теория оптимального управления: Введение. Энглвуд Клиффс, Нью-Джерси: Прентис-Холл. стр. 94–95. ISBN 978-0-13-638098-6.
4. "М. Памятка". J Словарь . Программное обеспечение J. Проверено 28 октября 2011 г.
5. ДеЛизи, Биополимеры, 1974, Том 13, Выпуск 7, страницы 1511–1512, июль 1974 г.
6. Гурский Г.В., Заседателев А.С., Биофизика, 1978, сентябрь-октябрь;23(5):932-46.
7. Снедович, М. (2006), «Возвращение к алгоритму Дейкстры: связь с динамическим программированием» (PDF) , Journal of Control and Cybernetics , 35 (3): 599–620.Онлайн-версия статьи с интерактивными вычислительными модулями.
8. Денардо, EV (2003), Динамическое программирование: модели и приложения , Минеола, Нью-Йорк: Dover Publications , ISBN 978-0-486-42810-9
9. Снедович, М. (2010), Динамическое программирование: основы и принципы , Тейлор и Фрэнсис , ISBN 978-0-8247-4099-3
10. Дейкстра, EW (декабрь 1959 г.). «Заметка о двух проблемах, связанных с графами». Нумерическая математика . 1 (1): 269–271. дои : 10.1007/BF01386390.
11. Эдди, SR (2004). «Что такое динамическое программирование?». Природная биотехнология . 22 (7): 909–910. дои : 10.1038/nbt0704-909. PMID  15229554. S2CID  5352062.
12. Моше Снедович (2002), «Игры OR/MS: 2. Проблема Ханойских башен», INFORMS Transactions on Education , 3 (1): 34–51, doi : 10.1287/ited.3.1.45 .
13. Конхаузер JDE, Веллеман Д. и Вагон С. (1996). В какую сторону проехал велосипед? Математические экспозиции Дольчиани - № 18. Математическая ассоциация Америки .
14. Снедович, Моше (2003). «Игры OR/MS: 4. Радость от падения яиц в Брауншвейге и Гонконге». ИНФОРМЫ Сделки по образованию . 4 : 48–64. дои : 10.1287/изд.4.1.48 .
15. Дин Коннэйбл Уиллс, Связи между комбинаторикой перестановок, алгоритмами и геометрией
16. Стюарт Дрейфус. «Ричард Беллман о рождении динамического программирования».
17. Носедаль, Дж.; Райт, С.Дж. (2006). Численная оптимизация . Спрингер. п. 9. ISBN 9780387303031.
18. Рассел, С.; Норвиг, П. (2009). Искусственный интеллект: современный подход (3-е изд.). Прентис Холл. ISBN 978-0-13-207148-2.

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

• Адда, Джером; Купер, Рассел (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), Динамическое программирование , Princeton University Press. Дуврское издание в мягкой обложке (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, Университет Билефельда.
• Дрейфус, Стюарт, «Ричард Беллман о рождении динамического программирования».
• Учебник по динамическому программированию
• Нежное введение в динамическое программирование и алгоритм Витерби
• Табличный Пролог BProlog, XSB, SWI-Prolog
• Онлайн-модули интерактивного динамического программирования IFORS, включая кратчайший путь, коммивояжера, рюкзак, фальшивую монету, падение яиц, мост и факел, замену, продукты с цепной матрицей и задачу критического пути.