10
правок
Изменения
поменял разделы местами в алгоритме Хиршберга
{{Определение
|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 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>.}}{{Задача|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>LCS(X,Y)</tex>
}}
== Постановка Наивное решение ==Переберем все различные подпоследовательности обеих строк и сравним их. Тогда искомая <tex>LCS</tex> гарантированно найдётся, однако время работы алгоритма будет экспоненциально зависеть от длины исходных последовательностей. == Динамическое программирование == Для решения данной задачи используем [[Динамическое программирование#Принцип оптимальности на префиксе | Принцип оптимальности на префиксе]]. === Доказательство оптимальности ==={{Теорема|statement=Даны две Пусть имеются последовательности: <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> X Z = \left \langle z_1, z_2, \dots, z_k \right \rangle </tex> и — их <tex> Y LCS</tex> максимальной длины. Заметим, что таких подпоследовательностей может быть несколько.
# Если <tex> x_m =y_n </tex>, то <tex> z_k = x_m = y_n </tex> и <tex> Z_{k - 1} </tex> — <tex>LCS(X_{m - 1},Y_{n - 1})</tex># Если <tex> x_m \neq y_n </tex>, то из <tex> z_k \neq x_m </tex> следует, что <tex> Z </tex> — <tex>LCS(X_{m - 1},Y)</tex># Если <tex> x_m \neq y_n </tex>, то из <tex> z_k \neq y_n </tex> следует, что <tex> Z </tex> — <tex>LCS(X,Y_{n - 1})</tex> |proof=# Если бы выполнялось <tex> z_k \neq x_m </tex>, то к <tex> Z </tex> можно было бы добавить элемент <tex> x_m = y_n </tex>, и тогда получилась бы общая подпоследовательность длины <tex> k + 1 </tex>, что противоречит предположению, что <tex> Z </tex> — <tex>LCS</tex>. Значит, выполняется <tex> z_k = Наивная идея решения x_m =y_n </tex>. Значит, <tex> Z_{k - 1} </tex> — общая подпоследовательность <tex> X_{m - 1} </tex> и <tex> Y_{n - 1} </tex>. Докажем от противного, что <tex> Z_{k - 1} </tex> — <tex>LCS</tex>: тогда есть общая подпоследовательность <tex> W </tex>, длина которой больше <tex> k - 1 </tex>. Добавив к <tex> W </tex> элемент <tex> x_m =y_n </tex>, получим <tex>LCS(X,Y)</tex>, длина которой больше <tex> k </tex> (т.е. больше длины <tex> Z </tex>), что приводит к противоречию.Переберем все различные подпоследовательности обеих строк # Если <tex> z_k \neq x_m </tex>, то <tex> Z </tex> — общая подпоследовательность <tex> X_{m - 1} </tex> и сравним <tex> Y </tex>. Пусть существует ихобщая подпоследовательность <tex> W </tex>, длина которой превышает <tex> k </tex>. Мы гарантированно найдем искомую НОПОна также является общей подпоследовательностью <tex> X </tex> и <tex> Y </tex>, однако время работы алгоритма будет экспоненциально зависеть от что противоречит предположению о том, что <tex> Z </tex> (длины исходных последовательностей<tex> k </tex>) — <tex>LCS(X,Y)</tex>.# Аналогично второму случаю.}}
=== Решение ===
Обозначим как <tex> alcs[i][j] </tex> <tex>LCS</tex> НОП префиксов данных последовательностей, заканчивающихся в элементах с номерами <tex> i </tex> и <tex> j </tex> соответственно. Получаем Получается следующее рекуррентное соотношение:
<tex>
\begin{cases}
0, & i = 0\text{ or }j = 0 \\
\end{cases}
</tex>
Очевидно, что сложность алгоритма составит <tex> O(mn) </tex>, где <tex> m </tex> и <tex> n </tex> — длины последовательностей.
=== Доказательство оптимальности Построение подпоследовательности ===Для каждой пары элементов помимо длины <tex>LCS</tex> соответствующих префиксов хранятся и номера последних элементов, участвующих в этой <tex>LCS</tex>.Таким образом, посчитав ответ, можно восстановить всю наибольшую общую подпоследовательность. === Псевдокод ===<tex> x </tex>, <tex> y </tex> — данные последовательности; <tex> lcs[i][j] </tex> — <tex>LCS</tex> для префикса длины <tex> i </tex> последовательности <tex> x </tex> и префикса длины <tex> j </tex> последовательности <tex> y </tex>; <tex> prev[i][j] </tex> — пара индексов элемента таблицы, соответствующего оптимальному решению вспомогательной задачи, выбранной при вычислении <tex> lcs[i][j] </tex>. ''<font color="green">// подсчёт таблиц</font>'' '''int''' LCS(x: '''int''', y: '''int'''): m = length(x) n = length(y) '''for''' i = 1 '''to''' m lcs[i][0] = 0 '''for''' j = 0 '''to''' n lcs[0][j] = 0 '''for''' i = 1 '''to''' m '''for''' j = 1 '''to''' n '''if''' x[i] == y[j] lcs[i][j] = lcs[i - 1][j - 1] + 1 prev[i][j] = pair(i - 1, j - 1) '''else''' '''if''' lcs[i - 1][j] >= lcs[i][j - 1] lcs[i][j] = lcs[i - 1][j] prev[i][j] = pair(i - 1, j) '''else''' lcs[i][j] =lcs[i][j - 1] prev[i][j] =pair(i, j - 1) ''<font color="green">// вывод LCS, вызывается как printLCS(m, n)</font>''База '''int''' printLCS(i: при '''int''', j: '''int'''): '''if''' i == 0 '''or''' j == 0 ''<font color="green">// пришли к началу LCS</font>'' '''return''' '''if''' prev[i][j] == pair(i - 1, j - 1) ''<font color="green">// если пришли в lcs[i][j] из lcs[i - 1][j - 1], то x[i] == y[j], надо вывести этот элемент</font>'' printLCS(i - 1, j - 1) print x[i] '''else''' '''if''' prev[i][j] == pair(i - 1, j) printLCS(i - 1, j) '''else''' printLCS(i, j - 1) == Оптимизация для вычисления только длины <tex>LCS</tex> ==Заметим, что для вычисления <tex> lcs[i][j] </tex> нужны только <tex> i </tex>-ая и <tex> (i -1) </tex>-ая строчки матрицы <tex> lcs </tex>. Тогда можно использовать лишь <tex> 2 \cdot min(m, n) </tex> элементов таблицы: '''int''' LCS2(x: '''int''', y: '''int'''): '''if''' length(x) < length(y) ''<font color="green">// в таблице будет length(y) столбцов, и если length(x) меньше, выгоднее поменять местами x и y</font>'' swap(x, y) m = length(x) n = length(y) '''for''' j = 0 '''to''' n lcs[0][j] = 0 lcs[1][j] = 0 '''for''' i = 1 '''to''' m lcs[1][0] = 0 '''for''' j = 1 '''to''' n lcs[0][j] = lcs[1][j] ''<font color="green">// элемент, который был в a[1][j], теперь в предыдущей строчке</font>'' '''if''' x[i] == y[j] lcs[1][j] = lcs[0][j - 1] + 1 '''else''' '''if''' lcs[0][j] >= lcs[1][j - 1] lcs[1][j] = lcs[0][j] '''else''' lcs[1][j] = lcs[1][j - 1] ''<font color="green">// ответ — lcs[1][n]</font>'' Также можно заметить, что от <tex> или (i - 1) </tex> -ой строчки нужны только элементы с <tex> (j - 1) </tex>-го столбца. В этом случае можно использовать лишь <tex> min(m, n) </tex> элементов таблицы: '''int''' LCS3(x: '''int''', y: '''int'''): '''if''' length(x) < length(y) ''<font color="green">// в таблице будет length(y) столбцов, и если length(x) меньше, выгоднее поменять местами x и y</font>'' swap(x, y) m = length(x) n = length(y) '''for''' j = 0 '''to''' n lcs[j] = 0 d = 0 ''<font color="green">// d — дополнительная переменная, в ней хранится lcs[i - 1][j - 1]'' ''// в lcs[j], lcs[j + 1], …, lcs[n] хранятся lcs[i - 1][j], lcs[i - 1][j + 1], …, lcs[i - 1][n]'' ''// в lcs[0], lcs[1], …, lcs[j - 1] хранятся lcs[i][0], lcs[i][1], …, lcs[i][j - 1]</font>'' '''for''' i = 1 '''to''' m '''for''' j = 1 '''to''' n tmp = lcs[j] '''if''' x[i] == y[j] lcs[j] = d + 1 '''else''' '''if''' lcs[j] >= lcs[j - 1] lcs[j] = lcs[j] ''<font color="green">// в lcs[j] и так хранится lcs[i - 1][j]</font>'' '''else''' lcs[j] = lcs[j - 1] d = tmp ''<font color="green">// ответ — lcs[n]</font>'' == Длина кратчайшей общей суперпоследовательности ==Для двух подпоследовательностей <tex>X_{m}</tex> и <tex>Y_{n}</tex> длина одной кратчайшей общей суперпоследовательности равна <tex>|SCS(X,Y)| = n + m - |LCS(X,Y)|</tex><ref>[http://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Relation_to_other_problems Wikipedia {{---}} Longest common subsequence problem]</ref> == Решение для случая k строк ==Найдем решение для 3 строк.{{Задача|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>Z = \left \langle z_1, z_2, \dots, z_k \right \rangle</tex>. Необходимо найти <tex>LCS(X,Y,Z)</tex>}}Наивное решение подсчёта <tex>LCS</tex> нескольких строк при помощи последовательного нахождения <tex>LCS</tex> двух строк и уменьшением набора строк на единицу, не срабатывает. Это доказывается следующим контрпримером.Даны три последовательности: <tex>X = \left \langle A, B, C, D, E\right \rangle </tex> <tex>Y = \left \langle D, E, A, B, C\right \rangle </tex> <tex>Z = \left \langle D, E, F, G, H\right \rangle </tex> Подсчитаем <tex>V = LCS(X,Y) = \left \langle A, B, C \right \rangle</tex> <tex>LCS(Z,V) = \emptyset</tex> Это неверно, так как <tex>LCS(X,Y,Z) = \left \langle D, E \right \rangle</tex> {{Теорема|statement = Пусть имеются последовательности <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> Z = \left \langle z_1, z_2, \dots, z_k \right \rangle </tex>, а <tex> V = \left \langle v_1, v_2, \dots, v_h \right \rangle</tex> — их <tex>LCS</tex>.# Если <tex>z_k = x_m = y_n</tex>, то <tex>z_k = x_m = y_n = v_h</tex> и <tex> V_{h - 1} </tex> — <tex>LCS(X_{m - 1},Y_{n - 1},Z_{k - 1})</tex># Если <tex>z_k \neq x_m \neq y_n</tex>, то из <tex>z_k \neq v_h</tex> следует, что <tex>V</tex> — <tex>LCS(X_m,Y_n,Z_{k - 1})</tex># Если <tex>z_k \neq x_m \neq y_n</tex>, то из <tex>y_n \neq v_h</tex> следует, что <tex>V</tex> — <tex>LCS(X_m,Y_{n - 1},Z_k)</tex># Если <tex>z_k \neq x_m \neq y_n</tex>, то из <tex>x_m \neq v_h</tex> следует, что <tex>V</tex> — <tex>LCS(X_{m - 1},Y_n,Z_k)</tex>|proof = Доказательство аналогично доказательству для двух последовательностей.}} ===Решение===Обозначим как <tex> lcs[i][j][l] </tex> наибольшую общую подпоследовательность префиксов данных последовательностей равна нулю, поэтому заканчивающихся в элементах с номерами <tex> i </tex>, <tex> j </tex> и <tex> l </tex> соответственно. Получается следующее рекуррентное соотношение: <tex>lcs[i][j][l] =\begin{cases} 0, & i = 0\text{ or }j = 0\text{ or }l = 0 \\ lcs[i - 1][j - 1][l - 1] + 1, & x[i] = y[j] = z[l] \\ \max(lcs[i][j - 1][l],\ lcs[i - 1][j][l],\ lcs[i][j][l - 1]), & x[i] \neq y[j] \neq z[l]\end{cases}</tex> Очевидно, что сложность алгоритма составит <tex> O(mnk) </tex>, где <tex> m </tex>, <tex> n </tex> и их НОП тоже нулевой <tex> k </tex> — длиныпоследовательностей. Аналогичным образом задача решается для <tex>k</tex> строк. Заполняется <tex>k</tex>-мерная динамика. == Алгоритм Хиршберга == {{Задача|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>LCS(X,Y)</tex> за время <tex> O(nm) </tex> и <tex> O(n + m) </tex> памяти.}}
Не теряя общности, будем считать, что <tex> m \geqslant n </tex>. Тогда разобьем последовательность <tex> X </tex> на две равные части <tex dpi="200"> x_1 \left [0 \dots \frac {m} {2} \right ] </tex> и <tex dpi="200"> x_2 \left [\frac {m} {2} + 1 \dots m \right ] </tex>. Найдем <tex> LCS </tex> для <tex> x_1 </tex> и всех префиксов последовательности <tex>Y</tex>, аналогично — для развернутых последовательностей <tex> x_2 </tex> и <tex> Y </tex>. Стоит отметить, что для нахождения <tex> LCS </tex> на всех префиксах достаточно одного квадратичного прохода, так как <tex>i</tex>-ый элемент последней строки результирующей матрицы есть не что иное, как <tex> LCS </tex> первой последовательности и префикса второй длины <tex>i</tex>. Затем выберем такой индекс <tex> j </tex>, что <tex> \left | LCS(x_1, y \left [0 \dots j \right ]) + LCS(reverse(x_2), reverse(y \left [j + 1 \dots n \right ])) \right | = Построение подпоследовательности ===max</tex>. Запустим алгоритм рекурсивно для пар Для каждой пары элементов будем хранить <tex>(x_1, y \left [0 \dots j \right ])</tex> и <tex>(x_2, y \left [j + 1 \dots n \right ])</tex>. Будем продолжать до тех пор, пока в <tex>X</tex> не только длину НОП соответствующих префиксовостанется ровно <tex>1</tex> элемент, тогда достаточно проверить, входит ли он текущую часть <tex>Y</tex>, но и номера последних элементовесли входит, участвующих то добавим этот символ в этой НОПответ, если нет — вернем пустую строку.Таким образом, посчитав ответв результате работы алгоритма соберем последовательность, мы сможем восстановить всю наибольшую общую подпоследовательностькоторая будет являться искомой.
=== Псевдокод ===
return
== Список литературы ==