ство умножении для каждой из них, или же с помощью алгоритма Recursive-Matrix-Chain?

16.2-3 Нарисуйте дерево рекурсии для алгоритма Merge-Sort (сортировка слиянием) из раздела 1.3.1, применённого к массиву из 16 элементов. Почему здесь нет смысла запоминать ответы к уже решённым подзадачам?

16.3. Наибольшая общая подпоследовательность

Подпоследовательность получается из данной последовательности, если удалить некоторые её элементы (сама последовательность также считается своей подпоследовательностью). Формально: последовательность Z = (z\, z2,..., Zk) называется подпоследовательностью (subsequence) последовательности X = (х\, ж2,..., хп), если существует строго возрастающая последовательность индексов (ii, г2,..., ik), Для которой Zj = жг-. при всех j = 1, 2,..., к. Например, Z = (B,C,D,B) является подпоследовательностью последовательности X = (А, В, С, В, D, А, В); соответствующая последовательность индексов есть (2,3,5,7). (Отметим, что говоря о последовательностях, мы - в отличие от курсов математического анализа - имеем в виду конечные последовательности.)

Будем говорить, что последовательность Z является общей подпоследовательностью (common subsequence) последовательностей X и У, если Z является подпоследовательностью как X, так и У. Пример: X = (А, В, С, В, D, А, В), У = (В, D, С, А, В, А), Z = (В, С, А). Последовательность Z в этом примере - не самая длинная из общих подпоследовательностей X и У (последовательность (В, С, В, А) длиннее). Последовательность (В, С, В, А) будет наибольшей общей подпоследовательностью для X и У, поскольку общих подпоследовательностей длины 5 у них нет. Наибольших общих подпоследовательностей может быть несколько. Например, (В, D, А, В) - другая наибольшая общая подпоследовательность X и У.

Задача о наибольшей общей подпоследовательности (сокращенно НОП; по-английски LCS = longest-common-subsequence) состоит в том, чтобы найти общую подпоследовательность наибольшей длины для двух данных последовательностей X и У. В этом разделе мы покажем, как решить эту задачу с помощью динамического программирования.

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

Если решать задачу о НОП «в лоб», перебирая все подпоследовательности последовательности X и проверяя для каждой из них, не будет ли она подпоследовательностью последовательности У, то алгоритм будет работать экспоненциальное время, поскольку последовательность длины то имеет 2т подпоследовательностей (столько же, сколько подмножеств у множества {1, 2,..., то}).

Однако задача о НОП обладает свойством оптимальности для подзадач, как показывает теорема 16.1 (см. ниже). Подходящее множество подзадач - множество пар префиксов двух данных последовательностей. Пусть X = (х\, х2, , хт) - некоторая последовательность. Её префикс (prefix) длины г - это последовательность Х{ = (х\, х2, , х{) (при г от 0 до то). Например, если X = (А, В, С, В, D, А, В), то Х4 = (А, В, С, В), а Х0 - пустая последовательность.

Теорема 16.1 (о строении НОП). Пусть Z = (z\, z2,..., Zk) -

одна из наибольших общих подпоследовательностей для X = (xt,x2,. ..,хт) uY = (yi,y2,. ..,уп)- Тогда:

1.если хт = уп, то Zj~ = хт = уп и Zk-\ является НОП для Хт \ и Уп-Ъ

2.если хт ф уп и Zk ф хт, то Z является НОП для Хт \ и Y;

3.если хт ф уп и Zk ф Уп, то Z является НОП для Хт и Yn-\-

Доказательство. (1) Если Zk ф хт, то мы можем дописать хт = уп в конец последовательности Z и получить общую подпоследовательность длины к + 1, что противоречит условию. Стало быть, Zk = хт = уп. Если у последовательностей Xm-i и Yn-\ есть более длинная (чем Zk-\) общая подпоследовательность, то мы можем дописать к ней хт = уп и получить общую подпоследовательность для X и У, более длинную, чем Z - противоречие.

(2)Коль скоро Zk ф хт, последовательность Z является общей подпоследовательностью для Xm-i и У. Так как Z - НОП для X и У, то она тем более является НОП для Xm-i и У.

(3)Аналогично (2).□

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

Рекуррентная формула

Теорема 16.1 показывает, что нахождение НОП последовательностей X = (х\, х2,..., хт) и У = (yi, у2,..., уп) сводится к реше-

нию либо одной, либо двух подзадач. Если хт = уп, то достаточно найти НОП последовательностей Xm i ии дописать к ней в

конце хт = уп. Если же хт ф уп, то надо решить две подзадачи: найти НОП для Xm i и У, а затем найти НОП для X и Yn-\. Более длинная из них и будет служить НОП для X и У.

Теперь сразу видно, что возникает перекрытие подзадач. Действительно, чтобы найти НОП X и У, нам может понадобиться найти НОП Хт \ и У, а также НОП X и Уга-1; каждая из этих задач содержит подзадачу нахождения НОП для Xm i и Yn-\. Аналогичные перекрытия будут встречаться и далее.

Как и в задаче перемножения последовательности матриц, мы начнём с рекуррентного соотношения для стоимости оптимального решения. Пусть c[i,j] обозначает длину НОП для последовательностей Х{ и Yv Если г или j равно нулю, то одна из двух последовательностей пуста, так что c[i,j] = 0. Сказанное выше можно записать так:

Вычисление длины НОП

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

Исходными данными для алгоритма LCS-Length служат последовательности X = (х\, Х2, , хт) и У = (у\, у2, , Уп) Числа c[i,j] записываются в таблицу с[0 . .то, 0 . .га] в таком порядке: сначала заполняется слева направо первая строка, затем вторая, и т. д. Кроме того, алгоритм запоминает в таблице Ь[1.. то, 1.. га] «происхождение» c[i, j]: в клетку b[i,j] заносится стрелка, указывающая на клетку с координатами [г - 1, j - 1), [г - l,j) или (г, j - 1), в зависимости от того, равно ли c[i,j] числу с[г - 1, j - 1] + 1, c[i - или c[i,j - 1] (см. (16.5)). Результатами работы алгоритма являются таблицы cub.

0

Ф, j] = < c[i - 1, j - 1] + 1

max(c[i,j - l],c[i- l,j])

если г = 0 или j = 0, если i,j > 0 и Xi = yj, если i,j > 0 и Xi ф yj.

(16.5)