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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Время работы)
Строка 18: Строка 18:
  
 
При предподсчёте перебирается <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> | \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> k < \frac{\log n}{1 + \log | \Sigma |}</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>
  
 
== Источники ==
 
== Источники ==

Версия 22:06, 24 марта 2012

Описание алгоритма

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

Table 4russians.GIF

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

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

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

Источники