Завдання про максимальну подматріца (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 може бути порахована як
Якщо ми зафіксуємо 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 градусів.
- Нехай A_left - рішення для лівої половини.
- A_right - рішення для правої половини.
- A_column - рішення для column-centered завдання.
Тепер column-centered завдання може бути вирішена наступним чином.
Ми фіксуємо i і k, і максимізували залишився вираз зміною l і j. Тоді це еквівалентно наступного виразу:
i = 1. m і k = 1. i - 1.
Нехай s * [i, j] = -s [j, i]. Тоді цей вислів може бути зведене до:
У першій частині - 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] - найменша відстань з вершини 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)).
Для отримання докладної інформації про можливості оптимізації компілятора зверніться до нашого повідомленням про оптимізацію.