Задача о наибольшей общей палиндромной подпоследовательности — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
'''[[Задача о наибольшей общей подпоследовательности]]''' (англ. ''longest common subsequence (LCS)'') {{---}} классическая и хорошо изученная проблема.
 
'''[[Задача о наибольшей общей подпоследовательности]]''' (англ. ''longest common subsequence (LCS)'') {{---}} классическая и хорошо изученная проблема.
  
'''[[Задача о наибольшей подпоследовательности-палиндроме]]''' (англ. ''longest palindromic subsequence (LPS)'') - также хорошо изучена.
+
'''[[Задача о наибольшей подпоследовательности-палиндроме]]''' (англ. ''longest palindromic subsequence (LPS)'') {{---}} также хорошо изучена.
  
 
В этой статье мы рассмотрим задачу, которая объединяет две вышеперечисленные задачи в одну.
 
В этой статье мы рассмотрим задачу, которая объединяет две вышеперечисленные задачи в одну.
  
'''Наибольшая общая подпалиндромная подпоследовательность''' (англ. ''The longest common palindromic subsequence (LCPS)'') {{---}} задача, являющаяся интересным вариантом классической задачи о поиске наибольшей общей подпоследовательности, которая находит наибольшую общую подпоследовательность среди двух последовательностей так, что она также является палиндромом.
+
'''Наибольшая общая подпалиндромная подпоследовательность''' (англ. ''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>.
+
|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>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>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>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>.
+
Заметим, что в качестве подзадач для <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>. Тогда выполняются следующие утверждения,
 
|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>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>).
 
}}
 
}}
 
На основании теоремы мы напишем следующую рекурсивную формулу для длины наибольшей общей подпалиндромной подпоследовательности:
 
На основании теоремы мы напишем следующую рекурсивную формулу для длины наибольшей общей подпалиндромной подпоследовательности:
Строка 28: Строка 29:
 
<tex>
 
<tex>
 
lcps[i,j,k,l] = \left\{\begin{array}{llcl}
 
lcps[i,j,k,l] = \left\{\begin{array}{llcl}
0&&;&i > j\ or\ k > l\\
+
0&&;&i > j\ \lor\ k > l\\
1&&;&(i = j)\ and\ (k = l)\ and\ (x_i=x_j=y_k=y_l)\\
+
1&&;&(i = j)\ \land\ (k = l)\ \land\ (x_i=x_j=y_k=y_l)\\
2+lcps[i+1,j-1,k+1,l-1]&&;&(i < j)\ and\ (k < l)\ and\ (x_i=x_j=y_k=y_l)\\
+
2+lcps[i+1,j-1,k+1,l-1]&&;&(i < j)\ \land\ (k < l)\ \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\ (k \leqslant l)\ and\ not(x_i=x_j=y_k=y_l)\\
+
\max{(}lcps[i+1,j,k,l],lcps[i,j-1,k,l],&&;&(i \leqslant j)\ \land\ (k \leqslant l)\ \land\ \lnot(x_i=x_j=y_k=y_l)\\
lcps[i,j,k+1,l],lcps[i,j,k,l-1])
+
\:\:\:\:\:\:\:\:\:\:\:lcps[i,j,k+1,l],lcps[i,j,k,l-1])
 
\end{array}\right.
 
\end{array}\right.
 
</tex>
 
</tex>
Строка 39: Строка 40:
  
 
===Реализация===
 
===Реализация===
Будем использовать динамику с запоминанием ответа. Оформим решения в виде рекурсивной функции <tex>lcps</tex>, которая возвращает ответ для подзадачи, на которую она была вызвана.<br> В массиве <tex>ans</tex> хранятся ответы для подзадач. До запуска функции <tex>lcps</tex> заполним массив <tex>ans</tex> <tex>-1</tex> и будем использовать такую логику: мы имеем подзадачу <tex>lcps(i,j,k,l)</tex>, если <tex>ans[i][j][k][l] = -1</tex>, то значение для данной подзадачи мы еще не вычисляли и именно этим мы и займемся, иначе значение уже посчитано и мы можем просто вернуть <tex>ans[i][j][k][l]</tex>. Так как каждое значение считается не более одного раза, мы получим асимптотику <tex>O(n^4)</tex>.
+
Будем использовать динамику с запоминанием ответа (с мемоизацией). Оформим решения в виде рекурсивной функции <tex>lcps</tex>, которая возвращает ответ для подзадачи, на которую она была вызвана.<br> В массиве <tex>\mathtt{ans}</tex> хранятся ответы для подзадач. До запуска функции <tex>lcps</tex> заполним массив <tex>ans</tex> значением <tex>-1</tex>. Так как каждое значение считается не более одного раза и эта операция происходит за <tex>O(1)</tex>, мы получим асимптотику <tex>O(n^4)</tex>.
  
 
===Псевдокод===
 
===Псевдокод===
  '''int''' lcps (i: '''int''', j: '''int''', k: '''int''', l: '''int''')
+
  '''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>
+
   '''if''' (ans[i][j][k][l] <tex> \neq </tex> -1) <span style="color:Green">// если значение уже посчитано, то надо его вернуть</span>
 
     '''return''' ans[i][j][k][l]
 
     '''return''' ans[i][j][k][l]
 
   '''if''' (i > j '''or''' k > l)
 
   '''if''' (i > j '''or''' k > l)
Строка 52: Строка 53:
 
       ans[i][j][k][l] = 1
 
       ans[i][j][k][l] = 1
 
       '''return''' 1       
 
       '''return''' 1       
     '''else'''
+
     '''else'''  
       tmp = (2 + lcps(i + 1, j - 1, k + 1, l - 1))
+
       ans[i][j][k][l] = (2 + lcps(i + 1, j - 1, k + 1, l - 1))  
       '''return''' tmp
+
       '''return''' (2 + lcps(i + 1, j - 1, k + 1, l - 1))   
      ans[i][j][k][l] = tmp
+
  ans[i][j][k][l] = 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))
  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))
+
   '''return''' 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''' tmp
 
 
==См. также==
 
==См. также==
* [[Динамическое программирование]]
+
* [[Задача о наибольшей возрастающей подпоследовательности]]
* [[Задача о наибольшей общей подпоследовательности]]
+
* [[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]
* [[Задача о наибольшей подпоследовательности-палиндроме]]
 
 
==Источники информации==
 
==Источники информации==
 
* [https://www.academia.edu/2015585/Computing_a_Longest_Common_Palindromic_Subsequence Academia.edu {{---}} Computing a Longest Common Palindromic Subsequence]
 
* [https://www.academia.edu/2015585/Computing_a_Longest_Common_Palindromic_Subsequence Academia.edu {{---}} Computing a Longest Common Palindromic Subsequence]
 +
 +
[[Категория:Дискретная математика и алгоритмы]]
 +
[[Категория:Динамическое программирование]]

Версия 22:34, 13 декабря 2014

Задача о наибольшей общей подпоследовательности (англ. longest common subsequence (LCS)) — классическая и хорошо изученная проблема.

Задача о наибольшей подпоследовательности-палиндроме (англ. longest palindromic subsequence (LPS)) — также хорошо изучена.

В этой статье мы рассмотрим задачу, которая объединяет две вышеперечисленные задачи в одну.

Наибольшая общая подпалиндромная подпоследовательность (англ. The longest common palindromic subsequence (LCPS)) — задача, являющаяся интересным вариантом классической задачи о поиске наибольшей общей подпоследовательности, которая также накладывает условия, что эта подпоследовательность должна быть палиндромом.

Задача:
Для последовательности [math]X[/math], мы обозначим её подпоследовательность [math]x_{i}...x_{j}\ (1 \leqslant i \leqslant j \leqslant n)\ [/math] как [math]X_{i,j}[/math]. Для двух последовательностей [math]X[/math] и [math]Y[/math], если общая подпоследовательность [math]Z[/math] последовательностей [math]X[/math] и [math]Y[/math] является палиндромом, то [math]Z[/math] называется общей подпалиндромной подпоследовательностью (англ. common palindromic subsequence). Общая подпалиндромная последовательность, имеющая максимальную длину, называется наибольшей общей подпалиндромной подпоследовательностью (англ. The longest common palindromic subsequence (LCPS)) и мы обозначим её как [math]LCPS(X,Y)[/math].

Наивное решение

Можно придумать такое решение данной задачи: найти наибольшую общую подпоследовательность, в ней найти наибольшую подпалиндромную подпоследовательность. Но, к сожалению, это решение неверно.

Контрпример

Возьмем две последовательности [math]X=[1,\ 2,\ 3,\ 1][/math] и [math]Y=[1,\ 1,\ 2,\ 3][/math].

Наибольшей общая подпоследовательность данных последовательностей равна [math]LCS(X,Y) = [1,\ 2,\ 3][/math] и в ней наибольшая подпалиндромная последовательность имеет длину [math]1[/math].

Но очевидно, что на самом деле последовательность [math]Z=[1,\ 1][/math] является наибольшим общей палиндромной подпоследовательностью [math]X[/math] и [math]Y[/math] и имеет длину [math]2[/math].

Решение с помощью динамического программирования

Заметим, что в качестве подзадач для [math]LCPS[/math], в которых мы можем посчитать ответ, логично взять подпоследовательность от [math]X[/math] и от [math]Y[/math]. Основываясь на этом наблюдении мы сформулируем следующую теорему, которая доказывает оптимальную подструктуру свойств задачи [math]LCPS[/math], что даст возможность воспользоваться идеей динамического программирования.

Теорема:
Пусть [math]X[/math] и [math]Y[/math] - две последовательности длин [math]n[/math] и [math]m[/math] соответственно, а [math]X_{i,j}[/math] и [math]Y_{i,j}[/math] — две подпоследовательности последовательностей [math]X[/math] и [math]Y[/math] соответственно. Пусть [math]Z = z_{1}z_{2}...z_{u}[/math] - наибольшая общая подпалиндромная последовательность двух подпоследовательностей [math]X_{i,j}[/math] и [math]Y_{k,l}[/math]. Тогда выполняются следующие утверждения,
  1. Если [math]x_i=x_j=y_k=y_l=a[/math] (для произвольного [math]a[/math]), тогда [math]z_1=z_u=a[/math] и [math]z_2...z_{u-1}[/math] — наибольшая общая палиндромная подпоследовательность от подпоследовательностей [math]X_{i+1,j-1}[/math] и [math]Y_{k+1,l-1}[/math].
  2. Если [math]x_i=x_j=y_k=y_l[/math] не выполняется, то [math]Z[/math] — наибольшая общая палиндромная подпоследовательность от подпоследовательностей ([math]X_{i+1,j}[/math] и [math]Y_{k,l}[/math]) или ([math]X_{i,j-1}[/math] и [math]Y_{k,l}[/math]) или ([math]X_{i,j}[/math] и [math]Y_{k+1,l}[/math]) или ([math]X_{i,j}[/math] и [math]Y_{k,l-1}[/math]).

На основании теоремы мы напишем следующую рекурсивную формулу для длины наибольшей общей подпалиндромной подпоследовательности:

[math] lcps[i,j,k,l] = \left\{\begin{array}{llcl} 0&&;&i \gt j\ \lor\ k \gt l\\ 1&&;&(i = j)\ \land\ (k = l)\ \land\ (x_i=x_j=y_k=y_l)\\ 2+lcps[i+1,j-1,k+1,l-1]&&;&(i \lt j)\ \land\ (k \lt l)\ \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)\ \land\ (k \leqslant l)\ \land\ \lnot(x_i=x_j=y_k=y_l)\\ \:\:\:\:\:\:\:\:\:\:\:lcps[i,j,k+1,l],lcps[i,j,k,l-1]) \end{array}\right. [/math]

Где [math]lcps[i,j,k,l][/math] — длина наибольшей общей палиндромной подпоследовательности от [math]X_{i,j}[/math] и [math]Y_{k,l}[/math]. Длина наибольшей общей палиндромной подпоследовательности от последовательностей [math]X[/math] и [math]Y[/math] будет расположена в [math]lcps[1,n,1,m][/math]. Мы можем вычислить эту длину за время [math]O(n^4)[/math] используя динамическое программирование.

Реализация

Будем использовать динамику с запоминанием ответа (с мемоизацией). Оформим решения в виде рекурсивной функции [math]lcps[/math], которая возвращает ответ для подзадачи, на которую она была вызвана.
В массиве [math]\mathtt{ans}[/math] хранятся ответы для подзадач. До запуска функции [math]lcps[/math] заполним массив [math]ans[/math] значением [math]-1[/math]. Так как каждое значение считается не более одного раза и эта операция происходит за [math]O(1)[/math], мы получим асимптотику [math]O(n^4)[/math].

Псевдокод

int lcps(i: int, j: int, k: int, l: int)
  if (ans[i][j][k][l] [math] \neq [/math] -1) // если значение уже посчитано, то надо его вернуть
    return ans[i][j][k][l]
  if (i > j or k > l)
    ans[i][j][k][l] = 0
    return 0
  if (X[i] == X[j] == Y[k] == Y[l])
    if (i == j and k == l)
      ans[i][j][k][l] = 1
      return 1       
    else   
      ans[i][j][k][l] = (2 + lcps(i + 1, j - 1, k + 1, l - 1))    
      return (2 + lcps(i + 1, j - 1, k + 1, l - 1))    
  ans[i][j][k][l] = 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))
  return 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))

См. также

Источники информации