Динамическое программирование (Dynamic Programming)

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

Кратчайший путь Пример. Дано: ориентированный взвешенный граф G=(V, A), c ij 0 – длина дуги (i, j). Требуется найти кратчайший путь из s t. Если кратчайший путь из s в t проходит через вершину p, то пути из s в p и из p в t также кратчайшие. Принцип оптимальности: подпуть кратчайшего пути также является кратчайшим. Обозначим через d(v) длину кратчайшего пути из s v. Тогда где I(v) = {i V : (i, v) A}. svt I(v)I(v) G

Кратчайший путь (Алгоритм Дейкстры) s 7 t T=O(|V| 2 ) M=O(|V|) Итерации: t

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

Задача производства и хранения продукции (I)(I)

Лемма. 1) opt решение: s t-1 x t =0, t=1,…,n. для нек. целого k 0. 2) opt решение : если x t >0, то Доказательство. Предположим, что моменты запуска производства выбраны opt (известно по каким дугам (0,t) идет положительный поток). Т.к. в сети нет ограничений на пропускные способности дуг opt решение : положительные дуговые потоки определяют дерево. Значит, только одна из дуг, имеющих концевой вершину t, может иметь положительный поток s t-1 x t = 0 утверждение 2).

Задача производства и хранения продукции Обоз.исключаем s t где Введем ц.ф. Если день t k является последним, когда осуществлялось производство (то есть x t =d tk ), то, очевидно, функционал H(t 1) также должен принимать min зн. H(n) - opt зн. ц.ф. Т.к. k = t(n) – 1 t(k) – предпоследний момент запуска производства… T=O(n 2 ), M=O(n)

Пример n = 4, d = (2, 4, 5, 1), p = (3, 3, 3, 3), h = (1, 2, 1, 1), f = (12, 20, 16, 8). Вычислим c = (8, 7, 5, 4), (d 1,1, d 1,2, d 1,3, d 1,4 ) = (2, 6, 11, 12) и const Прямой ход. Применив рекуррентные соотношения, получим: H(0)=0. H(1)= f 1 +c 1 d 1 =12+8 2=28; t(1)=1. H(2)=min{H(0)+f 1 +c 1 d 1,2, H(1)+f 2 +c 2 d 2 }= min{12+8 6, }=min{60, 76} = 60; t(2) = 1. H(3)=100; t(3) = 1. H(4)=106; t(4) = 3. Обратный ход. Из у-о решения t(4)=3 в opt решении последний раз производство осуществлялось в 3-й день. y 4 =x 4 =0, y 3 =1, x 3 =d 3 +d 4 =6. Т.к. t(2)=1, то y 2 =x 2 = 0, y 1 =1, x 1 =d 1 +d 2 =6. opt решение x=(6,0,6,0), y=(1,0,1,0), s=(4,0,1,0).

Другой алгоритм Сведем исх. задачу к задаче поиска кратчайшего пути в ориентированном взвешенном графе, в кот.: {0,1,...,n} - множество вершин; дуги (i, j), для всех i < j длина дуги (i, j) равна f i+1 +c i+1 d i+1,j стоимости запуска производства + стоимость производства продукции в день i+1 для удовлетворения потребностей периодов i+1,…,j. H(k) - длина кратчайшего пути из вершины 0 k

Булева задача о ранце Для =0,1,..., A и векторов (x 1,...,x k ), k=1,...,n, рассмотрим семейство задач: (P k ( )) - если k-й предмет не выбирается, то S k ( ) = S k-1 ( ); - иначе, S k ( ) = c k + S k-1 ( a k ). рекуррентные соотношения:

Булева задача о ранце Прямой ход S 1 ( )=0 при 0 1, то полагаем = a k, k=k 1 и повторяем итерацию. T=O(nA) M=O(nA)

Пример S 1 / x 1 S 2 / x 2 S 3 / x 3 S 4 / x 4 00 / / 17 / / 110 / / 117 / 117 / / 117 / 117 / / 117 / 117 / 024 / / 117 / 125 / 131 / / 117 / 132 / 134 / 1

Целочисленная задача о ранце P( ) Теорема. Справедливы следующие рекуррентные соотношения: Доказательство. Пусть x * ( ) – opt вектор задачи (P( )) S( )=(c, x * ( )). Если S( ) > 0 k : P(A)P(A)

Обратный ход Полагаем x * = 0, и * = А. Найдем индекс k=1,…,n: S( * )=S( * a k )+c k, a k *. (*) Полагаеми повторяем итерацию Если = (*) не выполняется ни для 1 номера k, то построенный вектор x * opt T=O(An) M=O(A+n)

Обратная задача о ранце x 0 ( ) – opt решение задачи Лемма. Функция Q( ) является неубывающей. Доказательство. Пусть 2 > 1 x 0 ( 2 ) доп. р. задачи Q( 2 ) = (a, x 0 ( 2 )) Q( 1 ). Рекуррентные соотношения: T=O(nB) M=O(B+n)

Связь прямой и обратной задач о ранце Теорема (Связь прямой и обратной задач о ранце). Пусть Тогдаи opt решение о.з.является opt и для п.з. Доказательство. Обозн. S * = S(A). Так как x * (A) – доп. вектор для обеих задач и P(A), то Q(S * ) (a, x * (A)) A. Из неравенства Q(S * ) A и определения С др. ст., т.к. opt решение о.з. п.з. (P(A)) является доп. для Теорема. ПустьТогда и opt решение п.з.является также opt решением x 0 (В) о.з.

Общая задача о ранце сепарабельная функция Рекуррентные соотношения:

Задача о ближайшем соседе Линейный объект представлен отрезком [0, M], M Z + точки разбиения x k [0, M] Z f(x, y) 0, 0 x y M – затраты на обслуживание отрезка [x, y] [0, M] 0Mxy f(x, y) P(k, y)

Рекуррентные соотношения Представим, что задан отрезок [0, y], y [0, M], и известно opt разбиение отрезка [0, x], x y на k 1 частей. Тогда 0Mxy f(x, y) S k-1 (x) рекуррентные соотношения: T=O(nM 2 ) M=O(nM)

ЗБС с произвольным числом точек разбиения f(x, y) 0 0Mxy f(x, y) S(x)S(x) рекуррентные соотношения: T=O(M 2 ) M=O(M)

Условие Глебова Функция f удовлетворяет условию (Глебова), если точек x 1 y 1 y 2 x 2 вып. неравенство f(x 1, x 2 )+f(y 1, y 2 ) f(x 1, y 2 )+f(y 1, x 2 ). x1x1 x2x2 y1y1 y2y2 f(y 1, y 2 ) f(x1, x2)f(x1, x2) f(x1, y2)f(x1, y2) f(y1, x2)f(y1, x2)

Замечания Кроме приведенных выше постановок ЗБС, на практике встречаются случаи, когда число отрезков разбиения принадлежит отрезку n [a, b], где a и b заданные целые числа. Способ решения таких задач будет рассмотрен на семинарах. При вычислении opt значений ц.ф. S k используются только значения S k-1, найденные на предыдущем шаге. Если не хранить всю таблицу значений S k (y), y = 0, …, Y, k = 1, …, n, а также не запоминать у-о решения, то можно сократить память в n раз. Такой вариант ДП называется релаксационным и состоит из (n 1)-го прямого хода…