Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

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

Читайте также:
  1. В оперативной памяти находятся 10 переменных, содержащих числа, - S1, S2, ... S10. Программирование в среде Ассемблера. Сосчитать их произведение.
  2. МОДУЛЬНОЕ ПРОГРАММИРОВАНИЕ
  3. Мультипрограммирование, многопользовательский режим работы и режим разделения времени
  4. НЕЙРО-ЛИНГВИСТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
  5. Программирование алгоритмов разветвляющейся структуры
  6. Программирование в задачах ЕГЭ по информатике.

 

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

 

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; просмотров: 244 | Нарушение авторских прав


Читайте в этой же книге: Многокритериальные задачи | Графический метод решения задач ЛП | Эквивалентные постановки задач ЛП | Симплекс-метод. | Транспортная задача ЛП | Задача о назначениях | Основы теории графов | Кратчайшие пути | Задача коммивояжера и метод ветвей и границ | Монте-Карло |
<== предыдущая страница | следующая страница ==>
Основы теории сложности вычислений| Атарының алғашқы екі мүшесінің қосындысын табыңыз

mybiblioteka.su - 2015-2024 год. (0.017 сек.)