Алгоритм поиска максимальной подматрицы в периодической матрице со сложностью 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. Алгоритм может быть модифицирован для матриц, в которых только часть элементов составляют периодическую матрицу. Поиск по непериодической части матрицы осуществляется модифицированным алгоритмом Кадане для матриц.

Пожалуйста, обратитесь к странице Уведомление об оптимизации для более подробной информации относительно производительности и оптимизации в программных продуктах компании Intel.

Комментарии

Аватар пользователя adavydow

Из описания мне не понятна одна вещь: что происходит, когда вы выкидываете первую строку, из-за того, что она дошла до конца. Чему теперь равна сумма для второй строки?

Аватар пользователя ronsenval

В общем случае сумму каждой строку можно считать отдельно (алгоритмом Кадане), но т.к. при описанном подходе к добавлению строк мы знаем, что к суммам строк на каждом элементе цикла будет добавляться одно и тоже число, то можно сделать так:
Считаем общую сумму (total_sum) чисел с самого первого элемента. А для новых строк запоминаем чему была равна общая сумма при появлении этой строки (row_sum). Тогда текущая сумма строки в дальнейшем может быть вычислена как total_sum - row_sum. Обнуление строки можно делать записывая значение общей суммы (total_sum) в значение суммы текущей строки (row_sum).
При таком подходе получается, что на каждом элементе цикла необходимо вычислять только общую сумму (total_sum), не трогая значения row_sum каждой из строк.
Вы об этом спрашивали?

Аватар пользователя

Автор сам придумал этот алгоритм?

Аватар пользователя

Автор сам придумал этот алгоритм?