Здесь мы разберем решение задачи о НОП.
В различных биологических задачах часто необходимо сравнивать ДНК двух или нескольких организмов. Моделью молекулы ДНК можно считать строку, над алфавитом из четырех символов (А, Г, Ц, Т). Тогда поставить задачу можно следующим образом: даны две строки, требуется найти подпоследовательность наибольшей длины, входящую в оба слова. Теперь сформулируем задачу в более общем случае.
Пусть есть последовательность X = {x1, x2, ..., xm},
тогда другая последовательность Z = {z1, z2, ..., zk}
будет подпоследовательностью X, если существует такая возрастающая
последовательность индексов I = {i1, i2, ..., ik},
что для всех j = 1, 2, ..., k, будет верно равенство
.
Пример: Z = {B, C, D, B} — подпоследовательность X = {A, B, C, B, D, A, B} с набором индексов I = {2, 3, 5, 7}.
Говорят, что Z - общая подпоследовательность X и Y, если она является подпоследовательностью для X и Y.
Тогда определим наибольшую общую подпоследовательность (НОП) двух данных последовательностей как общую подпоследовательность с максимальной длиной. Наибольших общих подпоследовательностей может быть несколько.
Пример: X = {A, B, C, B, D, A, B}, Y = {B, D, C, A, B, A}. Общая подпоследовательность: Z = {C, A, B}. Наибольшая общая подпоследовательность: Z1 = {B, D, A, B}, Z2 = {B, C, A, B}, Z3 = {B, C, B, A}.
Задача о наибольшей общей подпоследовательности состоит в том, чтобы найти общую подпоследовательность наибольшей длины для двух данных последовательностей [1, с.300].
Теперь задача окончательно формализована, и можно приступать к ее решению. Введем понятие i-го префикса для заданной входной строки. Пусть имеется последовательность X = {x1, x2, ..., xm}. Определим ее i-ый префикс (i = 1, 2, ..., m) как Xi = {x1, x2, ..., xm}, а X0 соответственно пустая последовательность. Для того чтобы лучше понять структуру НОП, весьма полезна следующая теорема.
Теорема (о структуре НОП)[1]:
Пусть Z = {z1, z2, ..., zk} — это одна из НОП для последовательностей X = {x1, x2, ..., xn} и Y = {y1, y2, ..., ym}. Тогда:
- Если xn = ym, то zk = xn = ym и Zk-1 — это НОП Xn-1 и Ym-1;
- Если xn ≠ ym и zk ≠ xn, то Z — это НОП Xn-1 и Y;
- Если xn ≠ ym и zk ≠ ym, то Z — это НОП X и Ym-1.
Примем теорему без доказательства.
Непосредственно из теоремы следует способ нахождения НОП двух заданных последовательностей X = {x1, x2, ..., xn} и Y = {y1, y2, ..., ym}. Если xn = ym , то нужно искать НОП для Xn-1 и Ym-1 и, присоединив к этому результату xn = ym , получим НОП для X и Y. Если же xn ≠ ym, то нужно решить две подзадачи: первая НОП Xn-1 и Y, вторая найти НОП X и Ym-1. Затем выбрать наибольший из двух результатов, это и будет НОП X и Y. Заметим, что каждая из двух подзадач потребует решения вновь появившихся подзадач, которые в свою очередь будут выявлять все новые подзадачи.
Остается только выбрать какой из двух алгоритмом прогонки здесь больше подходит, прямой или обратной. С вычислительной точки зрения наиболее рациональным будет алгоритм прямой прогонки, вычисляющий НОП снизу вверх. В случае вычисления очень удобно организовать в виде таблицы c[0…n, 0…m], где c[i, j] соответствует длине НОП префиксов Xi и Yj . Значение c[i, j] можем вычислять по следующим правилам:
- 0, если i = 0 или j = 0;
- c[i-1, j-1] + 1, если i > 0, j > 0 и xi = yj;
- max(c[i, j-1], c[i-1, j]), если i > 0, j > 0 и xi ≠ yj.
Таким образом, можно найти длину НОП, а для того чтобы найти саму НОП, необходимо хранить некоторую дополнительную информацию. Удобно хранить информацию, о том, по какому условию осуществляется переход. Для этого удобно использовать таблицу B[1..n, 1..m], где b[i, j] соответствует условию перехода. b[i, j] может принимать следующие значения:
- 3 – если переход осуществлен из клетки таблицы c[i-1, j-1];
- 1 – если переход осуществлен из клетки таблицы c[i-1, j];
- 2 – если переход осуществлен из клетки таблицы c[i, j-1].
Текст процедуры LCS_LENGTH, вычисляющей наибольшую длину подпоследовательности последовательностей X, Y (заполнение таблицы c[1..n, 1..m]) и заполняющей таблицу b[1..n, 1..m] можно посмотреть здесь.
Таким образом, получена длина НОП и путь ее получения. Осталось лишь найти саму подпоследовательность. Так как нужно найти лишь строку (НОП будем представлять в виде строкового типа), то целесообразнее использовать функцию, а не процедуру. При входе в подпрограмму запрашивается четыре параметра: i, j – размерность двумерного массива B или длина последовательностей X и Y; X – одна из последовательностей (то из чего составляется подпоследовательность); B – таблица пути получения НОП. На выходе получаем строку, содержащую НОП. L – строка, которая и будет содержать НОП X и Y. Первоначально она пуста. Затем идет получение НОП. Цикл while позволяет перемещаться по таблице B и находить элементы X, которые входят в НОП X и Y. При чем по таблице B двигаться начинаем с последнего элемента. Цикл заканчивается, когда достигнут первый элемент таблицы B, то есть элемент b[0,0]. При чем в НОП входят только те элементы, для которых b[i, j] = 3, то есть которые входят как в последовательность X, так и в Y. Последний шаг функции – значению функции присваивается значение переменной L, то есть сама НОП. Текст функции PRINT_LGS1 можно посмотреть здесь.
В тексте основной программы должно содержать обращение сначала к процедуре LCS_LENGTH, а затем к функции PRINT_LGS1. При этом не помешало бы сделать проверку: имеется ли вообще НОП этих двух последовательностей.
Решение вы можете посмотреть
здесь.
(1)Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — М.: МЦНМО, 2000.-960с.,263 ил.
На следующем шаге мы разберем решение задачи "Чебурашка".
