Динамическое программирование

Динамическое программирование (ДП) является универсальным методом решения экс- тремальных задач. Рассмотрим ДП как процесс построения множеств частичных решений исходной задачи и выбора из этих множеств доминирующих решений таких, что хотя бы одно из них может быть ”достроено” до оптимального. При таком подходе процесс реше- ния некоторой задачи может быть организован следующим образом. Для определенности, рассмотрим задачу минимизации

f (x) → min, x ∈ X.

Будем формировать множества X 0, X 1 ,..., Xn частичных решений, где множество Xk +1

получается из множества Xk путем ”достраивания” каждого решения из Xk. Оптимальное решение x∗ выбирается из множества Xn.

С каждым частичным решением x ∈ Xk будем связывать некоторый набор параметров

B = (k, b 1 ,...,bi),называемых переменными состояния. Набор B переменных состояния

называется состоянием.

Пусть Xk (B) обозначает множество частичных решений x ∈ Xk в состоянии (соответству-

ющих состоянию) B. Пусть B (x) обозначает состояние частичного решения x.

В методе ДП с каждым состоянием B связывается функция доминирования F (B) такая, что частичное решение, находящееся в состоянии B и максимизирующее (либо миними- зирующее) F (B), доминирует все остальные частичные решения в состоянии B, т.е. это частичное решение может быть достроено до полного допустимого решения с наимень- шим значением целевой функции среди всех полных допустимых решений, достроенных из любого частичного решения в состоянии B.

Из определения функции F (B) следует, что в каждом множестве Xk (B) достаточно вы- брать доминирующее решение для дальнейших построений.

Обозначим через S множество всех возможных состояний. Это множество называется

пространством состояний.

В методе ДП рекуррентно вычисляют значения F (B) и находят состояние, соответствую- щее оптимальному решению. Затем восстанавливают само оптимальное решение.

Для применения метода ДП необходимо корректно определить

1) пространство состояний S,

2) функцию доминирования F (B), B ∈ S,

3) способ построения частичных решений x1∈ Xk +1 из частичных решений x ∈ Xk,

4) метод вычисления состояния B (x1),используя состояние B (x), если x1∈ Xk +1 ”достроен”

из x ∈ Xk, и

5) рекуррентную формулу для вычисления значений F (B).

Пример алгоритма ДП. В качестве примера рассмотрим следующую задачу. Служа- щий должен выполнить n работ к заданному сроку d, начиная с момента времени ноль. Для каждой работы j задана длительность выполнения pj и штраф wj, выплачиваемый с случае завершения j после d. Все параметры являются неотрицательными целыми чис- лами. Требуется найти такую последовательность выполнения работ, чтобы суммарный штраф был наименьшим.

При заданной последовательности работ (i 1 ,..., in) легко определить момент завершения

j

выполнения каждой работы ij: Cij =

k =1 pik.

Введем в рассмотрение переменные Uj: Uj = 1, если работа j является запаздывающей

(Cj > d), и Uj = 0, если j является ранней (Cj ≤ d). Требуется найти такую последова-

j =1

тельность работ, что значение n

wjUj минимально.

Заметим, что на значение целевой функции влияет лишь информация о том, какие работы являются запаздывающими, а какие ранними. Поэтому существует оптимальная последо- вательность работ, в которой все ранние работы упорядочены произвольно и все запазды- вающие работы упорядочены произвольно и расположены после последней ранней работы.

Тогда задача может быть сформулирована следующим образом:

при условиях

n j =1

n

wjUj→ min

j =1

и

pj (1 − Uj) ≤ d,

Эта задача NP-трудна.

Uj∈ { 0, 1 }, j = 1 ,...,n.

Пусть U ∗ = (U∗,...,U∗) – оптимальный вектор для этой задачи и W ∗ – соответствующее

1 n

значение целевой функции.

Сформулированная задача, в свою очередь, может быть проинтерпретирована в терминах

ДП следующим образом.

Будем формировать частичные решения, определяя переменные Uj = 0 либо Uj = 1 для j = 1 ,..., n. Будем говорить, что частичное решение (U 1 ,..., Uk) находится в со- стоянии (k, a), если определены значения переменных U 1 ,..., Uk и значение ограничения

k

j =1 pj (1 − Uj) = a.

Переменные состояния могут принимать значения k = 0, 1 ,..., n и a = 0, 1 ,..., d.

Из начального состояния (0, 0) можно перейти в состояние (1, 0), при котором U 1 = 1, либо в состояние (1, p 1), где U 1 = 0, если p 1 ≤ d.

Рассмотрим некоторое состояние (k, a), k ∈ { 2 ,..., n}. В это состояние можно перейти только из состояния (k − 1, a), если Uk = 1, либо из состояния (k − 1, a − pk), если Uk = 0.

j =1

Определим функционал доминирования F (k, a) как значение целевой функции k

wjUj,

вычисленное для решений в состоянии (k, a). Из определения функционала F (k, a) следует,

что

W∗ = min {F (n, a) |a = 0, 1 ,...,d}.

Значения F (k, a) могут быть вычислены рекуррентно. Для инициализации рекуррентных вычислений положим F (0, 0) = 0 и F (k, a) = ∞ для всех (k, a) / = (0, 0).

Из определения функции F (k, a) следует, что общее рекуррентное соотношение может быть записано как

F (k, a) = min {F (k − 1, a) + wk, F (k − 1, a − pk) }, (2)

k = 1 ,..., n, a = 0, 1 ,..., d.

При этом, если F (k, a) = F (k − 1, a) + wk, то в частичном решении, соответствующем состоянию (k, a), переменная Uk = 1. Если же F (k, a) = F (k − 1, a − pk), то в этом решении

Uk = 0.

Обратный ход. Оптимальное решение U∗ может быть найдено с помощью следующей

процедуры, называемой обратный ход. Эта процедура использует таблицу размерности

n × (d + 1), в каждой ячейке (k, a) которой хранится информация о том, на первой или

второй компоненте достигается минимум в (2) для указанных значений k и a. На каж-

дой итерации этой процедуры проверяется, на первой или второй компоненте достигается минимум в (2) для определенных значений k и a. На первой итерации полагаем k = n и a = a∗, где a∗ определяется из W ∗ = F (n, a∗). Если минимум в (2) достигается на пер-

k

вой компоненте, то полагаем U ∗ = 1, k:= k − 1, оставляем a без изменений и переходим

k

к следующей итерации процедуры обратного хода. Если минимум достигается на второй компоненте, то полагаем U ∗ = 0, a:= a−pk, k:= k − 1, и переходим к следующей итерации. После выполнения n итераций будет построен оптимальный вектор U ∗ = (U ∗,..., U ∗).

1 n

Время работы и требуемая память. Эффективность алгоритма ДП определяется его временной сложностью и объемом требуемой памяти. Анализ алгоритма для рассматри- ваемой задачи показывает, что вычисление F (k, a) требует выполнения одной операции сложения и одной операции сравнения для каждой пары (k, a). Таким образом, временная сложность этого алгоритма равна O (nd).

Что касается объема памяти, то следует отметить, что для вычисления оптимального зна- чения целевой функции W ∗ на каждом шаге k достаточно хранить таблицу размерности

2 × (d + 1) со значениями F (k − 1, a) и F (k, a), a = 0, 1 ,..., d. Для отыскания оптимального вектора U ∗ достаточно применить процедуру обратного хода, которая требует n (d + 1)

дополнительных единиц памяти.

Из приведенного анализа можно сделать вывод, общий для всех алгоритмов ДП: времен- ная сложность и объем требуемой памяти алгоритма ДП непосредственно зависят от мощности соответствующего пространства состояний.

k

Выбор пространства состояний. Прямые и обратные алгритмы ДП. Как пра- вило, существует несколько вариантов для выбора пространства состояний. Например, для рассматриваемой задачи можно ввести состояния (k, w) такие, что частичное ре- шение находится в состоянии (k, w), если определены значения переменных U 1 ,..., Uk и

i =1 wiUi = w. В этом случае функционал F (k, w) определяется как наименьшее значение

i =1

ограничения k

pi (1 − Ui)для решений в состоянии (k, w). Рекуррентное соотношение

можно записать в виде

F (k, w) = min

(F (k − 1, w) + pk, если F (k − 1, w) + pk ≤ d, F (k − 1, w − wk)

k =1

Соответствующий алгоритм ДП требует O (n n

wk) единиц времени и памяти.

Алгоритмы ДП, в которых частичные решения формируются от начала к концу, как это делается в приведенных выше алгоритмах, называются прямыми. Альтернативный подход состоит в построении частичных решений от конца к началу. Такие алгоритмы называ- ются обратными. Например, рассматриваемая задача может быть решена в пространстве

состояний (k, a) следующим образом. Полагаем F (n + 1, 0) = 0, все остальные начальные значения F (k, a) равными бесконечности и вычисляем

F (k, a) = min {F (k + 1, a − pk), F (k + 1, a) + wk}

для k = n, n − 1 ,..., 1 и a = 0, 1 ,..., d. Оптимальное значение целевого функционала равно

W∗ = min {F (1 ,a) |a = 0, 1 ,...,d}.

Числовой пример решения задачи о рюкзаке методом ДП.

F (x) = x 1 + 2 x 2 + x 3 + x 4 + 2 x 5 + x 6 + 2 x 7 ⇒ max,

B (x) = 2 x 1 + x 2 + 2 x 3 + 2 x 4 + x 5 + x 6 + x 7 ≤ 5, xi∈ { 0, 1 }.

X 0	(0)
F (x)
B (x)

X 1	(0)	(1)
F (x)
B (x)

X 2	(0,0)	(0,1)	(1,0)	(1,1)
F (x)
B (x)

X 3	(0,0,0)	(0,0,1)	(0,1,0)	(0,1,1)	(1,0,0)	(1,0,1)	(1,1,0)	(1,1,1)
F (x)
B (x)

3 предпоследние частичные решения решения можно дальше не рассматривать, так как

есть доминирующие. Далее достраиваем только доминирующие.

X 4	(0,0,0,0)	(0,0,0,1)	(0,0,1,0)	(0,0,1,1)	(0,1,0,0)	(0,1,0,1)	(0,1,1,0)	(0,1,1,1)	(1,1,1,0)	(1,1,1,1)
F (x)
B (x)

X 5	(0,0,0,0,0)	(0,0,0,0,1)	(0,0,0,1,0)	(0,0,0,1,1)	(0,1,0,0,0)	(0,1,0,0,1)	(0,1,1,1,0)	(0,1,1,1,1)
F (x)
B (x)

X 6	(0,0,0,0,0,0)	(0,0,0,0,0,1)	(0,0,0,1,0,0)	(0,0,0,1,0,1)	(0,0,0,1,1,0)	(0,0,0,1,1,1)	(0,1,0,0,1,0)	(0,1,0,0,1,1)
F (x)
B (x)

X 7	(0,0,0,0,0,0,0)	(0,0,0,0,0,0,1)	(0,0,0,0,0,1,0)	(0,0,0,0,0,1,1)	(0,0,0,1,0,0,0)	(0,0,0,1,0,0,1)
F (x)
B (x)

X 7	(0,0,0,1,0,1,0)	(0,0,0,1,0,1,1)	(0,1,0,0,1,0,0)	(0,1,0,0,1,0,1)	(0,1,0,0,1,1,0)	(0,1,0,0,1,1,1)
F (x)
B (x)

Оптимальное решение x∗ = (0, 1, 0, 0, 1, 1, 1) со значением целевой функции F (x∗) = 7.

Дата добавления: 2015-07-08