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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{Определение |definition= Последовательность <tex> Z = \left \langle z_1, z_2, \dots, z_k \right \rangle </tex> является '''...»)
 
м (rollbackEdits.php mass rollback)
 
(не показаны 63 промежуточные версии 2 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Последовательность <tex> Z = \left \langle z_1, z_2, \dots, z_k \right \rangle </tex> является '''подпоследовательностью''' (англ. ''subsequence'') последовательности <tex> X = \left \langle x_1, x_2, \dots, x_m \right \rangle </tex>, если существует строго возрастающая последовательность <tex> \left \langle i_1, i_2, \dots, i_k \right \rangle </tex> индексов <tex> X </tex> таких, что для всех <tex> j = 1, 2, \dots, k </tex> выполняется соотношение <tex> x_{i_j} = z_j </tex>.
+
Последовательность <tex> Z = \left \langle z_1, z_2, \dots, z_k \right \rangle </tex> является '''суперпоследовательностью''' (англ. ''supersequence'') последовательности <tex> X = \left \langle x_1, x_2, \dots, x_n \right \rangle </tex>, если <tex>X</tex> — подпоследовательность <tex>Z</tex> , то есть существует строго возрастающая последовательность <tex> \left \langle i_1, i_2, \dots, i_n \right \rangle </tex> индексов <tex> Z </tex> таких, что для всех <tex> j = 1, 2, \dots, n </tex> выполняется соотношение <tex> z_{i_j} = x_j </tex>, при этом <tex> k \geqslant n </tex>.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Последовательность <tex> Z </tex> является '''общей суперпоследовательностью''' (англ. ''common supersequence'') последовательностей <tex> X </tex> и <tex> Y </tex>, если <tex> X </tex> и <tex> Y </tex> являются подпоследовательностями <tex> Z </tex>.
+
Последовательность <tex> Z </tex> является '''общей суперпоследовательностью''' (англ. ''common supersequence'') последовательностей <tex> X </tex> и <tex> Y </tex>, если <tex> Z </tex> является суперпоследовательностью как для <tex> X </tex>, так для и <tex> Y </tex>.
 
}}
 
}}
  
 
{{Задача
 
{{Задача
 
|definition=
 
|definition=
Пусть имеются последовательности <tex> X = \left \langle x_1, x_2, \dots, x_m \right \rangle </tex> и <tex> Y = \left \langle y_1, y_2, \dots, y_n \right \rangle </tex>. Необходимо найти <tex>SCS(X,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>  
 
}}
 
}}
  
 
== Наивное решение ==
 
== Наивное решение ==
Заметим, что если приписать к одной из данной последовательность другую, то полученная последовательность будет их суперпоследовательностью с длиной <tex> n + m </tex>. Запомним все элементы обеих последовательностей и из них построим все возможные последовательности. Тогда искомая <tex>SCS</tex> гарантированно найдётся, однако время работы алгоритма будет экспоненциально зависеть от длины исходных последовательностей.
+
Пусть даны две последовательности длин <tex>n</tex> и <tex>m</tex> соответственно. Заметим, что если приписать к одной из данных последовательностей другую, то полученная последовательность будет их суперпоследовательностью с длиной <tex> n + m </tex>. Запомним все элементы обеих последовательностей и из них построим все возможные последовательности. Тогда искомая <tex>SCS</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>
 +
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}
 +
</tex>
 +
 
 +
Cложность алгоритма составит <tex> O(mn) </tex>, где <tex> m </tex> и <tex> n </tex> — длины последовательностей.
 +
 
 +
===Восстановление ответа===
 +
Для восстановления ответа заведем массив <tex> prev[0 \dots n][0\dots m] </tex>, где <tex>prev[i][j]</tex> будет равняться:
 +
 
 +
<tex>
 +
prev[i][j] =
 +
\begin{cases}
 +
1, & x[i] = y[j] \\
 +
2, & x[i] \neq y[j], scs[i - 1][j] > scs[i][j - 1] \\
 +
3, & x[i] \neq y[j], scs[i - 1][j] \leqslant scs[i][j - 1] \\
 +
\end{cases}
 +
</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>''
 +
'''fun''' SCS(x: '''int[]''', y: '''int[]'''): 
 +
    n = x.size
 +
    m = y.size
 +
    ''
 +
    ''<font color="green">// инициализация массивов динамики </font>''
 +
    scs = '''int'''[][]
 +
    pref = '''int'''[][]
 +
    ''
 +
    ''<font color="green">// случай равенства одного из индексов 0 </font>''
 +
    '''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
 +
        ''<font color="green">// случай равенства элементов </font>''
 +
        '''if''' x[i] == y[j]
 +
          scs[i][j] = 1 + scs[i - 1][j - 1]
 +
          prev[i][j] = 1
 +
        '''else'''
 +
        ''<font color="green">// случай неравенства элементов </font>''
 +
          '''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
 +
 
 +
''<font color="green">// вывод SCS </font>''
 +
'''fun''' printSCS(n: '''int''', m: '''int'''):
 +
    i = n
 +
    j = m
 +
    ans = [] ''<font color="green">// массив ответа </font>''
 +
    ''
 +
    '''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
 +
    ''
 +
    ''<font color="green">// добавляем оставшиеся символы первой последовательности </font>''
 +
    '''while''' i > 0
 +
      ans.append(x[i])
 +
      i -= 1
 +
    ''<font color="green">// добавляем оставшиеся символы второй последовательности </font>''
 +
    '''while''' j > 0
 +
      ans.append(y[j])
 +
      j -= 1
 +
    ''
 +
    '''reverse'''(ans) ''<font color="green">// разворачиваем последовательность, так как шли с конца </font>''
 +
    '''return''' ans
 +
 
 +
==Связь с наибольшей общей подпоследовательностью==
 +
{{
 +
Теорема|statement=
 +
<tex>|LCS(X, Y)| + |SCS(X, Y)| = n + m</tex>, где <tex>|LCS(X, Y)|</tex> — длина [[Задача о наибольшей общей подпоследовательности| наибольшей общей подпоследовательности]], <tex>|SCS(X, Y)|</tex> — длина наименьшей общей суперпоследовательности, <tex>n</tex> и <tex>m</tex> — длины последовательностей <tex> X </tex> и <tex> Y </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>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>|LCS(X, Y)| + |SCS(X, Y)| = n + m</tex>
 +
 
 +
}}
 +
 
 +
== См. также ==
 +
*[[Задача о наибольшей общей подпоследовательности]]
 +
 
 +
== Источники информации ==
 +
*[https://en.wikipedia.org/wiki/Shortest_common_supersequence_problem Википедия — Shortest common supersequence problem]
 +
 
 +
[[Категория:Дискретная математика и алгоритмы]]
 +
[[Категория:Динамическое программирование]]

Текущая версия на 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]

См. также

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