Алгоритъмът на Тадао Такаока за намиране на максималната подматрица или проблем с максималния подмасив

Не толкова отдавна се проведе състезанието по паралелно програмиране Acceler8 2011. Същността на проблема беше да се намери максималната подматрица в тази матрица (сумата от елементите на намерената подматрица трябва да бъде максимална). След кратко гугълне се установи, че определен алгоритъм на Тадао Такаока решава този проблем по-бързо от други.

„Предизвикателството е прието!“ и започнах да търся този алгоритъм навсякъде, където е възможно, като се заех да го приложа. Въпреки факта, че е слабо паралелизиран и съдържа доста голяма константа в своята сложност.

Въпреки това, всичко, което беше намерено, бяха статии на английски от същия Тадао Такаока (ето една от тези статии). Трябваше да превеждам.

Самата идея на алгоритъма в началото изглеждаше безобразно проста:

Първо, трябва да изчислим всички префиксни суми s[i, j] за матрици като a[1..i, 1..j] за всички i и j с ограничението s[i, 0] = s[0, j] = 0. Очевидно това се прави за O(mn) време.Основен алгоритъм:Ако матрицата е един елемент, върнете нейната стойност. В противен случай:

  • ако m > n, завъртете матрицата на 90 градуса.
Следователно m ≤ n.
  • Нека A_left е решението за лявата половина.
  • A_right е решението за дясната половина.
  • A_column - решение за проблем, центриран в колона (намиране на такава максимална подматрица, която да пресича централната линия)
  • Общото решение е максималното от тези три.

Ако A_left и A_right са намерени чрез рекурсия, тогава A_column трябва да се намери ръчно.

Ето какво е написано за намирането на това решение в оригиналната статия:

"Сега проблемът, центриран върху колона, може да бъде решен по следния начин. A_column = max(k=1:i-1,l=0:n/2-1,i=1:m,j=n/2+1:n) . Фиксираме i и k, имаксимизиране на оставащия израз чрез промяна на l и j. Тогава това е еквивалентно на следния израз: i = 1, . m и k = 1, . i − 1. A_колона [i, k] = max(l=0:n/2-1,j=n/2+1:n) Нека s∗[i, j] = −s[j, i]. Тогава този израз може да бъде намален до: A_колона [i, k] = −min(l=0:n/2-1) + max(j=n/2+1:n) "

След това трябва да споменем друга задача на Тадао Такаока: Умножение на матрица на разстояние (не се наемам да превеждам този термин).

Целта на DMM е да изчисли произведението на разстоянието C = AB за две n-мерни матрици A = a[i,j] и B = b[i,j], чиито елементи са реални числа.

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

И така, като използвате тази дефиниция, можете да получите следното: Във формулата A_column [i, k] = −min(l=0:n/2-1) + max(j=n/2+1:n) можете да видите, че първата част на формулата е DMM за минимума, втората част е DMM за максимума. Нека S1 и S2 са матрици, чиито елементи (i, j) са съответно s[i, j − 1] s[i, j + n/2]. За всяка матрица T, нека T∗ е матрицата, получена от T чрез транспониране и отрицание. Тогава горният израз може да бъде изчислен чрез „умножаване“ на S1 и S1∗ за минимума и получаване на долна триъгълна матрица, „умножаване“ на S2 и S2∗ за максимума и получаване на долна триъгълна матрица и накрая изваждане от последната предишна матрица. Изчислявайки максимума в него, получаваме отговора: A_колона = max(DMM_max(S2*S2∗)-DMM_min(S1*S1∗)).

Следното е псевдокод за решаване на проблема с DMM за nxn матрици A и B:

Копиране на източника Копиране на HTML

  1. /Сортирайте n реда на B в низходящ ред в списък[ i ], т.е. всеки списък[i] ще съдържа индексите на подредените елементи на ред i;
  2. /Нека създадем набор V = < 1 , . n>;
  3. за i := 1 до n започвам
  4. за k := 1 до n направете начало
  5. cand[k]:=първо от списък[k];
  6. d[k] := a [i, k] + b [k, cand[k]];
  7. край;
  8. / Подредете V като приоритетна опашка по отношение на ключовете d[ 1 ], . d[n];
  9. / Множеството решения S е празно;
  10. /* Фаза 1: До критичната точка */
  11. докато S ≤ n − n log n започват
  12. /Намерете v с минималния ключ в опашката;
  13. /Поставете cand[v] в набор S;
  14. c[ i , cand[v]] := d[v];
  15. /Нека множеството W = ;
  16. за w в W правя
  17. докато cand[w] е в S, направете cand[w]:= следващ от списък[w];
  18. /Сортиране на опашка W по нови ключове d[w] = a [ i , w]+ b [w, cand[w]];
  19. край;
  20. U := S;
  21. /* Фаза 2: След критичната точка */
  22. докато S a [ i, w]+ b [w, cand[w]];
  23. край;
  24. край.

Статията препоръчва използването на двоична купчина за опашки. По-късните версии показват, че използването на фибонак куп може да ускори процеса още повече, но аз, за ​​мой срам, не успях да го приложа напълно. Ето защо използвах двоичен файл.

Въпреки това, дори след внедряването на този псевдокод, установих, че решението не работи. На етапа на изчисляване на S1 и S2 беше открита очевидна грешка - описаното правило за конструиране на тези матрици не беше достатъчно, за да работи алгоритъмът правилно. И не можах да намеря по-подробно описание в нито една статия.Така трябваше сам да изградя матриците.

И така, след дълги часове, прекарани в търсене и проверка, се получиха следните правила.

Нека S е префиксна матрица за матрица A.

Тогава m по n/2 матрица S1 съдържа първата колона от 0, а останалите n/2-1 колони съдържат първите колони на префиксната матрица S:

Матрицата n/2 по m S1∗ съдържа първия ред и колона от 0, останалата подматрица е отрицанието и транспонирането на първите редове и колони на префиксната матрица S: (k = n div 2 + n mod 2)

Матрицата m по k S2 съдържа колоните на префиксната матрица S, започвайки от k-тата:

Матрица S2∗ с размери k на m: първа колона от 0, след това транспониране и отрицание на колоните на префиксната матрица S, започвайки от k-тата колона:

Като цяло алгоритъмът се оказа много труден за разбиране и изпълнение и не оправда очакванията за изключителна бързина (не са правени допълнителни оптимизации).

Същата статия твърди, че този алгоритъм работи в O(n^3*log(log(n))/log(n)) и също така споменава, че алгоритъмът работи по-бързо в сравнение с други алгоритми на големи матрици (вероятно много големи).

Hardcore conf в C++. Каним само професионалисти.