Problema subarray-ului maxim (Problema Maximum Subarray):
Considerăm o matrice bidimensională o [1. m, 1. n] ca date de intrare. Sarcina de a găsi submatricul maxim (MSP suplimentar) este de a maximiza partea din matrice a [k. i, l. j], adică obținerea indiciilor corespunzătoare (K, L) și (I, J). Presupunem că colțul din stânga sus are coordonate (1, 1).
Decizia MSP a fost inițial propusă de Bentley. Apoi a fost îmbunătățită de Tamaki și Tokuyama. Bentley a obținut un timp cubic pentru acest algoritm. Tamaki și Tokuyama au primit în continuare timp subcubic pentru o matrice aproape pătrată. Acest algoritm este recursiv și extrem de complex. Tadao Takaoka simplificat și mai mult algoritmul Tamaki și Tokuyama printr-o metodă divide și cuceri de sub-cub ajunge timp pentru orice matrice dreptunghiulară.
Presupunem că m ≤ n fără pierderea generalității. Algoritmul Bentley rezolvă MSP în timp O (m ^ 2 * n). el folosește algoritmul Kadane pentru cazul unidimensional, care funcționează în timp liniar.
Algoritmul Kadane / * este subarajul maxim a [k..l] al matricei a [1..n] * /
(k, l): = (0, 0); s: = -∞; t: = 0; j: = 1;
pentru i: = 1 până la n începe
t: = t + a [i];
dacă t> s începe apoi (k, l): = (j, i); s: = t sfârșitul;
dacă t <0 then begin t := 0; j := i + 1 end
capăt
Din păcate, ideea lui Kadane nu funcționează pentru cazul bidimensional.
Algoritmul Tamaki și Tokuyama rezolvă această problemă pentru un timp subcubic, unde matricea dată este practic patrată: m = O (n).
Împărțim matricea în patru părți prin liniile verticale și orizontale centrale. Vom numi părțile din stânga sus, dreapta sus, partea din stânga și din dreapta jos a părților din NV (nord-vest), NE, SW și SE, respectiv. Definim trei soluții condiționate ale problemei. În primul rând, submatricul maxim care intersectează centrul este numit A_center. Această sarcină este numită sarcina centrală. În al doilea rând, submatricul maxim care intersectează linia orizontală este A_row. Această sarcină este numită rând-centrat. Iar cea de-a treia submatrice, care intersectează linia verticală, este desemnată coloană A_. Această sarcină se numește centrată pe coloană. Algoritmul este prezentat schematic în formularul recursiv de mai jos:
- Dacă matricea devine unidimensională, orizontală sau verticală, rezolvați problema prin algoritmul Kadane în timp liniar. în caz contrar:
- lăsați A_NW să fie soluția pentru partea nord-vestică,
- A_NE este soluția pentru partea NE,
- A_SW este soluția pentru partea SW,
- A_SE este pentru partea SE.
- A_row este soluția pentru sarcina centrată pe rând.
- Coloana A_ este soluția pentru sarcina centrată pe coloană.
Soluția pentru întreaga problemă va fi un maxim de aceste șase.
Algoritm pentru rezolvarea sarcinilor centrate pe rând:
- Împărțim matricea în două părți printr-o linie verticală.
- Fie A_left soluția pentru problema centrată pe rândul stâng.
- A_right este soluția pentru sarcina centrată pe rând.
- A_center este soluția pentru sarcina centrală.
Soluția este maximul acestor trei.
Algoritm pentru sarcinile centrate pe coloane
- Împărțim matricea în două părți printr-o linie orizontală.
- Fie ca A_upper să fie soluția pentru sarcina centrată pe coloană.
- A_lower este soluția pentru sarcina centrată pe coloană inferioară.
- A_centre - soluția sarcinii centrale.
Acum problema centrală poate fi rezolvată după cum urmează. Să presupunem că sumele parțiale ale elementelor matricei la nord-vest, nord-est, sud-vest și sud-est de centrul - S_NW [i, j], S_NE [i, j], S_SW [i, j] și S_SE [i, j ] respectiv. De exemplu, S_NW [i, j] - o parte din elementele unui [i..m / 2, j..n / 2]. Aceste sume parțiale pot fi calculate în timp O (mn). Apoi A_center poate fi considerat ca
Dacă vom repara i și k, căutarea maximă poate fi redusă la soluția de sarcini DMM (distanța de multiplicare matrice) pentru primii doi termeni și ultimele două. Rețineți, de asemenea, că trebuie să transpunem S_SW și S_SE, ceea ce ar duce la o soluție DMM. Astfel, problema poate fi rezolvată în O (M (m, n)), unde M (m, n) - timpul de funcționare pentru "multiplicare" distanța Dimensiunea matricei (m, n) și (n, m). În cele din urmă, acest algoritm este rezolvat în timp:
T (m, n) = 0 (m ^ 2 * n (log (log (m)) / log (m)) ^ 0,5 * log (n / m)).
Algoritmul Tadao Takaoka
Mai întâi trebuie să calculeze suma tuturor prefix s [i, j] pentru matrici cum ar fi [1..i, 1..j], pentru toți i și j cu restricție s [i, 0] = s [0, j] = 0. Evident, acest lucru se face în timp O (mn). Arătăm că problema centrată pe coloană poate fi rezolvată fără recurs. Schema algoritmului este prezentată mai jos. Rețineți, de asemenea, că aici nu este nevoie să rezolvăm problema unidimensională, iar sumele prefixelor necesită numărarea o singură dată.
Algoritmul de bază
- Dacă matricea este un element, vom întoarce valoarea sa.
- Dacă m> n, rotiți matricea cu 90 de grade.
- Lăsați A_left soluția pentru jumătatea stângă.
- A_right este soluția pentru jumătatea dreaptă.
- Coloana A_ este soluția pentru sarcina centrată pe coloană.
Problema centrată pe coloană poate fi rezolvată după cum urmează.
Fixăm i și k și maximizăm expresia rămasă schimbând l și j. Apoi, aceasta este echivalentă cu următoarea expresie:
i = 1. m și k = 1. i - 1.
Fie s * [i, j] = -s [j, i]. Apoi, această expresie poate fi redusă la:
În prima parte - DMM pentru un minim, în al doilea - DMM pentru un maxim. Să S1 și S2 matrice ale cărei elemente (i, j) sunt s [i, j - 1] s [i, j + n / 2], respectiv. Pentru orice matrice T, T * este matricea obținută din T prin transpunere și negare. Apoi, expresiile superioare pot fi numărate „înmulțirea“ S1 și S1 * la minimum și pentru a obține o matrice inferior triunghiulară, „înmulțirea“ S2 și S2 * pentru maxim și obținerea unei matrice inferior triunghiulară, și în cele din urmă scăzând ultima matrice anterioară. Calculând maximul în el, primim răspunsul.
DMM (Multiplicare matrice distanțată)
Obiectivul este de a calcula distanțele produsului DMM (produs la distanță) C = AB a doua n-dimensional matritsA = a [i, j] și B = b [i, j], ale căror elemente - sunt numere reale.
Esența c [i, j] - mai mică distanță de vârful i al primului strat la partea superioară j în al treilea strat din coloana orientrirovannom aciclic format din trei straturi de noduri. Aceste noduri numerotate 1. n în fiecare strat, iar distanța de la i la j primul strat la al doilea strat - a [i, j] i și al doilea strat al treilea j strat - b [i, j]. Evident, această expresie poate duce cu ușurință pentru a calcula valoarea maximă în loc de cel puțin - aceasta este problema de a găsi cea mai mare tractului.
Omitem rezolvarea acestei probleme în acest articol, ca urmare a faptului că nu este un algoritm pentru calcularea submăsurii maxime. Totuși, observăm că soluția sa prin metoda Tadao Takaoka ia O (n ^ 2 * log n) în timp.
În ceea ce privește algoritmul Tadao Takaoka pentru MSP, se pare că este cel mai rapid algoritm cunoscut în acest moment. Funcționează pentru o perioadă O (n ^ 3 * log (log (n)) / log (n)).
Pentru mai multe informații despre capacitățile de optimizare a compilatorului, consultați Notificarea noastră de optimizare.
Trimiteți-le prietenilor: