Применение метода четырёх русских в задачах ДП на примере задачи о НОП — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Предподсчёт: Кажется, опечатка?)
 
(не показано 18 промежуточных версий 9 участников)
Строка 1: Строка 1:
{{В разработке}}
+
== Описание алгоритма ==
 +
 
 +
=== Предподсчёт ===
 +
Рассмотрим [[Задача о наибольшей общей подпоследовательности|задачу о наибольшей общей подпоследовательности]] для двух последовательностей одинаковой длины. Тогда таблица динамического программирования имеет размер <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>
 +
|}
 +
|&nbsp;||&nbsp;||&nbsp;||&nbsp;||&nbsp;||&nbsp;||&nbsp;
 +
|
 +
{|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>
 +
|}
 +
|&nbsp;||&nbsp;||&nbsp;||&nbsp;||&nbsp;||&nbsp;||&nbsp;
 +
|
 +
{|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>(n + 1) \times (n + 1)</tex>. Разобьём её на квадраты размера <tex>k \times k</tex> следующим образом: выделим каждую <tex>k</tex>-ую строчку, начиная с первой. Аналогично выделяем столбцы.
+
== Анализ алгоритма ==
  
[[Файл:Table_4russians.GIF]]
+
=== Время работы ===
 +
При предподсчёте перебирается <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>k</tex> делило <tex>n</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>k - 1</tex> бит кодирует возрастание чисел в верхнем крае квадрата (0 - элемент равен предыдущему, 1 - больше предыдущего на один), потом <tex>k - 1</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>{\left (2|\Sigma| \right )}^{2k}</tex> предподсчитанных квадратов, подсчёт каждого происходит за время, пропорциональное <tex>k^2</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
  
Суммарное время работы алгоритма <tex>O\left({\left (2|\Sigma| \right )}^{2k} + \frac{n^2}{k^2}\right)</tex>. Понятно, что для получения выигрыша в производительности по сравнению с обычным алгоритмом необходимо, чтобы первое слагаемое не превышало второе. Это достигается при условии <tex>k < \frac{\log n}{1 + \log c}</tex>
+
[[Категория:Дискретная математика и алгоритмы]]
 +
[[Категория:Динамическое программирование]]
 +
[[Категория:Способы оптимизации методов динамического программирования]]

Текущая версия на 03:29, 19 октября 2019

Описание алгоритма[править]

Предподсчёт[править]

Рассмотрим задачу о наибольшей общей подпоследовательности для двух последовательностей одинаковой длины. Тогда таблица динамического программирования имеет размер [math] (n + 1) \times (n + 1) [/math]. Разобьём её на квадраты размера [math] k \times k [/math] следующим образом: выделим каждую [math] (k + 1) [/math]-ую строчку, начиная с первой. Аналогично выделяем столбцы.

Требуется, чтобы [math] k [/math] делило [math] n [/math], но это не является ограничением — можно дописать в конец последовательностей символы, которые не встречались в других местах этих последовательностей (символы для каждой последовательности должны быть разными). Тогда ответ на задачу не изменится, а длину можно «довести» до делителя [math] k [/math].

Сделаем предподсчёт действия каждого возможного квадрата. Окончательный результат зависит только от значений в верхнем левом «уголке» над квадратом и подстрок, для которых считается ответ — остальные значения в квадрате однозначно считаются с их помощью. Окончательным результатом будут значения в нижнем правом «уголке» квадрата.

Может показаться, что таких уголков может быть много. Но, так как соседние числа в матрице отличаются не более, чем на один, то результат зависит только от константы в верхнем левом элементе матрицы, и возрастания чисел в верхнем и левом крае квадрата. Возрастание чисел будем хранить с помощью битовых масок: сначала [math] k - 1 [/math] бит кодирует возрастание чисел в верхнем крае квадрата ([math]0[/math] — элемент равен предыдущему, [math]1[/math] — больше предыдущего на один), потом [math] k - 1 [/math] бит кодируют возрастание чисел в квадрате по левому краю аналогичным образом.

Более того, константу в верхнем левом элементе квадрата можно вообще не хранить: её можно прибавить при необходимости к каждому элементу результата.

Посчитаем эти квадраты для строк [math]abbaba[/math] и [math]bababb[/math]. Возьмём [math] k = 3 [/math]. Тогда предподсчитанные квадраты, которые понадобятся для дальнейшего вычисления НОП, выглядят так:

[math]0[/math] [math]0[/math] [math]0[/math]
[math]a[/math] [math]b[/math] [math]b[/math]
[math]0[/math] [math]b[/math] [math]0[/math] [math]1[/math] [math]1[/math]
[math]0[/math] [math]a[/math] [math]1[/math] [math]1[/math] [math]1[/math]
[math]0[/math] [math]b[/math] [math]1[/math] [math]2[/math] [math]2[/math]
             
[math]0[/math] [math]0[/math] [math]0[/math]
[math]a[/math] [math]b[/math] [math]a[/math]
[math]1[/math] [math]b[/math] [math]1[/math] [math]1[/math] [math]1[/math]
[math]0[/math] [math]a[/math] [math]2[/math] [math]2[/math] [math]2[/math]
[math]1[/math] [math]b[/math] [math]2[/math] [math]3[/math] [math]3[/math]


[math]1[/math] [math]1[/math] [math]0[/math]
[math]a[/math] [math]b[/math] [math]b[/math]
[math]0[/math] [math]a[/math] [math]1[/math] [math]2[/math] [math]2[/math]
[math]0[/math] [math]b[/math] [math]1[/math] [math]2[/math] [math]3[/math]
[math]0[/math] [math]b[/math] [math]1[/math] [math]2[/math] [math]3[/math]
             
[math]0[/math] [math]1[/math] [math]1[/math]
[math]a[/math] [math]b[/math] [math]a[/math]
[math]0[/math] [math]a[/math] [math]1[/math] [math]1[/math] [math]2[/math]
[math]1[/math] [math]b[/math] [math]1[/math] [math]2[/math] [math]2[/math]
[math]0[/math] [math]b[/math] [math]1[/math] [math]2[/math] [math]2[/math]

Вычисление НОП на сжатой матрице[править]

Ответ для самой задачи НОП считается аналогично обычному алгоритму, только рассматривая не каждую ячейку таблицы, а квадраты [math] k \times k [/math]. В очередной квадрат (пусть его левый верхний угол находится в ячейке с координатами [math] i, j [/math]) вставляем значения предподсчитанного квадрата, соответствующего данным подстрокам и битовым маскам, и прибавляем ко всем элементам в квадрате число, стоящее в уголке над квадратом, т.е. в ячейке с координатами [math] i - 1, j - 1 [/math].

Для нашего примера итоговая таблица выглядит так:

[math]a[/math] [math]b[/math] [math]b[/math] [math]a[/math] [math]b[/math] [math]a[/math]
[math]0[/math] [math]0[/math] [math]0[/math] [math]0[/math] [math]0[/math] [math]0[/math] [math]0[/math]
[math]b[/math] [math]0[/math] [math]0[/math] [math]1[/math] [math]1[/math] [math]1[/math] [math]1[/math] [math]1[/math]
[math]a[/math] [math]0[/math] [math]1[/math] [math]1[/math] [math]1[/math] [math]2[/math] [math]2[/math] [math]2[/math]
[math]b[/math] [math]0[/math] [math]1[/math] [math]2[/math] [math]2[/math] [math]2[/math] [math]3[/math] [math]3[/math]
[math]a[/math] [math]0[/math] [math]1[/math] [math]2[/math] [math]2[/math] [math]3[/math] [math]3[/math] [math]4[/math]
[math]b[/math] [math]0[/math] [math]1[/math] [math]2[/math] [math]3[/math] [math]3[/math] [math]4[/math] [math]4[/math]
[math]b[/math] [math]0[/math] [math]1[/math] [math]2[/math] [math]3[/math] [math]3[/math] [math]4[/math] [math]4[/math]

Анализ алгоритма[править]

Время работы[править]

При предподсчёте перебирается [math] | \Sigma | ^k [/math] (где [math] | \Sigma | [/math] — мощность алфавита) возможных подстрок первой строки и столько же — второй строки. Для каждой возможной подстроки обеих строк перебирается по [math] 2^{k - 1} [/math] битовых масок. Для самого предподсчёта требуется время [math] O(k^2) [/math]. Дальнейший алгоритм поиска НОП требует [math] O \left ( \frac{n^2}{k^2} \right ) [/math]. Тогда суммарное время работы алгоритма составляет [math] O \left ( |\Sigma| ^{2k} \cdot 2^{2k - 2} \cdot k^2 + \frac{n^2}{k^2} \right ) [/math]. Понятно, что для получения выигрыша в производительности по сравнению с обычным алгоритмом необходимо, чтобы первое слагаемое не превышало второе. Найдём [math] k [/math], решив неравенство:

[math] |\Sigma| ^{2k} \cdot 2^{2k - 2} \cdot k^2 \leqslant \frac{n^2}{k^2} [/math]

[math] \left ( 2 | \Sigma | \right ) ^{2k} \cdot \frac{1}{4} \cdot k^4 \leqslant n^2 [/math]

[math] \left ( 2 | \Sigma | \right ) ^k \cdot k^2 \leqslant 2n [/math].

[math] k \log {2 | \Sigma |} + 2 \log k \leqslant \log 2 + \log n [/math].

Пренебрегая [math] \log k [/math] и [math] \log 2 [/math] как [math] o(k) [/math], получаем [math] k \leqslant \frac{\log n}{1 + \log | \Sigma |}[/math]

Используемая память[править]

Для каждого предподсчитанного квадрата хранятся подстроки длиной [math] 2k [/math], битовые маски длиной [math] 2k [/math] и результат — нижний «уголок» длины [math] 2k - 1 [/math]. Как уже было подсчитано, всего предподсчитывается [math] |\Sigma| ^{2k} \cdot 2^{2k - 2} [/math] квадратов. Дальнейший алгоритм требует [math] O \left ( \frac{n^2}{k^2} \right ) [/math], значит, всего требуется [math] 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 ) [/math] памяти.

Источники информации[править]