Динамическое программирование
Динамическое программирование используется для решения многих задач оперативного исследования, поэтому мы не будем перечислять туториалы, связанные с этим методом.
Динамическое программирование — это точный метод решения проблем
оптимизация, в основном за счет R. Бельман (1957).
В частности, динамическое программирование — это парадигма разработки алгоритма, которую можно применить для решения проблемы, если она соответствует оптимальности Беллмана.
Динамическое программирование по идее похоже на метод разделяй и властвуй. Существенная разница между этими двумя методами заключается в том, что динамическое программирование позволяет перекрывать подзадачи. Другими словами, подзадача может использоваться при решении двух разных подзадач. В то время как подход «разделяй и властвуй» создает отдельные подзадачи, которые можно решать независимо друг от друга.
Следовательно, фундаментальное различие между этими двумя методами заключается в том, что подзадачи в динамическом программировании могут быть взаимодействующими, тогда как в методе «разделяй и властвуй» они не взаимодействуют.
Второе различие между этими двумя методами, как показано на рисунке выше, заключается в том, что метод «разделяй и властвуй» является рекурсивным, рекурсия берет глобальную проблему, чтобы разрезать ее на элементарную проблему. Динамическое программирование — это метод, расчеты которого выполняются снизу вверх: мы начинаем с решения самых маленьких подзадач. Комбинируя их решения, мы получаем решения все больших и больших подзадач.
Принцип
Парадигма распадается на четыре проблемный :
- Характеристика структуры оптимального решения.
- Рекурсивное определение значения оптимального решения.
- Расчет решения снизу вверх.
- Построение решения методом восходящего расчета.
Для запоминания уже проведенных вычислений строится таблица: каждому элементу будет соответствовать решение одной и только одной промежуточной задачи, и одно — окончательному решению. Таким образом, необходимо, чтобы можно было определить подзадачи, которые будут решаться во время расчета.
Существует два подхода к заполнению таблицы:
- Итеративный: мы инициализируем «блоки», соответствующие базовым случаям.
Затем таблица заполняется в очень точном порядке, который необходимо определить: мы начинаем с задач наименьшего возможного «размера», мы заканчиваем решением основной задачи: необходимо, чтобы для каждого расчета мы использовали только уже рассчитанные решения. - Рекурсивный: тот же принцип, что и в итеративном подходе, этот метод вычисляет только то, что строго необходимо для достижения поставленной цели.
Пример: произведение матриц
быть нет матрицы М1, …, Мнет, каждая матрица имеет некоторое число mя линий и мя+1 столбцы, записи являются действительными числами (линейная задача). Мы пытаемся вычислить M1*…*Мнет чтобы минимизировать количество операций.
Пусть сij количество операций для вычисления Mя*…*Мя. Тогда у нас есть cII=0 и ся (я + 1)=м(я-1)*мя*м(я+1) операции. Давайте сократим эту подзадачу, вычислив наилучший cij с Мя*…*Мк И м(к+1)*…*Мя. Такij =мин[сик + с(к+1)j +мя*м(к+1)*м(д+1)] с к из я в д-1, последний член сводится к умножению полученные результаты произведения матриц я в к с тем из к+1 в я.
Итак, у нас есть следующая программа:
- противij = 0, если я = j;
- противя (я + 1)=м(я-1)*мя*м(я+1);
- противij =мин[сик + с(к+1)j +мя*м(к+1)*м(д+1)] в противном случае.
Динамическая таблица программ принимает на вход количество операций, выполняемых в соответствии с выбранными матрицами. Рассмотрим следующий пример:
я | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
мя | 30 | 35 | 15 | 5 | 10 | 20 | 25 |
Исходная таблица выглядит следующим образом:
противij | 1 | 2 | 3 | 4 | 5 | 6 |
1 | 0 | – | – | – | – | – |
2 | – | 0 | – | – | – | – |
3 | – | – | 0 | – | – | – |
4 | – | – | – | 0 | – | – |
5 | – | – | – | – | 0 | – |
6 | – | – | – | – | – | 0 |
Тогда мы можем вычислить cij с двумя матрицами (без принципа подструктуры):
противij | 1 | 2 | 3 | 4 | 5 | 6 |
1 | 0 | 15750 | – | – | – | – |
2 | – | 0 | 2625 | – | – | – |
3 | – | – | 0 | 750 | – | – |
4 | – | – | – | 0 | 1000 | – |
5 | – | – | – | – | 0 | 5000 |
6 | – | – | – | – | 0 |
Остальная часть таблицы заполняется по диагонали по описанному выше правилу:
противij | 1 | 2 | 3 | 4 | 5 | 6 |
1 | 0 | 15750 | 7875 | 9375 | 11875 | 15125 |
2 | – | 0 | 2625 | 4375 | 7125 | 10500 |
3 | – | – | 0 | 750 | 2500 | 5375 |
4 | – | – | – | 0 | 1000 | 3500 |
5 | – | – | – | – | 0 | 5000 |
6 | – | – | – | – | – | 0 |
Результат получен для i=1 и j=6, т.е. прямоугольник в правом верхнем углу таблицы. Таким образом, минимальная стоимость составляет 15125 операций. Тогда возникает новый вопрос: как мы добились минимального количества вычислений?
При расчете минимальной стоимости каждой коробки мы выбираем одну из двух конфигураций. Например, для расчета c13, берем минимум между c12*М3 И м1*против23. Достаточно отметить сделанный выбор, чтобы узнать порядок вычисления матричного произведения.
Кij | 1 | 2 | 3 | 4 | 5 | 6 |
1 | – | – | 1 | 3 | 3 | 3 |
2 | – | – | – | 3 | 3 | 3 |
3 | – | – | – | – | 3 | 3 |
4 | – | – | – | – | – | 5 |
5 | – | – | – | – | – | – |
6 | – | – | – | – | – | – |
Таблица выглядит следующим образом: для расчета Mя*Мя, положим k = Kij по таблице, то вычисляем Mя*…*Мк И м(к+1)*…*Мя которые затем перемножаются.
В нашем примере для расчета против16, вычисляем c13*против46; вычислять против13, мы вычисляем M1*против23; вычислять против46 мы вычисляем c45*М6.
Большинство алгоритм на основе динамического программирования сохраняет в памяти выбор, сделанный для каждого расчета. Часто важен не результат, а путь к нему.
Пример: обмен валюты
Мы хотим внести сдачу на 67 фунтов стерлингов. Для этого мы хотим использовать минимум штук типа: 1, 5, 10, 25.
Здесь легко угадать оптимальное решение 67=2*25+10+5+2*1. Всегда выбирая монету с максимально возможным номиналом, мы получаем решение (путем жадный алгоритм).
Задача записывается следующим образом: Пусть D={ d1,.., дк} конечное количество номиналов монет. Мы предполагаем, что каждый dя является целым числом, и набор отсортирован по возрастанию значения. Стоимость каждой монеты доступна неограниченно. Задача состоит в том, чтобы сделать размен на значение n£ минимальным количеством монет, если dк =1, то всегда есть решение.
Жадный метод не всегда дает оптимальное решение. Например, D={25,10,1} и n=30. Оптимальный метод даст следующее решение: 25+5*1, что хуже, чем 3*10.
Шаг 1: Охарактеризуйте оптимальную подструктуру. Пусть C[j] — оптимальное решение для суммы j£. Таким образом, мы можем удалить кусок и таким образом найти оптимальное решение для C[j]=1+C[j-di].
Шаг 2: Значение оптимального решения. Мы можем рекурсивно определить оптимальное решение из подструктуры.
Шаг 3: Алгоритм.
Обмен монет(n,d,k) C[0]=0; Для j от 1 до n C[j]=inf; Для i от 1 до k Если j>=di и C[j-di] <C[j] then
C[j]=1+C[j-di]
Denom[j]=di
Return C
Мы используем дополнительную таблицу, называемую Denom, так что Denom[j] представляет часть, используемую для получения оптимального решения для суммы j£. Если мы увеличим номинал номинала на стоимость монеты, пока не достигнем j=1, то мы узнаем, какой выбор монеты был сделан. Возьмем пример со следующими монетами: 1, 5, 10, 25:
| я | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| С [я] | 0 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 5 | 1 | 2 | 3 | 4 | 5 | 2 |
| Имя[j] | 0 | 1 | 1 | 1 | 1 | 5 | 1 | 1 | 1 | 1 | 10 | 1 | 1 | 1 | 1 | 5 |
Из суммы n£ можно найти все комбинации монет, позволяющие внести сдачу. Возьмем одинаковые номиналы монет: 1, 5, 10, 25. Например, для N=4, D={1,2,3} есть четыре решения: {1,1,1,1}, {1 , 1,2}, {2,2} и {1,3}.
Шаг 1: Оптимальную подструктуру C(N,m) можно разбить на два множества:
- Решения, не содержащие частейм
- растворы, содержащие хотя бы одну частьм
Если в растворе нет кускам, то мы можем решить подзадачу N с D={d1, .., дм-1}, т. е. решения C(N,m-1).
Если раствор содержитм, то мы удалим кусокм, поэтому необходимо решить подзадачу N- dм , с D={d1, .., дм}. Либо решить следующую задачу C(N- dм, м).
2-й шаг: Правило: C(Nm)=+ C(N- dм, м) при основных условиях:
- С(Н,м)=1, Н=0
- C(N,m)=0, N<0
- C(N,m)=0, N>=1, m<=0
Шаг 3: Решения алгоритма заносятся в таблицу вида
| н/д | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 5 | 1 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 3 | 3 | 3 | 3 | 3 | 4 |
| 10 | 1 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 4 | 4 | 4 | 4 | 4 | 6 |
| 25 | 1 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 4 | 4 | 4 | 4 | 4 | 6 |
RU 
FR 
EN 
ES