1. Идея метода динамического программирования

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

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

Динамическое программирование может быть применено при выполнении следующих условий:

1) Существует способ выразить решение задачи через решение подзадач меньшей размерности. Этот способ задается рекуррентными соотношениями.

2) Существуют известные решения для задачи малой размерности (задача малой размерности решается просто).

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

Преимущество метода состоит в том, что раз уж задача решена,  ее ответ хранится и никогда не вычисляется заново.

 Можно выделить два класса задач, решаемых методом динамического программирования.

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

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

Мы рассмотрим на примерах использование метода динамического программирования для задач из обоих классов.

2.     Рекуррентные соотношения

Рекуррентные соотношения при использовании динамического программирования связывают решение задачи с решениями подзадач меньшей размерности. Приведем два примера задач, для которых можно записать такие рекуррентные соотношения.

 

Задача о числах Фибоначчи.

Задача состоит в вычислении N-ого числа в последовательности Фибоначчи  0, 1, 2, 3, 5, 8, ... , в которой первое число равно нулю, второе равно единице, а все остальные представляют собой сумму двух предыдущих чисел.

Обозначим F_i число Фибоначчи, стоящее на i-м месте в последовательности (считаем 0 нулевым членом последовательности). Последовательность чисел Фибоначчи определяется рекуррентным соотношением

F₀ =0, F₁ =1, F_i = F_i-1+ F_i-2 при i ≥ 1.              (1)

Задача о числе сочетаний.

Для n-элементного множества сочетанием из n элементов по k называется произвольное подмножество из k элементов. Например, для множества B={a,b,c,d} его подмножество {b,d} – это сочетание из 4-х элементов по 2.

Обозначение  применяется для числа всех сочетаний из n элементов по k. Так, для множества B множество всех двухэлементных подмножеств равно {{a,b}, {a,c}, {a,d}, {b,c}, {b,d}, {c,d}} и, следовательно,

Величины  называются также биномиальными коэффициентами.

Известно рекуррентное соотношение для вычисления :

,                                           (2)

позволяющее вычислять значение  по значениям для числа сочетаний при меньших значениях параметров n и k.

Заметим, что  – быстро растущая функция, поэтому для вычислений по этой формуле нужна арифметика «больших чисел».

3.     Динамическое программирование в задачах на поиск суммы

3.1. Числа Фибоначчи

Формула (1) задает рекуррентное соотношение для чисел Фибоначчи, позволяющее  решать задачу нахождения n-го числа Фибоначчи методом динамического программирования.

Вычисление начинается с задания значений для первых двух чисел Фибоначчи: F₀ =0, F₁ =1. Таким образом, нам известны решения для самых маленьких подзадач. Далее по F₀  и F₁ мы вычисляем F₂ , складывая F₀ и F₁, и запоминаем в таблице, по F₁ и F₂ находим F₃ и его значение запоминаем в таблице, и т.д., до тех пор, пока не найдем n-е число Фибоначчи.

Для хранения вычисляемых чисел Фибоначчи будем использовать одномерный массив F; элемент F[i] содержит значение F_i.

Алгоритм на псевдокоде выглядит так:

begin

      F[0] = 0

      F[1] = 1

      for i = 2 to n do  F[i] = F[i-1]+F[i-2]

      вывести F[n]

end

Число ячеек используемой памяти для вычисления F_n имеет порядок n. Поскольку время вычислений пропорционально числу используемых ячеек массива F, трудоемкость алгоритма оценивается как O(n).

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

3.2. Треугольник Паскаля

Из формулы (2) вытекает эффективный способ рекуррентного вычисления значений биномиальных коэффициентов, который можно представить в графической форме, известной как треугольник Паскаля.

В этом равнобедренном треугольнике каждое число (кроме единиц на боковых сторонах) является суммой двух чисел, стоящих над ним. Число сочетаний  находится в (n+1)-м ряду на (k+1)-м месте.

 

		1
	1		1
	1	2	1
1	3		3	1
1	4	6	4	1

                .         .         .          .          .          .

Рис. 1. Треугольник Паскаля

Чтобы найти значение , достаточно последовательно заполнить таблицу по строкам для n = 1, 2, … , пока не дойдем до нужных значений n и k.

Приведем описание на псевдокоде алгоритма вычисления числа сочетаний, в основе которого лежит метод динамического программирования. Алгоритм использует двумерный массив D, для элемента D[i, j] индекс i соответствует номеру строки таблицы в треугольнике Паскаля, индекс j – номеру столбца.

procedure БИНОМ_КОЭФ(n,k)

begin

 d[1,1]:=1              {заполнение первой строки таблицы}

d[2,1]:=1; d[2,2]:=1    {заполнение второй строки таблицы}

 for i=3 to n+1 do

      begin

            d[i,1]:=1; d[i,i]:=1 {заполнение первого и                       последнего элементов в i-й строке                         треугольника Паскаля}

            for j=2 to i-1 do

              d[i,j]:= d[i-1,j-1]+d[i-1,j] {вычисление                       биномиального коэффициента по двум                           элементам предыдущей строки }

      end

    Вывести d[n+1,k+1]

end

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

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

Заметим, что уменьшение вычислительной сложности алгоритма достигается за счет увеличения объема используемой памяти.

4.     Динамическое программирование в оптимизационных задачах. Перекрытие подзадач

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

Частичные решения, т.е. решения подзадач, из которых получается решение всей задачи, являются оптимальными решениями этих подзадач.

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

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

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

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

4.1. Оптимальная триангуляция многоугольника

Прежде чем сформулировать задачу, введем некоторые определения.

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

Выпуклый многоугольник можно задать, перечислив его вершины в порядке обхода по часовой стрелке. Будем считать, что многоугольник имеет n вершин  v₁, v₂, … , v_n, заданных своими координатами на плоскости.

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

Многоугольник может иметь несколько различных триангуляций, но все они состоят из n-3 диагоналей и разбивают многоугольник на n-2 треугольника. Примеры триангуляций семиугольника приведены на рис. 2.

 Стоимость триангуляции определим как сумму длин диагоналей.

Задача о триангуляции многоугольника состоит в нахождении триангуляции с наименьшей стоимостью.

 SHAPE  \* MERGEFORMAT

v4

v3

v2

v6

v5

v1

v7

v4

v2

v3

v6

v5

v1

v7

Рис. 2. Две триангуляции одного семиугольника

Пусть в оптимальной триангуляции присутствует диагональ (v_i, v_j). Область n-угольника, отсекаемую диагональю (v_i, v_j), будем описывать последовательностью номеров вершин (v_i, v_i+1, … , v_j) в порядке обхода границы области по часовой стрелке.

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

Основываясь на принципе оптимальности, обсудим порядок решения задачи.

 Рассмотрим треугольники, каждый из которых образован некоторой диагональю и двумя соседними сторонами многоугольника. Определим их стоимость равной нулю. Очевидно, число таких «коротких» диагоналей равно n.

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

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

На предпоследнем, (n-4)-м этапе будут решены задачи триангуляции для (n-1)-угольников, и на последнем, (n-3)-м этапе мы получим решение исходной задачи.

Перейдем к описанию рекуррентного соотношения.

Обозначим через C(i, j) длину диагонали n-угольника, соединяющей вершины v_i и v_j. C(i, j) находим по координатам вершин v_i и v_j, используя формулу для расстояния между двумя точками на плоскости: .

Определим T(i, j) как стоимость оптимальной триангуляции j-угольника с начальной вершиной  обхода границы v_i. Положим T(i, 2)=0 и T(i, 3)=0 для i=1,2, … ,n.

При cправедливо следующее рекуррентное соотношение:

 (3)

(В случае если при вычислениях мы получим номер вершины, больший n, возьмем его по модулю n).

 Поясним равенство (3).

Оптимальная триангуляция j-угольника при может быть получена одним из трех способов (см. рис. 3).

1)      Триангуляция может быть получена из оптимальной триангуляции (j-1)-угольника с границей (v_i, v_i+1, … , v_i+j-2), если в триангуляции         j-угольника есть диагональ (v_i ,v_i+j-2). Тогда , т.е.  складывается из стоимости  триангуляции (j-1)-угольника и длины диагонали     (v_i, v_i+j-2).

2)      Триангуляция может быть получена из оптимальной триангуляции (j-1)-угольника с границей (v_i+1, v_i+2, … , v_i+j-1), если в триангуляции         j-угольника есть диагональ (v_i+1 ,v_i+j-1). Тогда .

3)      Третий способ получается, если треугольник со стороной (v_i+1 ,v_i+j-1) образуется в триангуляции j-угольника с помощью еще двух диагоналей (v_i ,v_k) и (v_k, v_i+j-1), где k – некоторая промежуточная вершина при обходе границы j-угольника. В этом случае оптимальная триангуляция j-угольника складывается из оптимальных триангуляций двух многоугольников меньшего размера: многоугольника с границей (v_i, v_i+1, … , v_k) и многоугольника с границей (v_k, v_k+1, … , v_i+j-1) с добавлением двух диагоналей (v_i ,v_k) и (v_k, v_i+j-1). Поэтому к стоимости двух оптимальных триангуляций меньших многоугольников добавляются длины диагоналей (v_i ,v_k) и (v_k, v_i+j-1).

.

Можно немного упростить написание формулы (3), если положить C(i,k)=0 в случае, когда v_i и v_k являются соседними вершинами n-угольника. Тогда рекуррентное соотношение (3) эквивалентно соотношению

.       (4)

Таким образом, используя рекуррентное соотношение (4), сначала находим  стоимости оптимальных триангуляций для всех четырехугольников и заносим результаты в таблицу, затем, используя

vi

vi+j-2

vi+j-1

vi+j-1

vi+j-1

vi+j-2

vk

vi

vi+1

a)

vk

vi+1

vi+j-2

vk

vi

vi+1

b)

c)

Рис. 3. Способы получения триангуляции j-угольника

запомненные результаты и рекуррентное соотношение для j=5, решаем задачу триангуляции для всех пятиугольников,  и т.д.  Продолжаем процесс до тех пор, пока не найдем стоимость оптимальной триангуляции n-угольника. Результаты вычислений последовательно запоминаем в таблице и используем при необходимости, а не вычисляем заново.

4.2. Пример решения задачи о триангуляции

Проиллюстрируем решение задачи о триангуляции на примере семиугольника, заданного следующими координатами своих вершин:

 

Этап 1. При  j =4 формулу (4) можно переписать в виде

.

Применяя эту формулу, заполним первую строку таблицы значениями  для    i =1,2, … , 7.

Этап 2. При  j = 5 формула (4) принимает вид

.

Применяя эту формулу, заполним вторую строку таблицы значениями  для    i =1,2, … , 7.

Этап 3. При  j = 6 формула (4) принимает вид

.

Используя ее, заполняем четвертую строку таблицы значениями  для    i =1,2, … , 7.

Этап 4. При j=7 существует единственный (исходный) 7-угольник, поэтому достаточно вычислить T(1,7):

.

В результате вычислений получим табл. 1.

Таблица 1. Стоимости минимальных триангуляций для подзадач семиугольника

i    j	1	2	3	4	5	6	7
4	16,16	16,16	15,65	15,65	22,05	22,09	17,89
5	37,54	31,81	35,45	37,74	45,50	39,98	38,09
6	53,34	55,22	57,54	59,67	59,78	59,78	63,61
7	75,43

Из таблицы находим, что стоимость минимальной триангуляции равна 75,43.

Таблица, построенная в результате вычислений, позволяет определить стоимость оптимальной триангуляции, из нее непосредственно нельзя определить саму минимальную триангуляцию, так как для этого надо знать значение k, которое обеспечивает минимум в формуле (4). Если мы знаем значение k, тогда решение состоит из диагоналей (v_i ,v_k) и (v_k ,v_i+j-1) (исключая случай k=i+1 или k=i+j-2) плюс диагонали, указываемые решениями T(i, k+1) и T(i+k, j- k +1).

Поэтому при вычислении элементов таблицы полезно включить в нее значения k, при которых получается минимум в формуле (4).

Оптимальная триангуляция рассматриваемого семиугольника приведена на рис. 4.

 SHAPE  \* MERGEFORMAT

v3

v2

v4

v6

v5

v1

v7

Рис. 4. Триангуляция с минимальной стоимостью

4.3. Трудоемкость задачи триангуляции многоугольника при использовании динамического программирования

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

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

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

 

5. Литература

5.1. Использованные источники информации

1. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979. – 536 с.
2. Ахо А.А., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы. М.: Вильямс, 2007. – 400 с.
3. Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: Построение и анализ,. 2-е издание, - М.: Издательский дом "Вильямс", 2005. - 1296 с.
4. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. – М.: Мир, 1980. – 480 с.

5.2. Дополнительная литература

1. Шень А. Программирование: теоремы и задачи. – 3-е изд. – М.: МЦНМО, 2007. – 296 с.