Maksimum alt dizi sorunu - Maximum subarray problem

Bir örneğin başlangıç ve bitiş konumlarına göre alt dizilerin nasıl değiştiğinin görselleştirilmesi. Her olası bitişik alt dizi, renkli bir çizgi üzerinde bir nokta ile temsil edilir. Bu noktanın y koordinatı, örneğin toplamını temsil eder. X koordinatı örneğin sonunu temsil eder ve bu renkli çizgi üzerindeki en soldaki nokta örneğin başlangıcını temsil eder. Bu durumda, örneklerin alındığı dizi [2, 3, -1, -20, 5, 10]'dur.

Gelen bilgisayar bilimleri , maksimum toplamı altdizilim problemi , belirli bir tek boyutlu içinde, en büyük toplamı ile bitişik SubArray bulma görevi dizisi [n ... 1] sayıların A. Resmi olarak görev endekslerini bulmaktır ve birlikte böyle toplamı o, ${\görüntüleme stili ben}$ ${\görüntüleme stili j}$ $1\leq i\leq j\leq n$

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

olabildiğince büyüktür. (Sorunun bazı formülasyonları ayrıca boş alt dizinin dikkate alınmasına izin verir; geleneksel olarak, boş alt dizinin tüm değerlerinin toplamı sıfırdır.) A girdi dizisindeki her sayı pozitif, negatif veya sıfır olabilir.

Örneğin, [−2, 1, −3, 4, −1, 2, 1, −5, 4] değerleri dizisi için, en büyük toplamı olan bitişik alt dizi [4, −1, 2, 1]'dir. , toplamı 6 ile.

Bu sorunun bazı özellikleri şunlardır:

Dizi tüm negatif olmayan sayıları içeriyorsa, sorun önemsizdir; bir maksimum alt dizi, dizinin tamamıdır.
Dizi pozitif olmayan tüm sayıları içeriyorsa, çözüm dizinin maksimum değerini (ya da izin veriliyorsa boş alt diziyi) içeren 1 boyutundaki herhangi bir alt dizidir.
Birkaç farklı alt dizi aynı maksimum toplama sahip olabilir.

Bu problem, kaba kuvvet, böl ve yönet, dinamik programlama ve en kısa yollara indirgeme gibi birkaç farklı algoritmik teknik kullanılarak çözülebilir.

Tarih

Maksimum alt dizi problemi, 1977'de Ulf Grenander tarafından sayısallaştırılmış görüntülerdeki kalıpların maksimum olabilirlik tahmini için basitleştirilmiş bir model olarak önerildi .

Grenander, iki boyutlu gerçek sayılar dizisinde maksimum toplamı olan dikdörtgen bir alt dizi bulmaya çalışıyordu. İki boyutlu problem için bir kaba kuvvet algoritması O ( n ⁶ ) zamanında çalışır; Bu aşırı derecede yavaş olduğu için, Grenander tek boyutlu problemin yapısını anlamak için önerdi. Grenander çözer tek boyutlu bir sorun olduğu bir algoritma elde edilen O ( n, ² ) süresi, çalışma süresi kaba kuvvet iyileştirilmesi , O ( n, ³ ). Ne zaman Michael Shamos sorun hakkında duyduğumuz o gecede bir icat O ( n log n ) böl ve fethet algoritması bunun için. Kısa bir süre sonra Shamos , bir dakika içinde mümkün olduğu kadar hızlı bir O ( n )-zaman algoritması tasarlayan Jay Kadane'nin katıldığı bir Carnegie Mellon Üniversitesi seminerinde tek boyutlu problemi ve tarihini anlattı . 1982'de David Gries , Dijkstra'nın "standart stratejisini" uygulayarak aynı O ( n )-zaman algoritmasını elde etti ; 1989'da Richard Bird , Bird-Meertens formalizmini kullanarak kaba kuvvet algoritmasının tamamen cebirsel manipülasyonuyla bunu türetmiştir .

Grenander'ın iki boyutlu genellemesi, Kadane'nin algoritmasını bir alt program olarak kullanarak veya böl ve yönet yaklaşımıyla O( n ³ ) zamanında çözülebilir . Uzaklık matrisi çarpımına dayalı biraz daha hızlı algoritmalar Tamaki & Tokuyama (1998) ve Takaoka (2002) tarafından önerilmiştir . Önemli ölçüde daha hızlı bir algoritma olmadığına dair bazı kanıtlar var; Herhangi bir ε>0 için O( n ^3−ε ) zamanında iki boyutlu maksimum alt dizi problemini çözen bir algoritma , tüm çiftler en kısa yol problemi için benzer şekilde hızlı bir algoritma anlamına gelir .

Uygulamalar

Genomik dizi analizi ve bilgisayarla görme gibi birçok alanda maksimum alt dizi sorunu ortaya çıkmaktadır .

Genomik dizi analizi, protein dizilerinin önemli biyolojik bölümlerini tanımlamak için maksimum alt dizi algoritmalarını kullanır. Bu problemler, korunan segmentleri, GC açısından zengin bölgeleri, tandem tekrarlarını, düşük karmaşıklığa sahip filtreyi, DNA bağlama alanlarını ve yüksek yüklü bölgeleri içerir.

Gelen bilgisayar vizyonu , maksimum-altdizilim algoritmalar bir görüntünün en parlak alanını tespit etmek için bitmap görüntülerde kullanılır.

Kadane'nin algoritması

Boş alt diziler kabul edildi

Örnek çalıştırma
Yukarıdaki örnek dizide Kadane'nin algoritmasının yürütülmesi . Mavi : en büyük toplamı i ile biten alt dizi ; yeşil : şimdiye kadar karşılaşılan en büyük toplamlı alt dizi; küçük harf boş bir diziyi belirtir; i değişkeni Python kodunda örtük olarak bırakılır.

Kadane'nin orijinal algoritması, boş alt diziler kabul edildiğinde sorunlu versiyonu çözer. Verilen diziyi soldan sağa tarar . Gelen inci adımda, bu büyük toplamı biten de sahip SubArray hesaplar ; bu toplam değişkende tutulur . Ayrıca, herhangi bir yerde en büyük toplamı olan alt diziyi hesaplar, değişkende korunur ve şimdiye kadar görülen tüm değerlerin maksimumu olarak kolayca elde edilir , bkz. algoritmanın 7. satırı. $A[1\ldots n]$ ${\görüntüleme stili j}$ ${\görüntüleme stili j}$ current_sum ${\ Displaystyle A[1\ldots j]}$ best_sumcurrent_sum

Bir döngü değişmezi olarak , inci adımda, eski değeri tüm toplamın maksimumunu tutar . Bu nedenle, toplamın tamamı üzerinde maksimumdur . İkinci maksimumu durumu da kapsayacak şekilde genişletmek için boş alt diziyi de dikkate almak yeterlidir . Bu, 6. satırda , bundan sonra tüm toplam üzerinde maksimumu tutan yeni değer olarak atanarak yapılır . ${\görüntüleme stili j}$ current_sum $i\in \{1,\ldots ,j\}$ $A[i]+\cdots +A[j-1]$ current_sum ${\görüntüleme stili +A[j]}$ $i\in \{1,\ldots ,j\}$ $A[i]+\cdots +A[j]$ ${\görüntüleme stili i=j+1}$ $A[j+1\;\ldots \;j]$ ${\görüntüleme stili\maks(0,}$ current_sum ${\görüntüleme stili +A[j])}$ current_sum $i\in \{1,\ldots ,j+1\}$ $A[i]+\cdots +A[j]$

Böylece sorun, burada Python'da ifade edilen aşağıdaki kodla çözülebilir :

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

Algoritmanın bu sürümü, giriş pozitif öğe içermiyorsa (girişin boş olduğu zamanlar dahil) 0 döndürür.

Boş alt diziler kabul edilmez

Boş Altdizilim izin vermeyen bir sorun varyantı için, best_sumdöngü için yerine ve aynı zamanda negatif sonsuzluğa başlatılması gerektiği current_sumşekilde güncellenmelidir max(x, current_sum + x). Bu durumda, girdi pozitif eleman içermiyorsa, döndürülen değer en büyük elemanın değeridir (yani 0'a en yakın değer) veya girdi boşsa negatif sonsuzdur.

En iyi alt dizinin konumunu hesaplama

Algoritma, maksimum alt dizinin başlangıç ve bitiş endekslerini de takip edecek şekilde değiştirilebilir:

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

Python'da diziler 0'dan başlayarak indekslenir ve bitiş indeksi tipik olarak hariç tutulur, böylece [-11, 22, 33, -44] dizisindeki [22, 33] alt dizisi indeks 1'de başlar ve indekste biter. 3.

karmaşıklık

Bu algoritmanın optimal altyapıları kullanma şeklinden dolayı (her pozisyonda biten maksimum alt dizi, ilgili ancak daha küçük ve örtüşen bir alt problemden basit bir şekilde hesaplanır: önceki pozisyonda biten maksimum alt dizi), bu algoritma basit/ önemsiz dinamik programlama örneği .

Kadane algoritmasının çalışma zamanı karmaşıklığı . ${\görüntüleme stili O(n)}$

genellemeler

Daha yüksek boyutlu diziler için benzer problemler ortaya konabilir, ancak çözümleri daha karmaşıktır; bakınız, örneğin, Takaoka (2002) . Brodal ve Jørgensen (2007) , tek boyutlu bir dizideki en büyük k alt dizi toplamlarının optimal zaman sınırında nasıl bulunacağını gösterdi . ${\görüntüleme stili O(n+k)}$

Maksimum toplam k - ayrık alt diziler de optimal zaman sınırında hesaplanabilir . ${\görüntüleme stili O(n+k)}$

Ayrıca bakınız

Alt küme toplamı sorunu

Notlar

Referanslar

Backurs, Arturs; Dikkala, Nişantaşı; Tzamos, Christos (2016), "Maksimum Ağırlık Dikdörtgenleri için Sıkı Sertlik Sonuçları", Proc. 43. Uluslararası Otomatlar, Diller ve Programlama Kolokyumu : 81:1–81:13, doi : 10.4230/LIPIcs.ICALP.2016.81 , S2CID 12720136
Bae, Sung Eun (2007), Sıralı ve Paralel Algoritmalar for the Generalized Maximum Subarray Problem (PDF) (Doktora tezi), University of Canterbury, S2CID 2681670 , orijinalinden arşivlendi (PDF) 2017-10-26.
Bengtsson, Fredrik; Chen, Jingsen (2007), Maksimum puanlama segmentlerini optimal olarak hesaplama (PDF) (Araştırma raporu), Luleå Teknoloji Üniversitesi
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 (Mayıs 1989), Programming Pearls (2. baskı), Reading, MA: Addison Wesley, ISBN 0-201-10331-1
Bird, Richard S. (1989), "Program Hesaplaması için Cebirsel Kimlikler" (PDF) , The Computer Journal , 32 (2): 122–126 , doi : 10.1093/comjnl/32.2.122
Brodal, Gerth Stolting; Jørgensen, Allan Grønlund (2007), " k maksimal toplamlar problemi için doğrusal bir zaman algoritması ", Bilgisayar Biliminin Matematiksel Temelleri , Bilgisayar Biliminde Ders Notları, 4708 , Springer-Verlag, s. 442–453, doi : 10.1007/978 -3-540-74456-6_40.
Gries, David (1982), "Döngü Değişmezleri ve Döngüler Geliştirmek için Standart Strateji Üzerine Bir Not" (PDF) , Bilgisayar Programlama Bilimi , 2 (3): 207–241, doi : 10.1016/0167-6423(83)90015 -1 , hdl : 1813/6370
Takaoka, Tadao (2002), "Mesafe matris çarpımı ile maksimum alt dizi problemi için verimli algoritmalar", Electronic Notes in Theoretical Computer Science , 61 : 191–200, doi : 10.1016/S1571-0661(04)00313-5.
Tamaki, Hisao; Tokuyama, Takeshi (1998), "Matris Çarpımına Dayalı Maksimum Alt Dizi Problemi için Algoritmalar" , Ayrık Algoritmalar (SODA) 9. Sempozyumu Bildiriler Kitabı : 446–452 , alındı 17 Kasım 2018

Dış bağlantılar

TAN, Lirong. "Maksimum Bitişik Alt Dizi Toplamı Sorunları" (PDF) . Arşivlenmiş orijinal (PDF) 2015-10-10 tarihinde . 2017-10-26 alındı .
Mu, Shin-Cheng (2010). "Maksimum Segment Toplamı Problemi: Kökeni ve Bir Türevi" .
"Maksimum Alt Dizi Problemi Üzerine Notlar" . 2012.
www.algoritmist.com
alexeigor.wikidot.com
Rosetta Kodundaki en büyük müteakip toplam sorunu
Kadane'nin Algoritması üzerinde geeksforgeeks sayfası

Languages

In other projects