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

Введение

Динамическое программирование (ДП) определяет оптимальное решение 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.