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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «'''Задача о наибольшей общей подпоследовательности''' (англ. ''longest common subsequence (LCS)'') - класс...»)
 
Строка 4: Строка 4:
  
 
==Постановка задачи==
 
==Постановка задачи==
Мы предполагаем конечный алфавит <tex>\sum</tex>. Для последовательности <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 palindromicsubsequence''). Общая подпалиндромная последовательность, имеющая максимальную длину, называется '''наибольшей общей подпалиндромной подпоследовательностью''' (англ. ''The longest common palindromic sub-sequence (LCPS)'') и мы обозначим её как <tex>LCPS(X,Y)</tex>.
+
Для последовательности <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 palindromicsubsequence''). Общая подпалиндромная последовательность, имеющая максимальную длину, называется '''наибольшей общей подпалиндромной подпоследовательностью''' (англ. ''The longest common palindromic sub-sequence (LCPS)'') и мы обозначим её как <tex>LCPS(X,Y)</tex>.
  
 
==Динамическое программирование==
 
==Динамическое программирование==
Строка 11: Строка 11:
 
===Теорема 1===
 
===Теорема 1===
 
Пусть <tex>X</tex> и <tex>Y</tex> - две последовательности длины <tex>n</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</tex> и <tex>Y</tex> - две последовательности длины <tex>n</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>

Версия 01:02, 12 декабря 2014

Задача о наибольшей общей подпоследовательности (англ. longest common subsequence (LCS)) - классическая и хорошо изученная проблема. В данной статье мы рассмотрим её модификацию, где эта последовательность также должна быть палиндромом.

Определение:
Палиндромом (англ. palindrom) называется последовательность, которая одинаково читается как слева направо, так и справа налево.

Наибольшая общая подпалиндромная подпоследовательность (англ. The longest common palindromic sub-sequence (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 palindromicsubsequence). Общая подпалиндромная последовательность, имеющая максимальную длину, называется наибольшей общей подпалиндромной подпоследовательностью (англ. The longest common palindromic sub-sequence (LCPS)) и мы обозначим её как [math]LCPS(X,Y)[/math].

Динамическое программирование

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

Теорема 1

Пусть [math]X[/math] и [math]Y[/math] - две последовательности длины [math]n[/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]