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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
Строка 1: Строка 1:
{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
 
|+
 
|-align="center"
 
|'''НЕТ ВОЙНЕ'''
 
|-style="font-size: 16px;"
 
|
 
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
 
 
Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
 
 
Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
 
 
Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
 
 
''Антивоенный комитет России''
 
|-style="font-size: 16px;"
 
|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
 
|-style="font-size: 16px;"
 
|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
 
|}
 
 
 
== Описание алгоритма ==
 
== Описание алгоритма ==
  

Текущая версия на 19:39, 4 сентября 2022

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

Предподсчёт

Рассмотрим задачу о наибольшей общей подпоследовательности для двух последовательностей одинаковой длины. Тогда таблица динамического программирования имеет размер [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] памяти.

Источники информации