Изменения

Перейти к: навигация, поиск

Задача о наибольшей общей подпоследовательности

98 байт добавлено, 19:27, 4 сентября 2022
м
rollbackEdits.php mass rollback
''<font color="green">// подсчёт таблиц</font>''
'''int''' LCS(x: '''intvector''', y: '''intvector'''):
m = length(x)
n = length(y)
Заметим, что для вычисления <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: '''intvector''', y: '''intvector'''):
'''if''' length(x) < length(y) ''<font color="green">// в таблице будет length(y) столбцов, и если length(x) меньше, выгоднее поменять местами x и y</font>''
swap(x, y)
Также можно заметить, что от <tex> (i - 1) </tex>-ой строчки нужны только элементы с <tex> (j - 1) </tex>-го столбца. В этом случае можно использовать лишь <tex> min(m, n) </tex> элементов таблицы:
'''int''' LCS3(x: '''intvector''', y: '''intvector'''):
'''if''' length(x) < length(y) ''<font color="green">// в таблице будет length(y) столбцов, и если length(x) меньше, выгоднее поменять местами x и y</font>''
swap(x, y)
=== Алгоритм ===
Не теряя общности, будем считать, что <tex> m \ge geqslant n </tex>. Тогда разобьем последовательность <tex> X </tex> на две равные части <texdpi="200"> x^1 x_1 \left [0 \dots \frac {m} {2} \right ] </tex> и <texdpi="200"> x^2 x_2 \left [\frac {m} {2} + 1 \dots m \right ] </tex>. Найдем <tex> LCS </tex> для <tex> x^1 x_1 </tex> и всех префиксов последовательности <tex>Y</tex>, аналогично - для развернутых последовательностей <tex> x^2 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^1x_1, y \left [0 \dots j \right ]) + LCS(reverse(x^2x_2), reverse(y \left [j + 1 \dots n \right ])) \right | = max </tex> . Запустим алгоритм рекурсивно для пар <tex>(x^1x_1, y \left [0 \dots j \right ])</tex> и <tex>(x^2x_2, y \left [j + 1 \dots n \right ])</tex>. Будем продолжать до тех пор, пока в <tex>X</tex> не останется ровно <tex>1 </tex> элемент, тогда достаточно проверить, входит ли он текущую часть <tex>Y</tex>, если входит, то добавим этот символ в ответ, если нет - вернем пустую строку. Таким образом, в результате работы алгоритма соберем последовательность, которая будет являться искомой.
=== Псевдокод ===
В данном примере <tex> x, y </tex> - последовательности, <tex> ans </tex> - вектор ответа. <tex> LCS </tex> - функция, возвращающая последнюю строку матрицы <tex> lcs </tex>, для определения ответа на всех префиксах. Важно отметить, что для ее вычисления необходимо и достаточно хранить лишь две соседние строки матрицы <tex> lcs </tex> в любой момент времени. Так как вопрос оптимальности используемой памяти является важным местом данного алгоритма, то передачу различных отрезков последовательностей стоит воспринимать, как скрытую передачу границ для хранящихся глобально данных.
'''void''' hirschberg(x: '''vector''', y: '''vector'''):
it_max = -1
'''for''' j = 0 '''to''' y.size()
'''if''' f[j] + s[y.size() - (j + 1)] > max max = f[j] + s[y.size() - (j + 1)]
it_max = j
'''if''' f[y.size() - 1] > max
it_max = y.size() - 1
delete[] f
delete[] s ''<font color="green"> // промежуточные массивы необходимо удалять или хранить глобально </font>''
hirschberg(x[0 .. mid], y[0 .. it_max])
hirschberg(x[mid + 1 .. x.size()], y[it_max + 1 .. y.size()])
=== Доказательство корректности=== Осталось понять, что алгоритм находит нужную подпоследовательность. Не теряя общности, будем считать, что <tex> lcs </tex> единственная, так как нам не важно какую из равных по длине подпоследовательностей выбирать. Тогда рассмотрим разделение на две части <tex>X</tex>, часть символов LCS (возможно нулевая) попадет в первую половину, оставшаяся — во вторую. Пусть <tex> x_i </tex> последний символ из LCS в первой половине, тогда наш алгоритм выберет соответствующий ему <tex> y_i </tex> в качестве точки разделения. То есть символы из <tex> y </tex>, которые связанысо второй половиной <tex> x </tex>, лежат правее <tex> y_i </tex>, в противном случае, либо <tex> y_i </tex> не состоит в паре с <tex> x_i </tex>, либо <tex> x_i </tex> не последний символ из <tex> lcs </tex> в первой половине. Заметим, что если первая половина не содержит <tex> lcs </tex>, то точки разбиения не будет, для симметричного случая со второй половиной точкой разбиения будет <tex> y_i </tex>, которая включается в первую половину. Таким образом, мы свели поиск исходной <tex> lcs </tex> к поиску двух независимых частей. Когда в <tex> X </tex> останется <tex>1</tex> символ, то возможны два варинта, либо он входит в <tex> lcs </tex>, либо нет, в чем мы убеждаемся линейным поиском, случай, когда последний <tex> x </tex> не входит в <tex> lcs </tex>, возникает из-за того, что на каком-то шаге, вся подпоследовательность оказалась в одной из половин <tex> X </tex>. === Асимптотика ===
Рассмотрим временные затраты алгоритма. Рекурсия представима в виде бинарного дерева высоты не более <tex> \log (m) </tex>, так как она основана на разделении первой последовательности на две равные части на каждом шаге алгоритма.
Оценим время выполнения для произвольной глубины такого дерева и просуммируем результат по всем возможным значениям парметра. На глубине <tex> h </tex> находится <tex> 2^h </tex> вершин с частью последовательности <tex> x </tex> размера <tex dpi = "200"> \displaystyle\frac{m}{2^h} </tex>
и частью <tex> y </tex> длины <tex> k_i </tex>, где сумма семейства <tex> k_i </tex> равна <tex> n </tex>. Таким образом, получаем:
* На глубине h: <tex dpi = "200">{\displaystyle \sum_{i = 0}^{2^h - 1}\limits\frac{m}{2^h} k_i = \frac{m}{2^h} \sum_{i = 0}^{2^h - 1} \limits k_i = \frac{mn}{2^h}} </tex>
* Сумммируем по глубинам: <tex dpi = "200">{\displaystyle \sum_{i = 0}^{\log m}\limits\frac{mn}{2^i} = \frac{mn}{2^h} \sum_{i = 0}^{\log m} \limits \frac{1}{2^i} < \frac{mn}{2^i} \sum_{i = 0}^{\infty} \limits \frac{1}{2^i} = 2mn} </tex>
* Итоговая асимптотика алгоритма: <tex> O(mn) </tex>
Осталось понять, что алгоритм находит нужную подпоследовательностьПроанализируем затраты на память. Не теряя общностиТри глобальные последовательности (две исходные и одна для ответа), будем считатьк которым мы обращаемся внутри алгоритма, что требуют <tex> lcs m + n + \min (m, n) </tex> единственная, так как нам не важно какую из равных по длине подпоследовательностей выбиратьпамяти. Тогда рассмотрим разделение Дополнительно на две части каждом шаге рекурсии вызываются <tex>X2</tex>, часть символов LCS (возможно нулевая) попадет в первую половину, оставшаяся — во вторую. Пусть <tex> x_i функции </tex> последний символ из LCS в первой половине, тогда наш алгоритм выберет соответствующий ему <tex> y_i </tex> в качестве точки разделения. То есть символы из <tex> y </tex>, которые связанысо второй половиной суммарно требуют <tex> x 4k_i </tex>, лежат правее где <tex> y_i k_i </tex>, в противном случае, либо — длина части <tex> y_i y </tex> не состоит в паре с <tex> x_i </tex>текущий момент, либо так как для нахождения <tex> x_i LCS </tex> не последний символ из достаточно двух строк матрицы <tex> lcs </tex> в первой половине. Заметим, что если первая половина не содержит <tex> lcs </tex>, то точки разбиения не будет, для симметричного случая со второй половиной точкой разбиения будет <tex> y_i </tex>Вспомогательные массивы удаляются перед рекурсивным вызовом, которая включается в первую половину. Таким таким образом, мы свели поиск исходной <tex> lcs </tex> к поиску двух независимых частей. Когда в <tex> X </tex> останется 1 символобщие затраты равны сумме размеров массивов на одной глубине рекурсии, то возможны два варинта, либоон входит в <tex> lcs </tex>, либо нет, в чем мы убеждаемся линейным поиском, случай, когда последний <tex> x </tex> не входит в <tex> lcs </tex>, возникает из-за того, что на каком-то шаге, вся подпоследовательность оказалась в одной из половин <tex> X </tex>.есть:
* На глубине h: <tex dpi ="200">{\displaystyle\sum_{i =0}^{2^h - 1}\limits 4 k_i = Затраты на память =4 \sum_{i =0}^{2^h - 1}\limits k_i =4n} </tex>
Проанализируем затраты на память. Три глобальные последовательности (две исходные и одна для ответа), к которым мы обращаемся внутри алгоритма, требуют * Итого: <texdpi = "200"> {n + m + n + \min (m, n) + 4n = O(n + m)}</tex> памяти. Дополнительно на каждом шаге рекурсии вызываются 2 функции <tex> LCS </tex>, которые суммарно требуют <tex> 4k_i </tex>, где <tex> k_i </tex> — длина части <tex> y </tex> в текущий момент, так как для нахождения <tex> LCS </tex> достаточно двух строк матрицы <tex> lcs </tex>. Вспомогательные массивы удаляются перед рекурсивным вызовом, таким образом, общие затраты равны сумме размеров массивов на одной глубине рекурсии, то есть:
* На глубине h: <tex dpi = "200">{\sum_{i = 0}^{2^h - 1} 4 k_i = 4 \sum_{i = 0}^{2^h - 1} k_i = 4n} </tex>
 
* Итого: <tex dpi = "200">{n + m + \min(m, n) + 4n = O(n + m)}</tex>
== См. также ==
== Список литературы ==
* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 459. — ISBN 5-8489-0857-4
* Hirschberg, D.S.: A linear space algorithm for computing maximal common subsequences. Commun. ACM 18, 341–343 (1975)
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]
1632
правки

Навигация