Problemă maximă de subarray - Maximum subarray problem

Vizualizarea modului în care sub-tablourile se schimbă pe baza pozițiilor de început și de sfârșit ale unui eșantion. Fiecare posibilă sub-matrice contiguă este reprezentată de un punct pe o linie colorată. Coordonata y a acelui punct reprezintă suma eșantionului. Coordonata sa x reprezintă sfârșitul eșantionului, iar punctul cel mai la stânga de pe acea linie colorată reprezintă începutul eșantionului. În acest caz, matricea din care sunt prelevate probele este [2, 3, -1, -20, 5, 10].

În informatică , problema subarrayului sumă maximă este sarcina de a găsi o subarray contiguă cu cea mai mare sumă, într-un anumit tablou unidimensional A [1 ... n] de numere. În mod formal, sarcina este de a găsi indici și cu , astfel încât suma ${\ displaystyle i}$ ${\ displaystyle j}$ ${\ displaystyle 1 \ leq i \ leq j \ leq n}$

{\ displaystyle \ sum _ {x = i} ^ {j} A [x]}

este cât mai mare posibil. (Unele formulări ale problemei permit, de asemenea, să fie luată în considerare subarrayul gol; prin convenție, suma tuturor valorilor subarrayului gol este zero.) Fiecare număr din matricea de intrare A ar putea fi pozitiv, negativ sau zero.

De exemplu, pentru matricea de valori [−2, 1, −3, 4, −1, 2, 1, −5, 4], subarrayul contigu cu cea mai mare sumă este [4, −1, 2, 1] , cu suma 6.

Unele proprietăți ale acestei probleme sunt:

Dacă tabloul conține toate numerele care nu sunt negative, atunci problema este banală; un subarray maxim este întregul tablou.
Dacă matricea conține toate numerele nepozitive, atunci o soluție este orice subarray de dimensiunea 1 care conține valoarea maximă a matricei (sau subarrayul gol, dacă este permis).
Mai multe sub-tablouri diferite pot avea aceeași sumă maximă.

Această problemă poate fi rezolvată folosind mai multe tehnici algoritmice diferite, incluzând forța brută, divizarea și cucerirea, programarea dinamică și reducerea la cele mai scurte căi.

Istorie

Problema maximă a subarrayului a fost propusă de Ulf Grenander în 1977 ca model simplificat pentru estimarea maximă a probabilității modelelor din imaginile digitalizate.

Grenander căuta să găsească o sub-matrice dreptunghiulară cu suma maximă, într-o matrice bidimensională de numere reale. Un algoritm de forță brută pentru problema bidimensională rulează în timpul O ( n ⁶ ); deoarece acest lucru era prohibitiv de lent, Grenander a propus problema unidimensională pentru a obține o perspectivă asupra structurii sale. Grenander a derivat un algoritm care rezolvă problema unidimensională în timpul O ( n ² ), îmbunătățind timpul de funcționare a forței brute a lui O ( n ³ ). Când Michael Shamos a auzit de problemă, el a conceput peste noapte un algoritm O ( n log n ) de divizare și cucerire pentru aceasta. Curând după aceea, Shamos a descris problema unidimensională și istoria ei la un seminar al Universității Carnegie Mellon la care a participat Jay Kadane , care a proiectat într-un minut un algoritm de timp O ( n ), care este cât mai rapid posibil. În 1982, David Gries a obținut același algoritm de timp O ( n ) prin aplicarea „strategiei standard” a lui Dijkstra ; în 1989, Richard Bird a derivat-o prin manipularea pur algebrică a algoritmului forței brute folosind formalismul Bird-Meertens .

Generalizarea bidimensională a lui Grenander poate fi rezolvată în timp O ( n ³ ) fie utilizând algoritmul lui Kadane ca subrutină, fie printr-o abordare divizare și cucerire. Algoritmi puțin mai rapizi bazați pe multiplicarea matricii la distanță au fost propuși de Tamaki & Tokuyama (1998) și de Takaoka (2002) . Există unele dovezi că nu există un algoritm semnificativ mai rapid; un algoritm care rezolvă problema subdimensională maximă bidimensională în timpul O ( n ^{3 − ε} ), pentru orice ε> 0, ar implica un algoritm rapid similar pentru problema celor mai scurte căi din toate perechile .

Aplicații

Probleme maxime de subarray apar în multe domenii, cum ar fi analiza secvenței genomice și viziunea computerizată .

Analiza secvenței genomice utilizează algoritmi de subarray maxim pentru a identifica segmente biologice importante ale secvențelor proteice. Aceste probleme includ segmente conservate, regiuni bogate în GC, repetări în tandem, filtru cu complexitate redusă, domenii de legare a ADN și regiuni cu sarcină mare.

În viziunea computerizată , algoritmii de sub-matrice maximă sunt utilizați pe imaginile bitmap pentru a detecta cea mai strălucitoare zonă dintr-o imagine.

Algoritmul lui Kadane

S-au admis subgrupuri goale

Exemplu de rulare
Executarea algoritmului lui Kadane pe exemplul de mai sus . Albastru : subarray cu cea mai mare sumă care se termină la i ; verde : subarray cu cea mai mare sumă întâlnită până acum; o literă minusculă indică o matrice goală; variabila i este lăsată implicită în codul Python.

Algoritmul original al lui Kadane rezolvă versiunea problemă atunci când sunt admise subarrays goale. Scanează matricea dată de la stânga la dreapta. În pasul al treilea, calculează subarrayul cu cea mai mare sumă care se termină la ; această sumă este menținută în variabilă . Mai mult, calculează subarrayul cu cea mai mare sumă de oriunde , menținută în variabilă și ușor de obținut ca maximul tuturor valorilor văzute până acum, cf. linia 7 a algoritmului. ${\ displaystyle A [1 \ ldots n]}$ ${\ displaystyle j}$ ${\ displaystyle j}$ current_sum ${\ displaystyle A [1 \ ldots j]}$ best_sumcurrent_sum

Ca invariant de buclă , în pasul al treilea, vechea valoare a deține maximul pe toată suma . Prin urmare, este maximul peste toată suma . Pentru a extinde ultimul maxim pentru a acoperi și cazul , este suficient să se ia în considerare și subgabaritul gol . Acest lucru se face în linia 6 prin atribuirea ca nouă valoare a , care, după aceea, deține maximul asupra întregii sume . ${\ displaystyle j}$ current_sum ${\ displaystyle i \ in \ {1, \ ldots, j \}}$ ${\ displaystyle A [i] + \ cdots + A [j-1]}$ current_sum ${\ displaystyle + A [j]}$ ${\ displaystyle i \ in \ {1, \ ldots, j \}}$ ${\ displaystyle A [i] + \ cdots + A [j]}$ ${\ displaystyle i = j + 1}$ ${\ displaystyle A [j + 1 \; \ ldots \; j]}$ ${\ displaystyle \ max (0,}$ current_sum ${\ displaystyle + A [j])}$ current_sum ${\ displaystyle i \ in \ {1, \ ldots, j + 1 \}}$ ${\ displaystyle A [i] + \ cdots + A [j]}$

Astfel, problema poate fi rezolvată cu următorul cod, exprimat aici în Python :

def max_subarray(numbers):
    """Find the largest sum of any contiguous subarray."""
    best_sum = 0  # or: float('-inf')
    current_sum = 0
    for x in numbers:
        current_sum = max(0, current_sum + x)
        best_sum = max(best_sum, current_sum)
    return best_sum

Această versiune a algoritmului va returna 0 dacă intrarea nu conține elemente pozitive (inclusiv când intrarea este goală).

Nu sunt admise submatricii goale

Pentru varianta problemei care nu permite subarrays goale, best_sumtrebuie inițializat la infinit negativa si , de asemenea , în buclă current_sumtrebuie actualizate max(x, current_sum + x). În acest caz, dacă intrarea nu conține niciun element pozitiv, valoarea returnată este cea a celui mai mare element (adică valoarea cea mai apropiată de 0) sau infinit negativ dacă intrarea a fost goală.

Calculând cea mai bună poziție subarray

Algoritmul poate fi modificat pentru a urmări și indicii de început și de sfârșit ai subarrayului maxim:

def max_subarray(numbers):
    """Find a contiguous subarray with the largest sum."""
    best_sum = 0  # or: float('-inf')
    best_start = best_end = 0  # or: None
    current_sum = 0
    for current_end, x in enumerate(numbers):
        if current_sum <= 0:
            # Start a new sequence at the current element
            current_start = current_end
            current_sum = x
        else:
            # Extend the existing sequence with the current element
            current_sum += x

        if current_sum > best_sum:
            best_sum = current_sum
            best_start = current_start
            best_end = current_end + 1  # the +1 is to make 'best_end' exclusive

    return best_sum, best_start, best_end

În Python, matricile sunt indexate începând de la 0, iar indexul final este de obicei exclus, astfel încât subarray-ul [22, 33] din matricea [-11, 22, 33, -44] ar începe la indexul 1 și se va termina la index 3.

Complexitate

Datorită modului în care acest algoritm folosește substructuri optime (subarrayul maxim care se termină la fiecare poziție este calculat într-un mod simplu dintr-o subproblemă legată, dar mai mică și suprapusă: subarrayul maxim care se termină la poziția anterioară) acest algoritm poate fi văzut ca o simplă / exemplu banal de programare dinamică .

Complexitatea în timp de rulare a algoritmului lui Kadane este . ${\ displaystyle O (n)}$

Generalizări

Probleme similare pot fi puse pentru tablouri cu dimensiuni superioare, dar soluțiile lor sunt mai complicate; vezi, de exemplu, Takaoka (2002) . Brodal și Jørgensen (2007) au arătat cum să găsim cele mai mari sume subarray k într-o matrice unidimensională, în limita optimă de timp . ${\ displaystyle O (n + k)}$

Suma maximă k- sub-matrice disjuncte poate fi, de asemenea, calculată în limita optimă de timp . ${\ displaystyle O (n + k)}$

Vezi si

Problemă sumă subset

Note

Referințe

Backurs, Arturs; Dikkala, Nishanth; Tzamos, Christos (2016), „Rezultate strânse de duritate pentru dreptunghiuri cu greutate maximă”, Proc. 43 Colocviu internațional despre automate, limbaje și programare : 81: 1–81: 13, doi : 10.4230 / LIPIcs.ICALP.2016.81 , S2CID 12720136
Bae, Sung Eun (2007), Algoritmi secvențiali și paraleli pentru problema maximă generalizată a subarrayului (PDF) (teză de doctorat), Universitatea din Canterbury, S2CID 2681670 , arhivat din original (PDF) în data de 26-10-2017.
Bengtsson, Fredrik; Chen, Jingsen (2007), Calcularea optimă a segmentelor de scor maxim (PDF) (Raport de cercetare), Universitatea de Tehnologie Luleå
Bentley, Jon (1984), "Perle de programare: tehnici de proiectare a algoritmilor", Communications of the ACM , 27 (9): 865-873, doi : 10.1145 / 358234.381162 , S2CID 207565329
Bentley, Jon (mai 1989), Perle de programare (ediția a doua?), Reading, MA: Addison Wesley, ISBN 0-201-10331-1
Bird, Richard S. (1989), „Algebraic Identities for Program Calculation” (PDF) , The Computer Journal , 32 (2): 122–126, doi : 10.1093 / comjnl / 32.2.122
Brodal, Gerth Stølting; Jørgensen, Allan Grønlund (2007), "A linear time algorithm for the k maximal sums problem", Mathematical Foundations of Computer Science , Lecture Notes in Computer Science, 4708 , Springer-Verlag, pp. 442–453, doi : 10.1007 / 978 -3-540-74456-6_40.
Gries, David (1982), „A Note on the Standard Strategy for Developing Loop Invariants and Loops” (PDF) , Science of Computer Programming , 2 (3): 207–241, doi : 10.1016 / 0167-6423 (83) 90015 -1 , hdl : 1813/6370
Takaoka, Tadao (2002), "Algoritmi eficienți pentru problema maximă a subarray-ului prin multiplicarea matricii la distanță", Electronic Notes in Theoretical Computer Science , 61 : 191-200, doi : 10.1016 / S1571-0661 (04) 00313-5.
Tamaki, Hisao; Tokuyama, Takeshi (1998), „Algoritmi pentru problema maximă a subarray-ului bazat pe multiplicarea matricei” , Proceedings of the 9th Simposium on Discrete Algorithms (SODA) : 446–452 , recuperat 17 noiembrie 2018

linkuri externe

TAN, Lirong. „Probleme maxime adiacente de sumă subarray” (PDF) . Arhivat din original (PDF) la 10-10-2015 . Adus 26-10-2017 .
Mu, Shin-Cheng (2010). „Problema sumei segmentului maxim: originea și o derivare” .
"Note privind problema maximă a subarrayului" . 2012.
www.algorithmist.com
alexeigor.wikidot.com
cea mai mare problemă de sumă subsecvențială din Codul Rosetta
pagina geeksforgeeks din algoritmul lui Kadane

Languages

In other projects