418
правок
Изменения
Нет описания правки
{{Определение
|definition=
Последовательность <tex> z Z = \left \langle z_1, z_2, ..., z_k \right \rangle </tex> является '''подпоследовательностью''' (subsequence) последовательности <tex> x X = \left \langle x_1, x_2, ..., x_m \right \rangle </tex>, если существует строго возрастающая последовательность <tex> \left \langle i_1, i_2, ..., i_k \right \rangle </tex> индексов <tex> x X </tex> таких, что для всех <tex> j = 1, 2, ..., k </tex> выполняется соотношение <tex> x_{i_j} = z_j </tex>.
}}
Другими словами, подпоследовательность данной последовательности — это последовательность, из которой удалили ноль или больше элементов. Например, <tex> z Z = \left \langle B, C, D, B \right \rangle </tex> является подпоследовательностью последовательности <tex> x 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 Z </tex> является '''общей подпоследовательностью''' (common subsequence) последовательностей <tex> x X </tex> и <tex> y Y </tex>, если <tex> z Z </tex> является подпоследовательностью как <tex> x X </tex>, так и <tex> y Y </tex>.
}}
== Постановка задачи ==
Даны две последовательности: <tex> x X = \left \langle x_1, x_2, ..., x_m \right \rangle </tex> и <tex> y Y = \left \langle y_1, y_2, ..., y_n \right \rangle </tex>. Требуется найти общую подпоследовательность <tex> x X </tex> и <tex> y Y </tex> максимальной длины. Заметим, что таких подпоследовательностей может быть несколько.
== Наивная идея решения ==
== Динамическое программирование ==
Данная задача решается с использованием принципа оптимальности на префиксе.
=== Доказательство оптимальности ===
{{
Теорема|statement=
Пусть имеются последовательности <tex> X = \left \langle x_1, x_2, ..., x_m \right \rangle </tex> и <tex> Y = \left \langle y_1, y_2, ..., y_n \right \rangle </tex>, а <tex> Z = \left \langle z_1, z_2, ..., z_k \right \rangle </tex> — их НОП.
1) Если <tex> x_m = y_n </tex>, то <tex> z_k = x_m = y_n </tex> и <tex> Z_{k - 1} </tex> — НОП <tex> X_{m - 1} </tex> и <tex> Y_{n - 1} </tex>
2) Если <tex> x_m \neq y_n </tex>, то из <tex> z_k \neq x_m </tex> следует, что <tex> Z </tex> — НОП <tex> X_{m - 1} </tex> и <tex> Y </tex>
3) Если <tex> x_m \neq y_n </tex>, то из <tex> z_k \neq y_n </tex> следует, что <tex> Z </tex> — НОП <tex> X </tex> и <tex> Y_{n - 1} </tex>
|proof=
1) Если бы выполнялось <tex> z_k \neq x_m </tex>, то к <tex> Z </tex> можно было бы добавить элемент <tex> x_m = y_n </tex>, и тогда получилась бы общая подпоследовательность длины <tex> k + 1 </tex>, что противоречит предположению, что <tex> Z </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> W </tex>, длина которой больше <tex> k - 1 </tex> (т.е. больше длины <tex> Z </tex>). Добавив к <tex> W </tex> элемент <tex> x_m = y_n </tex>, получим НОП, длина которой больше <tex> k </tex>, что приводит к противоречию.
2) Если <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> X </tex> и <tex> Y </tex>/
3) Аналогично второму случаю.
}}
=== Решение ===
<tex>
Очевидно, что сложность алгоритма составит <tex> O(mn) </tex>, где <tex> m </tex> и <tex> n </tex> — длины последовательностей.
=== Построение подпоследовательности ===
