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

Введение

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

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

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

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

Задача о наибольшей общей подпоследовательности

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

Пусть у нас есть последовательность X = {x₁, x₂, …, x_m}, тогда другая последовательность Z = {z₁, z₂, …, z_k} будет подпоследовательностью X, если существует такая возрастающая последовательность индексов I = {i₁, i₂, …, i_m}, что для всех j = 1, 2, …, k, будет верно равенство x_ij = z_j.

Пример. Z = {B, C, D, B} — подпоследовательность X = {A, B, C, B, D, A, B} с набором индексов {2, 3, 5, 7}.

Говорят, что Z — общая подпоследовательность X и Y, если она является подпоследовательностью для X и Y. Тогда определим наибольшую общую подпоследовательность (НОП) двух данных последовательностей как общую подпоследовательность с максимальной длиной.

Теперь задача окончательно формализована, и можно приступать к ее решению. Введем понятие i-го префикса для заданной входной строки. Пусть имеется последовательностьX = {x₁, x₂, …,x_m}. Определим ее i-ый префикс (i = 1, 2, …, m) как X_i = {x₁, x₂, …, x_i}, а X₀ соответственно пустая последовательность. Для того, чтобы лучше понять структуру НОП, весьма полезна следующая теорема.

Теорема (о структуре  НОП)

Пусть Z = {z₁, z₂, …, z_k} — это любая НОП для последовательностей X = {x₁, x₂, …, x_n} и Y = {y₁, y₂, …, y_m}. Тогда

1. Если x_n = y_m, то z_k = x_n = y_m и Z_k−1 — это НОП X_n−1 и Y_m−1.
2. Если x_n ≠ y_m и z_k ≠ x_n, то Z — это НОП X_n−1 и Y.
3. Если x_n ≠ y_m и z_k ≠ y_m, то Z — это НОП X и Y_m−1.

Доказательство.

1. Предположим, что z_n ≠ x_n. Тогда мы можем присоединить x_n = y_m к Z и получить общую последовательность для X и Y длины k+1, но это противоречит нашему предположению о том, что Z — это НОП X и Y. Таким образом, z_k = x_n = y_m. Теперь, префикс Z_k−1 — это общая подпоследовательность для X_n−1 и Y_n−1 длины k−1. Покажем, что она является НОП для X_n−1 и Y_n−1. Предположим, что это не так, тогда существует общая подпоследовательность W дляX_n−1 и Y_n−1 длины большей, чем k−1. Тогда присоединяя к W x_n = y_m получим подпоследовательность общую для X и Y, длины большей, чем k, что противоречит условию.
2. Нужно показать, что если z_n ≠ x_n, то Z — это НОП X_n−1 и Y. Предположим, что это не так, тогда существует подпоследовательность W общая подпоследовательность дляX_n−1 и Y длины большей k. Но тогда W также общая подпоследовательность для X_n и Y, что противоречит тому, что Z это НОП для X и Y.
3. Доказательство этого пункта совершенно аналогично предыдущему.

Непосредственно из теоремы  следует способ нахождения НОП двух заданных последовательностей X = {x₁, x₂, …, x_n} и Y = {y₁, y₂, …, y_m}. Если x_n = y_m, то мы должны искать НОП для X_n−1 и Y_m−1 и, присоединив к этому результату x_n = y_m, мы получим НОП для X и Y. Если же x_n ≠ y_m, то мы должны решить две подзадачи: первая НОП X_n−1 и Y, вторая найти НОП X и Y_m−1. Затем выбрать наибольший из двух результатов, это и будет НОП Xи Y. Заметим, что каждая из двух подзадач потребует решения вновь появившихся подзадач, которые в свою очередь будут выявлять все новые подзадачи.

Остается только выбрать  какой из двух алгоритмов прогонки здесь больше подходит, прямой или обратной. С вычислительной точки зрения наиболее рациональным будет алгоритм прямой прогонки, вычисляющий НОП снизу вверх. В случае вычисления очень удобно организовать в виде таблицы c[0…n, 0…m], где c[i][j] соответствует длине НОП префиксов X_i и Y_j. Значение c[i][j] можем вычислять по следующим правилам:

• 0, если i = 0 или j = 0;
• c[i−1][j−1] + 1, если i, j > 0 и x_i = y_j;
• max(c[i][j−1], c[i−1][j]), если i, j > 0 и x_i ≠ y_j.

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

LCS-LENGTH(X,Y)

 1 m = length[X]

2 m = length[Y]

3 for i = 1 to m

4   do c[i, 0] = 0

5 for i = 1 to m

6   do c[0, j] = 0

7 for i = 1 to m do

8   do for j = 1 to n

9     do if x_i = y_i

10            then c[i,j] = c[i − 1, j − 1] + 1;

11                 b[i,j] = «стрелка по диагонали»

12            else if c[i − 1, j] ≥ c[i, j - 1]

13                    then c[i, j] = c[i − 1, j]

14                         b[i, j] = «стрелка вверх»

15                    else c[i, j] = c[i, j − 1]

16                         b[i, j] = «стрелка влево»

17 return b, c

На следующем рисунке  показана работа алгоритма для X = {A, B, C, B, D, A, B} и Y = {B, D, C, A, B, A}

Теперь покажем, как непосредственно  найти саму НОП.

PRINT_LCS(b, X, i, j)

1 if i = 0 or j = 0

2    then return

3 if b[i, j] = «стрелка по диагонали»

4    then PRINT_LCS(b, X, i −  1, j − 1)

5         print v_i

6 elseif b[im j] = «стрелка вверх»

7    then PRINT_LCS(b, X, i −  1, j)

8 else PRINT_LCS (b, X, i, j − 1)

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

Связь динамического  программирования и регулярных выражений

Шаблоном называется строка состоящая из букв латинского алфавита (a, …, z, A, …, Z) и символов ? и *. Каждый из символов ? разрешается заменить на одну произвольную букву, а каждый из символов * на произвольную (возможно пустую) последовательность букв. Про любую строку из букв, которую можно получить из шаблонов такими заменами, будем говорить, что она удовлетворяет данному шаблону. Тогда задачу состоит в том, чтобы для двух заданных шаблонов найти строку минимальной длины, которая удовлетворяет обоим шаблонам, либо выяснить, что такой строки не существует.

Нельзя не отметить, что  подобного рода задачи, находят большое  применение на практике, обычно они  возникают при анализе и разборе  регулярных выражений. Итак, пусть заданы два шаблона, S[1…M] и T[1…N]. Введем обозначение F(i, j) для строки минимальной длины, которая удовлетворяет шаблонам S[1…i] и T[1…j]. Если такой строки нет, то вF(i, j), будет стоять специальная пометка, говорящая об этом.

Вычисляем значение F(i, j) в порядке возрастания i, а при равных i, в порядке возрастания j. Возможны следующие содержательные ситуации (считаем, что i, j > 0, а разбор граничных случаев, не представляет особого интереса, и может быть оставлен как упражнение).

1. S[i] и T[j] — буквы. Если они совпадают, то в качестве значения F(i, j) берем F(i−1, j−1) с добавленной в конце этой буквой. Если в F(i−1, j−1) стоит пометка, говорящая о том, что строки не существует, то аналогичную пометку можно поставить и в F(i, j). В случае несовпадения букв S[i] и T[j], в F(i, j) необходимая строка также не существует.
2. S[i] и T[j] — буква и символ «?» или два символа «?». Поступаем точно так же, как и в предыдущей ситуации, однако случае несовпадения букв из-за наличия «?» здесь быть не может.
3. S[i] — символ «*», а T[j] — буква или символ «?». В данной ситуации выбираем наиболее короткое среди значений F(i, j−1) и F(i−1, j) с дописанной к нему буквой T[j] (или любой буквой, если T[j] есть символ «?» ).
4. S[i] — буква или символ «?», а T[j] — символ «*». Поступаем аналогично разобранному выше пункту.
5. S[i] и T[j] — два символа «*». В этом случае в качестве F(i, j), берем наиболее короткое из значений F(i, j−1) и F(i−1, j).

Задача триангуляции

В качестве еще одного примера  динамического программирования рассмотрим задачу триангуляции многоугольника. Заданы вершины многоугольника и расстояния между каждой парой вершин. Это расстояние может быть геометрическим расстоянием на плоскости или произвольной функцией стоимости, заданной в виде таблицы. Задача заключается в том, чтобы выбрать такую совокупность хорд (линий между несмежными вершинами), что никакие две хорды не будут пересекаться, а весь многоугольник будет поделен на треугольники. Общая длин всех хорд должна быть минимальной. Такая совокупность хорд называется минимальной триангуляцией. Зафиксируем несколько фактов, которые помогут разработать необходимый алгоритм. Предполагаем, что наш многоугольник имеет n вершин v₀, v₁, …, v_n−1, перечисленных по часовой стрелке.

1. В случае триангуляции любого многоугольника, содержащего более трех вершин, с каждой парой смежных вершин связана, по крайней мере одна хорда. Чтобы убедиться в этом, предположим, что ни v_i, ни v_i+1 не связаны ни с одной из хорд. В таком случае область, ограничиваемая стороной (v_i, v_i+1), должна бы включать стороны (v_i−1, v_i), (v_i+1, v_i+2) и по крайней мере еще одну дополнительную сторону или хорду. Но в таком случае это область не была бы треугольником.
2. Если (v_i, v_j) является хордой в триангуляции, значит должна найтись, такая вершина v_k что каждая из линий (v_i, v_k) и (v_k, v_i) либо стороной многоугольника либо хордой . В противном случае хорда (v_i, v_j), ограничивала бы область, не являющуюся треугольником.

Чтобы приступить к поиску минимальной триангуляции, выберем  две смежные вершины, например v₀ и v₁. Из указанных выше фактов следует, что в любой триангуляции (а значит и в минимальной) должна найтись такая вершина v_k, что (v₁, v_k) и (v_k, v₀) являются хордами или сторонами многоугольника. Необходимо рассмотреть, насколько приемлемую триангуляцию можно построить после выбора каждого значения k. Если в многоугольнике n вершин, то в нашем распоряжении имеется (n−2) возможных вариантов. Каждый вариант выбора k приводит к не более чем двум подзадачам, где мы имеем многоугольники образованные, одной хордой и сторонами исходного многоугольника. Например, могут возникнуть такие подзадачи при случае выбора вершины v₃.

Далее нужно найти минимальную  триангуляцию для многоугольников, полученных в результате появления  новых подзадач. Правда, если мы будем  решать все подзадачи, которые будут  появляться, то мы получим алгоритм с экспоненциальной трудоемкостью. Но, имея треугольник, включающий хорду (v₀, v_k), нам никогда не придется рассматривать многоугольники, у которых более одной стороны являются хордами исходного многоугольника. «Факт 2» говорит о том, что при минимальной триангуляции хорда в подзадаче (например, хорда (v₀, v₃) на рис. 1) должна составлять треугольник с одной из остальных вершин многоугольника.

Определим подзадачу размера s, начинающуюся с вершины v_i и обозначаемую S_is, как задачу минимальной триангуляции для многоугольника, образованного s вершинами, начинающегося с вершины v_i и содержащего вершины v_i, v_i+1, …, v_i+s−1, перечисляемые в порядке обхода вершин по часовой стрелке. В v₀ хордой является замыкающая сторона (v_i, v_i+s−1). Чтобы решить подзадачу S_is необходимо рассмотреть три варианта:

1. Можно выбрать вершину v_i+s−2, чтобы составить треугольник с хордами (v_i, v_i+s−1), (v_i, v_i+s−2) и третьей стороной (v_i+s−2, v_i+s−1), а затем решить подзадачу S_i,s−1.
2. Мы можем выбрать вершину v_i+1, чтобы составить треугольник с хордами (v_i, v_i+s−1), (v_i+1, v_i+s−1) и третьей стороной (v_i, v_i+1), а затем решить подзадачу S_i+1,s−1.
3. Для некоторого k из диапазона от 2 до s−3 можно выбрать вершину v_i+k и образовать треугольник со сторонами (v_i, v_i+k), (v_i+k, v_i+s−1), (v_i, v_i+s−1), а затем решить подзадачи S_i,k+1 и S_i+k,s−k.

Если учесть, что решение  подзадачи размером не более трех не требует вообще никаких действий, то рассматривая описанные варианты 1–3, следует предпочесть вариант 3, где нужно выбрать некоторое k из диапазона от 1 до s−2 и решить подзадачи S_i,k+1 S_i+k,s−k. Если для решения задачи размером более четыре и более воспользоваться очевидным рекурсивным алгоритмом, непосредственно вытекающим из перечисленных выше вариантов, то можно показать что общее число рекурсивных вызовов составляет 3^s−4, если подсчитать лишь обращения к подзадачам размером четыре и более. Таким образом количество подзадач, которые необходимо решить, возрастает по экспоненциальному закону в зависимости от s. А следовательно общее количество шагов экспоненциально зависит и от n.

Но известно, что, помимо исходной задачи существует лишь n(n−4) различных подзадач, которые в любом случае необходимо решить. Значит в приведенном анализе что-то явно не совсем верно. Очевидно, что совсем не все подзадачи отличаются между собой, если действовать рекурсивно, как приведено выше, то у нас возникают ситуации, когда одни и те же ситуации приходится решать несколько раз. Именно это подсказывает нам эффективный способ вычисления триангуляции. Прежде всего, вычисления удобно организовать в виде таблицы. Назначим стоимость C_is триангуляции S_is для всех i и s. Поскольку решение любой данной задачи зависит от решения задач меньшего размера, то логичным порядком заполнения такой таблицы является порядок, основанный на размерах подзадач, т. е. для размеров s = 4, 5, …, n−1 мы указываем минимальную стоимость задач S_is для всех вершин i. Удобно включить и задачи размеров 0 ≤ s < 4, но при этом нужно помнить, что S_is имеет стоимость 0, если s < 4.

В соответствии с перечисленными выше вариантами действий 1–3 при определении  подзадач формула вычисления C_is при s ≥ 4 должна иметь следующий вид:

C_is = min_{1≤k≤s−2} {C_i,k+1 + C_i+k,s−k + D(v_i, v_i+k) + D(v_i+k, v_i+s−1)},

где D(v_p, v_q) — это длина хорды между вершинами v_p и v_q, если v_p и v_q не являются смежными вершинами многоугольника; D(v_p, v_q) равняется 0, если являются смежными вершинами.

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

Задача о загрузке

Задача о загрузке — это задача о рациональной загрузке судна (самолета, автомашины, и т. п.), которое имеет ограничения по объему или грузоподъемности. Каждый помещенный на судно груз приносит определенную прибыль. Задача состоит в том, чтобы определении загрузки, такими грузами которые приносят наибольшую прибыль.

Отметим также, что данная задача известна как задача о рюкзаке, в который турист должен определить наиболее ценные предметы, подлежащие загрузке в рюкзак. Формализуем нашу задачу. Пусть W — грузоподъемность нашего судна и есть в наличии n наименований предметов, которые подлежат загрузке. Пусть m_i — количество предметов i-го наименования, r_i — прибыль, которую приносит один загруженный предмет i-го наименования, w_i — вес одного предмета i-го наименования. Тогда общая задача имеет вид следующей целочисленной задачи линейного программирования.

Максимизировать Z = r₁m₁ + r₂m₂ + … + r_nm_n при условии, что

w₁m₁ + w₂m₂ + … + w_nm_n ≤ W, 
m₁, m₂, …, m_n ≥ 0.

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

1. Определение этапов.
2. Определения на каждом этапе вариантов решения (альтернатив).
3. Определения состояний на каждом этапе.

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

1. Какие соотношения связывают этапы вместе?
2. Какая информация необходима для того, чтобы получить допустимые решения на текущем этапе без повторной проверки решений, принятых на предыдущих этапах.

В приведенной задаче о  загрузке три элемента модели динамического программирования определяются следующим образом.

1. Этап i ставится в соответствие предмету i-го наименования, i = 1, 2, …, n.
2. Варианты решения на этапе i описываются количеством предметов m_i предметов i-го наименования, подлежащих загрузке. Соответствующая прибыль равна r_im_i. Значение заключено m_i в пределах от 0 до [W⁄w_i], где [W⁄w_i] — целая часть числа W⁄w_i.
3. Состояние x_i на i выражает суммарный вес предметов, решения о погрузке которых приняты на этапах i, i+1, …, n. Это определение отражает тот факт, что ограничение по весу является единственным, которое связывает вместе все n этапов.

Пусть f_i(x_i) — максимальная суммарная прибыль от этапов i, i+1, …, n при заданном состоянии x_i. Определим рекуррентное уравнение с помощью следующей двухшаговой процедуры.

1. Выразим f_i(x_i) как функцию f_i+1(x_i+1) в виде

f_i(x_i) = max {r_im_i + f_i+1(x_i+1)}, i = 1, 2, …, n,

где max берется по всем

m_i = 0, 1, …, [W⁄w_i] и x_i = 0, 1, …, W,

где f_n+1(x_n+1) ≡ 0.

2. Выразим x_i+1 как функцию x_i для гарантии того, что левая часть последнего уравнения является функцией лишь x_i. По определению x_i+1 − x_i представляет собой вес, загруженный на этапе i, т. е. x_i+1 − x_i = w_im_i или x_i+1 = x_i − w_im_i. Тогда рекуррентное уравнение приобретает следующий вид.

f_i(x_i) = max {r_im_i + f_i+1(x_i−w_im_i)}, i = 1, 2, …, n,

где max берется по всем

m_i = 0, 1, …, [W⁄w_i] и x_i = 0, 1, …, W.

Задача о загрузке является типичным представителем задачи распределения  ресурсов, в которой ограниченный ресурс распределяется между конечным числом видов (экономической) деятельности. В таких моделях определения  состояния на каждом этапе будет  аналогично приведенному для задачи о загрузке : состоянием на этапе i является суммарное количество ресурса, распределяемого на этапах i, i+1, …, n.

Заключение

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

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

Литература

1. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — М.: МЦНМО, 1999.
2. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. — М.: Издательский дом «Вильямс», 2001.
3. Таха Х. Введение в исследование операций. — М.: Издательский дом «Вильямс», 2001.
4. Беров В.И., Лапунов А.В., Матюхин В.А., Пономарев А.Е. Особенности национальных задач по информатике. — Киров: Триада-С, 2000.

Камышан Андрей

Маша / 2009-05-27 21:27:59

Хочу сказать спасибо  автору за такую статью. Кучу сайтов, посвященных информатике, пересмотрела, но нигде такой доступной раскладки  алгоритма LCS не встретила. Да и к  тому же везде статьи повторяются. Еще  раз огромное спасибо!!!!

Виталий / 2010-07-08 12:21:22

Похоже, что в задаче о  загрузке есть ошибка:

"... По определению x(i+1) &#8722; x(i) представляет собой вес,  загруженный на этапе i, т. е. x(i+1) &#8722; x(i) = w(i)m(i) или x(i+1) = x(i) &#8722; w(i)m(i). Тогда рекуррентное уравнение  приобретает следующий вид.

fi(x(i)) = max {r(i)m(i) + f(i+1)(x(i)&#8722;w(i)m(i))}, i = 1, 2, ?, n,..."

Если x(i+1) &#8722; x(i) = w(i)m(i), то логично, чтобы x(i+1) = x(i) + w(i)m(i), а не x(i+1) = x(i) &#8722; w(i)m(i).

Миша / 2011-11-14 00:35:37

Автору спасибо за статью. Маша, ты не читала Окулова? Это очень  толковая книга и там про lcs хорошо написано