Обзор алгоритмов поиска максимальной подматрицы

Создать новую статью

31.10.2011 12:00


Задача о максимальной подматрице(Maximum Subarray Problem):

Мы рассматриваем двумерный массив a[1...m, 1...n] в качестве входных данных. Задачей нахождения максимальной подматрицы (далее MSP) является максимизация части массива a[k...i, l...j], то есть, получения соответствующих индексов (K, L) и (I, J). Мы предполагаем, что верхний левый угол имеет координаты (1, 1).

Решение MSP было впервые предложено Бентли. Затем оно было усовершенствовано Тамаки и Токуяма. Бентли было достигнуто кубическое время для этого алгоритма. Тамаки и Токуяма далее получили суб-кубическое время для почти квадратный матрицы. Этот алгоритм является рекурсивным и чрезвычайно сложным. Тадао Такаока далее упростил алгоритм Тамаки и Токуяма, с помощью разделяй-и-властвуй метода достигнув суб-кубического времени для любой прямоугольный матрицы.

Допустим, что m ≤ n без ограничения общности. Алгоритм Бентли решает MSP за время O(m^2*n), он использует алгоритм Каданэ для одномерного случая, который работает за линейное время.

Алгоритм Каданэ /* максимальный подмассив a[k..l] массива a[1..n] */

(k, l) := (0, 0); s := −∞; t := 0; j := 1;
for i:=1 to n do begin
t := t + a[i];
if t > s then begin (k, l) := (j, i); s := t end;
if t < 0 then begin t := 0; j := i + 1 end
end

К сожалению, идея Каданэ не работает для двумерного случая.

Алгоритм Тамаки и Токуяма решает данную задачу за суб-кубическое время, где данная матрица пракчтически квадратная: m = O(n).

Разобьем матрицу на четыре части центральной вертикальной и горизонтальной линиями. Мы назовём верхнюю-левую, верхнюю-правую, нижнюю-левую и нижнюю-правую части NW (северо-запад), NE, SW и SE частями соответственно. Определим три условных решения задачи. Первое: максимальную подматрицу,  пересекающую центр, назовём как A_center. Эта задача называется центральной задачей. Второе: максимальная подматрица, пересекающая горизонтальную линию, - A_row. Эта задача называется row-centered. И третья подматрица, пересекающая вертикальную линию, обозначается A_column. Эта задача называется column-centered. Алгоритм схематически представлен в рекурсивной форме ниже:

Основной алгоритм

  • Если матрица становится одномерной, горизонтальной или вертикальной, - решать задачу алгоритмом Каданэ за линейное время.
    • Иначе:
  • пусть A_NW будет решением для NW-части,
  • A_NE - решение для NE-части,
  • A_SW - решение для SW-части,
  • A_SE  - для SE-части.
  • A_row - решение для row-centered задачи.
  • A_column - решение для column-centered задачи.

Решением всей задачи будет максимум из этих шести.

Алгоритм для решения row-centered задачи:

  • Делим матрицу на две части вертикальной линией.
  • Пусть A_left - решение для левой row-centered задачи.
  • A_right - решение для right row-centered задачи.
  • A_center - решение для центральной задачи.
Решением будет максимум из этих трёх.

Алгоритм для column-centered задачи
  • Делим матрицу на две части горизонтальной линией.
  • Пусть A_upper будет решением для верхней column-centered задачи.
  • A_lower - решение для нижней column-centered задачи.
  • A_center - решение центральной задачи.
Общим решением будет максимум этих трёх.

Теперь центральная задача может быть решена следующим образом. Пусть частичные суммы элементов матрицы на северо-запад, северо-восток,  юго-запад и юго-восток от центра - S_NW[i, j], S_NE [i, j], S_SW[i, j] и S_SE[i, j] соответственно. Например, S_NW[i, j] - сумма элементов части a[i..m/2, j..n/2]. Эти частичные суммы могут быть посчитаны за время O(mn). Тогда A_center может быть посчитана как

max(i=1:m/2,j=1:n/2,k=m/2+1:m,l=n/2+1:n) {S_NW [i, j] + S_SW [k, j] + S_NE [i, l] + S_SE [k, l]}

Если мы зафиксируем i и k, то поиск такого максимума может быть сведен к решению задач DMM(distance matrix multiplication) для первых двух слагаемых и последних двух. Заметим также, что нам необходимо транспонировать S_SW и S_SE, что бы привести к решению DMM. Таким образом задача может быть решена за O(M (m, n)), где M (m, n)  - время работы для "перемножения" матриц расстояний размером (m, n) и (n, m). В конечном итоге этот алгоритм решается за время:

T (m, n) = O(m^2*n(log(log(m))/ log( m))^0.5*log(n/m)).

Алгоритм Тадао Такаока
Для начала нам необходимо посчитать все префиксные суммы s[i, j] для таких матриц, как a[1..i, 1..j], для всех i и j с ограничением s[i, 0] = s[0, j] = 0. Очевидно, это делается за время O(mn). Покажем, что column-centered задача может быть решена без рекурсий. Схема алгоритма представлена ниже. Отметим также, что нам нет необходимости решать одномерную задачу здесь, и префиксные суммы требуют подсчёта только один раз.

Основной алгоритм
  • Если матрица оказывается одним элементом - возвращаем его значение.
Иначие,
  • если m > n, поворачиваем матрицу на 90 градусов.
Таким образом m ≤ n.
  • Пусть A_left - решение для левой половины.
  • A_right - решение для правой половины.
  • A_column - решение для column-centered задачи.
Общее решение - максимум из этих трёх.

Теперь column-centered задача может быть решена следующим образом.

A_column = max(k=1:i-1,l=0:n/2-1,i=1:m,j=n/2+1:n) {s[i, j] − s[i, l] − s[k, j] + s[k, l]}.

Мы фиксируем i и k, и максимизируем оставшееся выражение изменением l и j. Тогда это эквивалентно следующему выражению:
i = 1, ..., m и k = 1, ..., i − 1.

A_column [i, k] = max(l=0:n/2-1,j=n/2+1:n) {−s[i, l] + s[k, l] + s[i, j] − s[k, j]}

Пусть s∗[i, j] = −s[j, i]. Тогда данное выражение может быть сведено к:

A_column [i, k] = −min(l=0:n/2-1) {s[i, l] + s∗ [l, k]} + max(j=n/2+1:n) {s[i, j] + s ∗[j, k]}

В первой части - DMM для минимума, во второй - DMM для максимума. Пусть S1 и S2 матрицы, чьи элементы (i, j) являются s[i, j − 1] s[i, j + n/2] соответственно. Для любой матрицы T, пусть T∗ - матрица, полученная из T транспонированием и отрицанием. Тогда верхнее выражение может быть посчитано "перемножением" S1 и S1∗ для минимума и получение нижне-треугольной матрицы, "перемножением" S2 и S2∗ для максимума и получение нижне-треугольной матрицы и, наконец, вычитания из последней предыдущей матрицы. Вычислив в ней максимум - получим ответ.
DMM(Distance Matrix Multiplication)
Целью DMM является вычисление произведения расстояний(distance product) C = AB  для двух n-мерных матрицA = а[i, j] and B = b[i,j], чьи элементы - вещественные числа.

c[i,j] = min(k=1:n) { ai,k + bk,j }

Суть c[i,j] - наименьшее расстояние из вершины i из первого слоя до вершины j в третьем слое в ациклическом ориентрированном графе, состоящем из трёх слоёв вершин. Эти вершины пронумерованы 1, ...,n в каждом слое, и расстояние от i в первом слое до j во втором слое - a[i,j] и из i во втором слое до j в третьем слое - b[i,j]. Очевидно, что это выражение можно легко привести для подсчёта максимума вместо минимума - это будет задача о нахождении наибольших путей.

Решение этой задачи в данной статье мы опустим, в следствие того, что оно не является алгоритмом подсчёта максимальной подматрицы. Однако заметим, что решение её методом Тадао Такаока занимает по времени O(n^2*log n).

Что же касается алгоритма Тадао Такаока для MSP - по всей видимости это наиболее быстрый алгоритм из всех известных на данный момент. Он работает за время O(n^3*log(log(n))/log(n)).