Problém najít největší rostoucí subsekvenci
Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 8. února 2015; kontroly vyžadují 7 úprav .Úkolem najít největší rostoucí podposloupnost je najít nejdelší rostoucí podposloupnost v dané posloupnosti prvků.
Prohlášení o problému
Všimněte si, že podsekvence nemusí být podřetězcem (to znamená, že její prvky nemusí být nutně po sobě jdoucí v původní sekvenci). Formálně je pro řetězec x délky n nutné najít maximální číslo l a odpovídající rostoucí posloupnost indexů , takže . Největší rostoucí podsekvence má aplikace ve fyzice, matematice, teorii reprezentace grup, teorii náhodných matic. V obecném případě je řešení této úlohy známo v čase n log n v nejhorším případě [1] .
![x[i_{{k}}]<x[i_{{k+1}}]\,\forall {k}\,{\mathcal {2}}{\,1\,..\,l-1 }](https://wikimedia.org/api/rest_v1/media/math/render/svg/f09a36199ec2e2a93940afacd7eab6439005ba3b)
Související algoritmy
- Problém největší rostoucí podposloupnosti je podobný problému hledání největší společné podposloupnosti , která má kvadratické dynamické řešení.
- V konkrétním případě, kdy je řetězec permutací 1..n, má problém řešení v n log log n [2] pomocí van Emde Boasových stromů .
- Při použití stromu sestaveného pro prvky abecedy je možné problém řešit v O(n log A), kde A je mohutnost abecedy, která je předem určena. Při implementaci pomocí vyvážených stromů není nutné specifikovat A předem. Z pochopitelných důvodů je A omezeno na délku řetězce.
- Je také možné redukovat problém na nalezení nejdelší cesty v orientovaném acyklickém grafu zadáním hran mezi rostoucími prvky. Výpočet nejdelší dráhy sice zabere lineární čas v počtu hran, ale v nejhorším případě může být kvadratický k délce provázku.
Příklad efektivního algoritmu
Ukažme si algoritmus pro řešení problému, který běží v O( n log n ).
Pro řetězec x uložíme pole M a P délky n . M[i] obsahuje index nejmenšího z posledních prvků rostoucích dílčích sekvencí x n j délky i , nalezených v tomto kroku. P[i] ukládá index předchozího znaku pro nejdelší vzestupnou podsekvenci končící na i-té pozici. V každém kroku uložíme aktuální maximální délku podsekvence a odpovídající index konečného znaku, přičemž nezapomeneme zachovat vlastnosti polí. Krok je přechod na další prvek řetězce, každý přechod nebude vyžadovat více než logaritmus času (binární vyhledávání na poli M ).
![({\mathcal {8}}j\,{\mathcal {2}}\,1\,..\,i:x[n_{{j}}]\leq \,M[i])](https://wikimedia.org/api/rest_v1/media/math/render/svg/81c7f83d08b0132275b77d92671f36eb2bab8594)
P = array of length N M = array of length N + 1 L = 0 for i in range 0 to N-1: lo = 1 hi = L while lo ≤ hi: mid = ceil((lo+hi)/2) if X[M[mid]] < X[i]: lo = mid+1 else: hi = mid-1 newL = lo P[i] = M[newL-1] M[newL] = i if newL > L: L = newL S = array of length L k = M[L] for i in range L-1 to 0: S[i] = X[k] k = P[k] return S
Je zřejmé, že po provedení algoritmu je L délka požadované podsekvence a samotné prvky lze získat expanzí P rekurzivně z prvku indexu.
Poznámky
- ↑ Schensted, C. (1961). „Nejdelší rostoucí a klesající dílčí sekvence“. Canadian Journal of Mathematics 13: 179-191.
- ↑ Hunt, James W. a Szymanski, Thomas G. Rychlý algoritmus pro výpočet nejdelších společných sekvencí // Commun . ACM. - ACM, 1977. - Sv. 20 , č. 5 . - str. 350--353 . — ISSN 0001-0782 .