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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Решение)
Строка 1: Строка 1:
Задача нахождения '''наибольшей общей подпоследовательности''' (''англ.'' '''''longest common subsequence, LCS''''') — это задача поиска последовательности, которая является подпоследовательностью нескольких последовательностей (обычно двух).
+
Задача нахождения '''наибольшей общей подпоследовательности''' (''longest common subsequence, LCS'') — это задача поиска последовательности, которая является самой длинной подпоследовательностью нескольких последовательностей (обычно двух).
  
 +
== Определения ==
 +
{{Определение
 +
|definition=
 +
Последовательность <tex> Z = \left \langle z_1, z_2, ..., z_k \right \rangle </tex> является '''подпоследовательностью''' (subsequence) последовательности <tex> 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 </tex> таких, что для всех <tex> j = 1, 2, ..., 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>.
 +
}}
 
== Постановка задачи ==
 
== Постановка задачи ==
 
+
Даны две последовательности: <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> X </tex> и <tex> Y </tex> максимальной длины. Заметим, что таких подпоследовательностей может быть несколько.
Подпоследовательность можно получить из некоторой конечной последовательности, если удалить из последней некоторое множество её элементов (возможно пустое). Например, BCDB является подпоследовательностью последовательности ABCDBAB. Будем говорить, что последовательность Z является общей подпоследовательностью последовательностей X и Y, если Z является подпоследовательностью как X, так и Y. Требуется для двух последовательностей X и Y найти общую подпоследовательность наибольшей длины. Заметим, что НОП может быть несколько.
 
  
 
== Наивная идея решения ==
 
== Наивная идея решения ==
 
 
Переберем все различные подпоследовательности обеих строк и сравним их. Мы гарантированно найдем искомую НОП, однако время работы алгоритма будет экспоненциально зависеть от длины исходных последовательностей.
 
Переберем все различные подпоследовательности обеих строк и сравним их. Мы гарантированно найдем искомую НОП, однако время работы алгоритма будет экспоненциально зависеть от длины исходных последовательностей.
  
 
== Динамическое программирование ==
 
== Динамическое программирование ==
 
=== Решение ===
 
=== Решение ===
Обозначим как <tex>a_{i, j}</tex> НОП префиксов данных последовательностей, заканчивающихся в элементах с номерами <tex>i</tex> и <tex>j</tex> соответственно.Получаем следующее рекуррентное соотношение:
+
Обозначим как <tex> a[i][j] </tex> НОП префиксов данных последовательностей, заканчивающихся в элементах с номерами <tex> i </tex> и <tex> j </tex> соответственно. Получаем следующее рекуррентное соотношение:
*<tex>a_{i, j} = a_{i - 1, j - 1} + 1</tex>, если <tex>s[i] = s[j]</tex> (соответствующие элементы последовательностей равны)
+
<tex>
*<tex>a_{i, j} = max(a_{i, j - 1}, a_{i - 1, j})</tex>, если <tex>s1[i] \neq s2[j]</tex> (соответствующие элементы последовательностей не равны).
+
a[i][j] =
Очевидно, что сложность алгоритма составит <tex>O(n^2)</tex>.
+
\begin{cases}
 +
a[i - 1][j - 1] + 1, & \text{если }x[i] = y[j]\text{ (соответствующие элементы последовательностей равны); } \\
 +
max(a[i][j - 1], a[i - 1][j]), & \text{если }x[i] \neq y[j]\text{ (соответствующие элементы последовательностей не равны).}
 +
\end{cases}
 +
</tex>
 +
Очевидно, что сложность алгоритма составит <tex> O(n^2) </tex>.
  
 
=== Доказательство оптимальности ===
 
=== Доказательство оптимальности ===
Предположим, что некоторое значение <tex>a_{i, j}</tex> посчитано неверно. Однако, в случае различия соответствующих символов, они не могут одновременно участвовать в НОП, а значит ответ действительно равен формуле для случая с различными символами. В случае же равенства, ответ не может быть больше, чем <tex>a_{i - 1, j - 1} + 1</tex>, так как тогда неверно посчитано значение <tex>a_{i - 1, j - 1} + 1</tex>.
+
Предположим, что некоторое значение <tex> a[i][j] </tex> посчитано неверно. Однако, в случае различия соответствующих символов, они не могут одновременно участвовать в НОП, а значит ответ действительно равен формуле для случая с различными символами. В случае же равенства, ответ не может быть больше, чем <tex> a[i - 1][j - 1] + 1 </tex>, так как тогда неверно посчитано значение <tex> a[i - 1][j - 1] + 1 </tex>.
  
 
=== Построение подпоследовательности ===
 
=== Построение подпоследовательности ===

Версия 00:06, 20 ноября 2011

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

Определения

Определение:
Последовательность [math] Z = \left \langle z_1, z_2, ..., z_k \right \rangle [/math] является подпоследовательностью (subsequence) последовательности [math] X = \left \langle x_1, x_2, ..., x_m \right \rangle [/math], если существует строго возрастающая последовательность [math] \left \langle i_1, i_2, ..., i_k \right \rangle [/math] индексов [math] X [/math] таких, что для всех [math] j = 1, 2, ..., k [/math] выполняется соотношение [math] x_{i_j} = z_j [/math].

Другими словами, подпоследовательность данной последовательности — это последовательность, из которой удалили ноль или больше элементов. Например, [math] Z = \left \langle B, C, D, B \right \rangle [/math] является подпоследовательностью последовательности [math] X = \left \langle A, B, C, B, D, A, B \right \rangle [/math], а соответствующая последовательность индексов имеет вид [math] \left \langle 2, 3, 5, 7 \right \rangle [/math].

Определение:
Последовательность [math] Z [/math] является общей подпоследовательностью (common subsequence) последовательностей [math] X [/math] и [math] Y [/math], если [math] Z [/math] является подпоследовательностью как [math] X [/math], так и [math] Y [/math].

Постановка задачи

Даны две последовательности: [math] X = \left \langle x_1, x_2, ..., x_m \right \rangle [/math] и [math] Y = \left \langle y_1, y_2, ..., y_n \right \rangle [/math]. Требуется найти общую подпоследовательность [math] X [/math] и [math] Y [/math] максимальной длины. Заметим, что таких подпоследовательностей может быть несколько.

Наивная идея решения

Переберем все различные подпоследовательности обеих строк и сравним их. Мы гарантированно найдем искомую НОП, однако время работы алгоритма будет экспоненциально зависеть от длины исходных последовательностей.

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

Решение

Обозначим как [math] a[i][j] [/math] НОП префиксов данных последовательностей, заканчивающихся в элементах с номерами [math] i [/math] и [math] j [/math] соответственно. Получаем следующее рекуррентное соотношение: [math] a[i][j] = \begin{cases} a[i - 1][j - 1] + 1, & \text{если }x[i] = y[j]\text{ (соответствующие элементы последовательностей равны); } \\ max(a[i][j - 1], a[i - 1][j]), & \text{если }x[i] \neq y[j]\text{ (соответствующие элементы последовательностей не равны).} \end{cases} [/math] Очевидно, что сложность алгоритма составит [math] O(n^2) [/math].

Доказательство оптимальности

Предположим, что некоторое значение [math] a[i][j] [/math] посчитано неверно. Однако, в случае различия соответствующих символов, они не могут одновременно участвовать в НОП, а значит ответ действительно равен формуле для случая с различными символами. В случае же равенства, ответ не может быть больше, чем [math] a[i - 1][j - 1] + 1 [/math], так как тогда неверно посчитано значение [math] a[i - 1][j - 1] + 1 [/math].

Построение подпоследовательности

Для каждой пары элементов будем хранить не только длину НОП соответствующих префиксов, но и номера последних элементов, участвующих в этой НОП.Таким образом, посчитав ответ, мы сможем восстановить всю наибольшую общую подпоследовательность.

Пример реализации на Java

 public int lcs(int[] s1, int[] s2) {
     int[][] a = new int[s1.length][s2.length];
     //Подсчет значений
     for (int i = 0; i < s1.length; i++)
         for (int j = 0; j < s2.length; j++) {
             if (s1[i] == s2[j])
                 if ((i == 0) || (j == 0)) {
                     a[i][j] = 1;
                 } else {
                     a[i][j] = a[i - 1][j - 1] + 1;
                 }
             else {
                 if ((i > 0) && (a[i - 1][j] > a[i][j])) {
                     a[i][j] = a[i - 1][j];
                 }
                 if ((j > 0) && (a[i][j - 1] > a[i][j])) {
                     a[i][j] = a[i][j - 1];
                 }
             }
         }
     return a[s1.length - 1][s2.length - 1];
   }