Алгоритм поиска максимальной подматрицы в периодической матрице со сложностью O(np)

Пусть матрица называется периодической, если ее элементы являются циклическим повторением некоторой последовательности чисел.

Задача: дана периодическая матрица произвольного размера, необходимо найти подматрицу, сумма элементов которой максимальна.


В дальнейших рассуждениях используется матрица (конкретные числа заменены номерами):


С чего начнем?

Цикл в ней составляют элементы 1, 2, 3, 4, 5, 6. Строки начинаются только с 1, 3 и 5. Для начала будем искать подматрицу высотой 1. Начнем искать лучшую подматрицу в первой строке (или с первого элемента цикла, что тоже самое), как в алгоритме Кадане. Когда мы дойдем до третьего элемента, начнем одновременно считать сумму и для второй строки. Аналогично на пятом элементе. Теперь посмотрим точнее, что происходит. Чтоб вычислить сумму на шестом элементе мы к каждой из имеющихся трех сумм добавляем одно и тоже число (6 элемент). На следующем шаге мы опять добавим к каждому из них одно и тоже число (1 элемент) и т.д.

Каковы шансы каждой из рассматриваемых строк содержать лучшую сумму?


1. Если сумма в первой строке ни разу не сбрасывалась (по алгоритму Кадане это происходит, когда сумма становиться меньше 0), то только она может содержать максимальную сумму;

2. Если она сбросилась на втором элементе, то она все еще имеет преимущество над суммой в строке, начавшейся с третьего элемента (т.к. дальнейшие числа у обеих строк одинаковые, а второй элемент может быть положительный – значение этого элемента и будет преимуществом);

3. Если сумма первой строки сбросилась на третьем элементе, то тогда по возможной дальнейшей сумме с суммой второй строки они на равных, но вторая строка началась позднее, а значит и закончится позднее, и в ней может набраться большая сумма. Сумма в первой строке уже никогда не сможет превысить сумму во второй строке и ее можно исключить из рассмотрения;

4. Если сумма первой строки сбросилась после третьего элемента, то рассуждения те же, что и в п.3.

5. Если на текущем элементе строка заканчивается, то дальше продолжать ее мы не можем, и если она сейчас не содержит максимальную сумму, то уже никогда не будет.

Аналогична для остальных строк.

Когда можно убрать строку из рассмотрения?

1. Если сумма в строке А обнулилась после элемента, с которого началась строка Б, то строку А можно исключить из рассмотрения;

2. Если на этом элементе цикла строка должна закончиться, то ее следует исключить ее из рассмотрения (применительно к примеру, первую строку необходимо исключить из рассмотрения на 3 элементе 3 цикла, вторую на 5 элементе 3 цикла, третью – на 1 элементе 4 цикла);

И что это нам дает?

Максимальную сумму может содержать только строка, появившаяся раньше других и не исключенная по правилам 1, 2. И наоборот: минимальную сумму может содержать только строка, появившаяся позднее других.

Как осуществляются проверки на максимальную сумму и на удаление строк из рассмотрения?

Пусть имеем список, в конец которого мы добавляем новые строки для проверки. Получаем, что на каждом следующем элементе цикла:
Для проверки максимальной суммы достаточно проверять только для строки в начале списка.
Для удаления строк по правилу 1 достаточно проверять только вторую строку с конца пока не встретиться строка, сумма которой больше нуля (для последней строки у нас пока нет никаких гарантий, что в ней не будет лучшей суммы при дальнейшем расчете).
Для удаления строки по правилу 2 достаточно проверять только строку в начале списка.

И как долго нам проверять эти правила?

После первого прохода цикла мы гарантированно начнем проверки всех возможных строк матрицы. Когда список строк будет пуст, поиск подматриц высоты 1 будет закончен: к этому моменту будут проверены все возможные варианты.

Пусть m – ширина матрицы, p – длина цикла. Тогда: поиск всех подматриц высоты 1 будет завершен после прохода по p+m элементам цикла (т.к. все строки появившиеся при первом проходе цикла (p) будут гарантированно удалены по правилу 2 еще через m элементов цикла).

А если точнее, как долго нам проверять эти правила?

Рассмотрим случай, когда m > 2p. Тогда после первого прохода цикла далее к суммам строк будут добавляться те же самые значения цикл за циклом. Имеем два варианта:

1. Если сумма элементов цикла больше нуля, то максимальная сумма будет в самом последнем цикле (при условии, что это полный цикл, в противном случае может быть и в предпоследнем).

2. Если сумма элементов цикла меньше нуля, то суммы, полученные на втором проходе цикла будут больше соответствующих сумм каждого следующего прохода.

Получаем, что для полной проверки всех элементов при m > 2p, необходимо обработать p элементов в первом проходе цикла, плюс не более 2p элементов в оставшихся циклах (т.к. последний цикл может быть не полным). Итого 3p элементов.


Рассмотрим случай, когда m <= 2p. Необходимо обработать m+p элементов цикла, или не более 3p.


Какова сложность по времени обработки одного элемента цикла?

На каждом элементе цикла выполняются следующие действия:

1. Проверка на добавление новой строки. Линейная сложность: только одна строка может быть добавлена. Если несколько строк начинаются с данного элемента цикла, то достаточно рассмотреть любую из них;

2. Проверка на максимальную сумму. Линейная сложность: проверить достаточно только сумму строки в начале списка;

3. Проверка на удаление строки по правилу 1. Не более p проверок в сумме по всем элементам цикла, т.к. количество строк p и удалить строку можно только 1 раз. В итоге линейная сложность;

4. Проверка на удаление по правилу 2. Линейная сложность: на каждом элементе цикла могло быть добавлена не более 1 строки, следовательно и закончиться на каждом элементе может не более 1 строки.

5. Проверка на опустошение списка строк. Линейная сложность.

6. Обновить суммы строк. Линейная сложность: считается только общая сумма элементов sum (обнуление отрицательной суммы строки row_sum происходит присвоением ей значения sum, текущая сумма строки находиться как sum - row_sum, значения суммы остальных строк не меняются).
Получаем: сложность действий, выполняемых на каждом элементе цикла, линейна.


Какова сложность по времени поиска лучшей подматрицы высоты 1?

Для случая m>2p необходимо обработать более 3p элементов цикла, для m<=2p необходимо обработать не более 3p элементов, поэтому для любых m и p необходимо обработать не более 3p элементов.

Т.к. сложность обработки одного элемента линейна, то сложность обработки 3p элементов O(p). Тогда сложность поиска подматрицы высотой 1 в заданной матрице равна O(p).


А что же делать с подматрицами, имеющими большую высоту?

Поиск подматриц большей высоты можно свести к поиску аналогичному поиску подматрицы высоты 1. Каждый столбец матрицы заменяется на сумму элементов этого столбца. Или ближе к практике: для подматриц высоты 2 значение элемента изначальной матрицы заменяется на сумму этого элемента и элемента стоящего под ним, для подматриц высоты 3 – на сумму этого элемента и двух элементов стоящих под ним и т.д. А на практике: сумма находиться только для элементов цикла. И далее уже производиться поиск аналогичный поиску подматрицы высоты 1.


На сколько сложен по времени поиск лучших подматриц имеющих большую высоту?

Проверять нужно строки от нуля до n-h, где n – высота матрицы, h – высота подматрицы (нумерация строк с нуля). Уникальных строк в них будет не более p. Поэтому сложность по времени будет складываться из:

1. Сложности подготовки элементов матрицы для поиска подматриц текущей высоты. Требуется p сложений для получения новых значений цикла из значений цикла для поиска подматрицы меньшей высоты (на 1 строку меньше). Итого O(p);

2. Сложности поиска подматрицы текущей высоты O(p).

Итого: сложность поиска подматрицы каждой высоты O(p).


А если в общем, какая сложность по времени?

Различных высот подматриц может быть n, поэтому сложность поиска подматрицы любой высоты будет O(np).


Понятно, но что со сложностью по памяти?

В случае обработки в одном потоке необходимо хранить:

1. p элементов – значения цикла, составляющего матрицу;

2. p элементов – для хранения сумм столбцов подматриц, при поиске подматриц высоты большей 1;

3. p элементов - для списка текущих проверяемых строк;

4. единичные значения (лучшая сумма, текущая высота подматрицы, временные значения и т.д.).

Итого: сложность поиска лучшей подматрицы по памяти O(p).


Как все сказанное соотноситься с задачей на конкурс Acceler8?

1. Для матриц содержащих малое число повторений цикла время поиска может быть хуже времени поиска с помощью модифицированного алгоритма Кадане для матриц;

2. Алгоритм может быть модифицирован для матриц, в которых только часть элементов составляют периодическую матрицу. Поиск по непериодической части матрицы осуществляется модифицированным алгоритмом Кадане для матриц.

Pour de plus amples informations sur les optimisations de compilation, consultez notre Avertissement concernant les optimisations.
Étiquettes: