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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (rollbackEdits.php mass rollback)
 
(не показана 21 промежуточная версия 2 участников)
Строка 11: Строка 11:
 
{{Задача
 
{{Задача
 
|definition=
 
|definition=
Пусть имеются последовательности <tex> X = \left \langle x_1, x_2, \dots, x_n \right \rangle </tex> и <tex> Y = \left \langle y_1, y_2, \dots, y_m \right \rangle </tex>. Необходимо найти <tex>SCS(X,Y)</tex>, где <tex>SCS(X, Y)</tex> — наименьшая общая суперпоследовательность последовательностей <tex> X </tex> и <tex> Y </tex>  
+
Пусть имеются последовательности <tex> X = \left \langle x_1, x_2, \dots, x_n \right \rangle </tex> и <tex> Y = \left \langle y_1, y_2, \dots, y_m \right \rangle </tex>. Необходимо найти <tex>SCS(X,Y)</tex>, где <tex>SCS(X, Y)</tex> — длина наименьшей общей суперпоследовательности последовательностей <tex> X </tex> и <tex> Y </tex>  
 
}}
 
}}
  
Строка 19: Строка 19:
 
== Динамическое программирование ==
 
== Динамическое программирование ==
 
===Решение===
 
===Решение===
Обозначим за <tex> scs[i][j] </tex>  наименьшую общую суперпоследовательность для префиксов данных последовательностей <tex> x[1 \dots n] </tex> и <tex> y[1 \dots m] </tex>, заканчивающихся в элементах с номерами <tex> i </tex> и <tex> j </tex> соответственно. Наименьшая общая суперпоследовательность <tex> x[1 \dots i] </tex> и <tex> y[1 \dots j] </tex> должна содержать каждый символ обеих последовательностей, поэтому если <tex> j = 0 </tex>, то <tex> SCS </tex> это просто последовательность <tex> x[1 \dots i] </tex>. Аналогичен случай, когда <tex> i = 0 </tex>. Если <tex> i > 0 </tex> и <tex> j > 0 </tex>, то возможны два случая. Если <tex> x[i] \neq y[j] </tex>, то <tex>SCS</tex> должна включать оба этих элемента. Значит нужно выбрать минимальный из ответов для префиксов, включающих один элемент и не включающих второй. Если же <tex> x[i] = y[j] </tex>, то <tex>SCS</tex> для последовательностей <tex> x[1 \dots i] </tex> и <tex> y[1 \dots j] </tex> должна заканчиваться этим элементом, так как он общий для них. Получается следующее рекуррентное соотношение:
+
Обозначим за <tex> scs[i][j] </tex>  длину наименьшей общей суперпоследовательности для префиксов данных последовательностей <tex> x[1 \dots n] </tex> и <tex> y[1 \dots m] </tex>, заканчивающихся в элементах с номерами <tex> i </tex> и <tex> j </tex> соответственно. Будем считать ответ методом динамического программирования на префиксе. Наименьшая общая суперпоследовательность <tex> x[1 \dots i] </tex> и <tex> y[1 \dots j] </tex> должна содержать каждый символ обеих последовательностей, поэтому если <tex> j = 0 </tex>, то <tex> SCS </tex> это просто последовательность <tex> x[1 \dots i] </tex>. Аналогичен случай, когда <tex> i = 0 </tex>. Если <tex> i > 0 </tex> и <tex> j > 0 </tex>, то возможны два случая. Если <tex> x[i] \neq y[j] </tex>, то <tex>SCS</tex> должна включать оба этих элемента. Значит нужно выбрать минимальный из ответов для префиксов, включающих один элемент и не включающих второй, а именно минимум из ответов для меньших подзадач: <tex>scs[i - 1][j]</tex> и <tex>scs[i][j - 1]</tex>. Если же <tex> x[i] = y[j] </tex>, то <tex>SCS</tex> для последовательностей <tex> x[1 \dots i] </tex> и <tex> y[1 \dots j] </tex> должна заканчиваться этим элементом, так как он общий для них. Поэтому в этом случае <tex>scs[i][j] = scs[i - 1][j - 1] + 1 </tex>. Получается следующее рекуррентное соотношение:
  
 
<tex>
 
<tex>
Строка 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> — массив для восстановления ответа.
  
  '''fun''' SCS(x: '''int''', y: '''int'''):   ''<font color="green">// аналог void </font>''
+
''<font color="green">// Подсчет динамики </font>''
 +
  '''fun''' SCS(x: '''int[]''', y: '''int[]'''):
 
     n = x.size
 
     n = x.size
 
     m = y.size
 
     m = y.size
 +
    ''
 +
    ''<font color="green">// инициализация массивов динамики </font>''
 +
    scs = '''int'''[][]
 +
    pref = '''int'''[][]
 +
    ''
 +
    ''<font color="green">// случай равенства одного из индексов 0 </font>''
 
     '''for''' i = 0 '''to''' n
 
     '''for''' i = 0 '''to''' n
 
       scs[i][0] = i
 
       scs[i][0] = i
 
     '''for''' j = 0 '''to''' m
 
     '''for''' j = 0 '''to''' m
 
       scs[0][j] = j
 
       scs[0][j] = j
 +
    ''
 
     '''for''' i = 1 '''to''' n
 
     '''for''' i = 1 '''to''' n
 
       '''for''' j = 1 '''to''' m
 
       '''for''' j = 1 '''to''' m
 +
        ''<font color="green">// случай равенства элементов </font>''
 
         '''if''' x[i] == y[j]
 
         '''if''' x[i] == y[j]
 
           scs[i][j] = 1 + scs[i - 1][j - 1]
 
           scs[i][j] = 1 + scs[i - 1][j - 1]
 
           prev[i][j] = 1
 
           prev[i][j] = 1
 
         '''else'''
 
         '''else'''
 +
        ''<font color="green">// случай неравенства элементов </font>''
 
           '''if''' scs[i - 1][j] > scs[i][j - 1]
 
           '''if''' scs[i - 1][j] > scs[i][j - 1]
 
             scs[i][j] = 1 + scs[i][j - 1]
 
             scs[i][j] = 1 + scs[i][j - 1]
Строка 69: Строка 79:
 
             scs[i][j] = 1 + scs[i - 1][j]
 
             scs[i][j] = 1 + scs[i - 1][j]
 
             prev[i][j] = 3
 
             prev[i][j] = 3
 
+
 
  '''fun''' printSCS(n: '''int''', m: '''int'''): ''<font color="green">// вывод SCS</font>''
+
''<font color="green">// вывод SCS </font>''
 +
  '''fun''' printSCS(n: '''int''', m: '''int'''):
 
     i = n
 
     i = n
 
     j = m
 
     j = m
 
     ans = [] ''<font color="green">// массив ответа </font>''
 
     ans = [] ''<font color="green">// массив ответа </font>''
 +
    ''
 
     '''while''' i > 0 '''and''' j > 0
 
     '''while''' i > 0 '''and''' j > 0
 
       '''if''' prev[i][j] == 1
 
       '''if''' prev[i][j] == 1
Строка 86: Строка 98:
 
           ans.append(x[i])
 
           ans.append(x[i])
 
           i -= 1
 
           i -= 1
     '''while''' i > 0 ''<font color="green">// добавляем оставшиеся символы первой последовательности </font>''
+
     ''
 +
    ''<font color="green">// добавляем оставшиеся символы первой последовательности </font>''
 +
    '''while''' i > 0
 
       ans.append(x[i])
 
       ans.append(x[i])
 
       i -= 1
 
       i -= 1
 +
    ''<font color="green">// добавляем оставшиеся символы второй последовательности </font>''
 
     '''while''' j > 0
 
     '''while''' j > 0
       ans.append(y[j]) ''<font color="green">// добавляем оставшиеся символы второй последовательности </font>''
+
       ans.append(y[j])  
 
       j -= 1
 
       j -= 1
 +
    ''
 
     '''reverse'''(ans) ''<font color="green">// разворачиваем последовательность, так как шли с конца </font>''
 
     '''reverse'''(ans) ''<font color="green">// разворачиваем последовательность, так как шли с конца </font>''
 
     '''return''' ans
 
     '''return''' ans
Строка 102: Строка 118:
 
|proof= Пусть <tex>  X = \left \langle x_1, x_2, \dots, x_n \right \rangle </tex>, <tex>  Y = \left \langle y_1, y_2, \dots, x_m \right \rangle </tex>. Обозначим за <tex> S </tex> их <tex>SCS</tex> и будем ее строить. Так как <tex>S</tex> являетcя суперпоследовательностью <tex> X </tex>, то можно представить <tex>S</tex> так:
 
|proof= Пусть <tex>  X = \left \langle x_1, x_2, \dots, x_n \right \rangle </tex>, <tex>  Y = \left \langle y_1, y_2, \dots, x_m \right \rangle </tex>. Обозначим за <tex> S </tex> их <tex>SCS</tex> и будем ее строить. Так как <tex>S</tex> являетcя суперпоследовательностью <tex> X </tex>, то можно представить <tex>S</tex> так:
 
<tex> S = \dots x_1 \dots x_2 \dots x_i \dots x_n \dots </tex>
 
<tex> S = \dots x_1 \dots x_2 \dots x_i \dots x_n \dots </tex>
Мы должны на место некоторых пропусков поставить элементы <tex>Y</tex>, так чтобы суммарная длина <tex> S </tex> была минимальна, и <tex> S </tex> являлась суперпоследовательностью <tex>Y</tex>. Рассмотрим любую общую подпоследовательность <tex>X</tex> и <tex>Y</tex>.Заметим, что она уже находятся в <tex>S</tex>, а значит все её элементы не нужно добавлять. Поэтому мы добавим не меньше чем <tex> m - |LCS(X, Y)| элементов </tex>. Длину <tex> SCS(X, Y) </tex> нужно минимизировать, значит имеет место равенство:
+
Мы должны на место некоторых пропусков поставить элементы <tex>Y</tex>, так чтобы суммарная длина <tex> S </tex> была минимальна, и <tex> S </tex> являлась суперпоследовательностью <tex>Y</tex>. Рассмотрим любую общую подпоследовательность <tex>X</tex> и <tex>Y</tex>. Заметим, что она уже находятся в <tex>S</tex>, а значит все её элементы не нужно добавлять. Поэтому мы добавим не меньше, чем <tex> m - |LCS(X, Y)| элементов </tex>. Длину <tex> SCS(X, Y) </tex> нужно минимизировать, значит имеет место равенство:
 
<tex>|SCS(X,Y)| = n + (m - |LCS(X, Y)|)</tex>.  
 
<tex>|SCS(X,Y)| = n + (m - |LCS(X, Y)|)</tex>.  
 
Поэтому: <tex>|LCS(X, Y)| + |SCS(X, Y)| = n + m</tex>
 
Поэтому: <tex>|LCS(X, Y)| + |SCS(X, Y)| = n + m</tex>

Текущая версия на 19:36, 4 сентября 2022

Определение:
Последовательность [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]scs[i - 1][j][/math] и [math]scs[i][j - 1][/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] = scs[i - 1][j - 1] + 1 [/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
   
   // инициализация массивов динамики 
   scs = int[][]
   pref = int[][]
    
   // случай равенства одного из индексов 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]

См. также

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