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

Метод оптимизации проблемы

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

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

Этого можно достичь двумя способами: ^{[ необходима цитата ]}

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

Некоторые языки программирования могут автоматически запоминать результат вызова функции с определенным набором аргументов, чтобы ускорить оценку вызова по имени (этот механизм называется вызовом по необходимости ). Некоторые языки делают это возможным переносимо (например, Scheme , Common Lisp , Perl или D ). Некоторые языки имеют встроенную автоматическую запоминание , например, табличный Prolog и 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, или подзадач , что приводит к алгоритму экспоненциального времени.

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

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

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

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

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

В обоих примерах мы производим вычисления только 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)) к = 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)) к = 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)) к = 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)) к = 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

Допустим, есть шашка, которая может начать с любой клетки на первой вертикали (т. е. строки), и вы хотите узнать кратчайший путь (сумму минимальных затрат на каждой посещенной вертикали), чтобы добраться до последней вертикали; предполагая, что шашка может двигаться только по диагонали влево вперед, по диагонали вправо вперед или прямо вперед. То есть шашка на (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моделируется как смещение относительно индекса (в 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] р[у, х] := -1 иначе если m = q[y-1, x] р[у, х] := 0 еще р[у, х] := 1

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

функция computeShortestPath() computeShortestPathArrays() минИндекс := 1 мин := q[n, 1] для i от 2 до n, если q[n, i] < min минИндекс := i мин := q[n, i] printPath(n, minIndex)

функция printPath(y, x) print (x) print ("<-") если y = 2 print (x + p[y, x]) иначе 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, не(h,t)) ; S(1,h,t) ; S(n-1, не(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 ( n , k ) = 1 + мин{макс( 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}}$ :

функция OptimalMatrixChainParenthesis(цепочка) n = длина(цепи) для i = 1, n m[i,i] = 0 // Так как для умножения одной матрицы не требуется никаких вычислений  для len = 2, n для i = 1, n - len + 1 j = i + 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 — это ⁠ ⁠ ${\displaystyle (A_{1}\times A_{2})\times A_{3}}$ и для умножения этих матриц потребуется 100 скалярных вычислений.

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

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

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

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

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

 function MatrixChainMultiply ( цепочка от 1 до n ) // возвращает конечную матрицу, т. е. A1×A2×... ×An OptimalMatrixChainParenthesis ( цепочка от 1 до n ) // это создаст s[.] и m[.] "таблицы" 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 return Ai // матрица в позиции i else print "error, i <= j must hold"                                        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 ] return C, иначе вывести "ошибка, несовместимые измерения".                                            

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

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

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

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

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

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

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

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

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

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

Ссылки

1. Кормен, TH; Лейзерсон, CE; Ривест, РЛ; Штейн, К. (2001), Введение в алгоритмы (2-е изд.), MIT Press & McGraw – Hill, ISBN  0-262-03293-7 . стр. 344.
2. Камьен, MI ; Шварц, NL (1991). Динамическая оптимизация: исчисление вариаций и оптимальное управление в экономике и менеджменте (второе изд.). Нью-Йорк: Elsevier. стр. 261. ISBN 978-0-444-01609-6.
3. Кирк, Дональд Э. (1970). Оптимальная теория управления: Введение. Englewood Cliffs, NJ: Prentice-Hall. С. 94–95. ISBN 978-0-13-638098-6.
4. "M. Memo". J Vocabulary . J Software . Получено 28 октября 2011 г.
5. Делиси, Чарльз (июль 1974 г.), «Кооперативные явления в гомополимерах: альтернативная формулировка функции распределения», Биополимеры , 13 (7): 1511–1512, doi :10.1002/bip.1974.360130719
6. Гурский, Г.В.; Заседателев, А.С. (сентябрь 1978), «Точные соотношения для расчета связывания регуляторных белков и других решеточных лигандов в двухцепочечных полинуклеотидах», Биофизика , 23 (5): 932–946, PMID  698271
7. Снедович, М. (2006), «Повторный взгляд на алгоритм Дейкстры: связь с динамическим программированием» (PDF) , Журнал управления и кибернетики , 35 (3): 599–620.Электронная версия статьи с интерактивными вычислительными модулями.
8. Денардо, Э.В. (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. Eddy, SR (2004). «Что такое динамическое программирование?». Nature Biotechnology . 22 (7): 909–910. doi :10.1038/nbt0704-909. PMID  15229554. S2CID  5352062.
12. Моше Снедович (2002), «OR/MS Games: 2. The Towers of Hanoi Problem», INFORMS Transactions on Education , 3 (1): 34–51, doi : 10.1287/ited.3.1.45 .
13. Konhauser JDE, Velleman, D., and Wagon, S. (1996). Куда поехал велосипед? Dolciani Mathematical Expositions – № 18. Математическая ассоциация Америки .
14. Снидович, Моше (2003). «OR/MS Games: 4. Радость от бросания яиц в Брауншвейге и Гонконге». INFORMS Transactions on Education . 4 : 48–64. doi : 10.1287/ited.4.1.48 .
15. Дин Коннебл Уиллс, Связи между комбинаторикой перестановок и алгоритмами и геометрией
16. Стюарт Дрейфус. «Ричард Беллман о рождении динамического программирования».
17. Nocedal, J.; Wright, SJ (2006). Численная оптимизация . Springer. стр. 9. ISBN 9780387303031.
18. Рассел, С.; Норвиг, П. (2009). Искусственный интеллект: современный подход (3-е изд.). Prentice Hall. ISBN 978-0-13-207148-2.
19. Кушнер, Гарольд Дж. (2004-07-01). "Премия Ричарда Э. Беллмана за контроль наследия". Архивировано из оригинала 2014-10-19.

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

• Адда, Джером; Купер, Рассел (2003), Динамическая экономика, MIT Press, ISBN 9780262012010. Доступное введение в динамическое программирование в экономике. Код MATLAB для книги Архивировано 2020-10-09 на Wayback Machine .
• Беллман, Ричард (1954), «Теория динамического программирования», Бюллетень Американского математического общества , 60 (6): 503–516, doi : 10.1090/S0002-9904-1954-09848-8 , MR  0067459. Включает обширную библиографию литературы по данной области до 1954 года.
• Беллман, Ричард (1957), Динамическое программирование , Princeton University Press. Мягкая обложка издания Dover (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.
• Giegerich, R.; Meyer, C.; Steffen, P. (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, архивировано из оригинала 2010-06-19.
• Шритаран, СС (1991). «Динамическое программирование уравнений Навье-Стокса». Systems and Control Letters . 16 (4): 299–307. doi :10.1016/0167-6911(91)90020-f.
• Стоки, Нэнси ; Лукас, Роберт Э.; Прескотт , Эдвард (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, в том числе кратчайший путь, коммивояжер, рюкзак, фальшивая монета, бросание яйца, мост и факел, замена, цепочечные матричные продукты и задача критического пути.