Применение метода четырёх русских в задачах ДП на примере задачи о НОП — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
(не показано 15 промежуточных версий 8 участников) | |||
Строка 1: | Строка 1: | ||
== Описание алгоритма == | == Описание алгоритма == | ||
− | Рассмотрим задачу о наибольшей общей подпоследовательности для двух последовательностей одинаковой длины. Тогда таблица динамического программирования имеет размер <tex> (n + 1) \times (n + 1) </tex>. Разобьём её на квадраты размера <tex> k \times k </tex> следующим образом: выделим каждую <tex> k </tex>-ую строчку, начиная с первой. Аналогично выделяем столбцы. | + | === Предподсчёт === |
+ | Рассмотрим [[Задача о наибольшей общей подпоследовательности|задачу о наибольшей общей подпоследовательности]] для двух последовательностей одинаковой длины. Тогда таблица динамического программирования имеет размер <tex> (n + 1) \times (n + 1) </tex>. Разобьём её на квадраты размера <tex> k \times k </tex> следующим образом: выделим каждую <tex> (k + 1) </tex>-ую строчку, начиная с первой. Аналогично выделяем столбцы. | ||
− | + | Требуется, чтобы <tex> k </tex> делило <tex> n </tex>, но это не является ограничением {{---}} можно дописать в конец последовательностей символы, которые не встречались в других местах этих последовательностей (символы для каждой последовательности должны быть разными). Тогда ответ на задачу не изменится, а длину можно «довести» до делителя <tex> k </tex>. | |
− | + | Сделаем предподсчёт действия каждого возможного квадрата. Окончательный результат зависит только от значений в верхнем левом «уголке» над квадратом и подстрок, для которых считается ответ {{---}} остальные значения в квадрате однозначно считаются с их помощью. Окончательным результатом будут значения в нижнем правом «уголке» квадрата. | |
− | + | Может показаться, что таких уголков может быть много. Но, так как соседние числа в матрице отличаются не более, чем на один, то результат зависит только от константы в верхнем левом элементе матрицы, и возрастания чисел в верхнем и левом крае квадрата. Возрастание чисел будем хранить с помощью битовых масок: сначала <tex> k - 1 </tex> бит кодирует возрастание чисел в верхнем крае квадрата (<tex>0</tex> {{---}} элемент равен предыдущему, <tex>1</tex> {{---}} больше предыдущего на один), потом <tex> k - 1 </tex> бит кодируют возрастание чисел в квадрате по левому краю аналогичным образом. | |
− | + | Более того, константу в верхнем левом элементе квадрата можно вообще не хранить: её можно прибавить при необходимости к каждому элементу результата. | |
− | + | Посчитаем эти квадраты для строк <tex>abbaba</tex> и <tex>bababb</tex>. Возьмём <tex> k = 3 </tex>. Тогда предподсчитанные квадраты, которые понадобятся для дальнейшего вычисления НОП, выглядят так: | |
− | + | {| | |
+ | | | ||
+ | {|class="wikitable" style="background-color:#FFF; text-align:center; " | ||
+ | | colspan="2" rowspan="2" | | ||
+ | ! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex> | ||
+ | ! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex> | ||
+ | ! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex> | ||
+ | |- | ||
+ | ! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>a</tex> | ||
+ | ! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex> | ||
+ | ! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex> | ||
+ | |- | ||
+ | ! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex> | ||
+ | ! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex> | ||
+ | |<tex>0</tex> | ||
+ | |<tex>1</tex> | ||
+ | |<tex>1</tex> | ||
+ | |- | ||
+ | ! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex> | ||
+ | ! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>a</tex> | ||
+ | |<tex>1</tex> | ||
+ | |<tex>1</tex> | ||
+ | |<tex>1</tex> | ||
+ | |- | ||
+ | ! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex> | ||
+ | ! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex> | ||
+ | |<tex>1</tex> | ||
+ | |<tex>2</tex> | ||
+ | |<tex>2</tex> | ||
+ | |} | ||
+ | | || || || || || || | ||
+ | | | ||
+ | {|class="wikitable" style="background-color:#FFF; text-align:center; " | ||
+ | | colspan="2" rowspan="2" | | ||
+ | ! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex> | ||
+ | ! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex> | ||
+ | ! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex> | ||
+ | |- | ||
+ | ! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>a</tex> | ||
+ | ! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex> | ||
+ | ! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>a</tex> | ||
+ | |- | ||
+ | ! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>1</tex> | ||
+ | ! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex> | ||
+ | |<tex>1</tex> | ||
+ | |<tex>1</tex> | ||
+ | |<tex>1</tex> | ||
+ | |- | ||
+ | ! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex> | ||
+ | ! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>a</tex> | ||
+ | |<tex>2</tex> | ||
+ | |<tex>2</tex> | ||
+ | |<tex>2</tex> | ||
+ | |- | ||
+ | ! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>1</tex> | ||
+ | ! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex> | ||
+ | |<tex>2</tex> | ||
+ | |<tex>3</tex> | ||
+ | |<tex>3</tex> | ||
+ | |} | ||
+ | |} | ||
− | |||
− | + | {| | |
− | + | | | |
+ | {|class="wikitable" style="background-color:#FFF; text-align:center; " | ||
+ | | colspan="2" rowspan="2" | | ||
+ | ! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>1</tex> | ||
+ | ! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>1</tex> | ||
+ | ! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex> | ||
+ | |- | ||
+ | ! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>a</tex> | ||
+ | ! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex> | ||
+ | ! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex> | ||
+ | |- | ||
+ | ! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex> | ||
+ | ! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>a</tex> | ||
+ | |<tex>1</tex> | ||
+ | |<tex>2</tex> | ||
+ | |<tex>2</tex> | ||
+ | |- | ||
+ | ! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex> | ||
+ | ! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex> | ||
+ | |<tex>1</tex> | ||
+ | |<tex>2</tex> | ||
+ | |<tex>3</tex> | ||
+ | |- | ||
+ | ! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex> | ||
+ | ! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex> | ||
+ | |<tex>1</tex> | ||
+ | |<tex>2</tex> | ||
+ | |<tex>3</tex> | ||
+ | |} | ||
+ | | || || || || || || | ||
+ | | | ||
+ | {|class="wikitable" style="background-color:#FFF; text-align:center; " | ||
+ | | colspan="2" rowspan="2" | | ||
+ | ! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex> | ||
+ | ! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>1</tex> | ||
+ | ! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>1</tex> | ||
+ | |- | ||
+ | ! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>a</tex> | ||
+ | ! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex> | ||
+ | ! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>a</tex> | ||
+ | |- | ||
+ | ! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex> | ||
+ | ! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>a</tex> | ||
+ | |<tex>1</tex> | ||
+ | |<tex>1</tex> | ||
+ | |<tex>2</tex> | ||
+ | |- | ||
+ | ! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>1</tex> | ||
+ | ! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex> | ||
+ | |<tex>1</tex> | ||
+ | |<tex>2</tex> | ||
+ | |<tex>2</tex> | ||
+ | |- | ||
+ | ! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex> | ||
+ | ! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex> | ||
+ | |<tex>1</tex> | ||
+ | |<tex>2</tex> | ||
+ | |<tex>2</tex> | ||
+ | |} | ||
+ | |} | ||
− | == Источники == | + | === Вычисление НОП на сжатой матрице === |
+ | Ответ для самой задачи НОП считается аналогично обычному алгоритму, только рассматривая не каждую ячейку таблицы, а квадраты <tex> k \times k </tex>. В очередной квадрат (пусть его левый верхний угол находится в ячейке с координатами <tex> i, j </tex>) вставляем значения предподсчитанного квадрата, соответствующего данным подстрокам и битовым маскам, и прибавляем ко всем элементам в квадрате число, стоящее в уголке над квадратом, т.е. в ячейке с координатами <tex> i - 1, j - 1 </tex>. | ||
+ | |||
+ | Для нашего примера итоговая таблица выглядит так: | ||
+ | |||
+ | {| style=" border-collapse:collapse; text-align: center" | ||
+ | | style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 0 0 1px"| | ||
+ | | style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 0 0 0"| | ||
+ | | style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>a</tex> | ||
+ | | style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>b</tex> | ||
+ | | style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>b</tex> | ||
+ | | style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>a</tex> | ||
+ | | style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>b</tex> | ||
+ | | style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>a</tex> | ||
+ | |- | ||
+ | | style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 0 0 0 1px"| | ||
+ | | style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex> | ||
+ | | style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex> | ||
+ | | style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex> | ||
+ | | style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex> | ||
+ | | style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex> | ||
+ | | style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex> | ||
+ | | style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex> | ||
+ | |- | ||
+ | | style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>b</tex> | ||
+ | | style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>0</tex> | ||
+ | | style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex> | ||
+ | | style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex> | ||
+ | | style="background-color: #E0FFFF; width: 40px; height: 40px;border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex> | ||
+ | | style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex> | ||
+ | | style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex> | ||
+ | | style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex> | ||
+ | |- | ||
+ | | style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>a</tex> | ||
+ | | style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex> | ||
+ | | style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex> | ||
+ | | style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex> | ||
+ | | style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex> | ||
+ | | style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>2</tex> | ||
+ | | style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>2</tex> | ||
+ | | style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>2</tex> | ||
+ | |- | ||
+ | | style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>b</tex> | ||
+ | | style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex> | ||
+ | | style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex> | ||
+ | | style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>2</tex> | ||
+ | | style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>2</tex> | ||
+ | | style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>2</tex> | ||
+ | | style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>3</tex> | ||
+ | | style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>3</tex> | ||
+ | |- | ||
+ | | style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>a</tex> | ||
+ | | style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex> | ||
+ | | style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex> | ||
+ | | style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>2</tex> | ||
+ | | style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>2</tex> | ||
+ | | style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>3</tex> | ||
+ | | style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>3</tex> | ||
+ | | style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>4</tex> | ||
+ | |- | ||
+ | | style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>b</tex> | ||
+ | | style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex> | ||
+ | | style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex> | ||
+ | | style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>2</tex> | ||
+ | | style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>3</tex> | ||
+ | | style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>3</tex> | ||
+ | | style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>4</tex> | ||
+ | | style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>4</tex> | ||
+ | |- | ||
+ | | style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>b</tex> | ||
+ | | style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex> | ||
+ | | style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex> | ||
+ | | style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>2</tex> | ||
+ | | style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>3</tex> | ||
+ | | style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>3</tex> | ||
+ | | style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>4</tex> | ||
+ | | style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>4</tex> | ||
+ | |} | ||
+ | |||
+ | == Анализ алгоритма == | ||
+ | |||
+ | === Время работы === | ||
+ | При предподсчёте перебирается <tex> | \Sigma | ^k </tex> (где <tex> | \Sigma | </tex> {{---}} мощность алфавита) возможных подстрок первой строки и столько же {{---}} второй строки. Для каждой возможной подстроки обеих строк перебирается по <tex> 2^{k - 1} </tex> битовых масок. Для самого предподсчёта требуется время <tex> O(k^2) </tex>. Дальнейший алгоритм поиска НОП требует <tex> O \left ( \frac{n^2}{k^2} \right ) </tex>. Тогда суммарное время работы алгоритма составляет <tex> O \left ( |\Sigma| ^{2k} \cdot 2^{2k - 2} \cdot k^2 + \frac{n^2}{k^2} \right ) </tex>. | ||
+ | Понятно, что для получения выигрыша в производительности по сравнению с обычным алгоритмом необходимо, чтобы первое слагаемое не превышало второе. Найдём <tex> k </tex>, решив неравенство: | ||
+ | |||
+ | <tex> |\Sigma| ^{2k} \cdot 2^{2k - 2} \cdot k^2 \leqslant \frac{n^2}{k^2} </tex> | ||
+ | |||
+ | <tex> \left ( 2 | \Sigma | \right ) ^{2k} \cdot \frac{1}{4} \cdot k^4 \leqslant n^2 </tex> | ||
+ | |||
+ | <tex> \left ( 2 | \Sigma | \right ) ^k \cdot k^2 \leqslant 2n </tex>. | ||
+ | |||
+ | <tex> k \log {2 | \Sigma |} + 2 \log k \leqslant \log 2 + \log n </tex>. | ||
+ | |||
+ | Пренебрегая <tex> \log k </tex> и <tex> \log 2 </tex> как <tex> o(k) </tex>, получаем <tex> k \leqslant \frac{\log n}{1 + \log | \Sigma |}</tex> | ||
+ | |||
+ | === Используемая память === | ||
+ | Для каждого предподсчитанного квадрата хранятся подстроки длиной <tex> 2k </tex>, битовые маски длиной <tex> 2k </tex> и результат {{---}} нижний «уголок» длины <tex> 2k - 1 </tex>. Как уже было подсчитано, всего предподсчитывается <tex> |\Sigma| ^{2k} \cdot 2^{2k - 2} </tex> квадратов. Дальнейший алгоритм требует <tex> O \left ( \frac{n^2}{k^2} \right ) </tex>, значит, всего требуется <tex> O \left ( |\Sigma| ^{2k} \cdot 2^{2k - 2} \cdot (2k + 2k + 2k - 1) + \frac{n^2}{k^2} \right ) = O \left ( |\Sigma| ^{2k} \cdot 2^{2k - 2} \cdot k + \frac{n^2}{k^2} \right ) </tex> памяти. | ||
+ | |||
+ | == Источники информации == | ||
* http://pages.cpsc.ucalgary.ca/~pmohasse/private-lcs.pdf | * http://pages.cpsc.ucalgary.ca/~pmohasse/private-lcs.pdf | ||
[[Категория:Дискретная математика и алгоритмы]] | [[Категория:Дискретная математика и алгоритмы]] | ||
[[Категория:Динамическое программирование]] | [[Категория:Динамическое программирование]] | ||
+ | [[Категория:Способы оптимизации методов динамического программирования]] |
Текущая версия на 19:39, 4 сентября 2022
Содержание
Описание алгоритма
Предподсчёт
Рассмотрим задачу о наибольшей общей подпоследовательности для двух последовательностей одинаковой длины. Тогда таблица динамического программирования имеет размер . Разобьём её на квадраты размера следующим образом: выделим каждую -ую строчку, начиная с первой. Аналогично выделяем столбцы.
Требуется, чтобы
делило , но это не является ограничением — можно дописать в конец последовательностей символы, которые не встречались в других местах этих последовательностей (символы для каждой последовательности должны быть разными). Тогда ответ на задачу не изменится, а длину можно «довести» до делителя .Сделаем предподсчёт действия каждого возможного квадрата. Окончательный результат зависит только от значений в верхнем левом «уголке» над квадратом и подстрок, для которых считается ответ — остальные значения в квадрате однозначно считаются с их помощью. Окончательным результатом будут значения в нижнем правом «уголке» квадрата.
Может показаться, что таких уголков может быть много. Но, так как соседние числа в матрице отличаются не более, чем на один, то результат зависит только от константы в верхнем левом элементе матрицы, и возрастания чисел в верхнем и левом крае квадрата. Возрастание чисел будем хранить с помощью битовых масок: сначала
бит кодирует возрастание чисел в верхнем крае квадрата ( — элемент равен предыдущему, — больше предыдущего на один), потом бит кодируют возрастание чисел в квадрате по левому краю аналогичным образом.Более того, константу в верхнем левом элементе квадрата можно вообще не хранить: её можно прибавить при необходимости к каждому элементу результата.
Посчитаем эти квадраты для строк
и . Возьмём . Тогда предподсчитанные квадраты, которые понадобятся для дальнейшего вычисления НОП, выглядят так:
|
|
|
|
Вычисление НОП на сжатой матрице
Ответ для самой задачи НОП считается аналогично обычному алгоритму, только рассматривая не каждую ячейку таблицы, а квадраты
. В очередной квадрат (пусть его левый верхний угол находится в ячейке с координатами ) вставляем значения предподсчитанного квадрата, соответствующего данным подстрокам и битовым маскам, и прибавляем ко всем элементам в квадрате число, стоящее в уголке над квадратом, т.е. в ячейке с координатами .Для нашего примера итоговая таблица выглядит так:
Анализ алгоритма
Время работы
При предподсчёте перебирается
(где — мощность алфавита) возможных подстрок первой строки и столько же — второй строки. Для каждой возможной подстроки обеих строк перебирается по битовых масок. Для самого предподсчёта требуется время . Дальнейший алгоритм поиска НОП требует . Тогда суммарное время работы алгоритма составляет . Понятно, что для получения выигрыша в производительности по сравнению с обычным алгоритмом необходимо, чтобы первое слагаемое не превышало второе. Найдём , решив неравенство:
.
.
Пренебрегая
и как , получаемИспользуемая память
Для каждого предподсчитанного квадрата хранятся подстроки длиной
, битовые маски длиной и результат — нижний «уголок» длины . Как уже было подсчитано, всего предподсчитывается квадратов. Дальнейший алгоритм требует , значит, всего требуется памяти.