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

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

С точки зрения динамического программирования, Алгоритм Дейкстры для проблема кратчайшего пути представляет собой схему последовательного приближения, которая решает функциональное уравнение динамического программирования для задачи кратчайшего пути с помощью Достижение метод.^[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 (п ^ {2})}$ время для больших n из-за сложения двух целых чисел с ${ Displaystyle Omega (п)}$ бит каждый занимает ${ Displaystyle Omega (п)}$ время. (The п^th число Фибоначчи имеет ${ Displaystyle Omega (п)}$ бит.) Также существует закрытая форма для последовательности Фибоначчи, известная как формула Бине, откуда ${ displaystyle n}$-й семестр может быть вычислен примерно в ${ Displaystyle О (п ( журнал п) ^ {2})}$ время, что более эффективно, чем описанный выше метод динамического программирования. Однако простое повторение прямо дает матричная форма что приводит к примерно ${ Displaystyle О (п журнал п)}$ алгоритм быстро матричное возведение в степень.

Тип сбалансированной матрицы 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 1 & 1 & 0 & 0 1 & 1 & 0 & 0 {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 е ((п / 2, п / 2), (п / 2, п / 2), ldots (п / 2, п / 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),

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

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

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

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

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

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

${ Displaystyle д (А) = мин (д (В), д (С), д (D)) + с (А) ,}$

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

${ displaystyle q (i, j) = { begin {cases} infty & j <1 { text {или}} 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 {в противном случае.}} 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 О (нк ^ {2})}$ время с раствором DP. Это можно улучшить до ${ Displaystyle О (нк  журнал к)}$ время бинарным поиском по оптимальному ${ displaystyle x}$ в приведенном выше повторении, поскольку ${ Displaystyle W (п-1, х-1)}$ увеличивается в ${ displaystyle x}$ в то время как ${ Displaystyle W (п, к-х)}$ уменьшается в ${ displaystyle x}$, таким образом, локальный минимум ${ Displaystyle  макс (W (п-1, х-1), W (п, к-х))}$ это глобальный минимум. Кроме того, сохраняя оптимальные ${ displaystyle x}$ для каждой ячейки в таблице DP и со ссылкой на ее значение для предыдущей ячейки оптимальное ${ displaystyle x}$ для каждой ячейки можно найти за постоянное время, улучшая его до ${ Displaystyle О (нк)}$ время. Однако есть еще более быстрое решение, которое предполагает другую параметризацию проблемы:
Позволять ${ displaystyle k}$ быть общим количеством этажей, на которых яйца разбиваются при падении с ${ displaystyle k}$-го этажа (приведенный выше пример эквивалентен взятию ${ displaystyle k = 37}$).
Позволять ${ displaystyle m}$ быть минимальным этажом, с которого нужно уронить яйцо, чтобы разбить его.
Позволять ${ Displaystyle f (т, п)}$ быть максимальным количеством значений ${ displaystyle m}$ которые различимы с помощью ${ displaystyle t}$ пытается и ${ displaystyle n}$ яйца.
потом ${ Displaystyle f (t, 0) = f (0, n) = 1}$ для всех ${ Displaystyle т, п  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 е (т, п) = е (т-1, п-1) + е (т-1, п)}$.
Тогда задача эквивалентна нахождению минимума ${ displaystyle x}$ такой, что ${ Displaystyle е (х, п)  geq k}$.
Для этого мы могли бы вычислить ${ Displaystyle  {е (т, я): 0  Leq я  Leq п }}$ в порядке увеличения ${ displaystyle t}$, который займет ${ displaystyle O (nx)}$ время.
Таким образом, если рассматривать отдельно случай ${ Displaystyle п = 1}$, алгоритм примет ${ Displaystyle О (п { sqrt {k}})}$ время.
Но на самом деле рекуррентное соотношение может быть разрешено, давая ${ Displaystyle е (т, п) =  сумма _ {я = 0} ^ {п} { бином {т} {я}}}$, который можно вычислить в ${ Displaystyle О (п)}$ время, используя личность ${ displaystyle { binom {t} {я + 1}} = { binom {t} {i}} { frac {t-i} {я + 1}}}$ для всех ${ displaystyle i  geq 0}$.
поскольку ${ Displaystyle е (т, п)  leq е (т + 1, п)}$ для всех ${ Displaystyle т  geq 0}$, мы можем выполнять двоичный поиск по ${ displaystyle t}$ найти ${ displaystyle x}$, давая ${ Displaystyle О (п  журнал к)}$ алгоритм.[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 (А_ {1}  раз А_ {2})  раз А_ {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 (Помогите)
^ а б c Эдди, С. (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.
внешние ссылки








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