Suurin osajoukon ongelma - Maximum subarray problem

Visualisointi siitä, miten aliryhmät muuttuvat otoksen alku- ja loppukohtien perusteella. Jokainen mahdollinen viereinen aliryhmä on piste värillisellä viivalla. Pisteen y-koordinaatti edustaa otoksen summaa. Sen x-koordinaatti edustaa näytteen loppua ja vasemmanpuoleisin piste värillisellä viivalla edustaa näytteen alkua. Tässä tapauksessa taulukko, josta näytteet otetaan, on [2, 3, -1, -20, 5, 10].

In Computer Science , The enimmäismäärä Alijärjestelyn ongelma on tehtävänä on löytää vierekkäisiä alaryhmän, jolla on suurin summa, tietyssä yksiulotteisen taulukon A [1 ... n] numeroita. Muodollisesti tehtävä on löytää indeksejä ja joissa siten, että summa ${\ displaystyle i}$ ${\ displaystyle j}$ ${\ displaystyle 1 \ leq i \ leq j \ leq n}$

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

on mahdollisimman suuri. (Jotkut ongelman muotoilut mahdollistavat myös tyhjän aliryhmän huomioimisen; sopimuksen mukaan tyhjän aliryhmän kaikkien arvojen summa on nolla.) Syöttömatriisin A jokainen numero voi olla positiivinen, negatiivinen tai nolla.

Esimerkiksi arvotaulukolle [−2, 1, −3, 4, -1, 2, 1, −5, 4] vierekkäinen alirivi, jolla on suurin summa, on [4, -1, 2, 1] , summa 6.

Jotkut tämän ongelman ominaisuudet ovat:

Jos taulukko sisältää kaikki ei-negatiiviset luvut, ongelma on triviaali; suurin alirivi on koko ryhmä.
Jos taulukko sisältää kaikki ei-positiiviset luvut, ratkaisu on mikä tahansa koon 1 aliryhmä, joka sisältää taulukon maksimiarvon (tai tyhjä aliryhmä, jos se on sallittu).
Useilla eri aliryhmillä voi olla sama enimmäissumma.

Tämä ongelma voidaan ratkaista käyttämällä useita erilaisia algoritmisia tekniikoita, kuten raakaa voimaa, jakamista ja valloitusta, dynaamista ohjelmointia ja lyhentämistä lyhyimmille poluille.

Historia

Ulf Grenander ehdotti vuonna 1977 enimmäisaliryhmäongelmaa yksinkertaistettuna mallina digitaalisten kuvien kuvioiden maksimaalisen todennäköisyyden arvioimiseksi.

Grenander halusi löytää suorakulmaisen alirivin, jossa oli suurin summa, kaksiulotteisesta reaalilukutaulukosta. Raa'an voiman algoritmi kaksiulotteiselle ongelmalle suoritetaan O ( n ⁶ ): ssa; koska tämä oli kohtuuttoman hidasta, Grenander ehdotti yksiulotteista ongelmaa saadakseen käsityksen sen rakenteesta. Grenander johti algoritmin, joka ratkaisee yksiulotteisen ongelman O ( n ² ): ssa, mikä parantaa O ( n ³ ): n raa'an voiman käyttöaikaa . Kun Michael Shamos kuuli ongelmasta, hän kehitti yön aikana sille O ( n log n ) jakamis- ja valloitusalgoritmin . Pian tämän jälkeen Shamos kuvasi yksiulotteista ongelmaa ja sen historiaa Carnegie Mellonin yliopiston seminaarissa, johon osallistui Jay Kadane , joka suunnitteli minuutissa O ( n ) -aikaisen algoritmin, joka on mahdollisimman nopea. Vuonna 1982 David Gries sai saman O ( n ) -ajan algoritmin soveltamalla Dijkstran "standardistrategiaa"; Vuonna 1989 Richard Bird johdatti sen puhtaasti algebrallisella manipuloinnilla raa'an voiman algoritmilla käyttäen Bird-Meertensin formalismia .

Grenanderin kaksiulotteinen yleistys voidaan ratkaista O ( n ³ ) -ajalla joko käyttämällä Kadanen algoritmia aliohjelmana tai jakamalla ja valloita -lähestymistavan avulla. Tamaki & Tokuyama (1998) ja Takaoka (2002) ovat ehdottaneet hieman nopeampia etäisyysmatriisin kertolaskuun perustuvia algoritmeja . On olemassa joitakin todisteita siitä, ettei ole olemassa merkittävästi nopeampaa algoritmia; algoritmi, joka ratkaisee kaksiulotteisen enimmäisaliryhmän ongelman O ( n ^{3 ε} ) -ajalla, missä tahansa ε> 0, tarkoittaisi yhtä nopeaa algoritmia kaikkien parien lyhyimpien polkujen ongelmaan.

Sovellukset

Suurimmat osajoukko -ongelmat syntyvät monilla aloilla, kuten genomisen sekvenssin analyysi ja tietokoneen visio .

Genomisessa sekvenssianalyysissä käytetään enimmäisaliryhmäalgoritmeja proteiinisekvenssien tärkeiden biologisten segmenttien tunnistamiseksi. Näihin ongelmiin kuuluvat konservoidut segmentit, GC-rikkaat alueet, tandem-toistot, matalan kompleksisuuden suodatin, DNA: ta sitovat domeenit ja korkean varauksen alueet.

Vuonna konenäkö , maksimi-alijärjestelylle algoritmeja käytetään bittikarttakuvien havaita kirkkain alue kuvassa.

Kadanen algoritmi

Tyhjät alaryhmät hyväksyttiin

Esimerkki ajo
Kadanen algoritmin suorittaminen yllä olevassa esimerkkitaulukossa. Sininen : alirivi, jonka suurin summa päättyy kohtaan i ; vihreä : aliryhmä, jolla on suurin tähän mennessä havaittu summa; pieni kirjain osoittaa tyhjää matriisia; muuttuja i jätetään implisiittiseksi Python -koodissa.

Kadanen alkuperäinen algoritmi ratkaisee ongelmaversion, kun tyhjät alisarjat hyväksytään. Se skannaa annetun taulukon vasemmalta oikealle. Kolmannessa vaiheessa se laskee alirivin, jonka suurin summa päättyy kohtaan ; tämä summa pysyy muuttujana . Lisäksi se laskee alirivin, jolla on suurin summa kaikkialla , muuttujana ja helposti saavutettavissa kaikkien tähän mennessä nähtyjen arvojen maksimina , vrt. algoritmin rivi 7. ${\ displaystyle A [1 \ lpistettä n]}$ ${\ displaystyle j}$ ${\ displaystyle j}$ current_sum ${\ displaystyle A [1 \ ldots j]}$ best_sumcurrent_sum

Koska silmukka muuttumaton , että th vaiheessa, vanha arvo omistaa suurimman kaikkien summan . Siksi se on maksimi koko summasta . Jälkimmäisen enimmäismäärän laajentamiseksi kattamaan myös tapaus , riittää, kun otetaan huomioon myös tyhjä aliryhmä . Tämä tehdään rivillä 6 määrittämällä uudeksi arvoksi arvo , joka sen jälkeen pitää maksimissaan koko summan . ${\ 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]}$

Näin ollen ongelma voidaan ratkaista seuraavalla koodilla, joka ilmaistaan täällä Pythonissa :

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

Tämä algoritmin versio palauttaa arvon 0, jos syöte ei sisällä positiivisia elementtejä (myös silloin, kun syöte on tyhjä).

Tyhjiä alaryhmiä ei sallita

Ongelman muunnelmassa, joka ei salli tyhjiä alaryhmiä, best_sumse on alustettava negatiiviseen äärettömyyteen ja myös for -silmukassa current_sumon päivitettävä muodossa max(x, current_sum + x). Siinä tapauksessa, jos syöte ei sisällä positiivista elementtiä, palautettu arvo on suurimman elementin arvo (eli arvo, joka on lähinnä 0) tai negatiivinen ääretön, jos syöte oli tyhjä.

Parhaan aliryhmän sijainnin laskeminen

Algoritmia voidaan muokata myös seuratakseen enimmäisaliryhmän alku- ja loppuindeksejä:

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

Pythonissa taulukot indeksoidaan 0: sta alkaen ja lopetusindeksi jätetään yleensä pois, jotta matriisin [-11, 22, 33, -44] alimatriisi [22, 33] alkaa indeksistä 1 ja päättyy indeksiin 3.

Monimutkaisuus

Koska tämä algoritmi käyttää optimaalisia alarakenteita (jokaisen sijainnin enimmäispääte lasketaan yksinkertaisella tavalla asiaan liittyvästä mutta pienemmästä ja päällekkäisestä alitehtävästä: suurin alirivi päättyy edelliseen paikkaan), tätä algoritmia voidaan pitää yksinkertaisena/ triviaali esimerkki dynaamisesta ohjelmoinnista .

Kadanen algoritmin suoritusaikainen monimutkaisuus on . ${\ displaystyle O (n)}$

Yleistykset

Samankaltaisia ongelmia voi esiintyä korkeamman ulottuvuuden matriiseille, mutta niiden ratkaisut ovat monimutkaisempia; katso esim. Takaoka (2002) . Brodal & Jørgensen (2007) esittivät kuinka löytää k suurimman alirivisumman yksiulotteisesta taulukosta optimaalisella aikarajalla . ${\ displaystyle O (n+k)}$

Suurin summa k -hajautetut aliryhmät voidaan myös laskea optimaalisella aikarajalla . ${\ displaystyle O (n+k)}$

Katso myös

Osajoukon summaongelma

Huomautuksia

Viitteet

Backurs, Arturs; Dikkala, Nishanth; Tzamos, Christos (2016), "Tight Hardness Results for Maximum Weight Rectangles", Proc. 43. kansainvälinen kollokviumi automaateista, kielistä ja ohjelmoinnista : 81: 1–81: 13, doi : 10.4230/LIPIcs.ICALP.2016.81 , S2CID 12720136
Bae, Sung Eun (2007), Sequential and Parallel Algorithms for the Generalized Maximum Subarray Problem (PDF) (väitöskirja), University of Canterbury, S2CID 2681670 , arkistoitu alkuperäisestä (PDF) 26.10.2017.
Bengtsson, Fredrik; Chen, Jingsen (2007), Enimmäispistemääräsegmenttien optimaalinen laskenta (PDF) (Tutkimusraportti), Luulajan teknillinen yliopisto
Bentley, Jon (1984), "Programming Pearls: Algorithm Design Techniques", Communications of the ACM , 27 (9): 865–873, doi : 10.1145/358234.381162 , S2CID 207565329
Bentley, Jon (toukokuu 1989), Programming Pearls (2.? Toim.), 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), "Lineaarinen aika-algoritmi k- maksimiarvojen ongelmaan", Tietotekniikan matemaattiset perusteet, Tietotekniikan luento, 4708 , Springer-Verlag, s. 442–453, doi : 10.1007/978 -3-540-74456-6_40.
Gries, David (1982), "Huomautus silmukkainvarianttien ja silmukoiden kehittämisen standardistrategiasta" (PDF) , Tietokoneohjelmoinnin tiede , 2 (3): 207–241, doi : 10.1016/0167-6423 (83) 90015 -1 , HDL : 1813/6370
Takaoka, Tadao (2002), "Tehokkaita algoritmeja alimatriisin enimmäisongelmalle etäisyysmatriisin kertomalla", Electronic Notes in Theoretical Computer Science , 61 : 191–200, doi : 10.1016/S1571-0661 (04) 00313-5.
Tamaki, Hisao; Tokuyama, Takeshi (1998), "Algorithms for the Maximum Subarray Problem based on Matrix Multiplication" , Proceedings of the 9. Symposium on Discrete Algorithms (SODA) : 446–452 , haettu 17. marraskuuta 2018

Ulkoiset linkit

TAN, Lirong. "Suurin vierekkäisten alirivien summaongelmat" (PDF) . Arkistoitu alkuperäisestä (PDF) 10.10.2015 . Haettu 2017-10-26 .
Mu, Shin-Cheng (2010). "Suurin segmenttisumman ongelma: sen alkuperä ja johdannainen" .
"Huomautuksia enimmäisaliriviongelmasta" . 2012.
www.algorithmist.com
alexeigor.wikidot.com
suurin jälkimmäisen summan ongelma Rosetta -koodissa
geeksforgeeks -sivu Kadanen algoritmissa

Languages

In other projects