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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Псевдокод)
(Псевдокод)
Строка 50: Строка 50:
 
<tex> x, y</tex> — данные последовательности; <tex>scs[i][j] </tex> — <tex>SCS</tex> для префикса длины <tex>i</tex> последовательности <tex>x</tex> и префикса длины <tex>j</tex> последовательности <tex>y</tex>; <tex>prev[i][j]</tex> — массив для восстановления ответа.
 
<tex> x, y</tex> — данные последовательности; <tex>scs[i][j] </tex> — <tex>SCS</tex> для префикса длины <tex>i</tex> последовательности <tex>x</tex> и префикса длины <tex>j</tex> последовательности <tex>y</tex>; <tex>prev[i][j]</tex> — массив для восстановления ответа.
  
  ''<font color="green">// Подсчет динамики </font>''
+
''<font color="green">// Подсчет динамики </font>''
 
  '''fun''' SCS(x: '''int''', y: '''int'''):   
 
  '''fun''' SCS(x: '''int''', y: '''int'''):   
 
     n = x.size
 
     n = x.size
Строка 59: Строка 59:
 
         scs[i][j] = 0
 
         scs[i][j] = 0
 
         prev[i][j] = 0
 
         prev[i][j] = 0
   
+
    ''<font color="green">//случай равенства одного из индексов 0 </font>''
 
     '''for''' i = 0 '''to''' n
 
     '''for''' i = 0 '''to''' n
 
       scs[i][0] = i
 
       scs[i][0] = i
Строка 77: Строка 77:
 
             prev[i][j] = 3
 
             prev[i][j] = 3
  
  ''<font color="green">//вывод SCS </font>''
+
''<font color="green">//вывод SCS </font>''
 
  '''fun''' printSCS(n: '''int''', m: '''int'''):
 
  '''fun''' printSCS(n: '''int''', m: '''int'''):
 
     i = n
 
     i = n
Строка 94: Строка 94:
 
           ans.append(x[i])
 
           ans.append(x[i])
 
           i -= 1
 
           i -= 1
    ''<font color="green">// добавляем оставшиеся символы первой последовательности </font>''
+
    ''<font color="green">// добавляем оставшиеся символы первой последовательности </font>''
 
     '''while''' i > 0  
 
     '''while''' i > 0  
 
       ans.append(x[i])
 
       ans.append(x[i])
 
       i -= 1
 
       i -= 1
    ''<font color="green">// добавляем оставшиеся символы второй последовательности </font>''
+
    ''<font color="green">// добавляем оставшиеся символы второй последовательности </font>''
 
     '''while''' j > 0
 
     '''while''' j > 0
 
       ans.append(y[j])  
 
       ans.append(y[j])  

Версия 17:56, 27 декабря 2017

Определение:
Последовательность [math] Z = \left \langle z_1, z_2, \dots, z_k \right \rangle [/math] является суперпоследовательностью (англ. supersequence) последовательности [math] X = \left \langle x_1, x_2, \dots, x_n \right \rangle [/math], если [math]X[/math] — подпоследовательность [math]Z[/math] , то есть существует строго возрастающая последовательность [math] \left \langle i_1, i_2, \dots, i_n \right \rangle [/math] индексов [math] Z [/math] таких, что для всех [math] j = 1, 2, \dots, n [/math] выполняется соотношение [math] z_{i_j} = x_j [/math], при этом [math] k \geqslant n [/math].


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


Задача:
Пусть имеются последовательности [math] X = \left \langle x_1, x_2, \dots, x_n \right \rangle [/math] и [math] Y = \left \langle y_1, y_2, \dots, y_m \right \rangle [/math]. Необходимо найти [math]SCS(X,Y)[/math], где [math]SCS(X, Y)[/math] — длина наименьшей общей суперпоследовательности последовательностей [math] X [/math] и [math] Y [/math]


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

Пусть даны две последовательности длин [math]n[/math] и [math]m[/math] соответственно. Заметим, что если приписать к одной из данных последовательностей другую, то полученная последовательность будет их суперпоследовательностью с длиной [math] n + m [/math]. Запомним все элементы обеих последовательностей и из них построим все возможные последовательности. Тогда искомая [math]SCS[/math] гарантированно найдётся, однако время работы алгоритма будет экспоненциально зависеть от длин исходных последовательностей.

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

Решение

Обозначим за [math] scs[i][j] [/math] наименьшую общую суперпоследовательность для префиксов данных последовательностей [math] x[1 \dots n] [/math] и [math] y[1 \dots m] [/math], заканчивающихся в элементах с номерами [math] i [/math] и [math] j [/math] соответственно. Наименьшая общая суперпоследовательность [math] x[1 \dots i] [/math] и [math] y[1 \dots j] [/math] должна содержать каждый символ обеих последовательностей, поэтому если [math] j = 0 [/math], то [math] SCS [/math] это просто последовательность [math] x[1 \dots i] [/math]. Аналогичен случай, когда [math] i = 0 [/math]. Если [math] i \gt 0 [/math] и [math] j \gt 0 [/math], то возможны два случая. Если [math] x[i] \neq y[j] [/math], то [math]SCS[/math] должна включать оба этих элемента. Значит нужно выбрать минимальный из ответов для префиксов, включающих один элемент и не включающих второй. Если же [math] x[i] = y[j] [/math], то [math]SCS[/math] для последовательностей [math] x[1 \dots i] [/math] и [math] y[1 \dots j] [/math] должна заканчиваться этим элементом, так как он общий для них. Получается следующее рекуррентное соотношение:

[math] scs[i][j] = \begin{cases} i, & j = 0 \\ j, & i = 0 \\ 1 + scs[i - 1][j - 1], & x[i] = y[j] \\ 1 + min(scs[i][j - 1],\ scs[i - 1][j]), & x[i] \neq y[j] \end{cases} [/math]

Cложность алгоритма составит [math] O(mn) [/math], где [math] m [/math] и [math] n [/math] — длины последовательностей.

Восстановление ответа

Для восстановления ответа заведем массив [math] prev[0 \dots n][0\dots m] [/math], где [math]prev[i][j][/math] будет равняться:

[math] prev[i][j] = \begin{cases} 1, & x[i] = y[j] \\ 2, & x[i] \neq y[j], scs[i - 1][j] \gt scs[i][j - 1] \\ 3, & x[i] \neq y[j], scs[i - 1][j] \leqslant scs[i][j - 1] \\ \end{cases} [/math]

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

Псевдокод

[math] x, y[/math] — данные последовательности; [math]scs[i][j] [/math][math]SCS[/math] для префикса длины [math]i[/math] последовательности [math]x[/math] и префикса длины [math]j[/math] последовательности [math]y[/math]; [math]prev[i][j][/math] — массив для восстановления ответа.

// Подсчет динамики 
fun SCS(x: int, y: int):  
   n = x.size
   m = y.size
    //инициализация массивов динамики 
   for i = 0 to n
     for j = 0 to m
        scs[i][j] = 0
        prev[i][j] = 0
   //случай равенства одного из индексов 0 
   for i = 0 to n
     scs[i][0] = i
   for j = 0 to m
     scs[0][j] = j
   for i = 1 to n
     for j = 1 to m
       if x[i] == y[j]
         scs[i][j] = 1 + scs[i - 1][j - 1]
         prev[i][j] = 1
       else
         if scs[i - 1][j] > scs[i][j - 1]
           scs[i][j] = 1 + scs[i][j - 1]
           prev[i][j] = 2
         else
           scs[i][j] = 1 + scs[i - 1][j]
           prev[i][j] = 3
//вывод SCS 
fun printSCS(n: int, m: int):
   i = n
   j = m
   ans = [] // массив ответа 
   while i > 0 and j > 0
     if prev[i][j] == 1
       ans.append(x[i])
       i -= 1
       j -= 1
     else
       if prev[i][j] == 2
         ans.append(y[j])
         j -= 1
       else
         ans.append(x[i])
         i -= 1
   // добавляем оставшиеся символы первой последовательности 
   while i > 0 
     ans.append(x[i])
     i -= 1
   // добавляем оставшиеся символы второй последовательности 
   while j > 0
     ans.append(y[j]) 
     j -= 1
   reverse(ans) // разворачиваем последовательность, так как шли с конца 
   return ans

Связь с наибольшей общей подпоследовательностью

Теорема:
[math]|LCS(X, Y)| + |SCS(X, Y)| = n + m[/math], где [math]|LCS(X, Y)|[/math] — длина наибольшей общей подпоследовательности, [math]|SCS(X, Y)|[/math] — длина наименьшей общей суперпоследовательности, [math]n[/math] и [math]m[/math] — длины последовательностей [math] X [/math] и [math] Y [/math] соответственно.
Доказательство:
[math]\triangleright[/math]

Пусть [math] X = \left \langle x_1, x_2, \dots, x_n \right \rangle [/math], [math] Y = \left \langle y_1, y_2, \dots, x_m \right \rangle [/math]. Обозначим за [math] S [/math] их [math]SCS[/math] и будем ее строить. Так как [math]S[/math] являетcя суперпоследовательностью [math] X [/math], то можно представить [math]S[/math] так: [math] S = \dots x_1 \dots x_2 \dots x_i \dots x_n \dots [/math] Мы должны на место некоторых пропусков поставить элементы [math]Y[/math], так чтобы суммарная длина [math] S [/math] была минимальна, и [math] S [/math] являлась суперпоследовательностью [math]Y[/math]. Рассмотрим любую общую подпоследовательность [math]X[/math] и [math]Y[/math].Заметим, что она уже находятся в [math]S[/math], а значит все её элементы не нужно добавлять. Поэтому мы добавим не меньше, чем [math] m - |LCS(X, Y)| элементов [/math]. Длину [math] SCS(X, Y) [/math] нужно минимизировать, значит имеет место равенство: [math]|SCS(X,Y)| = n + (m - |LCS(X, Y)|)[/math].

Поэтому: [math]|LCS(X, Y)| + |SCS(X, Y)| = n + m[/math]
[math]\triangleleft[/math]

См. также

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