Problemet med att hitta den största ökande efterföljden
Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 8 februari 2015; kontroller kräver 7 redigeringar .Uppgiften att hitta den största ökande undersekvensen är att hitta den längst ökande undersekvensen i en given sekvens av element.
Förklaring av problemet
Observera att en delsekvens kanske inte är en delsträng (det vill säga att dess element inte nödvändigtvis är konsekutiva i den ursprungliga sekvensen). Formellt, för en sträng x med längden n , är det nödvändigt att hitta det maximala antalet l och motsvarande ökande sekvens av index , så att . Den största ökande undersekvensen har tillämpningar inom fysik, matematik, grupprepresentationsteori, slumpmatristeori. I det allmänna fallet är lösningen av detta problem känd i tiden n log n i värsta fall [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)
Relaterade algoritmer
- Det största ökande subsekvensproblemet liknar problemet med att hitta den största gemensamma subsekvensen som har en kvadratisk dynamisk lösning.
- I det speciella fallet där strängen är en permutation av 1..n, har problemet en lösning i n log log n [2] med hjälp av van Emde Boas trees .
- När man använder ett träd byggt för element i alfabetet är det möjligt att lösa problemet i O(n log A), där A är alfabetets kardinalitet, vilket bestäms i förväg. När det implementeras av balanserade träd är det inte nödvändigt att ange A i förväg. Av uppenbara skäl är A begränsat till strängens längd.
- Det är också möjligt att reducera problemet till att hitta den längsta vägen i en riktad acyklisk graf genom att ange kanter mellan ökande element. Även om beräkningen av den längsta vägen kommer att ta linjär tid i antalet kanter, kan den i värsta fall vara kvadratisk på strängens längd.
Ett exempel på en effektiv algoritm
Låt oss presentera en algoritm för att lösa problemet som körs i O( n log n ).
För sträng x kommer vi att lagra arrayerna M och P med längden n . M[i] innehåller indexet för det minsta av de sista elementen av ökande delsekvenser x n j av längden i , , som finns i detta steg. P[i] lagrar indexet för det föregående tecknet för den längsta stigande undersekvensen som slutar i den i:te positionen. Vid varje steg kommer vi att lagra den nuvarande maximala längden på undersekvensen och motsvarande index för det sista tecknet, och komma ihåg att behålla egenskaperna för arrayer. Ett steg är en övergång till nästa element i strängen, varje övergång kräver inte mer än logaritmen av tid (binär sökning på arrayen 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
Efter exekvering av algoritmen är L uppenbarligen längden på den önskade undersekvensen, och själva elementen kan erhållas genom att expandera P rekursivt från indexelementet.
Anteckningar
- ↑ Schensted, C. (1961). "Längsta ökande och minskande delsekvenser". Canadian Journal of Mathematics 13: 179-191.
- ↑ Hunt, James W. och Szymanski, Thomas G. A Fast Algorithm for Computing Longest Common Subsequences // Commun . ACM. - ACM, 1977. - Vol. 20 , nej. 5 . - S. 350--353 . — ISSN 0001-0782 .