4.1 Задача динамического программирования. Её решение методом динамического программирования

Определение: Задача динамического программирования (ДП) – это задача оптимального управления некоторым многошаговым процессом.

Подобных задач, равно как и методов их решения, существует великое множество. Изобретаются они в каждом конкретном случае индивидуально, но все объединены общей идеей решения – так называемого метода решения задачи про чайник: чтобы вскипятить воду, нужно налить её в чайник, поставить его на плиту, включить плиту и т.д. Если же вода в чайник уже налита, то нужно её вылить. А что делать дальше, мы уже знаем. Таким образом, в процессе решения мы сводим задачу к той, решать которую уже научились на предыдущем шаге.

Рассуждения при этом проводятся примерно следующие:

Нам необходимо найти оптимальное значение в конце маршрута. Если бы мы знали оптимальное решение для всех предыдущих этапов, то нашли бы решение для последнего. Чтобы найти решение для предпоследнего этапа, мы должны знать решение для второго с конца этапа, и т.д. То есть разрабатывается метод динамического программирования с конца. Реализуется же он сначала: высчитываем оптимальные значения с самого начала и находим оптимальную стоимость. После этого необходимо найти собственно оптимальный маршрут. Его находим с конца.

Задача: Рассмотрим задачу оптимального управления многошаговым процессом. Над ребрами данного графа проставлены стоимости переходов из одной вершины в другую. Необходимо найти путь, по которому с минимальными затратами можно попасть из 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 Восстановление оптимального пути

4.2 Задача об оптимальном наборе самолетом скорости и высоты

Задача: Необходимо, имея стартовую нулевую скорость 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. В каждом кружке – левое число – стоимость маршрута из левого нижнего угла до данного кружка. Правое число – стоимость маршрута из правого верхнего угла до данного кружка.

4.3 Задача грабителя (задача о рюкзаке)

Задача: Имеется склад, на котором есть некоторый ассортимент товаров. Запас каждого товара считается неограниченным. Товары имеют две характеристики: 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.

4.4 Задача о перемножении матриц

Как известно из высшей математики, умножение матриц ассоциативно, то есть результат перемножения зависит только от порядка матриц и не зависит от расстановки скобок:

(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]=[50100] трудоёмкость 50∙1∙100 = 5000

[20>50] ∙ [50×100]=[20×100] трудоёмкость 20∙100∙50 = 100 000 125 000

[10×20] ∙ [20100]=[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).

Далее смотрим, где достигнут минимум в . Он достигнут в . Т.е. следующими скобками будут 12 М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;