Изменения

Перейти к: навигация, поиск
Нет описания правки
'''[[Задача о наибольшей общей подпоследовательности]]''' (англ. ''longest common subsequence (LCS)'') {{---}} классическая и хорошо изученная проблема.
'''[[Задача о наибольшей подпоследовательности-палиндроме]]''' (англ. ''longest palindromic subsequence (LPS)'') {{- --}} также хорошо изучена.
В этой статье мы рассмотрим задачу, которая объединяет две вышеперечисленные задачи в одну.
'''Наибольшая общая подпалиндромная подпоследовательность''' (англ. ''The longest common palindromic subsequence (LCPS)'') {{---}} задача, являющаяся интересным вариантом классической задачи о поиске наибольшей общей подпоследовательности, которая находит наибольшую общую подпоследовательность среди двух последовательностей тактакже накладывает условия, что она также является эта подпоследовательность должна быть палиндромом.
{{Задача
|definition = Для последовательности <tex>X</tex>, мы обозначим его её подпоследовательность <tex>x_{i}...x_{j} \ (1 \leqslant i \leqslant j \leqslant n)\ </tex> как <tex>X_{i,j}</tex>. Для двух последовательностей <tex>X</tex> и <tex>Y</tex>, если общая подпоследовательность <tex>Z</tex> последовательностей <tex>X</tex> и <tex>Y</tex> является палиндромом, то <tex>Z</tex> называется '''общей подпалиндромной подпоследовательностью''' (англ. ''common palindromic subsequence''). Общая подпалиндромная последовательность, имеющая максимальную длину, называется '''наибольшей общей подпалиндромной подпоследовательностью''' (англ. ''The longest common palindromic subsequence (LCPS)'') и мы обозначим её как <tex>LCPS(X,Y)</tex>.
}}
==Наивное решение==
Можно придумать такое решение данной задачи: найти наибольшую общую подпоследовательность, в ней найти наибольшую подпалиндромную подпоследовательность. Но, к сожалению, это решение '''неверно'''.
===Контрпример===
Возьмем 2 две последовательности <tex>X=[1,\ 2,\ 3,\ 1]</tex> и <tex>Y=[1,\ 1,\ 2,\ 3]</tex>.
Наибольшей общая подпоследовательность данных последовательностей равна <tex>LCS(X,Y) = [1,\ 2,\ 3]</tex> и в ней наибольшая подпалиндромная последовательность имеет длину <tex>1</tex>.
Но очевидно, что на самом деле последовательность <tex>Z=[1,\ 1]</tex> является наибольшим общей палиндромной подпоследовательностью <tex>X</tex> и <tex>Y</tex> и имеет длину <tex>2</tex>.==[[Динамическое программирование]]Решение с помощью динамического программирования==Заметим, что в качестве подзадач для <tex>LCPS</tex>, в которых мы можем посчитать ответ, логично взять подпоследовательность от <tex>X</tex> и от <tex>Y</tex>. Основываясь на этом наблюдении мы сформулируем следующую теорему, которая доказывает оптимальную подструктуру свойств задачи <tex>LCPS</tex>, что даст возможность воспользоваться идеей [[Динамическое программирование | динамического программирования]].
{{Теорема
|statement=Пусть <tex>X</tex> и <tex>Y</tex> - две последовательности длин <tex>n</tex> и <tex>m</tex> соответственно, а <tex>X_{i,j}</tex> и <tex>Y_{i,j}</tex> {{---}} две подпоследовательности последовательностей <tex>X</tex> и <tex>Y</tex> соответственно. Пусть <tex>Z = z_{1}z_{2}...z_{u}</tex> - наибольшая общая подпалиндромная последовательность двух подпоследовательностей <tex>X_{i,j}</tex> и <tex>Y_{k,l}</tex>. Тогда выполняются следующие утверждения,
 #Если <tex>x_i=x_j=y_k=y_l=a</tex> (для произвольного <tex>a</tex>), тогда <tex>z_1=z_u=a</tex> и <tex>z_2...z_{u-1}</tex> {{---}} наибольшая общая палиндромная подпоследовательность от подпоследовательностей <tex>X_{i+1,j-1}</tex> и <tex>Y_{k+1,l-1}</tex>.#Если <tex>x_i=x_j=y_k=y_l</tex> не выполняется, то <tex>Z</tex> {{---}} наибольшая общая палиндромная подпоследовательность от подпоследовательностей (<tex>X_{i+1,j}</tex> и <tex>Y_{k,l}</tex>) или (<tex>X_{i,j-1}</tex> и <tex>Y_{k,l}</tex>) или (<tex>X_{i,j}</tex> и <tex>Y_{k+1,l}</tex>) или (<tex>X_{i,j}</tex> и <tex>Y_{k,l-1}</tex>).
}}
На основании теоремы мы напишем следующую рекурсивную формулу для длины наибольшей общей подпалиндромной подпоследовательности:
<tex>
lcps[i,j,k,l] = \left\{\begin{array}{llcl}
0&&;&i > j\ or\lor\ k > l\\1&&;&(i = j)\ and\land\ (k = l)\ and\land\ (x_i=x_j=y_k=y_l)\\2+lcps[i+1,j-1,k+1,l-1]&&;&(i < j)\ and\land\ (k < l)\ and\land\ (x_i=x_j=y_k=y_l)\\\max{(}lcps[i+1,j,k,l],lcps[i,j-1,k,l],&&;&(i \leqslant j)\ and\land\ (k \leqslant l)\ and\ notland\ \lnot(x_i=x_j=y_k=y_l)\\\:\:\:\:\:\:\:\:\:\:\:lcps[i,j,k+1,l],lcps[i,j,k,l-1])
\end{array}\right.
</tex>
===Реализация===
Будем использовать динамику с запоминанием ответа(с мемоизацией). Оформим решения в виде рекурсивной функции <tex>lcps</tex>, которая возвращает ответ для подзадачи, на которую она была вызвана.<br> В массиве <tex>\mathtt{ans}</tex> хранятся ответы для подзадач. До запуска функции <tex>lcps</tex> заполним массив <tex>ans</tex> значением <tex>-1</tex> . Так как каждое значение считается не более одного раза и будем использовать такую логику: мы имеем подзадачу эта операция происходит за <tex>lcpsO(i,j,k,l1)</tex>, если <tex>ans[i][j][k][l] = -1</tex>, то значение для данной подзадачи мы еще не вычисляли и именно этим мы и займемся, иначе значение уже посчитано и мы можем просто вернуть <tex>ans[i][j][k][l]</tex>. Так как каждое значение считается не более одного раза, мы получим асимптотику <tex>O(n^4)</tex>.
===Псевдокод===
'''int''' lcps (i: '''int''', j: '''int''', k: '''int''', l: '''int''') '''if''' (ans[i][j][k][l] <tex> \neq </tex> -1) <span style="color:Green">// если так, то значение уже посчитано и нужно просто , то надо его вернуть</span>
'''return''' ans[i][j][k][l]
'''if''' (i > j '''or''' k > l)
ans[i][j][k][l] = 1
'''return''' 1
'''else''' tmp ans[i][j][k][l] = (2 + lcps(i + 1, j - 1, k + 1, l - 1)) '''return''' tmp(2 + lcps(i + 1, j - 1, k + 1, l - 1)) ans[i][j][k][l] = tmp tmp = '''max'''(lcps(i + 1, j, k, l), lcps(i, j - 1, k, l), lcps(i, j, k + 1, l), lcps(i, j, k, l - 1)) ans[i][j][k][l] = tmp '''return''' tmpmax(lcps(i + 1, j, k, l), lcps(i, j - 1, k, l), lcps(i, j, k + 1, l), lcps(i, j, k, l - 1))
==См. также==
* [[Динамическое программирование]]* [[Задача о наибольшей общей возрастающей подпоследовательности]]* [[Задача о наибольшей подпоследовательностиредакционном расстоянии, алгоритм Вагнера-палиндромеФишера]]
==Источники информации==
* [https://www.academia.edu/2015585/Computing_a_Longest_Common_Palindromic_Subsequence Academia.edu {{---}} Computing a Longest Common Palindromic Subsequence]
 
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]
55
правок

Навигация