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

Метод «Разделяй и властвуй» сводит решение задачи к разделению на несколько простых подзадач и их решению с объединением результатов. Часто не удается разделить задачу на подзадачи, либо в результате разделения получается N^m подзадач с многократным решением одних и тех же подзадач. В результате получается алгоритм с экспоненциальной сложностью.

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

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

Виды алгоритмов ДП могут быть различными. Общей их частью является лишь заполняемая таблица и порядок заполнения ее элементов.

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

Здесь процесс решения сводится к пошаговому заполнению таблицы.

Алгоритм ДП вычисляет решения всех подзадач от малых к большим, и ответы запоминаются в таблице. Это не дает сокращения объема задачи, но алгоритм является простым и понятным. Выигрыш по времени достигается лишь за счет исключения повторного решения подзадач.

Алгоритм ДП в худшем случае имеет экспоненциальную сложность для задач со сложностью порядка O(n!).

В теории ДП выделяют 3 аспекта:

1 – теоретический (ДП используется для доказательства теорем существования сходимости и др.);

2 – прикладной (ДП используется для построения модели задач оптимизации);

3 – вычислительный (касается программной реализации).

Основные работы по ДП написаны Беллманом, Венцем и Вагнером.

В основе поиска оптимального решения в алгоритме ДП лежит принцип оптимальности Беллмана:

Оптимальное решение обладает тем свойством, что какими бы ни были начальное состояние и начальное решение, все последующие решения должны быть оптимальной последовательностью решений относительно текущего состояния.

Этот метод дает глобальное оптимальное решение, в отличие от эвристик или «жадного алгоритма». Для ДП решение на каждом шаге должно быть оптимальным с точки зрения процесса в целом.

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

Примеры задач:

1. Задачи оптимального распределения ресурсов.

2. Задачи оптимального управления запасами.

3. Задача реинженеринга (оптимальная стратегия модернизации).

4. Задача оптимального плана производства.

5. Задачи целочисленного линейного программирования.

6. Задачи маршрутизации (сетевые графики, транспортные перевозки).

Пример 1:

Задача коммивояжера.

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

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

Определим параметр T(i; j₁, j₂, …, j_k) как стоимость оптимального маршрута от вершины с индексом i в первую вершину, который проходит каждый город в точности один раз в любом порядке и не проходит через другие города, не принадлежащие подмножеству j.тогда принцип оптимальности приводит к следующей системе рекуррентных соотношений:

Данная система является рекуррентной, т. к. каждое частное решение рекурсии описывается как покрытие подмножества городов, то возможно 2ⁿ подмножеств из n покрытий.

Поэтому верхняя граница сложности 2ⁿ  O(2ⁿ), т. е. гораздо лучше, чем алгоритм прямого перебора, сложность которого O_пр(n!).

При n=5 дерево рекурсии выглядит следующим образом:

Т (1; 2, 3, 4, 5)

Т(2; 3, 4, 5) Т(3; 2, 4, 5) Т(4; 2, 3, 5) Т(5; 2, 3, 4)

Т(3; 4, 5) Т(4; 3, 5) Т(5; 3, 4) Т(2; 4, 5) Т(2; 3, 5) Т(3; 2, 5) все повторы

Т(4; 5) Т(5; 4) Т(3; 5) Т(5; 3) Т(3; 4) Т(4; 3) Т( 4; 5) Т(5; 4)

Здесь заметно дублирование решений в листьях. Однако дублирование может появляться и в узлах при больших n. Чем раньше они появятся, тем лучше. При этом алгоритм «поиска с возвратом» не позволяет исключать дублирующие ветви и листья, в отличие от ДП.

Пример 2:

Вероятность победы в спортивном турнире.

Две команды (А и В) проводят серию игр до N побед любой из команд. Предполагается, что силы команд равны (Р=0,5). Ничья не допускается.

Пусть Р(i, j) – вероятность того, что для победы команде А нужно провести i матчей, а для победы команды В – j матчей.

Составляется рекуррентное соотношение:

где P(i-1, j) – вероятность выигрыша команды А, если она победит в очередной игре;

P(i, j-1) – вероятность победы А в турнире, если в очередной игре она проиграет.

Для вычисления таблицы вероятностей требуется время  O(2^i+j).

Пусть i+j = n = const.

В этом случае получаем:

T(n)  2^n-1*C+(2^n-1-1)*d=O(2ⁿ) – верхняя граница сложности

i=j  (2ⁿ/ )

При этом для вычисления рекурсии нужно находить одно и то же значение P(i,j) несколько раз.

Например, при построении дерева при Р(2, 3) нужно вычислить предварительное значение

Р(2, 3)

Р(1, 3) Р(2, 2)

 

Р(1, 2) Р(1, 2)

В методе динамического программирования таблица вероятностей строится, начиная с правого нижнего угла

1/2	21/32	15/16	15/16	1
11/32	1/2	11/16	7/8	1
3/16	5/16	1/2	3/4	1
1/16	1/8	1/4	1/2	1
0	0	0	0	-

Function ODDS (i, j: integer): real;

var S, K: integer;

begin

for S:=1 to i+j do begin

P[0, S]:=1; P[S, 0]:=0;

end;

for K:=1 to S-1 do

P[K, S-K]:=(P[K-1, S-K]+P[K, S-K-1])/2;

Result:=P[i, j];

end;

Сложность всей программы при n=i+j O(n²).

Пример 3:

Произведение матриц.

Пусть требуется вычислить произведение матриц М=М₁*М₂*М₃*…*М_к, где M_i(i-1, j).

Порядок перемножения матриц может существенно влиять на число операций независимо от выбранного метода умножения.

Для перемножения (p; q)*(q; r) потребуется p*q*r операций. В результате получится матрица (p; r).

Рассмотрим конкретный числовой пример:

М=М₁(10, 20)*М₂(20, 50)*М₃(50, 1)*М₄(1, 100)

Вычисление произведения этих матриц согласно общим правилам (справа налево) М=М₁*(М₂*(М₃*М₄)) потребует 125 тысяч операций.

Умножение другим способом М=(М₁*(М₂*М₃))*М₄ потребует 220 тысяч операций.

Однако процесс перебора всех способов перемножения с целью минимизировать число операций имеет экспоненциальную сложность O(2^n-1-2), что неприемлемо при больших n.

Алгоритм динамического программирования, дающий метод поиска оптимального произведения матриц, имеет полиномиальную сложность O(n²).

Зададим минимальную стоимость произведения матриц М_i*М_i+1*… *М_j, 1  i  j  n:

Эта формула дает минимально возможную сложность из набора k значений (i, j-1).

В алгоритме динамического программирования m_ij вычисляется в порядке возрастания разностей нижних индексов:

m_ii,  i

m_i,i+1­ и т. д.

При этом в формуле m_ik и m_{k+1, j} оказываются ранее вычисленными на момент поиска m_ij.

Для приведенного примера построим таблицу сложности.

m11=0	m22=0	m33=0	m44=0
m12=10000	m23=1000	m34=5000	-
m13=1200	m24=3000	-	-
m14=2200	-	-	-

Алгоритм может быть реализован в виде функции, вычисляющей минимальную стоимость, и выглядящей следующим образом:

Function MinMatrix(N: integer): longint;

begin

for i:=1 to n do m[i, i]:=0;

for l:=1 to n-1 do

for i:=1 to n-1 do

begin

j:=i+l;

m[i, j]:= min(m[i, k]+m[k+1, j]+r[i-1]*r[k]*r[j]);

end;

Result:=m[1, n];

end;