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

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

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

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

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

Биоинформатика [ править ]

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

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

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

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

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

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

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

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

Последовательность Фибоначчи [ править ]

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

функция fib (n) if n <= 1 return n return fib (n - 1) + fib (n - 2)

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

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

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

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

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

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

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

function fib (n) if n = 0 return 0 else  var previousFib: = 0, currentFib: = 1 repeat n - 1 times  // цикл пропускается, если n = 1  var newFib: = previousFib + currentFib previousFib: = currentFib currentFib: = newFib вернуть currentFib

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

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

Тип сбалансированной матрицы 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}}.}$

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

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

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

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

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

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

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

Шахматная доска [ править ]

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

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

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

function minCost (i, j) if j <1 or j> n вернуть бесконечность else if i = 1 return c (i, j) else  return  min (minCost (i-1, j-1), minCost (i-1, j), minCost (i-1, j + 1)) + c (i, j)

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

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

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

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

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

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

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

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

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

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

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

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

Загадка Ханойской башни [ править ]

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

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

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

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

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), где

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 + min {max ( W ( n - 1, x - 1), W ( n , k - x )): x = 1, 2, ..., k }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Умножение цепочки матриц [ править ]

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

((A ₁ × A ₂ ) × A ₃ ) × ... A _n

A ₁ × (((A ₂ × A ₃ ) × ...) × A _n )

(A ₁ × A ₂ ) × (A ₃ × ... 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 = я + len -1 m [i, j] = infinity // Таким образом, первое вычисление обновляется  для 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 печать "A" 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 [. ] И м[ . ] "таблицы"  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  // matrix at position i  else  print  "error, i <= j must hold" function  MatrixMultiply ( A ,  B )  // функция, которая умножает две матрицы,  если  столбцы ( A )  =  строки ( B )  для  i  =  1 ,  строки ( A )  для  j  =  1 ,  столбцы ( B )  C [ i ,  j ]  =  0  для  к  =  1 ,  столбцы ( ) С [ i ,  j ]  =  C [ i ,  j ]  +  A [ i ,  k ] * B [ k ,  j ]  вернуть  C  иначе  выведите  «ошибка, несовместимые размеры».

История [ править ]

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

Беллман объясняет причину термина динамическое программирование в своей автобиографии Eye of the Hurricane: An Autobiography :

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

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

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

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

Алгоритмы, использующие динамическое программирование [ править ]

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

См. Также [ править ]

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

Ссылки [ править ]

Дальнейшее чтение [ править ]

• Адда, Джером; Купер, Рассел (2003), Dynamic Economics , MIT Press. Доступное введение в динамическое программирование в экономике. Код MATLAB для книги .
• Беллмана, Ричард (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 .; Штеффен, P. (2004), "дисциплина динамического программирования над последовательностью данных" (PDF) , Наука компьютерного программирования , 51 (3): 215-263, DOI : 10.1016 / j.scico.2003.12.005.
• Мейн, Шон (2007), Методы управления для сложных сетей , Cambridge University Press, ISBN 978-0-521-88441-9, архивировано из оригинала 19.06.2010.
• Шритаран, СС (1991). «Динамическое программирование уравнений Навье-Стокса». Системы и контрольные письма . 16 (4): 299–307. DOI : 10.1016 / 0167-6911 (91) 90020-F .
• Стоки, Нэнси ; Лукас, Роберт Э .; Прескотт, Эдвард (1989), Рекурсивные методы в экономической динамике , Гарвардский университет. Пресса, ISBN 978-0-674-75096-8.

Внешние ссылки [ править ]

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

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