Основы динамического программирования. Всё, что вы хотели знать о динамическом программировании, но боялись спросить
Допустим, есть задача, которую мы уже решили динамическим программированием, например, извечные числа Фибоначчи.
Давайте немного переформулируем её. Пусть у нас есть вектор , из которого мы хотим получить вектор . Чуть-чуть раскроем формулы: . Можно заметить, что из вектора можно получить вектор 
путем умножения на какую-то матрицу, ведь в итоговом векторе фигурируют только сложенные переменные из первого вектора. Эту матрицу легко вывести, вот она: 
. Назовём её матрицей перехода.
Это значит, что если взять вектор 
и умножить его на матрицу перехода n - 1 раз, то получим вектор , в котором лежит fib[n] - ответ на задачу.
А теперь, зачем всё это надо. Умножение матриц обладает свойством ассоциативности, то есть (но при этом не обладает коммутативностью, что по-моему удивительно). Это свойство даёт нам право сделать так: .
Это хорошо тем, что теперь можно применить метод быстрого возведения в степень , который работает за . Итого мы сумели посчитать N -ое число Фибоначчи за логарифм арифметических операций.
А теперь пример посерьёзнее:
Пример №3: Пилообразная последовательность
Обозначим пилообразную последовательность длины N как последовательность, у которой для каждого не крайнего элемента выполняется условие: он или меньше обоих своих соседей или больше. Требуется посчитать количество пилообразных последовательностей из цифр длины N . Выглядит это как-то так:
Решение
Для начала решение без матрицы перехода:
1) Состояние динамики: dp[n] - количество пилообразных последовательностей длины n , заканчивающихся на цифру last . Причём если less == 0 , то последняя цифра меньше предпоследней, а если less == 1 , значит больше.
2) Начальные значения:
for last in range(10):
dp = 9 - last
dp = last
3) Пересчёт динамики:
for prev in range(10):
if prev > last:
dp[n] += dp
if prev < last:
dp[n] += dp
4) Порядок пересчёта: мы всегда обращаемся к предыдущей длине, так что просто пара вложенных for "ов.
5) Ответ - это сумма dp[N] .
Теперь надо придумать начальный вектор и матрицу перехода к нему. Вектор, кажется, придумывается быстро: все состояния, обозначающие длину последовательности N . Ну а матрица перехода выводится, смотря на формулы пересчёта.
Вектор и матрица перехода
Динамика по подотрезкам
Это класс динамики, в котором состояние - это границы подотрезка какого-нибудь массива. Суть в том, чтобы подсчитать ответы для подзадач, основывающихся на всех возможных подотрезках нашего массива. Обычно перебираются они в порядке увеличения длины, и пересчёт основывается, соответственно на более коротких отрезках.Пример №4: Запаковка строки
Вот Развернутое условие . Я вкратце его перескажу:Определим сжатую строку:
1) Строка состоящая только из букв - это сжатая строка. Разжимается она в саму себя.
2) Строка, являющаяся конкатенацией двух сжатых строк A и B . Разжимается она в конкатенацию разжатых строк A и B .
3) Строка D(X) , где D - целое число, большее 1 , а X - сжатая строка. Разжимается она в конкатенацию D строк, разжатых из X .
Пример: “3(2(A)2(B))C” разжимается в “AABBAABBAABBC” .
Необходимо по строке s узнать длину самой короткой сжатой строки, разжимающийся в неё.
Решение
Решается эта задача, как вы уже наверняка догадались, динамикой по подотрезкам.
1) Состояние динамики: d[l][r] - сжатая строка минимальной длины, разжимающаяся в строку s
2) Начальные состояния: все подстроки длины один можно сжать только в них самих.
3) Пересчёт динамики:
У лучшего ответа есть какая-то последняя операция сжатия: либо это просто строка из заглавных букв, или это конкатенация двух строк, или само сжатие. Так давайте переберём все варианты и выберем лучший.
Dp_len = r - l
dp[l][r] = dp_len # Первый вариант сжатия - просто строка.
for i in range(l + 1, r):
dp[l][r] = min(dp[l][r], dp[l][i] + dp[i][r]) # Попробовать разделить на две сжатые подстроки
for cnt in range(2, dp_len):
if (dp_len % cnt == 0): # Если не делится, то нет смысла пытаться разделить
good = True
for j in range(1, (dp_len / cnt) + 1): # Проверка на то, что все cnt подстрок одинаковы
good &= s == s
if good: # Попробовать разделить на cnt одинаковых подстрок и сжать
dp[l][r] = min(dp[l][r], len(str(cnt)) + 1 + dp[l] + 1)
4) Порядок пересчёта: прямой по возрастанию длины подстроки или ленивая динамика.
5) Ответ лежит в d .
Пример №5: Дубы
Динамика по поддеревьям
Параметром состояния динамики по поддеревьям обычно бывает вершина, обозначающая поддерево, в котором эта вершина - корень. Для получения значения текущего состояния обычно нужно знать результаты всех своих детей. Чаще всего реализуют лениво - просто пишут поиск в глубину из корня дерева.Пример №6: Логическое дерево
Дано подвешенное дерево, в листьях которого записаны однобитовые числа - 0 или 1 . Во всех внутренних вершинах так же записаны числа, но по следующему правилу: для каждой вершины выбрана одна из логических операций: «И» или «ИЛИ». Если это «И», то значение вершины - это логическое «И» от значений всех её детей. Если же «ИЛИ», то значение вершины - это логическое «ИЛИ» от значений всех её детей.
Требуется найти минимальное количество изменений логических операций во внутренних вершинах, такое, чтобы изменилось значение в корне или сообщить, что это невозможно.
Решение
1) Состояние динамики: d[v][x] - количество операций, требуемых для получения значения x в вершине v . Если это невозможно, то значение состояния - +inf .
2) Начальные значения: для листьев, очевидно, что своё значение можно получить за ноль изменений, изменить же значение невозможно, то есть возможно, но только за +inf операций.
3) Формула пересчёта:
Если в этой вершине уже значение x , то ноль. Если нет, то есть два варианта: изменить в текущей вершине операцию или нет. Для обоих нужно найти оптимальный вариант и выбрать наилучший.
Если операция «И» и нужно получить «0», то ответ это минимум из значений d[i] , где i - сын v .
Если операция «И» и нужно получить «1», то ответ это сумма всех значений d[i] , где i - сын v .
Если операция «ИЛИ» и нужно получить «0», то ответ это сумма всех значений d[i] , где i - сын v .
Если операция «ИЛИ» и нужно получить «1», то ответ это минимум из значений d[i] , где i - сын v .
4) Порядок пересчёта: легче всего реализуется лениво - в виде поиска в глубину из корня.
5) Ответ - d xor 1] .
Динамика по подмножествам
В динамике по подмножествам обычно в состояние входит маска заданного множества. Перебираются чаще всего в порядке увеличения количества единиц в этой маске и пересчитываются, соответственно, из состояний, меньших по включению. Обычно используется ленивая динамика, чтобы специально не думать о порядке обхода, который иногда бывает не совсем тривиальным.Пример №7: Гамильтонов цикл минимального веса, или задача коммивояжера
Задан взвешенный (веса рёбер неотрицательны) граф G размера N . Найти гамильтонов цикл (цикл, проходящий по всем вершинам без самопересечений) минимального веса.Решение
Так как мы ищем цикл, проходящий через все вершины, то можно выбрать за «начальную» вершину любую. Пусть это будет вершина с номером 0 .
1) Состояние динамики: dp[v] - путь минимального веса из вершины 0 в вершину v , проходящий по всем вершинам, лежащим в mask и только по ним.
2) Начальные значения: dp = 0 , все остальные состояния изначально - +inf .
3) Формула пересчёта: Если i -й бит в mask равен 1 и есть ребро из i в v , то:
dp[v] = min(dp[v], dp[i] + w[i][v])
Где w[i][v] - вес ребра из i в v .
4) Порядок пересчёта: самый простой и удобный способ - это написать ленивую динамику, но можно поизвращаться и написать перебор масок в порядке увеличения количества единичных битов в ней.
5) Ответ лежит в d[(1 << N) - 1] .
Динамика по профилю
Классическими задачами, решающимися динамикой по профилю, являются задачи на замощение поля какими-нибудь фигурами. Причём спрашиваться могут разные вещи, например, количество способов замощения или замощение минимальным количеством фигур.Эти задачи можно решить полным перебором за , где a - количество вариантов замощения одной клетки. Динамика по профилю же оптимизирует время по одной из размерностей до линейной, оставив от себя в экспоненте только коэффициент. Получится что-то такое: .
Профиль - это k (зачастую один) столбцов, являющиеся границей между уже замощённой частью и ещё не замощённой. Эта граница заполнена только частично. Очень часто является частью состояния динамики.
Почти всегда состояние - это профиль и то, где этот профиль. А переход увеличивает это местоположение на один. Узнать, можно ли перейти из одного профиля в другой можно за линейное от размера профиля время. Это можно проверять каждый раз во время пересчёта, но можно и предподсчитать. Предподсчитывать будем двумерный массив can - можно ли от одной маски перейти к другой, положив несколько фигурок, увеличив положение профиля на один. Если предподсчитывать, то времени на выполнение потребуется меньше, а памяти - больше.
Пример №8: Замощение доминошками
Найти количество способов замостить таблицу N x M с помощью доминошек размерами 1 x 2 и 2 x 1 .Решение
Здесь профиль - это один столбец. Хранить его удобно в виде двоичной маски: 0 - не замощенная клетка столбца, 1 - замощенная. То есть всего профилей .
0) Предподсчёт (опционально): перебрать все пары профилей и проверить, что из одного можно перейти в другой. В этой задаче это проверяется так:
Если в первом профиле на очередном месте стоит 1 , значит во втором обязательно должен стоять 0 , так как мы не сможем замостить эту клетку никакой фигуркой.
Если в первом профиле на очередном месте стоит 0 , то есть два варианта - или во втором 0 или 1 .
Если 0 , это значит, что мы обязаны положить вертикальную доминошку, а значит следующую клетку можно рассматривать как 1 . Если 1 , то мы ставим вертикальную доминошку и переходим к следующей клетке.
Примеры переходов (из верхнего профиля можно перейти в нижние и только в них):
После этого сохранить всё в массив can - 1 , если можно перейти, 0 - если нельзя.
1) Состояние динамики: dp - количество полных замощений первых pos - 1 столбцов с профилем mask .
2) Начальное состояние: dp = 1 - левая граница поля - прямая стенка.
3) Формула пересчёта:
dp += dp * can
4) Порядок обхода - в порядке увеличения pos .
5) Ответ лежит в dp.
Полученная асимптотика - .
Динамика по изломанному профилю
Это очень сильная оптимизация динамики по профилю. Здесь профиль - это не только маска, но ещё и место излома. Выглядит это так:
Теперь, после добавления излома в профиль, можно переходить к следующему состоянию, добавляя всего одну фигурку, накрывающую левую клетку излома. То есть увеличением числа состояний в N раз (надо помнить, где место излома) мы сократили число переходов из одного состояния в другое с до . Асимптотика улучшилась с до 
.
Переходы в динамике по изломанному профилю на примере задачи про замощение доминошками (пример №8):
Восстановление ответа
Иногда бывает, что просто знать какую-то характеристику лучшего ответа недостаточно. Например, в задаче «Запаковка строки» (пример №4) мы в итоге получаем только длину самой короткой сжатой строки, но, скорее всего, нам нужна не её длина, а сама строка. В таком случае надо восстановить ответ.В каждой задаче свой способ восстановления ответа, но самые распространенные:
- Рядом со значением состояния динамики хранить полный ответ на подзадачу. Если ответ - это что-то большое, то может понадобиться чересчур много памяти, поэтому если можно воспользоваться другим методом, обычно так и делают.
- Восстанавливать ответ, зная предка(ов) данного состояния. Зачастую можно восстановить ответ, зная только как он был получен. В той самой «Запаковке строки» можно для восстановления ответа хранить только вид последнего действия и то, из каких состояний оно было получено.
- Есть способ, вообще не использующий дополнительную память - после пересчёта динамики пойти с конца по лучшему пути и по дороге составлять ответ.
Небольшие оптимизации
Память
Зачастую в динамике можно встретить задачу, в которой состояние требует быть посчитанными не очень большое количество других состояний. Например, при подсчёте чисел Фибоначчи мы используем только два последних, а к предыдущим уже никогда не обратимся. Значит, можно про них забыть, то есть не хранить в памяти. Иногда это улучшает асимптотическую оценку по памяти. Этим приёмом можно воспользоваться в примерах №1, №2, №3 (в решении без матрицы перехода), №7 и №8. Правда, этим никак не получится воспользоваться, если порядок обхода - ленивая динамика.Время
Иногда бывает так, что можно улучшить асимптотическое время, используя какую-нибудь структуру данных. К примеру, в алгоритме Дейкстры можно воспользоваться очередью с приоритетами для изменения асимптотического времени.Замена состояния
В решениях динамикой обязательно фигурирует состояние - параметры, однозначно задающие подзадачу, но это состояние не обязательно одно единственное. Иногда можно придумать другие параметры и получить с этого выгоду в виде снижения асимптотического времени или памяти.Пример №9: Разложение числа
Требуется найти количество разложений числа N на различные слагаемые. Например, если N = 7 , то таких разложений 5:- 3 + 4
- 2 + 5
- 1 + 7
- 1 + 2 + 4
Динамическое программирование - тема, которой в рунете посвящено довольно мало статей, поэтому мы решили ею заняться. В этой статье будут разобраны классические задачи на последовательности, одномерную и двумерную динамику, будет дано обоснование решениям и описаны разные подходы к их реализации. Весь приведённый в статье код написан на Java.
О чём вообще речь? Что такое динамическое программирование?
Метод решения задачи путём её разбиения на несколько одинаковых подзадач, рекуррентно связанных между собой. Самым простым примером будут числа Фибоначчи - чтобы вычислить некоторое число в этой последовательности, нам нужно сперва вычислить третье число, сложив первые два, затем четвёртое таким же образом
на основе второго и третьего, и так далее (да, мы слышали про замкнутую формулу).
Хорошо, как это использовать?
Решение задачи динамическим программированием должно содержать следующее:
И что, мне для решения рекурсивный метод писать надо? Я слышал, они медленные.
Конечно, не надо, есть и другие подходы к реализации динамики. Разберём их на примере следующей задачи:
Вычислить n-й член последовательности, заданной формулами:
a 2n = a n + a n-1 ,
a 2n+1 = a n — a n-1 ,
a 0 = a 1 = 1.
Идея решения
Здесь нам даны и начальные состояния (a 0 = a 1 = 1), и зависимости. Единственная сложность, которая может возникнуть - понимание того, что 2n - условие чётности числа, а 2n+1 - нечётности. Иными словами, нам нужно проверять, чётно ли число, и считать его в зависимости от этого по разным формулам.
Рекурсивное решение
Очевидная реализация состоит в написании следующего метода:
Private static int f(int n){ if(n==0 || n==1) return 1; // Проверка на начальное значение if(n%2==0){ //Проверка на чётность return f(n/2)+f(n/2-1); // Вычисляем по формуле для чётных индексов, // ссылаясь на предыдущие значения }else{ return f((n-1)/2)-f((n-1)/2-1); // Вычисляем по формуле для нечётных //индексов, ссылаясь на предыдущие значения } }
И она отлично работает, но есть нюансы. Если мы захотим вычислить f(12) , то метод будет вычислять сумму f(6)+f(5) . В то же время, f(6)=f(3)+f(2) и f(5)=f(2)-f(1) , т.е. значение f(2) мы будем вычислять дважды. Спасение от этого есть - мемоизация (кеширование значений).
Рекурсивное решение с кэшированием значений
Идея мемоизации очень проста - единожды вычисляя значение, мы заносим его в какую-то структуру данных. Перед каждым вычислением мы проверяем, есть ли вычисляемое значение в этой структуре, и если есть, используем его. В качестве структуры данных можно использовать массив, заполненный флаговыми значениями. Если значение элемента по индексу N равно значению флага, значит, мы его ещё не вычисляли. Это создаёт определённые трудности, т.к. значение флага не должно принадлежать множеству значений функции, которое не всегда очевидно. Лично я предпочитаю использовать хэш-таблицу - все действия в ней выполняются за O(1) , что очень удобно. Однако, при большом количестве значений два числа могут иметь одинаковый хэш, что, естественно, порождает проблемы. В таком случае стоит использовать, например, красно-чёрное дерево .
Для уже написанной функции f(int) кэширование значений будет выглядеть следующим образом:
Private static HashMap
Не слишком сложно, согласитесь? Зато это избавляет от огромного числа операций. Платите вы за это лишним расходом памяти.
Последовательное вычисление
Теперь вернёмся к тому, с чего начали - рекурсия работает медленно. Не слишком медленно, чтобы это приносило действительные неприятности в настоящей жизни, но на соревнованиях по спортивному программированию каждая миллисекунда на счету.
Метод последовательного вычисления подходит, только если функция ссылается исключительно на элементы перед ней - это его основной, но не единственный минус. Наша задача этому условию удовлетворяет.
Суть метода в следующем: мы создаём массив на N элементов и последовательно заполняем его значениями. Вы, наверное, уже догадались, что таким образом мы можем вычислять в том числе те значения, которые для ответа не нужны. В значительной части задач на динамику этот факт можно опустить, так как для ответа часто бывают нужны как раз все значения. Например, при поиске наименьшего пути мы не можем не вычислять путь до какой-то точки, нам нужно пересмотреть все варианты. Но в нашей задаче нам нужно вычислять приблизительно log 2 (N) значений (на практике больше), для 922337203685477580-го элемента (MaxLong/10) нам потребуется 172 вычисления.
Private static int f(int n){
if(n<2) return 1; //Может, нам и вычислять ничего не нужно?
int fs = int[n]; //Создаём массив для значений
fs=fs=1; //Задаём начальные состояния
for(int i=2; i Ещё одним минусом такого подхода является сравнительно большой расход памяти. Сейчас нам предстоит, по сути, написать свою собственную рекурсию. Идея состоит в следующем - сначала мы проходим «вниз» от N до начальных состояний, запоминая аргументы, функцию от которых нам нужно будет вычислять. Затем возвращаемся «вверх», последовательно вычисляя значения от этих аргументов, в том порядке, который мы записали. Зависимости вычисляются следующим образом: LinkedList Полученный размер стека – то, сколько вычислений нам потребуется сделать. Именно так я получил упомянутое выше число 172. Теперь мы поочередно извлекаем индексы и вычисляем для них значения по формулам – гарантируется, что все необходимые значения уже будут вычислены. Хранить будем как раньше – в хэш-таблице. HashMap Все необходимые значения вычислены, осталось только написать Return values.get(n);
Конечно, такое решение гораздо более трудоёмкое, однако это того стоит. Для больше ясности разберём следующую задачу на одномерную динамику: На вершине лесенки, содержащей N ступенек, находится мячик, который начинает прыгать по ним вниз, к основанию. Мячик может прыгнуть на следующую ступеньку, на ступеньку через одну или через 2. (То есть, если мячик лежит на 8-ой ступеньке, то он может переместиться на 5-ую, 6-ую или 7-ую.) Определить число всевозможных «маршрутов» мячика с вершины на землю. На первую ступеньку можно попасть только одним образом - сделав прыжок с длиной равной единице. На вторую ступеньку можно попасть сделав прыжок длиной 2, или с первой ступеньки - всего 2 варианта. На третью ступеньку можно попасть сделав прыжок длиной три, с первой или со втрой ступенек. Т.е. всего 4 варианта (0->3; 0->1->3; 0->2->3; 0->1->2->3). Теперь рассмотрим четвёртую ступеньку. На неё можно попасть с первой ступеньки - по одному маршруту на каждый маршрут до неё, со второй или с третьей - аналогично. Иными словами, количество путей до 4-й ступеньки есть сумма маршрутов до 1-й, 2-й и 3-й ступенек. Математически выражаясь, F(N) = F(N-1)+F(N-2)+F(N-3) . Первые три ступеньки будем считать начальными состояниями. Здесь ничего хитрого нет. Исходя из того, что, по большому счёту, простое решение на массиве из N элементов очевидно, я продемонстрирую тут решение на массиве всего из трёх. Int vars = new int;
vars=1;vars=2;vars=4;
for(int i=3; i Так как каждое следующее значение зависит только от трёх предыдущих, ни одно значение под индексом меньше i-3 нам бы не пригодилось. В приведённом выше коде мы записываем новое значение на место самого старого, не нужного больше. Цикличность остатка от деления на 3 помогает нам избежать кучи условных операторов. Просто, компактно, элегантно. С двумерной динамикой не связано никаких особенностей, однако я, на всякий случай, рассмотрю здесь одну задачу и на неё. В прямоугольной таблице NxM в начале игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). Посчитайте, сколько есть способов у игрока попасть в правую нижнюю клетку. Логика решения полностью идентична таковой в задаче про мячик и лестницу - только теперь в клетку (x,y) можно попасть из клеток (x-1,y) или (x, y-1) . Итого F(x,y) = F(x-1, y)+F(x,y-1) . Дополнительно можно понять, что все клетки вида (1,y) и (x,1) имеют только один маршрут - по прямой вниз или по прямой вправо. Ради всего святого, не нужно делать двумерную динамику через рекурсию. Уже было упомянуто, что рекурсия менее выгодна, чем цикл по быстродействию, так двумерная рекурсия ещё и читается ужасно. Это только на таком простом примере она смотрится легко и безобидно. Private static int f(int i, int j) {
if(i==1 || j==1) return 1;
return f(i-1, j)+f(i, j-1);
}
В заключение приведу ряд типичных задач на одномерную и двумерную динамику, разборы прилагаются. При переработке радиоактивных материалов образуются отходы двух видов - особо опасные (тип A) и неопасные (тип B). Для их хранения используются одинаковые контейнеры. После помещения отходов в контейнеры последние укладываются вертикальной стопкой. Стопка считается взрывоопасной, если в ней подряд идет более одного контейнера типа A. Стопка считается безопасной, если она не является взрывоопасной. Для заданного количества контейнеров N определить количество возможных типов безопасных стопок. Ответом является (N+1)-е число Фибоначчи. Догадаться можно было, просто вычислив 2-3 первых значения. Строго доказать можно было, построив дерево возможных построений. Каждый основной элемент делится на два - основной (заканчивается на B) и побочный (заканчивается на A). Побочные элементы превращаются в основные за одну итерацию (к последовательности, заканчивающейся на A, можно дописать только B). Это характерно для чисел Фибоначчи. Например, так: //Ввод числа N с клавиатуры
N+=2;
BigInteger fib = new BigInteger;
fib=fib=BigInteger.ONE;
for(int i=2; i Мальчик подошел к платной лестнице. Чтобы наступить на любую ступеньку, нужно заплатить указанную на ней сумму. Мальчик умеет перешагивать на следующую ступеньку, либо перепрыгивать через ступеньку. Требуется узнать, какая наименьшая сумма понадобится мальчику, чтобы добраться до верхней ступеньки. Очевидно, что сумма, которую мальчик отдаст на N-ой ступеньке, есть сумма, которую он отдал до этого плюс стоимость самой ступеньки. «Сумма, которую он отдал до этого» зависит от того, с какой ступеньки мальчик шагает на N-ую - с (N-1)-й или с (N-2)-й. Выбирать нужно наименьшую. Например, так: Int Imax;
//*ввод с клавиатуры числа ступенек*
DP = new int;
for(int i=0; i Имеется калькулятор, который выполняет три операции: Определите, какое наименьшее число операций необходимо для того, чтобы получить из числа 1 заданное число N. Выведите это число, и, на следующей строке, набор исполненных операций вида «111231». Наивное решение состоит в том, чтобы делить число на 3, пока это возможно, иначе на 2, если это возможно, иначе вычитать единицу, и так до тех пор, пока оно не обратится в единицу. Это неверное решение, т.к. оно исключает, например, возможность убавить число на единицу, а затем разделить на три, из-за чего на больших числах (например, 32718) возникают ошибки. Правильное решение заключается в нахождении для каждого числа от 2 до N минимального количества действий на основе предыдущих элементов, иначе говоря: F(N) = min(F(N-1), F(N/2), F(N/3)) + 1 . Следует помнить, что все индексы должны быть целыми. Для воссоздания списка действий необходимо идти в обратном направлении и искать такой индекс i, что F(i)=F(N) , где N - номер рассматриваемого элемента. Если i=N-1 , записываем в начало строки 1, если i=N/2 - двойку, иначе - тройку. В каждой клетке прямоугольной таблицы N*M записано некоторое число. Изначально игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). При проходе через клетку с игрока берут столько килограммов еды, какое число записано в этой клетке (еду берут также за первую и последнюю клетки его пути). Требуется найти минимальный вес еды в килограммах, отдав которую игрок может попасть в правый нижний угол. ), выглядящим как набор перекрывающихся подзадач, сложность которых чуть меньше исходной. В этом случае время вычислений, по сравнению с «наивными» методами, можно значительно сократить. Ключевая идея в динамическом программировании достаточно проста. Как правило, чтобы решить поставленную задачу, требуется решить отдельные части задачи (подзадачи), после чего объединить решения подзадач в одно общее решение. Часто многие из этих подзадач одинаковы. Подход динамического программирования состоит в том, чтобы решить каждую подзадачу только один раз, сократив тем самым количество вычислений. Это особенно полезно в случаях, когда число повторяющихся подзадач экспоненциально велико. Метод динамического программирования сверху
- это простое запоминание результатов решения тех подзадач, которые могут повторно встретиться в дальнейшем. Динамическое программирование снизу
включает в себя переформулирование сложной задачи в виде рекурсивной последовательности более простых подзадач. Словосочетание «динамическое программирование» впервые было использовано в -х годах Р. Беллманом для описания процесса нахождения решения задачи, где ответ на одну задачу может быть получен только после решения задачи, «предшествующей» ей. В г. он уточнил это определение до современного. Первоначально эта область была основана, как системный анализ и инжиниринг, которая была признана IEEE . Вклад Беллмана в динамическое программирование был увековечен в названии уравнения Беллмана , центрального результата теории динамического программирования, который переформулирует оптимизационную задачу в рекурсивной форме. Слово «программирование» в словосочетании «динамическое программирование» в действительности к "традиционному" программированию (написанию кода) почти никакого отношения не имеет и имеет смысл как в словосочетании «математическое программирование », которое является синонимом слова «оптимизация». Поэтому слово «программа» в данном контексте скорее означает оптимальную последовательность действий для получения решения задачи. К примеру, определенное расписание событий на выставке иногда называют программой. Программа в данном случае понимается как допустимая последовательность событий. Нахождение кратчайшего пути в графе из одной вершины в другую, используя оптимальную подструктуру; прямая линия обозначает простое ребро; волнистая линия обозначает кратчайший путь между вершинами, которые она соединяет (промежуточные вершины пути не показаны); жирной линией обозначен итоговый кратчайший путь. Оптимальная подструктура
в динамическом программировании означает, что оптимальное решение подзадач меньшего размера может быть использовано для решения исходной задачи. К примеру, кратчайший путь в графе из одной вершины (обозначим s) в другую (обозначим t) может быть найден так: сначала считаем кратчайший путь из всех вершин, смежных с s, до t, а затем, учитывая веса ребер, которыми s соединена со смежными вершинами, выбираем лучший путь до t (через какую вершину лучше всего пойти). В общем случае мы можем решить задачу, в которой присутствует оптимальная подструктура, проделывая следующие три шага. Подзадачи решаются делением их на подзадачи ещё меньшего размера и т. д., пока не приходят к тривиальному случаю задачи, решаемой за константное время (ответ можно сказать сразу). К примеру, если нам нужно найти n!, то тривиальной задачей будет 1! = 1 (или 0! = 1). Перекрывающиеся подзадачи
в динамическом программировании означают подзадачи, которые используются для решения некоторого количества задач (не одной) большего размера (то есть мы несколько раз проделываем одно и то же). Ярким примером является вычисление последовательности Фибоначчи , и - даже в таком тривиальном случае вычисления всего двух чисел Фибоначчи мы уже посчитали дважды. Если продолжать дальше и посчитать , то посчитается ещё два раза, так как для вычисления будут нужны опять и . Получается следующее: простой рекурсивный подход будет расходовать время на вычисление решение для задач, которые он уже решал. Чтобы избежать такого хода событий мы будем сохранять решения подзадач, которые мы уже решали, и когда нам снова потребуется решение подзадачи, мы вместо того, чтобы вычислять его заново, просто достанем его из памяти. Этот подход называется кэширование . Можно проделывать и дальнейшие оптимизации - например, если мы точно уверены, что решение подзадачи нам больше не потребуется, можно выкинуть его из памяти, освободив её для других нужд, или если процессор простаивает и мы знаем, что решение некоторых, ещё не посчитанных подзадач, нам понадобится в дальнейшем, мы можем решить их заранее. Подводя итоги вышесказанного можно сказать, что динамическое программирование пользуется следующими свойствами задачи: Динамическое программирование обычно придерживается двух подходов к решению задач: Языки программирования могут запоминать результат вызова функции с определенным набором аргументов (мемоизация), чтобы ускорить «вычисление по имени». В некоторых языках такая возможность встроена (например, Scheme , Common Lisp , Perl), а в некоторых требует дополнительных расширений (C++). Известны сериальное динамическое программирование, включённое во все учебники по исследованию операций , и несериальное динамическое программирование (НСДП), которое в настоящее время слабо известно, хотя было открыто в 1960-х годах. Обычное динамическое программирование является частным случаем несериального динамического программирования, когда граф взаимосвязей переменных - просто путь. НСДП, являясь естественным и общим методом для учета структуры задачи оптимизации, рассматривает множество ограничений и/или целевую функцию как рекурсивно вычислимую функцию. Это позволяет находить решение поэтапно, на каждом из этапов используя информацию, полученную на предыдущих этапах, причём эффективность этого алгоритма прямо зависит от структуры графа взаимосвязей переменных. Если этот граф достаточно разрежен, то объём вычислений на каждом этапе может сохраняться в разумных пределах. Одним из основных свойств задач, решаемых с помощью динамического программирования, является аддитивность . Неаддитивные задачи решаются другими методами. Например, многие задачи по оптимизации инвестиций компании являются неаддитивными и решаются с помощью сравнения стоимости компании при проведении инвестиций и без них. Wikimedia Foundation
.
2010
.
динамическое программирование
- — [Е.С.Алексеев, А.А.Мячев. Англо русский толковый словарь по системотехнике ЭВМ. Москва 1993] динамическое программирование Раздел математического программирования, совокупность приемов, позволяющих находить оптимальные решения, основанные … Справочник технического переводчика
Динамическое программирование
- раздел математического программирования, совокупность приемов, позволяющих находить оптимальные решения, основанные на вычислении последствий каждого решения и выработке оптимальной стратегии для последующих решений.… … Экономико-математический словарь
Раздел математики, посвященный теории и методам решения многошаговых задач оптимального управления. В Д. п. для управляемых процессов среди всевозможных управлений ищется то, к рое доставляет экстремальное (наименьшее или наибольшее) значение… … Математическая энциклопедия
Раздел математики, посвящённый теории и методам решения многошаговых задач оптимального управления (См. Оптимальное управление). В Д. п. для управляемых процессов среди всех возможных управлений ищется то, которое доставляет… … Большая советская энциклопедия
динамическое программирование
- dinaminis programavimas statusas T sritis automatika atitikmenys: angl. dynamic programming vok. dynamische Programmierung, f rus. динамическое программирование, n pranc. programmation dynamique, f … Automatikos terminų žodynas
Раздел математич. программирования, изучающий многошаговые процессы поиска оптим. решения сложных задач. Применяется при составлении программ решения таких задач оптимизации, для к рых процесс поиска решения можно представить в виде нек рой… … Большой энциклопедический политехнический словарь
На уроке будет рассмотрено понятие динамического программирования и исторический аспект его появления. Рассмотрены задачи динамического программирования и некоторые примеры их решения Само понятие «динамическое программирование» впервые было использовано в 1940-х годах Ричардом Беллманом для описания процесса нахождения решения задачи, где ответ на одну задачу может быть получен только после решения другой задачи, «предшествующей» ей. Позднее формулировка понятия была доработана и усовершенствованна до современного вида самим же Беллманом. Слово «программирование»
в контексте «динамическое программирование» на самом деле к классическому пониманию программирования (написанию кода на языке программирования) практически никакого отношения не имеет
. Слово «Программирование» имеет такой же смысл как в словосочетании «математическое программирование», которое является синонимом слова «оптимизация». Поэтому программы
будут использоваться в качестве оптимальной последовательности действий для получения решения задачи. В общем же для начала, неформальное определение понятия динамического программирования
может звучать так: Динамическое программирование
— это техника или метод, которая позволяет решать некоторые задачи комбинаторики, оптимизации и другие задачи, обладающие определенным свойством (свойством сооптимальности у подзадач). Задачи оптимизации
, как правило, связаны с задачей максимизации или минимизации той или иной целевой функции (например, максимизировать вероятность того, что система не сломается, максимизировать мат. ожидание получения прибыли и т.д.). Задачи комбинаторики
, как правило, отвечают на вопрос, сколько существует объектов, обладающих теми или иными свойствами, или сколько существует комбинаторных объектов, обладающих заданными свойствами. То есть, ДП решает не все задачи, а лишь некоторые, определенный класс подзадач. Но этот класс подзадачи используется во многих областях знаний: программирование, математика, лингвистика, статистика, теория игр, экономика, в компьютерных науках и т.п. Задачи, решаемые при помощи динамического программирования, должны обладать свойством сооптимальности
, о котором будет сказано в дальнейших уроках. Неформальное объяснение свойства оптимальности у подзадач может быть продемонстрировано с помощью диаграммы: Рис. 1.1. Неформальное объяснение свойства оптимальности у подзадач Более подробно неформальное объяснение рассматривается . Сначала рассмотрим задачи оптимизации (задачи 1-5): Пример:
Есть некоторая карта дорог, представленная в виде графа. Наша цель: добраться из пункта А
в пункт Б
. Это сделать надо так, чтобы минимизировать расстояние или потраченное топливо. Целевой функцией
здесь является расстояние от А
до Б
. Т.е. наша цель — минимизировать расстояние. А что является переменной выбора
? Для того, чтобы найти кратчайший путь, надо каждый раз принимать решения. Т.е. в каждой точке или на каждом перекрестке необходимо принимать решения: куда повернуть или ехать прямо. Важно:
Из этой задачи уже можно увидеть общую структуру задач, решаемых при помощи динамического программирования: в каждой задаче есть целевая функция и переменная выбора
. Пример:
Каждый год мы принимаем решение, ездить ли на старой машине еще год и понести при этом издержки на поддержку и обслуживание старой машины или же продать эту машину и купить новую (и понести при этом издержки на покупку). Целевая функция:
минимизация расходов (либо на издержки на поддержку старого автомобиля, либо на покупку нового). Переменная выбора:
каждый год принимать решение продать машину или оставить. Пример:
Игра на бирже, приобретение акций каких-либо компаний Переменная выбора:
то, какой портфель вложений будет: сколько акций и какой фирмы нам необходимо купить. Пример:
Есть завод, изготавливающий мебель. На заводе работает определенное количество работников, которые могут изготовить соответствующее кол-во определенной мебели (стулья, столы, шкафы и т.п.) Переменная выбора:
выбор того, сколько необходимо изготовить стульев или столов, чтобы хватило рабочей силы. Пример:
Участие в различных играх Переменная выбора здесь зависит от конкретной игры. Задачи 1 — 5 — это примеры задач оптимизации.
Комбинаторика:
Пример:
Задача на решение того, сколько существует деревьев, у которых определенное число листьев; или сколько существует графов для решения такого-то задания и т.п. Пример:
Есть монеты разного достоинства, какими способами можно вернуть сдачу. Это краткое описание задач для динамического программирования, которые подробно будут рассмотрены позднее. Неформальное объяснение оптимальности подзадач ДП.
Рассмотрим неформальную
идею ДП. Итак, возьмем пример с заводом, изготавливающим мебель. Для достижения цели максимизации прибыли необходимо решить множество подзадач:
При большом количестве подзадач сложно понять, как решать такую задачу. Как правило, решить одну малую задачу проще, чем решить большую задачу
, состоящую из маленьких. Поэтому ДП предлагает следующее: Например, завод производит только стулья. У директора стоит задача получения максимальной прибыли с продажи стульев. Часто при постановке задачи кажущимся оптимальным решением является перебор всех возможных вариантов
. Однако, вследствии очень большого количества таких вариантов и, как результат, перегрузки памяти компьютера, такой способ не всегда приемлем. Кроме того, может возникнуть такой вопрос: для того чтобы найти, например, минимум или максимум, почему бы нам не найти производную? или не использовать множества Ла-Гранжа, или другие методы аппарата математического анализа? Зачем нужно ДП, если есть большой арсенал средств? Дело в том, что: В основе динамического программирования лежит идея решения поставленной задачи путем деления ее на отдельные части (подзадачи, этапы), решение этих подзадач и последующего объединения этих решений в одно общее решение. Часто большинство из подзадач абсолютно одинаковы. При этом важно, что при решении более сложной задачи, мы не решаем заново маленькую подзадачу, а используем уже решенный ответ этой подзадачи.
Важно:
По этой причине разделение задачи на подзадачи и решение этих подзадач только один раз (!)
, сокращая этим количество общих вычислений — более оптимальный способ, который и заложен в динамическом программировании Когда мы решаем задачу с производными, множествами Ла-Гранжа и т.п., то мы работаем с непрерывными функциями. При решении же задач ДП мы будем работать в основном с дискретными функциями, поэтому говорить здесь о применении непрерывных функций неуместно. Рассмотрим вариант решения задачи с помощью динамического программирования. Пример:
Необходимо вычислить сумму n чисел: 1 + 2 + 3 + ... + n Попробуем применить к задаче идеи ДП и решить ее, разбивая на простые подзадачи. Простой пример, где пока неоправданно используется ДП (искусственно), демонстрирует принцип идей ДП. Рассмотрим еще один пример. Пример:
имеется лесенка из n ступенек, перед которой находится человек, который за 1
шаг умеет подниматься либо на следующую ступеньку, либо перепрыгивает через одну ступеньку. Вопрос: сколькими способами он может попасть на последнюю ступеньку? Рассмотрим самые простые варианты (подзадачи): Рассмотрим пример из i ступенек
Как мы можем попасть на i ступеньку: Например, как попасть на 4-ю ступеньку
: Т.о., общее количество способов
попасть на i ступеньку: Определим начальные значения
, с которых следует начинать решать задачу. Мы видим, что задача по сути комбинаторная (т.е. количество способов сделать что-либо) свелась к вычислению некоторой рекуррентной последовательности. Задание 1:
реализовать пример для первых десяти ступенек (по сути, первые 10 чисел ряда Фибоначчи), используя рекурсию.
Дополните код:
var c:integer;
procedure getKolSposob(i,n: integer);
begin
writeln (i+n," ");
inc(c);
if ... then
getKolSposob(...,...)
end;
begin
c:=1;
getKolSposob(0,1);
end. Задание 2:
Динамическое программирование (иначе «динамическое планирование») есть особый метод оптимизации решений, специально приспособленный к так называемым «многошаговым» (или «многоэтапным») операциям. Представим себе некоторую операцию О, распадающуюся на ряд последовательных «шагов» или «этапов», - например, деятельность отрасли промышленности в течение ряда хозяйственных лет; или же преодоление группой самолетов нескольких полос противовоздушной обороны; или последовательность тестов, применяемых при контроле аппаратуры. Некоторые операции (подобно вышеприведенным) расчленяются на шаги естественно; в некоторых членение приходится вводить искусственно - скажем, процесс наведения ракеты на цель можно условно разбить на этапы, каждый из которых занимает какое-то время Итак, рассмотрим операцию О, состоящую из шагов (этапов). Пусть эффективность операции характеризуется каким-то показателем W, который мы для краткости будем в этой главе называть «выигрышем». Предположим, что выигрыш W за всю операцию складывается из выигрышей на отдельных шагах: где - выигрыш на i-м шаге. Если W обладает таким свойством, то его называют аддитивным критерием . Операция О, о которой идет речь, представляет собой управляемый процесс, т. е. мы можем выбирать какие-то параметры, влияющие на его ход и исход, причем на каждом шаге выбирается какое-то решение, от которого зависит выигрыш на данном шаге и выигрыш за операцию в целом. Будем называть это решение «шаговым управлением». Совокупность всех шаговых управлений представляет собой управление операцией в целом. Обозначим его буквой , а шаговые управления - буквами : Следует иметь в виду, что в общем случае - не числа, а, может быть, векторы, функции и т. д. Требуется найти такое управление при котором выигрыш W обращается в максимум: То управление при котором этот максимум достигается, будем называть оптимальным управлением. Оно состоит из совокупности оптимальных шаговых управлений: Тот максимальный выигрыш, который достигается при этом управлении, мы будем обозначать : Формула (12.5) читается так: величина W есть максимум из всех при разных управлениях (максимум берется по всем управлениям возможным в данных условиях). Иногда это последнее оговаривается в формуле и пишут: Рассмотрим несколько примеров многошаговых операций и для каждого из них поясним, что понимается под «управлением» и каков «выигрыш» (показатель эффективности) 1. Планируется деятельность группы промышленных предприятий на период хозяйственных лет (-летку). В начале периода на развитие группы выделены какие-то средства которые должны быть как-то распределены между предприятиями. В процессе работы предприятия вложенные в него средства частично расходуются (амортизируются), а частично сохраняются и снова могут быть перераспределены. Каждое предприятие за год приносит доход, зависящий от того, сколько средств в него вложено. В начале каждого хозяйственного года имеющиеся в наличии средства перераспределяются между предприятиями. Ставится вопрос: какое количество средств в начале каждого года нужно выделять каждому предприятию, чтобы суммарный доход за лет был максимальным? Выигрыш W (суммарный доход) представляет собой сумму доходов на отдельных шагах (годах): значит, обладает свойством аддитивности. Управление на шаге состоит в том, что в начале года предприятиям выделяются какие-то средства (первый индекс - номер шага, второй - номер предприятия). Таким образом, шаговое управление есть вектор с к составляющими: Разумеется, величины в формуле (12.6) зависят от количества вложенных в предприятия средств. Управление всей операцией состоит из совокупности всех шаговых управлений: Требуется найти такое распределение средств по предприятиям и по годам (оптимальное управление при котором величина W обращается в максимум. В этом примере шаговые управления были векторами; в последующих примерах они будут проще и выражаться просто числами. 2. Космическая ракета состоит из ступеней, а процесс ее вывода на орбиту - из этапов, в конце каждого из которых очередная ступень сбрасывается. На все ступени (без учета «полезного» веса кабины) выделен какой-то общий вес: где - вес ступени. В результате этапа (сгорания и сбрасывания ступени) ракета получает приращение скорости А, зависящее от веса данной ступени и суммарного веса всех оставшихся плюс вес кабины. Спрашивается, как нужно распределить вес G между ступенями, чтобы, скорость ракеты V при ее выводе на орбиту была максимальна? В данном случае показатель эффективности (выигрыш) будет где А - выигрыш (приращение скорости) на шаге. Управление представляет собой совокупность весов всех ступеней Оптимальным управлением будет то распределение весов по ступеням, при котором скорость V максимальна. В этом примере шаговое управление - одно число, а именно, вес данной ступени. 3. Владелец автомашины эксплуатирует ее в течение лет. В начале каждого года он может принять одно из трех решений: 1) продать машину и заменить ее новой; 2) ремонтировать ее и продолжать эксплуатацию; 3). продолжать эксплуатацию без ремонта. Шаговое управление - выбор одного из этих трех решений. Непосредственно числами они не выражаются, но можно приписать первому численное значение 1, второму 2, третьему 3. Какие нужно принять решения по годам (т. е. как чередовать управления 1, 2,3), чтобы суммарные расходы на эксплуатацию, ремонт и приобретение новых машин были минимальны? Показатель эффективности (в данном случае это не «выигрыш», а «проигрыш», но это неважно) равен где - расходы в i-м году. Величину W требуется обратить в минимум. что означает: первые два года эксплуатировать машину без ремонта, последующие три года ее ремонтировать, в начале шестого года продать, купить новую, затем снова эксплуатировать без ремонта и т. д. Любое управление представляет собой вектор (совокупность чисел): где каждое из чисел имеет одно из трех значений: 1, 2 или 3. Нужно выбрать совокупность чисел (12.11), при которой величина (12.10) минимальна. 4. Прокладывается участок железнодорожного пути между пунктами А и В (рис. 12.1). Местность пересеченная, включает лесистые зоны, холмы, болота, реку, через которую надо строить мост. Требуется так провести дорогу из в В, чтобы суммарные затраты на сооружение участка были минимальны. В этой задаче, в отличие от трех предыдущих, нет естественного членения на шаги: его приходится вводить искусственно, для чего, например, можно отрезок АВ разделить на частей, провести через точки деления прямые, перпендикулярные АВ, и считать за «шаг» переход с одной такой прямой на другую. Если провести их достаточно близко друг от друга, то можно считать на каждом шаге участок пути прямолинейным. Шаговое управление на i-м шаге представляет собой угол , который составляет участок пути с прямой АВ. Управление всей операцией состоит из совокупности шаговых управлений: Требуется выбрать такое (оптимальное) управление при котором суммарные затраты на сооружение всех участков минимальны: Итак, мы рассмотрели несколько примеров многошаговых задач исследования операций. А теперь поговорим о том, как можно решать подобного рода задачи? Любую многошаговую задачу можно решать по-разному: либо искать сразу все элементы решения на всех шагах, либо же строить оптимальное управление шаг за шагом, на каждом этапе расчета оптимизируя только один шаг. Обычно второй способ оптимизации оказывается проще, чем первый, особенно при большом числе шагов. Такая идея постепенной, пошаговой оптимизации и лежит в основе метода динамического программирования. Оптимизация одного шага, как правило, проще оптимизации всего процесса: лучше, оказывается, много раз решить сравнительно простую задачу, чем один раз - сложную. С первого взгляда идея может показаться довольно тривиальной. В самом деле, чего казалось бы, проще: если трудно оптимизировать операцию в целом, разбить ее на ряд шагов. Каждый такой шаг будет отдельной, маленькой операцией, оптимизировать которую уже нетрудно. Надо выбрать на этом шаге такое управление, чтобы эффективность этого шага была максимальна. Не так ли? Нет, вовсе не так! Принцип динамического программирования отнюдь не предполагает, что каждый шаг оптимизируется отдельно, независимо от других. Напротив, шаговое управление должно выбираться дальновидно, с учетом всех его последствий в будущем. Что толку, если мы выберем на данном шаге управление, при котором эффективность этого шага максимальна, если этот шаг лишит нас возможности хорошо выиграть на последующих шагах? Пусть, например, планируется работа группы промышленных предприятий, из которых часть занята выпуском предметов потребления, а остальные производят для них машины. Задача операции - получить за лет максимальный объем выпуска предметов потребления. Допустим, планируются капиталовложения на первый год. Исходя из узких интересов этого шага (года), мы должны были бы все наличные средства вложить в производство предметов потребления. Но правильно ли будет такое решение с точки зрения эффективности операции в целом? Очевидно, нет. Это решение - расточительное, недальновидное. Имея в виду будущее, надо выделить какую-то долю средств и на производство машин. От этого объем продукции за первый год, конечно, снизится, зато будут созданы условия для его увеличения в последующие годы. Еще пример. Допустим, что в задаче 4 (прокладка железнодорожного пути из А в В) мы прельстимся идеей сразу же устремиться по самому легкому (дешевому) направлению. Что толку от экономии на первом шаге, если в дальнейшем он заведет нас (буквально или фигурально) в «болото»? Значит, планируя многошаговую операцию, надо выбирать управление на каждом шаге с учетом всех его будущих последствий на еще предстоящих шагах. Управление на шаге выбирается не так, чтобы выигрыш именно на данном шаге был максимален, а так, чтобы была максимальна сумма выигрышей на всех оставшихся до конца шагах плюс данный. Однако из этого правила есть исключение. Среди всех шагов есть один, который может планироваться попросту, без оглядки на будущее. Какой это шаг? Очевидно, последний! Этот шаг, единственный из всех, можно планировать так, чтобы он сам, как таковой принес наибольшую выгоду. Поэтому процесс динамического программирования обычно разворачивается от конца к началу: прежде всего планируется последний, шаг. А как его спланировать, если мы не знаем, чем кончился предпоследний? Т. е. не знаем условий, в которых мы приступаем к последнему шагу? Вот тут-то и начинается самое главное. Планируя последний шаг, нужно сделать разные предположения о том, чем кончился предпоследний, шаг, и для каждого из этих предположений найти условное оптимальное управление на шаге («условное» потому, что оно выбирается исходя из условия, что предпоследний шаг кончился так-то, и так-то). Предположим, что мы это сделали, и для каждого из возможных исходов предпоследнего шага знаем, условное оптимальное управление и соответствующий ему условный оптимальный выигрыш на шаге. Отлично! Теперь мы можем оптимизировать управление на предпоследнем, шаге. Снова сделаем все возможные предположения о том, чем кончился предыдущий, и найти не условно оптимальный, а просто оптимальный выигрыш . В самом деле, пусть мы знаем, в каком состоянии была управляемая система (объект управления S) в начале первого шага. Тогда мы можем выбрать оптимальное управление на первом шаге. Применив его, мы изменим состояние системы на некоторое новое S и в этом состоянии мы подошли ко второму шагу. Тогда нам тоже известно условное оптимальное управление которое к концу второго шага переводит систему в состояние и т. д. Что касается оптимального выигрыша W за всю операцию, то он нам уже известен: ведь именно на основе его максимальности мы выбирали управление на первом шаге. Таким образом, в процессе оптимизации управления методом динамического программирования многошаговый процесс «проходится» дважды: первый раз - от конца к началу, в результате чего находятся условные оптимальные управления и условные оптимальные выигрыши за оставшийся «хвост» процесса; второй раз - от начала к концу, когда нам остается только «прочитать» уже готовые рекомендации и найти безусловное оптимальное управление состоящее из оптимальных шаговых управлений Первый этап - условной оптимизации - несравненно сложнее и длительнее второго. Второй этап почти не требует дополнительных вычислений. Автор не льстит себя надеждой, что из такого описания метода динамического программирования читатель, не встречавшийся с ним до сих пор, поймет по-настоящему его идею. Истинное понимание возникает при рассмотрении конкретных примеров, к которым мы и перейдем.Создание стека индексов
Хорошо, математика - это красиво. А что с задачами, в которых не всё дано?
Идея решения
Реализация через рекурсию
private static int f(int n){
if(n==1) return 1;
if(n==2) return 2;
if(n==3) return 4;
return f(n-1)+f(n-2)+f(n-3);
}
Там вверху ещё было написано про какую-то двумерную динамику?..
Идея решения
Реализация через рекурсию
Реализация через массив значений
int dp = new int;
for(int i=0; iОтлично, я всё понял. На чём мне проверить свои навыки?
Взрывоопасность
Решение
Реализация
Подъём по лестнице
Решение
Реализация
Калькулятор
Решение
Реализация
int N;
//Ввод с клавиатуры
int a = new int;
a= 0;
{
int min;
for(int i=2; iСамый дешёвый путь
История
Идея динамического программирования
Классические задачи динамического программирования
Литература
Ссылки
Смотреть что такое "Динамическое программирование" в других словарях:
Таким образом, американский математик и один из ведущих специалистов в области математики и вычислительной техники — Ричард Эрнст Беллман
— стал прородителем динамического программирования.
Есть задача, которую мы хотим решить при помощи ДП, т.е. найти какой-то план ее решения. Допустим эта задача сложна и сразу решить мы ее не можем. Мы берем малую подзадачу и решаем сначала ее (для x1). Затем используя это малое решение x1 , и не меняя структуру этого решения, решаем следующую задачу уже с x1 и x2 . И т.д.
Примеры, решаемых при помощи динамического программирования задач
Целевая функция:
максимизация средних
доходов, т.к. на бирже доход получается вероятностным путем, т.е. это статистический процесс, вероятностный.
Целевая функция
: максимизация прибыли.
Целевая функция:
максимизация вероятности выигрыша или максимизация среднего выигрыша и т.д.
Понятие динамического программирования
Формальная идея ДП
На графике это может выглядеть так:
По этой причине во многих задачах, но не во всех, применение аппарата математического анализа будет неприемлемым.Простой пример решения задач при помощи ДП
В чем состоит якобы «сложность» данной задачи: в том, что необходимо сразу взять большое количество чисел и получить ответ.
(В ДП всегда необходимо сначала определить начальные условия или условие)
F(1) = 1
F(2) = F(1) + 2 = 1 + 2 = 3 , т.е. надо взять сумму первого элемента и добавить к нему второй элемент
F(n) = F(n-1) + An
Итак, что мы сделали: определили порядок и вычленили подзадачи, затем решили каждую из них, опираясь на решение предыдущей.
Решение:
f(a i) = f(a i-1) + f(a i-2)
Если начинать с 1, то формула соответствует нахождению последовательности чисел Фибоначчи. 1
2
3
4
5
6
7
8
9
10
11
12
13
var
c:
integer
;
procedure
getKolSposob(i,
n:
integer
)
;
begin
writeln
(i+
n,
" "
)
;
inc(c)
;
if
...
then
getKolSposob(...,...
)
end
;
begin
c:
=
1
;
getKolSposob(0
,
1
)
;
end
.
Решение 15-го типа заданий ЕГЭ (Графы. Поиск количества путей).
(12.10)
(12.12)