Метод динамического программирования
Метод динамического программирования (ДП)[5] был предложен известным математиком Р.Беллманом как очень общий подход к решению некоторых типов задач из разных областей дискретной и непрерывной математики, включая даже вариационное исчисление. В данном пособии будет рассматриваться только приложение этого метода к комбинаторным задачам.
Рассмотренный выше метод ветвей и границ является попыткой ограничить перебор при движении по дереву сверху вниз. Метод ДП действует в какой-то мере противоположным образом.
Вспомним дерево перебора, изображенное на рис.1.1. Если корень дерева представляет исходную задачу, то с каждой вершиной обычно можно связать некоторую подзадачу того же типа, но меньшей размерности. Например, вершины на один уровень ниже корня являются корневыми для поддеревьев перебора, решающих задачи с различными фиксированными значениями x1. Листья дерева в таком случае представляют простейшие задачи, решение которых получается сразу, без перебора. В ходе решения исходной задачи выполняется решение всех подзадач. Как мы знаем, основной недостаток решения задач путем полного перебора заключается в астрономически большом количестве решаемых подзадач.
Для некоторых практически важных задач дерево перебора обладает приятным свойством: многие вершины, лежащие на разных ветвях дерева, соответствуют одинаковым подзадачам, т.е. соответствующие поддеревья абсолютно одинаковы. Это наводит на мысль, что нет смысла много раз решать одни и те же подзадачи. Следует найти такой способ организации исчерпывающего перебора, при котором каждая подзадача решается один раз, а результат ее решения может использоваться многократно.
Примером ситуации, описанной в предыдущем абзаце, может служить решение задачи о рюкзаке. Допустим, нужно уложить рюкзак объемом 100 единиц, и при этом уже найдена оптимальная укладка для рюкзака объемом 20 единиц. Далее можно пытаться по-разному распорядиться остальными 80 единицами, всякий раз используя готовое решение для 20. В свою очередь, при решении задачи для объема 20 единиц может многократно понадобиться распорядиться меньшим объемом, например, 10 единицами, и если эта подзадача была заранее решена, то ее результат очень пригодится.
Другой пример – задача о коммивояжере. Допустим, мы рассмотрели все варианты проезда из города A в город B с заездом в C, D и E: ACDEB, ADECB, AEDCB и т.п. При этом найден кратчайший из таких путей. Далее в ходе отыскания полного маршрута можно использовать этот результат всякий раз, когда будет рассматриваться маршрут из B в A, проходящий через все города, кроме C, D и E.
Решение комбинаторной задачи методом ДП выглядит следующим образом:
· Вместо исходной задачи рассматривается более общая совокупность задач, различающихся размерностью и другими параметрами.
· На первом этапе решаются самые простые задачи из этой совокупности (с минимальной размерностью) и результаты их решения при разных значениях параметров собираются в таблицу.
· На следующих этапах строятся решения задач все большей размерности, при этом каждый раз используется таблица, построенная на предыдущем этапе.
· На последнем этапе находится решение исходной задачи, при этом используется таблица результатов предпоследнего этапа.
Тут весь фокус в том, чтобы размеры таблиц промежуточных результатов оказались не слишком велики и эти таблицы уместились в памяти. Для этого нужно суметь разложить исходную задачу на не очень большое число подзадач.
Рассмотрим применение метода ДП на примере алгоритма Беллмана для задачи о рюкзаке.
Итак, дано число товаров n, объем единицы каждого товара bi, стоимость единицы товара ci, объем рюкзака B. Требуется максимизировать суммарную стоимость C(X) = Scixi при ограничении Sbixi £ B.
Пусть v(k,y) – это максимальное (неизвестное пока) значение, которое может принять C(X) при условии, что Sbixi £ y и все xi при i > k равны 0. Постараемся вычислить значения v(k,y) для всех k, 0 £ k £ n , и для всех y, 0 £ y £ B. Это означает, что вместо одной конкретной задачи о рюкзаке мы как бы будем решать серию задач с разным объемом рюкзака и разным количеством товаров. На самом деле нас интересует единственное значение v(n,B), а все остальные значения нужны только как промежуточные.
Для определения v(k,y) будем использовать следующие соотношения:
v(1,y) = entier(y/b1) × ci ;
v(k,y) = max(ckxk + v(k-1, y - bkxk)) для k > 1.
Максимум берется по всем значениям xk таким, что 0 £ xk £ entier(y/bk), а функция entier, кто не помнит, означает целую часть числа.
Переведем эти соотношения на русский язык. Первое из них означает, что при единственном виде товара максимальная достижимая стоимость равна стоимости стольких единиц товара, сколько удалось втиснуть в рюкзак объема y.
Второе соотношение чуть посложнее. Мы можем положить в пустой рюкзак объема y любое число единиц k-того товара от 0 до entier(y/bk). Пусть это число равно xk, тогда стоимость k-того товара в рюкзаке будет равна ckxk, объем этого товара составит bkxk, а на все товары с номерами от 1 до k-1 останется y - bkxk единиц свободного объема. Какую максимальную стоимость можно получить от использования этого объема? По определению функции v, это есть не что иное, как v(k-1, y - bkxk)! Максимум по всем возможным значениям xk позволяет определить наиболее выгодное количество k-того товара.
Подобные функциональные уравнения, связывающие значения функции v для разных значений аргументов, очень характерны для метода ДП и называются уравнениями Беллмана. Искусство применения метода ДП к конкретным задачам заключается в построении уравнений Беллмана для данной задачи.
Когда уравнения получены, решение задачи сводится к табулированию функции v(k,y) при возрастающих значениях k.
Рассмотрим конкретный пример задачи о рюкзаке со следующими параметрами: n = 4, bi = (5, 7, 9, 4), ci = (9, 15, 19, 8), B = 20.
Прежде всего, можно получить хорошую оценку сверху. Если бы постановка задачи допускала вещественные значения xk, то решение было бы тривиально: подсчитать стоимость единицы объема каждого товара (ck/bk) и заполнить весь рюкзак тем товаром, для которого эта стоимость максимальна. Нетрудно видеть, что в данном примере наиболее выгодным является второй товар, для которого стоимость единицы объема равна 15/7, что при объеме 20 единиц дало бы общую стоимость 300 / 7 » 42.86. Очевидно, что дополнительное условие целочисленности может только ухудшить результат, а потому максимальная стоимость товара в рюкзаке не может быть больше 42.
Теперь протабулируем функцию v(k,y) для данного примера. Кроме значений функции, будем запоминать те значения xk, при которых достигается максимум в уравнении Беллмана. Результаты сведены в табл.1.11.
Таблица 1.11
| k = 1 | k = 2 | k = 3 | k = 4 | |||||
| y | x1 | v(1,y) | x2 | v(2,y) | x3 | v(3,y) | x4 | v(4,y) |
Продолжение табл. 1.11
| k = 1 | k = 2 | k = 3 | k = 4 | |||||
| y | x1 | v(1,y) | x2 | v(2,y) | x3 | v(3,y) | x4 | v(4,y) |
| 0 (3) | ||||||||
| 0 (1) | ||||||||
| 0 (3) | ||||||||
Заполнение таблицы выполняется согласно приведенным выше уравнениям Беллмана. Для примера рассмотрим заполнение двух ячеек.
При k = 2, y = 7 entier(y/bk) = entier(7/7) = 1, поэтому переменная xk может принимать значения 0 и 1. Отсюда имеем:
v(2, 7) = max((15×0 + v(1, 7–7×0)), (15×1 + v(1, 7–7×1))) =
= max((0+v(1,7)), (15+v(1,0))) = max(0+9, 15+0) = 15.
При k = 4, y = 12 entier(y/bk) = entier(12/4) = 3, xk может принимать значения 0, 1, 2 и 3. Имеем:
v(4, 12) = max((8×0 + v(3, 12–4×0)), (8×1 + v(3, 12–4×1),
(8×2 + v(3, 12–4×2), (8×3 + v(3, 12–4×3))) =
= max((0+v(3,12)), (8+v(3,8)), (16+v(3,4)), (24+v(3,0))) =
= max(0+24, 8+15, 16+0, 24+0) = 24.
В данном случае максимум достигается при двух разных значениях xk, что отражено в табл.1.11. Это означает, что имеется несколько разных планов с одинаковым значением целевой функции.
Аналогично заполняются и остальные клетки таблицы.
Отметим следующую деталь. При заполнении k-того столбца таблицы используются только значения параметров bk, ck и значения v(k-1, y) из предыдущего столбца таблицы. С точки зрения программирования это означает, что в оперативной памяти можно хранить не всю таблицу, а только два столбца, предыдущий и текущий.
Собственно говоря, заполнять все строки таблицы при k = 4 было вовсе не обязательно, поскольку важна лишь последняя строка, которая показывает, что максимальная достижимая стоимость товаров 4 видов в рюкзаке объемом 20 составляет 42 единицы. Приятно отметить, что это совпадает с полученной выше верхней оценкой!
Однако помимо значения максимальной стоимости, необходимо получить и сам оптимальный план, т.е. набор значений xk, на котором достигается максимум. Для этого используется так называемый обратный ход по таблице.
Из четвертого столбца таблицы видим, что значение v(4,20) = 42 достигается при x4 = 1. Отсюда следует, что на первые три вида товаров остается 20 – b4x4 = 16 единиц объема. Из третьего столбца видно, что v(3,16) = 34 при x3 = 1. На два первых товара остается 16 – b3x3 = 7 единиц объема. Из второго столбца v(2,7) = 15 при x2 = 1. На первый товар остается 7 – b2x2 = 0 единиц объема, и можно уже даже не смотреть в таблицу, чтобы сказать, что x1 = 0. Итак, оптимальным будет план X = (0, 1, 1, 1).
Оценим, как зависит трудоемкость алгоритма Беллмана от основных параметров задачи: числа видов товаров n и объема рюкзака B. Число столбцов таблицы равно n, а число строк – B+1. Трудоемкость вычисления одного значения в таблице пропорциональна количеству членов, из которых выбирается максимум, а это количество пропорционально B. Таким образом, T(n,B) = O(nB2).