304
правки
Изменения
Новая страница: «{{В разработке}} == Описание алгоритма == Рассмотрим задачу о наибольшей общей подпоследова…»
{{В разработке}}
== Описание алгоритма ==
Рассмотрим задачу о наибольшей общей подпоследовательности для двух последовательностей одинаковой длины. Тогда таблица динамического программирования имеет размер <tex>(n + 1) \times (n + 1)</tex>. Разобьём её на квадраты размера <tex>k \times k</tex> следующим образом: выделим каждую <tex>k</tex>-ую строчку, начиная с первой. Аналогично выделяем столбцы.
Требуется, чтобы <tex>k</tex> делило <tex>n</tex>, но это не является ограничением - можно дописать в конец последовательностей символы, которые не встречались в других местах этих последовательностей (символы для каждой последовательности должны быть разными). Тогда ответ на задачу не изменится, а длину можно "довести" до делителя <tex>k</tex>.
Предпосчитаем действие каждого возможного квадрата. Понятно, что окончательный результат зависит только от значений в верхнем левом "уголке" квадрата и подстрок, для которых считается ответ. Окончательным результатом будут значения в нижнем правом "уголке" квадрата.
Может показаться, что таких уголков может быть много. Но, так как соседние числа в матрице отличаются не более, чем на один, то результат зависит только от константы в верхнем левом элементе матрицы, и возрастания чисел в верхнем и левом крае квадрата. Возрастание чисел будем хранить с помощью битовых масок: сначала <tex>k - 1</tex> бит кодирует возрастание чисел в верхнем крае квадрата (0 - элемент равен предыдущему, 1 - больше предыдущего на один), потом <tex>k - 1</tex> бит кодируют возрастание чисел в квадрате по левому краю аналогичным образом.
Более того, константу в верхнем левом элементе квадрата можно вообще не хранить - её можно прибавить при надобности к каждому элементу результата.
Итого, получается <tex>{\left (2|\Sigma| \right )}^{2k}</tex> предпосчитанных квадратов, подсчёт каждого происходит за время, пропорциональное <tex>k^2</tex>.
После этого ответ для самой задачи НОП считается аналогично обычному алгоритму, только на этот раз пересчитывается не каждый элемент матрицы, а только уголки.
== Время работы ==
Суммарное время работы алгоритма <tex>O\left({\left (2|\Sigma| \right )}^{2k} + \frac{n^2}{k^2}\right)</tex>. Понятно, что для получения выигрыша в производительности по сравнению с обычным алгоритмом необходимо, чтобы первое слагаемое не превышало второе. Это достигается при условии <tex>k < \frac{\log n}{1 + \log c}</tex>
== Описание алгоритма ==
Рассмотрим задачу о наибольшей общей подпоследовательности для двух последовательностей одинаковой длины. Тогда таблица динамического программирования имеет размер <tex>(n + 1) \times (n + 1)</tex>. Разобьём её на квадраты размера <tex>k \times k</tex> следующим образом: выделим каждую <tex>k</tex>-ую строчку, начиная с первой. Аналогично выделяем столбцы.
Требуется, чтобы <tex>k</tex> делило <tex>n</tex>, но это не является ограничением - можно дописать в конец последовательностей символы, которые не встречались в других местах этих последовательностей (символы для каждой последовательности должны быть разными). Тогда ответ на задачу не изменится, а длину можно "довести" до делителя <tex>k</tex>.
Предпосчитаем действие каждого возможного квадрата. Понятно, что окончательный результат зависит только от значений в верхнем левом "уголке" квадрата и подстрок, для которых считается ответ. Окончательным результатом будут значения в нижнем правом "уголке" квадрата.
Может показаться, что таких уголков может быть много. Но, так как соседние числа в матрице отличаются не более, чем на один, то результат зависит только от константы в верхнем левом элементе матрицы, и возрастания чисел в верхнем и левом крае квадрата. Возрастание чисел будем хранить с помощью битовых масок: сначала <tex>k - 1</tex> бит кодирует возрастание чисел в верхнем крае квадрата (0 - элемент равен предыдущему, 1 - больше предыдущего на один), потом <tex>k - 1</tex> бит кодируют возрастание чисел в квадрате по левому краю аналогичным образом.
Более того, константу в верхнем левом элементе квадрата можно вообще не хранить - её можно прибавить при надобности к каждому элементу результата.
Итого, получается <tex>{\left (2|\Sigma| \right )}^{2k}</tex> предпосчитанных квадратов, подсчёт каждого происходит за время, пропорциональное <tex>k^2</tex>.
После этого ответ для самой задачи НОП считается аналогично обычному алгоритму, только на этот раз пересчитывается не каждый элемент матрицы, а только уголки.
== Время работы ==
Суммарное время работы алгоритма <tex>O\left({\left (2|\Sigma| \right )}^{2k} + \frac{n^2}{k^2}\right)</tex>. Понятно, что для получения выигрыша в производительности по сравнению с обычным алгоритмом необходимо, чтобы первое слагаемое не превышало второе. Это достигается при условии <tex>k < \frac{\log n}{1 + \log c}</tex>
