Главная » Java, Структуры данных и алгоритмы » Применение динамического программирования для поиска наиболее длинной общей подпоследовательности

0

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

Напомним, что для решения поставленной задачи имеются две строки X и У длиной пит каждая, и требуется определить самую длинную строку S, которая будет подпоследовательностью обеих строк одновременно. Так как Хи У состоят из символов, имеется естественное множество индексов, с помощью которых можно определить подзадачи — индексы в строке Хи в строке К

Определим подзадачи таким образом, чтобы использовать при вычислениях значения L[i,j], применяемого для хранения длины наиболее длинной строки, являющейся подпоследовательностью обеих X = х$х\х2 … х, и У= УоУ\У2 – У/- Это позволит переопределять L[i,j] для оптимального решения подзадачи, что зависит от ситуации, которая может быть следующей (см. рис. 11.12).

Рис. 11.12. ‘Два случая алгоритма наиболее длинной общей подпоследовательности: (а) дс/ =у/, (b) xt ф уу Заметьте, что алгоритм сохраняет только значения L[i,j], а не совпадения

•          х,- — уу В этом случае имеется совпадение последнего символа в … /] и последнего символа в У[0 …Д. рудем считать, что этот символ принадлежит наиболее длинной общей подпоследовательности из Х[0 … /] и У [О …у]. Для доказательства предположим, что это утверждение неверно. В то же время для Хи У существует некоторая наиболее длинная общая подпоследовательность хпха … xik = = У]\У/2 — У]к- Если xik = Xj или У]к~Ур то подпоследовательность удлиняется добавлением х, в ее конец. Таким образом, самая длинная общая подпоследовательность в ^[0 … /] и У[0 …у] будет заканчиваться на X/. Следовательно, устанавливаем

L[iJ] = L[i -1,у -1] + 1, если х. =У;

•          X/ * yj. В этом случае невозможно получить общую подпоследовательность из X/ и Уу То есть можно получить общую подпоследовательность, заканчивающуюся только на х, или на Уу или (возможно) ни ту ни другую, но никак не обе. Следовательно, устанавливаем

L[iJ] = max{L[/ -1,у],?[/,у-1],} если х,- *уг

Чтобы оба эти уравнения имели смысл даже при / = 0 или j = 0, полагаем W> — 1 ] = 0 при / = -1, 0, 1,…, я – 1 и L[-\J] = 0 при j = -1, 0, 1,…, т – 1.

Такое определение для L[i,j\ отвечает требованиям оптимизации подзадачи, так как невозможно получить наиболее длинную общую подпоследовательность, не имея наиболее длинной подпоследовательности для данной подзадачи. К тому же здесь применяется наложение подзадач, так как решение подзадачи L[i,J\ может использоваться и в других задачах (а именно, задачах L[i + 1 J], L[iJ + 1] и L[i + 1J + 1]).

Алгоритм определения наиболее длинной общей подпоследовательности

Превращение описанного определения L[i,j] в алгоритм представляется достаточно простым и наглядным. Создается массив (п + 1) х (т + 1), L для пограничных случаев, когда i = 0 или j = 0. То есть L[i, -1] = 0 для / = -1, 0, 1, п- 1, и L[-l,j\ = 0 для j= -1, 0, 1, т – 1 (при этом порядок несколько нарушается, поскольку в действительности строки и столбцы в L должны индексироваться, начиная с 0). Затем итеративно определяются значения L до тех пор, пока не получим L[n – 1,/я – 1], длину наиболее длинной общей подпоследовательности Хи Y. Псевдокод такого подхода в динамическом программировании для решения задачи поиска наиболее длинной общей подпоследовательности приведен во фрагменте кода 11.9.

Алгоритм LCS(X,Y):

Input: строки Хи У из п и т элементов соответственно.

Output: длина L[iJ] наиболее длинной строки для / = 0,…, п -1,у = 0, т – 1, которая является общей подпоследовательностью обеих строк ЛГ[0…/] = Л Ъ ••• х и Y[Q…i] = yQyxy2 …yj.

fop / <————- 1 to n – 1 do

/.[/,—1 ] <- 0 for j <- 0 to m – 1 do

L[-1, /] <- 0 for / <- 0 to n – 1 do for у <- 0 to m – 1 do if Xj = yj then

L[ij] <- L[i- 1, y- 1] + 1 else

L[iJ] <- max{L[/- 1, y] , L[i, /- 1]} return array L

Фрагмент кода 11.9. Алгоритм динамического программиробания для задачи определения наиболее длинной общей подпоследовательности (LCS)

Производительность

Время выполнения алгоритма фрагмента кода 11.9 можно легко проанализировать, поскольку он управляется двумя вложенными циклами: внешний выполняет п итераций, а внутренний — т итераций. Поскольку каждое if-услойие и каждая установка внутри цикла требуют по 0(1) времени на базовую операцию, алгоритм выполняется за О(пт) времени. Таким образом, методика динамического программирования может применяться в задачах наиболее длинной общей подпоследовательности, значительно повышая результативность по сравнению с силовым решением этой задачи в экспоненциальном времени.

Алгоритм LCS (фрагмент кода 11.9) определяет длину найболее длинной общей подпоследовательности (хранящейся в L[n- 1, /и – 1]), но не саму подпоследовательность. Как показано ниже, простая операция, выполняемая после этого алгоритма, позволяет вычленить подпоследовательность из массива L, возвращаемого алгоритмом.

Утверждение 11.7. При наличии строки Хкз п символов и строки Y из т символов наиболее длинная общая подпоследовательность Хи Коп- ределяется за 0(пт) времени.

Доказательство. Алгоритм LCS вычисляет длину наиболее длинной общей подпоследовательности L[n- 1, т- 1] за 0(пт) времени. Имея таблицу значений L[i,j], построить такую подпоследовательность достаточно просто. Первый метод заключается в реконструировании наиболее длинной общей подпоследовательности от конца к началу, начиная от L[n, т] и следуя в обратном направлении через таблицу, В любой позиции L[i,j] просто определяется, является ли х, = у у Если это верно, то х, принимается в качестве следующего символа подпоследовательности (х, расположен перед предыдущим обнаруженным символом при наличии такового), перемещаясь к L[i- 1 , у- 1]. Если х, * ур то передвигаемся к следующему L[i,j- 1] и L[i- 1 J] (см. рис. 11.13). Останавливаемся при достижении последней ячейки (где / = -1 или j = -1). Метод выстраивает наиболее длинную общую подпоследовательность дополнительно за 0(п + т) времени.

Рис. 11.13. Алгоритм построения наиболее длинной общей подпоследовательности из массива L

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии