16
правок
Изменения
Нет описания правки
== Определения ==
{{Определение
|definition=
Последовательность <tex> Z = \left \langle z_1, z_2, ...\dots, z_k \right \rangle </tex> является '''подпоследовательностью''' (англ. ''subsequence'') последовательности <tex> X = \left \langle x_1, x_2, ...\dots, x_m \right \rangle </tex>, если существует строго возрастающая последовательность <tex> \left \langle i_1, i_2, ...\dots, i_k \right \rangle </tex> индексов <tex> X </tex> таких, что для всех <tex> j = 1, 2, ...\dots, k </tex> выполняется соотношение <tex> x_{i_j} = z_j </tex>.
}}
Другими словами, подпоследовательность данной последовательности — это последовательность, из которой удалили ноль или больше элементов. Например, <tex> Z = \left \langle B, C, D, B \right \rangle </tex> является подпоследовательностью последовательности <tex> X = \left \langle A, B, C, B, D, A, B \right \rangle </tex>, а соответствующая последовательность индексов имеет вид <tex> \left \langle 2, 3, 5, 7 \right \rangle </tex>.
{{Определение
|definition=
Последовательность <tex> Z </tex> является '''общей подпоследовательностью''' (англ. ''common subsequence'') последовательностей <tex> X </tex> и <tex> Y </tex>, если <tex> Z </tex> является подпоследовательностью как <tex> X </tex>, так и <tex> Y </tex>.}} {{Задача|definition=Найти '''наибольшую общую подпоследовательность''' (англ. ''longest common subsequence, <tex>LCS</tex>''), которая является самой длинной подпоследовательностью нескольких последовательностей (обычно двух).
}}
== Наивное решение ==
Переберем все различные подпоследовательности обеих строк и сравним их. Тогда искомая <tex>LCS </tex> гарантированно найдётся, однако время работы алгоритма будет экспоненциально зависеть от длины исходных последовательностей.
== Динамическое программирование ==
{{
Теорема|statement=
Пусть имеются последовательности <tex> X = \left \langle x_1, x_2, ...\dots, x_m \right \rangle </tex> и <tex> Y = \left \langle y_1, y_2, ...\dots, y_n \right \rangle </tex>, а <tex> Z = \left \langle z_1, z_2, ...\dots, z_k \right \rangle </tex> — их <tex>LCS</tex>.
# Если <tex> x_m = y_n </tex>, то <tex> z_k = x_m = y_n </tex> и <tex> Z_{k - 1} </tex> — <tex>LCS </tex> <tex> X_{m - 1} </tex> и <tex> Y_{n - 1} </tex># Если <tex> x_m \neq y_n </tex>, то из <tex> z_k \neq x_m </tex> следует, что <tex> Z </tex> — <tex>LCS </tex> <tex> X_{m - 1} </tex> и <tex> Y </tex># Если <tex> x_m \neq y_n </tex>, то из <tex> z_k \neq y_n </tex> следует, что <tex> Z </tex> — <tex>LCS </tex> <tex> X </tex> и <tex> Y_{n - 1} </tex>
|proof=
# Если бы выполнялось <tex> z_k \neq x_m </tex>, то к <tex> Z </tex> можно было бы добавить элемент <tex> x_m = y_n </tex>, и тогда получилась бы общая подпоследовательность длины <tex> k + 1 </tex>, что противоречит предположению, что <tex> Z </tex> — <tex>LCS</tex>. Значит, выполняется <tex> z_k = x_m = y_n </tex>. Значит, <tex> Z_{k - 1} </tex> — общая подпоследовательность <tex> X_{m - 1} </tex> и <tex> Y_{n - 1} </tex>. Докажем от противного, что <tex> Z_{k - 1} </tex> — <tex>LCS</tex>: тогда есть общая подпоследовательность <tex> W </tex>, длина которой больше <tex> k - 1 </tex>. Добавив к <tex> W </tex> элемент <tex> x_m = y_n </tex>, получим <tex>LCS </tex> <tex> X </tex> и <tex> Y </tex>, длина которой больше <tex> k </tex> (т.е. больше длины <tex> Z </tex>), что приводит к противоречию.# Если <tex> z_k \neq x_m </tex>, то <tex> Z </tex> — общая подпоследовательность <tex> X_{m - 1} </tex> и <tex> Y </tex>. Пусть существует их общая подпоследовательность <tex> W </tex>, длина которой превышает <tex> k </tex>. Она также является общей подпоследовательностью <tex> X </tex> и <tex> Y </tex>, что противоречит предположению о том, что <tex> Z </tex> (длины <tex> k </tex>) — <tex>LCS </tex> <tex> X </tex> и <tex> Y </tex>.
# Аналогично второму случаю.
}}
=== Решение ===
Обозначим как <tex> lcs[i][j] </tex> <tex> LCS </tex> префиксов данных последовательностей, заканчивающихся в элементах с номерами <tex> i </tex> и <tex> j </tex> соответственно. Получается следующее рекуррентное соотношение:
<tex>
=== Построение подпоследовательности ===
Для каждой пары элементов помимо длины <tex>LCS </tex> соответствующих префиксов хранятся и номера последних элементов, участвующих в этой LCS.Таким образом, посчитав ответ, можно восстановить всю наибольшую общую подпоследовательность.
=== Псевдокод ===
<tex> x </tex>, <tex> y </tex> — данные последовательности; <tex> lcs[i][j] </tex> — <tex>LCS </tex> для префикса длины <tex> i </tex> последовательности <tex> x </tex> и префикса длины <tex> j </tex> последовательности <tex> y </tex>; <tex> prev[i][j] </tex> — пара индексов элемента таблицы, соответствующего оптимальному решению вспомогательной задачи, выбранной при вычислении <tex> lcs[i][j] </tex>.
''<font color="green">// подсчёт таблиц</font>''
printLCS(prev, x, i, j - 1)
== Оптимизация для вычисления только длины <tex>LCS </tex> ==
Заметим, что для вычисления <tex> lcs[i][j] </tex> нужны только <tex> i </tex>-ая и <tex> (i-1) </tex>-ая строчки матрицы <tex> lcs </tex>. Тогда можно использовать лишь <tex> 2 \cdot min(m, n) </tex> элементов таблицы:
''<font color="green">// ответ — lcs[n]</font>''
== Длинна кратчайшей общей подпоследовательности суперпоследовательности ==Для двух подпоследовательностей <tex> X = \left \langle x_1, x_2, ...\dots, x_m \right \rangle </tex> и <tex> Y = \left \langle y_1, y_2, ...\dots, y_n \right \rangle </tex> длинна кратчайшая общей подпоследовательности суперпоследовательности равна
<tex>
|SCS(X,Y)| = n + m - |LCS(X,Y)|
</tex>
<ref>[http://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Relation_to_other_problems Wikipedia {{---}} Longest common subsequence problem]</ref>
== См. также ==
*[[Наибольшая общая возрастающая подпоследовательность]]
*[[Задача о наибольшей общей палиндромной подпоследовательности]]
== Примечания ==
<references />
== Список литературы ==
