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

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

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

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

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

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

Обзор

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

С точки зрения математической оптимизации, динамическое программирование обычно означает упрощение решения путем разбиения его на последовательность шагов принятия решения во времени. Это делается путем определения последовательности функции значения V₁, V₂, ..., V_п принимая y как аргумент, представляющий штат системы временами я от 1 до п. Определение V_п(y) - значение, полученное в состоянии y в последний раз п. Ценности V_я в прежние времена я = п −1, п - 2, ..., 2, 1 можно найти, работая в обратном направлении, используя рекурсивный отношения под названием Уравнение беллмана. Для я = 2, ..., п, V_я−1 в любом состоянии y рассчитывается из V_я максимизируя простую функцию (обычно сумму) выигрыша от решения во время я - 1 и функция V_я при новом состоянии системы, если это решение принято. поскольку V_я уже вычислен для необходимых состояний, вышеуказанная операция дает V_я−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\}}$

а уравнение в частных производных известный как Уравнение Гамильтона – Якоби – Беллмана., в котором ${\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)}$.^[2] На практике это обычно требует численные методы для некоторого дискретного приближения к точному соотношению оптимизации.

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

${\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 {g}}\left(\mathbf {x} _{n-k},\mathbf {u} _{n-k}\right)\right)\right\}}$

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

Пример из экономики: задача Рамсея об оптимальной экономии

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

В экономике цель обычно состоит в том, чтобы максимизировать (а не минимизировать) некоторую динамику. функция социального обеспечения. В задаче Рэмси эта функция связывает объемы потребления с уровнями полезность. Грубо говоря, планировщик сталкивается с выбором между одновременным потреблением и потреблением в будущем (через инвестиции в основной капитал который используется в производстве), известный как межвременной выбор. Будущее потребление дисконтируется по постоянной ставке ${\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}$ это производственная функция удовлетворение Условия Inada. Первоначальный основной капитал ${\displaystyle k_{0}>0}$ предполагается.

Позволять ${\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}}$ не является переменной выбора - первоначальный капитал потребителя принимается заданным.)

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

Эта задача намного проще, чем та, которую мы записали ранее, потому что она включает только две переменные решения: ${\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}}}$

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

Компьютерное программирование

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

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

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

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

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

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

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

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

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

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

   функция фиб (п) если п <= 1 вернуть п вернуть фиб (п - 1) + фиб (п - 2)

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

1. фиб (5)
2. фиб (4) + фиб (3)
3. (фиб (3) + фиб (2)) + (фиб (2) + фиб (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) )

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

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

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

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

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

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

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

Вышеупомянутый метод фактически требует ${\displaystyle \Omega (n^{2})}$ время для больших n из-за сложения двух целых чисел с ${\displaystyle \Omega (n)}$ бит каждый занимает ${\displaystyle \Omega (n)}$ время. (The п^th число Фибоначчи имеет ${\displaystyle \Omega (n)}$ бит.) Также существует закрытая форма для последовательности Фибоначчи, известная как формула Бине, откуда ${\displaystyle n}$-й семестр может быть вычислен примерно в ${\displaystyle O(n(\log n)^{2})}$ время, что более эффективно, чем описанный выше метод динамического программирования. Однако простое повторение прямо дает матричная форма что приводит к примерно ${\displaystyle O(n\log n)}$ алгоритм быстро матричное возведение в степень.

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

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

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

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

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

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

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

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

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

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

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

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

5
4
3
2		Икс	Икс	Икс
1			о
	1	2	3	4	5

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

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

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

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

5
4			А
3		B	C	D
2
1
	1	2	3	4	5

${\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 на самой нижней границе и п на самой высокой границе. Вторая строка определяет, что происходит на первом ранге; обеспечение базового случая. Третья строка, рекурсия, является важной частью. Он представляет собой А, Б, В, D термины в примере. Из этого определения мы можем вывести простой рекурсивный код для q (i, j). В следующем псевдокоде п это размер доски, с (я, j) - функция стоимости, а мин () возвращает минимум из ряда значений:

функция minCost (i, j) если j <1 или j> n вернуть бесконечность иначе если я = 1 вернуть с (я, j) еще        вернуть мин(minCost (i-1, j-1), minCost (i-1, j), minCost (i-1, j + 1)) + c (i, j)

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

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

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

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

 функция computeShortestPath () computeShortestPathArrays () minIndex: = 1 мин: = q [n, 1] для я от 2 к п если q [n, i] 
 функция printPath (y, x) Распечатать(Икс) Распечатать("<-")     если у = 2 Распечатать(х + р [у, х]) еще         printPath (y-1, x + p [y, x])
Выравнивание последовательности
В генетика, выравнивание последовательностей является важным приложением, в котором необходимо динамическое программирование.[11]  Обычно проблема состоит в преобразовании одной последовательности в другую с помощью операций редактирования, которые заменяют, вставляют или удаляют элемент. Каждая операция имеет соответствующую стоимость, и цель состоит в том, чтобы найти последовательность правок с наименьшей общей стоимостью.
Проблема может быть сформулирована естественным образом как рекурсия, последовательность A оптимально редактируется в последовательность B одним из следующих способов:
вставка первого символа B и выполнение оптимального выравнивания A и хвоста B
удаление первого символа A и выполнение оптимального выравнивания хвоста A и B
замена первого символа A на первый символ B и выполнение оптимального выравнивания хвостов A и B.
Частичные выравнивания могут быть сведены в таблицу в матрице, где ячейка (i, j) содержит стоимость оптимального выравнивания A [1..i] к B [1..j]. Стоимость в ячейке (i, j) может быть рассчитана путем добавления стоимости соответствующих операций к стоимости соседних ячеек и выбора оптимума.
Существуют разные варианты, см. Алгоритм Смита – Уотермана и Алгоритм Нидлмана – Вунша.
Загадка Ханойская башня
  
Модельный набор Башен Ханоя (с 8 дисками)
  
Анимированное решение Ханойская башня головоломка для Т (4,3).
В Ханойская башня или Башни Ханой это математическая игра или головоломка. Он состоит из трех стержней и нескольких дисков разного размера, которые могут скользить по любому стержню. Головоломка начинается с дисков в аккуратной стопке в порядке возрастания размера на одном стержне, наименьший наверху, образуя конусообразную форму.
Задача головоломки - переместить всю стопку на другой стержень, соблюдая следующие правила:
Одновременно можно перемещать только один диск.
Каждое движение состоит в том, чтобы снять верхний диск с одного из стержней и надеть его на другой стержень, поверх других дисков, которые могут уже присутствовать на этом стержне.
Диск не может быть помещен поверх меньшего диска.
Решение динамического программирования состоит из решения функциональное уравнение
S (n, h, t) = S (n-1, h, not (h, t)); S (1, h, t); S (n-1, а не (h, t), t)
где n обозначает количество дисков, которые необходимо переместить, h обозначает базовую штангу, t обозначает целевой стержень, а не (h, t) обозначает третий стержень (ни h, ни t), «;» обозначает конкатенацию, а
S (n, h, t): = решение задачи, состоящей из n дисков, которые нужно переместить от стержня h к стержню t.
Для n = 1 задача тривиальна, а именно S (1, h, t) = «переместить диск от стержня h к стержню t» (остался только один диск).
Количество ходов, необходимых для этого решения, равно 2.п - 1. Если цель - максимизировать количество ходов (без цикла), затем динамическое программирование функциональное уравнение  немного сложнее и 3п - Требуется 1 ход.[12]
Головоломка с падением яиц
Ниже приводится описание экземпляра этого известного головоломка с участием N = 2 яиц и здания H = 36 этажей:[13]
Предположим, что мы хотим знать, с каких этажей 36-этажного здания можно безопасно сбрасывать яйца, а из каких они разбиваются при приземлении (используя Американский английский терминология, в которой первый этаж находится на уровне земли). Сделаем несколько предположений:
Яйцо, пережившее падение, можно использовать снова.
Разбитое яйцо нужно выбросить.
Эффект от падения одинаков для всех яиц.
Если яйцо разбивается при падении, оно сломается, если его уронить из более высокого окна.
Если яйцо переживет падение, оно переживет более короткое падение.
Не исключено, что окна первого этажа разбивают яйца, равно как и не исключено, что яйца могут пережить окна 36 этажа.
Если доступно только одно яйцо и мы хотим быть уверены в получении правильного результата, эксперимент может быть проведен только одним способом. Бросьте яйцо из окна первого этажа; если он выживает, бросьте его из окна второго этажа. Продолжайте движение вверх, пока не сломается. В худшем случае для этого метода может потребоваться 36 помет. Допустим, есть 2 яйца. Какое наименьшее количество яичного помета гарантированно работает во всех случаях?
Вывести динамическое программирование функциональное уравнение для этой головоломки пусть штат модели динамического программирования - пара s = (n, k), где
п = количество доступных тестовых яиц, п = 0, 1, 2, 3, ..., N − 1.
k = количество (последовательных) этажей, которые еще предстоит протестировать, k = 0, 1, 2, ..., ЧАС − 1.
Например, s = (2,6) означает, что доступны два тестовых яйца и 6 (последовательных) этажей еще предстоит проверить. Начальное состояние процесса s = (N,ЧАС) где N обозначает количество тестовых яиц, доступных на начало эксперимента. Процесс завершается, когда тестовых яиц больше нет (п = 0) или когда k = 0, в зависимости от того, что произойдет раньше. Если завершение происходит в состоянии s = (0,k) и k > 0, то тест не пройден.
Теперь позвольте
W(п,k) = минимальное количество испытаний, необходимое для определения значения критического минимального уровня при наихудшем сценарии, учитывая, что процесс находится в состоянии s = (п,k).
Тогда можно показать, что[14]
W(п,k) = 1 + мин. {Макс. (W(п − 1, Икс − 1), W(п,k − Икс)): Икс = 1, 2, ..., k }
с участием W(п, 0) = 0 для всех п > 0 и W(1,k) = k для всехk. Это уравнение легко решить итеративно, систематически увеличивая значения п иk.
Более быстрое решение DP с использованием другой параметризации
Обратите внимание, что приведенное выше решение требует ${\displaystyle O(nk^{2})}$ время с раствором DP. Это можно улучшить до ${\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}$ для каждой ячейки в таблице DP и со ссылкой на ее значение для предыдущей ячейки оптимальное ${\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}$.
поскольку ${\displaystyle f(t,n)\leq f(t+1,n)}$ для всех ${\displaystyle t\geq 0}$, мы можем выполнять двоичный поиск по ${\displaystyle t}$ найти ${\displaystyle x}$, давая ${\displaystyle O(n\log k)}$ алгоритм.[15]
Умножение матричной цепочки
Основная статья: Умножение матричной цепочки
Умножение цепочки матриц - хорошо известный пример, демонстрирующий полезность динамического программирования. Например, инженерные приложения часто должны умножать цепочку матриц. Неудивительно, что встречаются матрицы больших размеров, например 100 × 100. Поэтому наша задача - умножить матрицы ${\displaystyle A_{1},A_{2},....A_{n}}$. Как мы знаем из базовой линейной алгебры, умножение матриц не коммутативно, а ассоциативно; и мы можем перемножать только две матрицы за раз. Итак, мы можем умножить эту цепочку матриц множеством разных способов, например:
((A1 × А2) × А3) × ... Ап
А1× (((A2× А3) × ...) × Ап)
(А1 × А2) × (A3 × ... Ап)
и так далее. Есть множество способов умножить эту цепочку матриц. Все они будут давать один и тот же конечный результат, однако на их вычисление уйдет больше или меньше времени, в зависимости от того, какие конкретные матрицы умножаются. Если матрица 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 и может быть вычислена двумя способами, показанными ниже:
Ax (B × C) Этот порядок умножения матриц потребует скалярных умножений nps + mns.
(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я × .... × Аj, т.е. i <= j). Мы разбиваем цепочку на некоторой матрице k, такой что i <= k 
Формула:
       если я = j, m [я, j] = 0 если i (m [i, k] + m [k + 1, j] + ${\displaystyle p_{i-1}*p_{k}*p_{j}}$)
где k колеблется от я к 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] = бесконечность // Чтобы первый расчет обновился             для к = я, j-1 q = m [i, k] + m [k + 1, j] + ${\displaystyle p_{i-1}*p_{k}*p_{j}}$                 если q // Новый порядок скобок лучше, чем у нас                     m [i, j] = q // Обновить                     s [i, j] = k // Записываем, какие k нужно разделить, т.е. где разместить скобки
Пока что мы рассчитали значения для всех возможных м[я, j], минимальное количество вычислений для умножения цепочки из матрицы я в матрицу j, и мы записали соответствующую "точку разделения"s[я, j]. Например, если мы умножаем цепочку А1× А2× А3× А4, и оказывается, что м[1, 3] = 100 и s[1, 3] = 2, это означает, что оптимальное расположение скобок для матриц с 1 по 3 - ${\displaystyle (A_{1}\times A_{2})\times A_{3}}$ и для умножения этих матриц потребуется 100 скалярных вычислений.
Этот алгоритм будет производить «таблицы» м[, ] и s[,], в котором будут записи для всех возможных значений i и j. Окончательное решение для всей цепочки - m [1, n] с соответствующим разбиением в s [1, n]. Решение будет рекурсивным, начиная сверху и продолжая до тех пор, пока мы не дойдем до базового случая, то есть умножения отдельных матриц.
Следовательно, следующим шагом будет фактическое разделение цепочки, то есть размещение скобок там, где они (оптимально) принадлежат. Для этого можно использовать следующий алгоритм:
функция PrintOptimalParenthesis (s, i, j) если i = j выведите "A" i еще        print "(" PrintOptimalParenthesis (s, i, s [i, j]) PrintOptimalParenthesis (s, s [i, j] + 1, j) print ")»
Конечно, этот алгоритм бесполезен для реального умножения. Этот алгоритм - просто удобный способ увидеть, как выглядит результат.
Чтобы действительно умножить матрицы с использованием правильного разбиения, нам понадобится следующий алгоритм:
   функция MatrixChainMultiply(цепь от 1 к п)       // возвращает окончательную матрицу, то есть A1 × A2 × ... × An      OptimalMatrixChainParenthesis(цепь от 1 к п)   // это даст s [. ] И м[ . ] "столы"      OptimalMatrixMultiplication(s, цепь от 1 к п)  // фактически умножаем   функция OptimalMatrixMultiplication(s, я, j)   // возвращает результат умножения цепочки матриц от Ai до Aj оптимальным образом      если я < j         // продолжаем разбивать цепочку и перемножать матрицы в левой и правой частях         Левая сторона = OptimalMatrixMultiplication(s, я, s[я, j])         Правая сторона = OptimalMatrixMultiplication(s, s[я, j] + 1, j)         вернуть MatrixMultiply(Левая сторона, Правая сторона)       еще если я = j         вернуть Ай   // матрица в позиции i      еще          Распечатать "ошибка, я <= j должен удерживаться"    функция MatrixMultiply(А, B)    // функция, которая умножает две матрицы      если столбцы(А) = ряды(B)          для я = 1, ряды(А)            для j = 1, столбцы(B)               C[я, j] = 0               для k = 1, столбцы(А)                   C[я, j] = C[я, j] + А[я, k]*B[k, j]                вернуть C       еще           Распечатать «ошибка, несовместимые размеры».
История









Период, термин динамическое программирование первоначально использовался в 1940-х годах Ричард Беллман описывать процесс решения проблем, в котором нужно одно за другим находить лучшие решения. К 1953 году он уточнил это до современного смысла, конкретно обращаясь к вложению меньших проблем принятия решений в более крупные решения,[16]  и после этого поле было признано IEEE как системный анализ и инженерное дело тема. Вклад Беллмана запомнился во имя Уравнение беллмана, центральный результат динамического программирования, который ставит задачу оптимизации в рекурсивный форма.
Беллман объясняет причину этого термина динамическое программирование в его автобиографии, Глаз урагана: автобиография:
Осенний квартал (1950 г.) я провел в RAND. Моей первой задачей было найти название для многоступенчатых процессов принятия решений. Интересный вопрос: «Откуда взялось название« динамическое программирование »?» 1950-е годы не были хорошими годами для математических исследований. У нас был очень интересный джентльмен в Вашингтоне по имени Уилсон. Он был министром обороны и на самом деле испытывал патологический страх и ненависть к слову «исследование». Я не использую этот термин легкомысленно; Я использую точно. Его лицо покрылось кровью, он покраснел и стал бы агрессивным, если бы люди использовали термин «исследование» в его присутствии. Вы можете себе представить, как он относился к термину «математика». Корпорация RAND использовалась в ВВС, и, по сути, во главе ВВС был Уилсон. Следовательно, я чувствовал, что должен что-то сделать, чтобы оградить Уилсона и ВВС от того факта, что я действительно занимался математикой внутри корпорации RAND. Какое название, какое имя я мог бы выбрать? В первую очередь меня интересовало планирование, принятие решений, мышление. Но планирование - не лучшее слово по разным причинам. Поэтому я решил использовать слово «программирование». Я хотел донести идею, что это было динамично, это было многоэтапно, это было изменяющимся во времени. Я подумал, давай убьем двух зайцев одним выстрелом. Возьмем слово, имеющее абсолютно точное значение, а именно динамический в классическом физическом смысле. У него также есть очень интересное свойство прилагательного: слово «динамический» невозможно употреблять в уничижительном смысле. Попробуйте придумать какую-нибудь комбинацию, которая, возможно, придаст этому уничижительное значение. Это невозможно. Таким образом, я подумал, что динамическое программирование - хорошее имя. Против этого не мог возражать даже конгрессмен. Поэтому я использовал его как зонтик для своей деятельности.
— Ричард Беллман, Глаз урагана: автобиография (1984, стр.159)
Слово динамичный был выбран Беллманом, чтобы охватить меняющийся во времени аспект проблем, и потому что это звучало впечатляюще.[11] Слово программирование упомянули об использовании метода для поиска оптимального программав смысле военного расписания для обучения или логистики. Это употребление такое же, как и во фразах линейное программирование и математическое программирование, синоним для математическая оптимизация.[17]
Приведенное выше объяснение происхождения термина отсутствует. Как написали Рассел и Норвиг в своей книге, ссылаясь на приведенную выше историю: «Это не может быть строго правдой, потому что его первая статья, в которой используется этот термин (Bellman, 1952), появилась до того, как Вильсон стал министром обороны в 1953 году».[18] Также в выступлении есть комментарий Гарольд Дж. Кушнер, где он вспоминает Беллмана. Цитируя Кушнера, когда он говорит о Беллмане: «С другой стороны, когда я задал ему тот же вопрос, он ответил, что пытался отодвинуть на задний план линейное программирование Данцига, добавив динамику. Возможно, обе мотивации были верны».
Алгоритмы, использующие динамическое программирование









Повторяющиеся решения для решетчатые модели для связывания белок-ДНК
Обратная индукция как метод решения для конечного горизонта дискретное время задачи динамической оптимизации
Метод неопределенных коэффициентов можно использовать для решения Уравнение беллмана в бесконечном горизонте, в дискретном времени, со скидкой, неизменный во времени задачи динамической оптимизации
Много строка алгоритмы, включая самая длинная общая подпоследовательность, самая длинная возрастающая подпоследовательность, самая длинная общая подстрока, Расстояние Левенштейна (редактировать расстояние)
Многие алгоритмические проблемы на графики эффективно решается для графов ограниченного ширина дерева или ограниченный ширина клики с помощью динамического программирования на разложение дерева графа.
В Алгоритм Кок-Янга-Касами (CYK) который определяет, может ли и как данная строка быть сгенерирована данным контекстно-свободная грамматика
Алгоритм переноса слов Кнута что сводит к минимуму неровность при переносе текста по словам
Использование таблицы транспонирования и таблицы опровержения в компьютерные шахматы
В Алгоритм Витерби (используется для скрытые марковские модели, и особенно в часть тегов речи )
В Алгоритм Эрли (тип анализатор диаграмм )
В Алгоритм Нидлмана – Вунша и другие алгоритмы, используемые в биоинформатика, в том числе выравнивание последовательностей, структурное выравнивание, Предсказание структуры РНК [11]
Алгоритм кратчайшего пути для всех пар Флойда
Оптимизация заказа для цепное умножение матриц
Псевдополиномиальное время алгоритмы для сумма подмножества, рюкзак и раздел проблемы
В динамическое искажение времени алгоритм вычисления глобального расстояния между двумя временными рядами
В Селинджер (a.k.a. Система R ) алгоритм оптимизации запросов к реляционной базе данных
Алгоритм де Бура для оценки кривых B-сплайна
Метод Дакворта – Льюиса для решения проблемы, когда игры в крикет прерываются
Метод итерации значений для решения Марковские процессы принятия решений
Некоторые грани графического изображения следуют за методами выделения, такими как инструмент выделения "магнит" в Фотошоп
Некоторые методы решения интервальное планирование проблемы
Некоторые методы решения задача коммивояжера, либо точно (в экспоненциальное время ) или приблизительно (например, через битонический тур )
Рекурсивный метод наименьших квадратов метод
Бить отслеживание в поиск музыкальной информации
Стратегия обучения адаптивному критику для искусственные нейронные сети
Стереоалгоритмы решения проблема переписки используется в стереозрении
Резьба по шву (изменение размера изображения с учетом содержимого)
В Алгоритм Беллмана – Форда для нахождения кратчайшего расстояния на графике
Некоторые приближенные методы решения задача линейного поиска
Алгоритм Кадане для проблема максимального подмассива
Оптимизация планов расширения производства электроэнергии в Автоматическое системное планирование Wein (WASP) пакет
Смотрите также









Выпуклость в экономике
Жадный алгоритм
Невыпуклость (экономика)
Стохастическое программирование
Стохастическое динамическое программирование
Обучение с подкреплением
использованная литература









 Cormen, T. H .; Leiserson, C.E .; Rivest, R.L .; Стейн, К. (2001), Введение в алгоритмы (2-е изд.), MIT Press & McGraw – Hill, ISBN  0-262-03293-7 . С. 344.
 Камиен, М.И.; Шварц, Н. (1991). Динамическая оптимизация: вариационный расчет и оптимальное управление в экономике и менеджменте (Второе изд.). Нью-Йорк: Эльзевир. п. 261. ISBN  978-0-444-01609-6.
 Кирк, Дональд Э. (1970). Теория оптимального управления: введение. Энглвуд Клиффс, Нью-Джерси: Прентис-Холл. С. 94–95. ISBN  978-0-13-638098-6.
 "М. Памятка". J Словарь. J Программное обеспечение. Получено 28 октября 2011.
 ДеЛиси, Биополимеры, 1974 г., том 13, выпуск 7, страницы 1511–1512, июль 1974 г.
 Гурский Г.В., Заседателев А.С., Биофизика, 1978 сен-октябрь; 23 (5): 932-46
 Сниедович, М. (2006), «Новый взгляд на алгоритм Дейкстры: связь с динамическим программированием» (PDF), Журнал управления и кибернетики, 35 (3): 599–620. Онлайн-версия статьи с интерактивными вычислительными модулями.
 Денардо, Э. (2003), Динамическое программирование: модели и приложения, Минеола, штат Нью-Йорк: Dover Publications, ISBN  978-0-486-42810-9
 Сниедович, М. (2010), Динамическое программирование: основы и принципы, Тейлор и Фрэнсис, ISBN  978-0-8247-4099-3
 Дейкстра 1959, п. 270 ошибка harvnb: нет цели: CITEREFDijkstra1959 (Помогите)
 Эдди, С. (2004). «Что такое динамическое программирование?». Природа Биотехнологии. 22 (7): 909–910. Дои:10.1038 / nbt0704-909. PMID  15229554. S2CID  5352062.
 Моше Сниедович (2002), «OR / MS Games: 2. Проблема Ханойских башен», ИНФОРМАЦИЯ Об образовании, 3 (1): 34–51, Дои:10.1287 / ited.3.1.45.
 Конхаузер Дж. Д. Э., Веллеман Д. и Вагон С. (1996). Куда пошел велосипед? Математические экспозиции Дольчани - № 18. Математическая ассоциация Америки.
 Сниедович, Моше (2003). «OR / MS Games: 4. Удовольствие от яиц в Брауншвейге и Гонконге». Информирует транзакции об образовании. 4: 48–64. Дои:10.1287 / ited.4.1.48.
 Дин Коннэбл Уиллс, Связь комбинаторики перестановок, алгоритмов и геометрии
 Стюарт Дрейфус. «Ричард Беллман о рождении динамического программирования».
 Nocedal, J .; Райт, С. Дж. (2006). Численная оптимизация. Springer. п.9.
 Russell, S .; Норвиг, П. (2009). Искусственный интеллект: современный подход (3-е изд.). Прентис Холл. ISBN  978-0-13-207148-2.
дальнейшее чтение









Адда, Джером; Купер, Рассел (2003), Динамическая экономика, MIT Press. Доступное введение в динамическое программирование в экономике. Код MATLAB для книги.
Беллман, Ричард (1954), «Теория динамического программирования», Бюллетень Американского математического общества, 60 (6): 503–516, Дои:10.1090 / S0002-9904-1954-09848-8, Г-Н  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 .; Штеффен, П. (2004), «Дисциплина динамического программирования над последовательными данными» (PDF), Наука компьютерного программирования, 51 (3): 215–263, Дои:10.1016 / j.scico.2003.12.005.
Мейн, Шон (2007), Методы управления сложными сетями, Издательство Кембриджского университета, ISBN  978-0-521-88441-9, заархивировано из оригинал на 2010-06-19.
Шритаран, С. С. (1991). «Динамическое программирование уравнений Навье-Стокса». Системы и контрольные письма. 16 (4): 299–307. Дои:10.1016 / 0167-6911 (91) 90020-ф.
Стоки, Нэнси; Лукас, Роберт Э.; Прескотт, Эдвард (1989), Рекурсивные методы в экономической динамике, Гарвардский университет. Нажмите, ISBN  978-0-674-75096-8.
внешние ссылки









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