4.2. Задача об оптимальном наборе самолетом скорости и высоты
Задача. Необходимо, имея стартовую нулевую скорость v и стартовую нулевую высоту h, набрать некоторую скорость V и высоту H, минимизировав при этом суммарные затраты топлива.
Если в какой-то момент времени t мы увеличиваем скорость на dv, а высоту на dh, то затраты горючего на это изменение могут быть определены по формуле:
Cv(v(t),h(t))dv + Ch(v(t),h(t))dh,
где v(t) и h(t) – скорость и высота в момент времени t;
Cv(v(t),h(t)) и Ch(v(t),h(t)) – коэффициенты пропорциональности затрат топлива.
Идея решения. Нам необходимо минимизировать интеграл, выбирая оптимальный вариант набора сокрости и высоты (ищем оптимальное управление):
Дискретизируем эту задачу. Для этого разобьем весь участок приращения скорости и высоты на несколько меньших интервалов:
h
Рисунок 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 ≤ M), и стоимость набора была как можно больше (Σci→max).
Идея решения. Считаем, что все массы mi целочисленные. Решим эту задачу методом динамического программирования. Изобретаем метод, т.е. формулу.
Нам необходимо найти f(M), т.е. максимально возможную сумму mi при заданном М. Предположим, что к этому моменту мы знаем, как решать эту задачу для всех меньших значений грузоподъемности. Тогда смотрим, какой товар мы положили в рюкзак предпоследним. Если это был первый товар стоимость c1, то мы должны оптимизировать стоимость рюкзака при грузоподъемности M – m1. Если это был второй товар стоимость c2, то оптимизация при грузоподъемности M – m2, и т.д. Среди этих величин выбираем максимальную.
Таким
образом, получаем формулу:
Пример. Рассмотрим решение этой задача при следующем наборе товаров:
|
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(3-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.