Определение: Задача динамического программирования (ДП) – это задача оптимального управления некоторым многошаговым процессом.
Подобных задач, равно как и методов их решения, существует великое множество. Изобретаются они в каждом конкретном случае индивидуально, но все объединены общей идеей решения – так называемого метода решения задачи про чайник: чтобы вскипятить воду, нужно налить её в чайник, поставить его на плиту, включить плиту и т.д. Если же вода в чайник уже налита, то нужно её вылить. А что делать дальше, мы уже знаем. Таким образом, в процессе решения мы сводим задачу к той, решать которую уже научились на предыдущем шаге.
Рассуждения при этом проводятся примерно следующие:
Нам необходимо найти оптимальное значение в конце маршрута. Если бы мы знали оптимальное решение для всех предыдущих этапов, то нашли бы решение для последнего. Чтобы найти решение для предпоследнего этапа, мы должны знать решение для второго с конца этапа, и т.д. То есть разрабатывается метод динамического программирования с конца. Реализуется же он сначала: высчитываем оптимальные значения с самого начала и находим оптимальную стоимость. После этого необходимо найти собственно оптимальный маршрут. Его находим с конца.
Задача: Рассмотрим задачу оптимального управления многошаговым процессом. Над ребрами данного графа проставлены стоимости переходов из одной вершины в другую. Необходимо найти путь, по которому с минимальными затратами можно попасть из S(0) в S(5) (см. рисунок 4.1).
Рисунок 4.1 Исходный граф
Идея решения: В принципе мы умеем решать подобные задачи по алгоритму Дейкстры и Форда-Беллмана. Попробуем теперь решить эту задачу методом динамического программирования. Он изобретается с конца. Нам необходимо найти минимально возможную сумму, имея которую, мы можем добраться до S(5) .
Рассуждаем
так: если бы мы знали “стоимости” всех вершин, из которых мы можем попасть в
S(5) (то есть вершин ), то мы бы нашли
стоимости всех вершин S(5) (для этого к стоимости вершин из S(4)
прибавляем стоимости переездов и выбираем минимум из получившихся сумм). Чтобы
найти стоимости S(4) мы должны знать стоимости S(3)
и т.д. Так спускаемся до вершины S(0), стоимость которой равно
нулю.
Итак,
здесь
– минимально возможная сумма денег, имея которую мы можем добраться от
до
.
Имеем:
Рисунок 4.2
Здесь– полученные
стоимости вершин.
Реализация метода ДП происходит от начала к концу (то есть слева направо в нашем случае). Самый внешний цикл – по i; в нём в прямом порядке перебираем уровни вершин. Следующий по вложенности цикл – по j; в нём перебираем вершины одного уровня. Самый внутренний цикл – по k. Изменение направления прохода двух вложенных циклов не повлияет на конечный результат.
Последний этап – восстановление оптимального пути – реализуется из конца в начало. Для этого смотрим, из какой вершины предыдущего уровня была достигнута стоимость нашей вершины, постепенно продвигаясь справа налево.
Рисунок 4.3 Восстановление оптимального пути
Задача: Необходимо, имея стартовую нулевую скорость v и стартовую нулевую высоту h, набрать некоторую скорость V и высоту H, минимизировав при этом суммарные затраты топлива.
Если в какой-то момент времени t мы увеличиваем скорость на dv, а высоту на dh, то затраты горючего на это изменение могут быть определены по формуле:
где v(t) и h(t) – скорость и высота в момент времени t.
и
– коэффициенты пропорциональности затрат топлива.
Идея решения: Нам необходимо минимизировать интеграл, выбирая оптимальный вариант набора скорости и высоты (ищем оптимальное управление):
Дискретизируем эту задачу. Для этого разобьем весь участок приращения скорости и высоты на несколько меньших интервалов:
Рисунок 4.4 Дискретизация исходной задачи
Заполняем стоимости, начиная с левого нижнего угла, и записываем их в левый сектор круга. Аналогично считаем стоимости вершин с правого верхнего угла и записываем их в правый сектор. Глядя на полученные стоимости, восстанавливаем оптимальный путь: 87 получили из 79 + 8; 79 из 70 + 9 и т.д.
Комментарии:
● В принципе, при восстановлении оптимального пути, возможно ветвление маршрута (когда минимум получен на пути не из одной, а из большего количества вершин).
● Все вершины графа разбиваются на группы состояний по диагоналям. Но в группу S(i) мы попадаем не только из S(i– 1), но и из S(i–2).
● При проходе слева направо и справа налево, как и следовало ожидать, стоимость пути одинакова и равна 87. В каждом кружке сумма чисел больше либо равна 87. Причем сумма равна 87 в кружках, лежащих на оптимальном пути, а для остальных она превышает 87. В каждом кружке – левое число – стоимость маршрута из левого нижнего угла до данного кружка. Правое число – стоимость маршрута из правого верхнего угла до данного кружка.
Задача:
Имеется склад, на котором есть некоторый ассортимент товаров. Запас каждого
товара считается неограниченным. Товары имеют две характеристики: mi
– масса, ci – стоимость; .
Необходимо выбрать набор
товаров так, чтобы его суммарная масса не превосходила заранее фиксированную
массу М (т.е. ), и стоимость набора была как можно
больше (
).
Идея решения: Считаем, что все массы mi целочисленные. Решим эту задачу методом динамического программирования. Изобретаем метод, т.е. формулу:
Нам необходимо
найти , т.е. максимально возможную
сумму
при заданном М.
Предположим, что к этому моменту мы знаем, как решать эту задачу для всех меньших
значений грузоподъемности. Тогда смотрим, какой товар мы положили в рюкзак последним.
Если это был первый товар стоимостью с1, то мы должны оптимизировать
стоимость рюкзака при грузоподъемности
. Если это
был второй товар стоимостью с2 , то оптимизация при грузоподъемности
, и т.д. Среди всех этих величин выбираем максимальную.
Таким образом,
получаем формулу:
Пример: Рассмотрим решение этой задачи при следующем наборе товаров:
m: 3 5 8 – массы товаров,
c: 8 14 23 – стоимости товаров.
Решение:
Вычислим последовательно:
f(0)=0; f(1)=0; f(2)=0; f(3)=8; f(4)=8;
f(5)= 14 = max( f(5–3)+8; f(5–5)+14; f(5–8)+23);–не рассматриваем при поиске максимума, так как f(–3) не определена.
f(6)=16; f(7)=16; f(8)= 23; f(9)= 24 =max( f(9–3)+8; f(9–5)+14; f(9–8)+23 );
f(10)=28; f(11)=31; f(12)=32; f(13)= 37 =max( f(13–3)+8;
f(13–5)+14; f(13–8)+23 )
Оценим трудоемкость решения задачи о рюкзаке методом ДП:
Для применения метода ДП все массы должны быть целочисленные ( а стоимости – необязательно). Тогда, если k – количество видов товаров, m – грузоподъемность, то имеем m шагов внешнего цикла (по грузоподъемности) и на каждом шаге находим максимум среди k чисел, каждое из которых является суммой двух слагаемых. В итоге получаем трудоемкость: T = m·k.
Как известно из высшей математики, умножение матриц ассоциативно, то есть результат перемножения зависит только от порядка матриц и не зависит от расстановки скобок:
(A*B)*C = A*(B*C).
Результат перемножения от расстановки скобок не зависит, зато трудоемкость этого перемножения при разных расстановках скобок может отличаться существенно.
Оценим трудоемкость умножения двух матриц A(p×q) и B(q×>r):
C(p×r)=A(p×q)*B(q×r),
каждый элемент матрицы С(p×r) есть сумма q попарных произведений.
Трудоемкость перемножения двух матриц: Т = p∙q∙r.
Пример: Рассмотрим пример перемножения матриц разными способами:
Пусть имеется четыре матрицы разных размерностей:
M1[10×20] , M2[20×50] M3[50×1], M4[1×100].
Решение:
Рассмотрим умножение матриц в следующем порядке:
М1 ∙ (М2 ∙ (М3 ∙ М4) )
[50×1] ∙ [1×100]=[50>×100] трудоёмкость 50∙1∙100 = 5000
[20>×>50] ∙ [50×100]=[20×100] трудоёмкость 20∙100∙50 = 100 000 125 000
[10×20] ∙ [20>×100]=[10×100] òрудоёмкость 10∙20∙100 = 20 000 операций
Рассмотрим другой вариант умножения матриц
(М1 ∙ (М2 ∙ М3) ) ∙ М4
[20×50] ∙ [50>×1]=[20>×>1] трудоёмкость. 20∙50∙1=1000
[10×20] ∙ [20×1]=[10×1] трудоёмкость 10∙20∙1=200 2200 операций
[10×1] ∙ [1×100]=[10×100] трудоёмкость 10∙1∙100=1000
При умножении вторым способом действий потребовалось значительно меньше (2200 против 125 000). Придумаем формулу метода ДП применительно к данной задаче:
Допустим, нам необходимо оптимальным образом перемножить 5 матриц, i-тая матрица имеет размерность [ri–1×ri]. Смотрим, где стояла последняя пара скобок : существует 4 варианта:
(М1)× (М2∙М3∙М4∙М5) (1)
[r0×r1] [r1>×>r5]
(М1∙М2)× (М3∙М4∙М5) (2)
[r0×>r2] [r2×r5]
(М1∙М2∙М3)× (М4∙М5) (3)
[r0×>r3] [r3×r5]
(М1∙М2∙М3∙М4)× (М5) (4)
[r0×r4] [r4×r5]
При первом варианте расстановки скобок нам потребуется
f(1,1) + f(2,5) + r0r1r5 операций.
Здесь f(k,l) – минимальное количество действий, за которое можно вычислить произведение матриц с k-той по l-тую.
Для последующих трех вариантов:
операций соответственно.
Здесь f(k,p) – минимальное количество действий, за которое можно вычислить произведение матриц с k-той по p-тую.
Выбираем минимум среди всех этих чисел и получаем общую формулу:
Замечание: В отличие от задачи о рюкзаке, где была динамика по одному параметру (грузоподъемности), здесь динамика по двум параметрам: начало и конец блока перемножаемых матриц.
Итак, в окончательном виде эта задача решается с помощью следующего алгоритма:
1) Заполняем трудоемкости матриц:
Трудоемкости на главной диагонали равны 0:
for i:=1 to n do f(i,i):=0;
2) Внешний цикл по t – длине перемножаемого блока;
Средний цикл по k – местоположению блока;
Внутренний – поиск минимума по j.
for t:=1 to n–1 do
for k:=1 to n–t do
.
Для матриц М1, М2, М3, М4 из рассмотренного выше примера расставим скобки оптимальным образом.
f(1,1) f(1,2) f(1,3) f(1,4)
f(2,2) f(2,3) f(2,4)
f(3,3) f(3,4)
f(4,4)
Итак, заполняем такую матрицу в следующем порядке:
После вычисления оптимальных трудоемкостей восстанавливаем оптимальную расстановку скобок;
Смотрим,
где достигнут минимум в . Он
достигнут в
. Следовательно,
последними скобками будут (М1 М2 М3) (М4).
Далее смотрим,
где достигнут минимум в . Он
достигнут в
. Т.е. следующими
скобками будут (М1 (М2 М3)) М4.
Т.к. у нас
3 вложенных цикла, длина каждого порядка n (n – количество перемножаемых
матриц), то трудоемкость решаемой задачи методом ДП
При решении этой задачи методом прямого перебора получаем не полиномиальную трудоемкость, а намного большую. То же самое получаем и для задачи о рюкзаке: её решение методом динамического программирования имеет полиномиальную трудоемкость (2 вложенных цикла), а методом прямого перебора получаем неполиномиальную трудоемкость.
Домашнее задание №2 (А, Б)
А) Задача грабителя (о рюкзаке). Имеется склад, на котором присутствует ассортимент товаров (каждого товара неограниченный запас). У каждого товара своя стоимость Ci и масса mi . Выбрать набор товаров так, чтобы его суммарный вес не превышал заданную грузоподъемность М, и суммарная стоимость этого набора товаров была бы максимальной.
Номер товара, i |
mi |
Ci |
1 |
5 |
9 |
2 |
7 |
13 |
3 |
11 |
21 |
Максимальная грузоподъемность: М=23; 24.
Решение:
Вычислим f(М) – максимально возможную стоимость товаров при грузоподъемности М:
f(0)=0;
f(1)=0;
f(2)=0;
f(3)=0;
f(4)=0;
f(5)=max(f(5–5)+9, f(5–7)+13, f(5–11)+21)= max(0+9)=9;
f(6)=max(f(6–5)+9, f(6–7)+13, f(6–11)+21)= max(0+9)=9;
f(7)=max(f(7–5)+9, f(7–7)+13, f(7–11)+21)= max(0+9, 0+13)=13;
f(8)=max(f(8–5)+9, f(8–7)+13, f(8–11)+21)= max(0+9, 0+13)=13;
f(9)=max(f(9–5)+9, f(9–7)+13, f(9–11)+21)= max(0+9, 0+13)=13;
f(10)=max(f(10–5)+9, f(10–7)+13, f(10–11)+21)= max(9+9, 0+13)=18;
f(11)=max(f(11–5)+9, f(11–7)+13, f(11–11)+21)= max(9+9, 0+13, 0+21)=21;
f(12)=max(f(12–5)+9, f(12–7)+13, f(12–11)+21)= max(13+9, 9+13, 0+21)=22;
f(13)=max(f(13–5)+9, f(13–7)+13, f(13–11)+21)= max(13+9, 9+13, 0+21)=22;
f(14)=ma(f(14–5)+9, f(14–7)+13, f(14–11)+21)= max(13+9, 13+13, 0+21)=26;
f(15)=max(f(15–5)+9, f(15–7)+13, f(15–11)+21)= max(18+9, 13+13, 0+21)=27;
f(16)=max(f(16–5)+9, f(16–7)+13, f(16–11)+21)= max(21+9, 13+13, 9+21)=30;
f(17)=max(f(17–5)+9, f(17–7)+13, f(17–11)+21)= max(22+9, 18+13, 9+21)=31;
f(18)=max(f(18–5)+9, f(18–7)+13, f(18–11)+21)= max(22+9, 21+13, 13+21)=34;
f(19)=max(f(19–5)+9, f(19–7)+13, f(19–11)+21)= max(26+9, 22+13, 13+21)=35;
f(20)=max(f(20–5)+9, f(20–7)+13, f(20–11)+21)= max(27+9, 22+13, 13+21)=36;
f(21)=max(f(21–5)+9, f(21–7)+13, f(21–11)+21)= max(30+9, 26+13, 18+21)=9;
f(22)=max(f(22)+9, f(22)+13, f(22–11)+21)= max(31+9, 27+13, 21+21)=42;
f(23)=max(f(23–5)+9, f(23–7)+13, f(23–11)+21)= max(34+9,30+13, 22+21)=43;
f(24)=max(f(24–5)+9, f(24–7)+13, f(24–11)+21)= max(35+9, 31+15, 22+21)=44.
Определим оптимальный набор товаров при М=23:
f(23)=43;
f(23–5)+9=f(18)+9=34+9=43;