Problema găsirii celei mai mari subsecvențe crescătoare
Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 8 februarie 2015; verificările necesită 7 modificări .Sarcina de a găsi cea mai mare subsecvență crescătoare este de a găsi cea mai lungă subsecvență crescătoare într-o anumită secvență de elemente.
Enunțul problemei
Rețineți că o subsecvență poate să nu fie un subșir (adică elementele sale nu sunt neapărat consecutive în secvența originală). Formal, pentru un șir x de lungime n , este necesar să se găsească numărul maxim l și secvența crescătoare corespunzătoare de indici , astfel încât . Cea mai mare subsecvență în creștere are aplicații în fizică, matematică, teoria reprezentării grupurilor, teoria matricei aleatoare. În cazul general, soluția acestei probleme este cunoscută în timp n log n în cel mai rău caz [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)
Algoritmi înrudiți
- Cea mai mare problemă a subsecvenței crescătoare este similară cu problema găsirii celei mai mari subsecvențe comune care are o soluție dinamică pătratică.
- În cazul particular în care șirul este o permutare a lui 1..n, problema are o soluție în n log log n [2] folosind arbori van Emde Boas .
- Când se folosește un arbore construit pentru elemente ale alfabetului, este posibil să se rezolve problema în O(n log A), unde A este cardinalitatea alfabetului, care este determinată în prealabil. Când este implementat de arbori echilibrați , nu este necesar să specificați A dinainte. Din motive evidente, A este limitat la lungimea șirului.
- De asemenea, este posibil să se reducă problema la găsirea celei mai lungi căi într-un graf aciclic direcționat prin specificarea muchiilor dintre elementele crescătoare. Deși calculul celui mai lung drum va dura timp liniar în numărul de muchii, în cel mai rău caz poate fi pătratic al lungimii șirului.
Un exemplu de algoritm eficient
Să prezentăm un algoritm pentru rezolvarea problemei care rulează în O( n log n ).
Pentru șirul x , vom stoca tablourile M și P de lungime n . M[i] conține indicele celui mai mic dintre ultimele elemente ale subsecvențelor crescătoare x n j de lungime i , , găsit la acest pas. P[i] stochează indexul caracterului precedent pentru cea mai lungă subsecvență ascendentă care se termină în poziția i-a. La fiecare pas, vom stoca lungimea maximă curentă a subsecvenței și indexul corespunzător al caracterului final, amintindu-ne să menținem proprietățile tablourilor. Un pas este o tranziție la următorul element al șirului, fiecare tranziție nu va necesita mai mult decât logaritmul timpului (căutare binară pe tabloul 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
Evident, după executarea algoritmului, L este lungimea subsecvenței dorite, iar elementele în sine pot fi obținute prin extinderea recursiv P din elementul index.
Note
- ↑ Schensted, C. (1961). „Cele mai lungi subsecvențe crescătoare și descrescătoare”. Canadian Journal of Mathematics 13: 179-191.
- ↑ Hunt, James W. și Szymanski, Thomas G. A Fast Algorithm for Computing Longest Common Subsequences // Commun . ACM. - ACM, 1977. - Vol. 20 , nr. 5 . - P. 350--353 . — ISSN 0001-0782 .