Nejdelší rostoucí posloupnost - Longest increasing subsequence

v počítačová věda, nejdelší rostoucí posloupnost problém je najít posloupnost daného sekvence ve kterém jsou prvky subsekvence v seřazeném pořadí, od nejnižšího po nejvyšší, a ve kterém je posloupnost co nejdelší. Tato subsekvence nemusí být nutně souvislá nebo jedinečná. Nejdůležitější rostoucí posloupnosti jsou studovány v kontextu různých oborů souvisejících s matematika, počítaje v to algoritmy, teorie náhodných matic, teorie reprezentace, a fyzika.[1] Nejdelší problém s rostoucí posloupností je řešitelný v čase O (n log n), kde n označuje délku vstupní sekvence.[2]

Příklad

V prvních 16 podmínkách binárního souboru Van der Corputova sekvence

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15

nejdelší rostoucí subsekvence je

0, 2, 6, 9, 11, 15.

Tato subsekvence má délku šest; vstupní sekvence nemá žádné sedmičlenné zvyšující se posloupnosti. Nejdelší rostoucí posloupnost v tomto příkladu není jediným řešením: například

0, 4, 6, 9, 11, 15
0, 2, 6, 9, 13, 15
0, 4, 6, 9, 13, 15

jsou další rostoucí subsekvence stejné délky ve stejné vstupní posloupnosti.

Vztahy k dalším algoritmickým problémům

Nejdelší rostoucí problém subsekvence úzce souvisí s nejdelší společný problém s posloupností, který má kvadratický čas dynamické programování řešení: nejdelší rostoucí posloupnost sekvence S je nejdelší společnou posloupností S a T, kde T je výsledkem třídění S. Pro speciální případ, ve kterém je vstupem permutace celých čísel 1, 2, ..., n, lze tento přístup zefektivnit, což povede k časovým hranicím formy O (n log log n).[3]

Největší klika v permutační graf odpovídá nejdelší klesající subsekvenci permutace, která definuje graf (za předpokladu, že původní nepermutovaná sekvence je tříděna od nejnižší hodnoty po nejvyšší). Podobně maximum nezávislá sada v permutačním grafu odpovídá nejdelší neklesající subsekvenci. Proto lze k řešení použít nejdelší rostoucí algoritmy subsekvence klika problém efektivně v permutačních grafech.[4]

V Robinson – Schenstedova korespondence mezi obměny a Mladé obrazy, délka první řady tabla odpovídající permutaci se rovná délce nejdelší rostoucí subsekvence permutace a délka prvního sloupce se rovná délce nejdelší klesající subsekvence.[2]

Efektivní algoritmy

Algoritmus popsaný níže řeší problém s nejdelší rostoucí subsekvencí efektivně pomocí polí a binární vyhledávání. Zpracovává prvky sekvence v pořadí, přičemž udržuje dosud nalezenou nejdelší rostoucí posloupnost. Označte hodnoty sekvence jako X [0], X [1] atd. Poté, po zpracování X [i], bude mít algoritmus uložené hodnoty ve dvou polích:

M [j] - uloží index k nejmenší hodnoty X [k] tak, že existuje rostoucí posloupnost délky j končící v X [k] na rozsahu k ≤ i (Je třeba, aby toto prohlášení bylo jasnější). Všimněte si, že j ≤ (i + 1), protože j ≥ 1 představuje délku rostoucí subsekvence a k ≥ 0 představuje index jeho ukončení.
P [k] - uloží index předchůdce X [k] v nejdelší rostoucí posloupnosti končící na X [k].

Algoritmus navíc ukládá proměnnou L představující délku dosud nalezené nejdelší rostoucí posloupnosti. Protože níže uvedený algoritmus používá číslování založené na nule, pro jasnost je M vyplněno M [0], které se nepoužívá, takže M [j] odpovídá posloupnosti délky j. Skutečná implementace může M [0] přeskočit a podle toho upravit indexy.

Všimněte si, že v kterémkoli bodě algoritmu sekvence

X [M [1]], X [M [2]], ..., X [M [L]]

stoupá. Pro, pokud existuje rostoucí posloupnost délky j ≥ 2 končící na X [M [j]], pak existuje také subsekvence délky j-1 končící na menší hodnotě: konkrétně ta končící na X [P [M [j]]]. Můžeme tedy provádět binární vyhledávání v této sekvenci v logaritmickém čase.

Algoritmus tedy postupuje následovně:

Ukázka kódu.
P = pole délky NM = pole délky N + 1L = 0pro i v dosahu 0 na N-1: // Binární hledání největšího pozitivního j ≤ L // takové, že X [M [j]] <= X [i] lo = 1 hi = L zatímco lo ≤ hi: mid = ceil ((lo + hi) / 2) -li X [M [mid]] jiný: hi = mid-1 // Po vyhledání je lo o 1 větší než // délka nejdelší předpony X [i] newL = lo // Předchůdce X [i] je poslední index // subsekvence délky newL-1 P [i] = M [newL-1] M [newL] = i -li newL> L: // Pokud jsme našli sekvenci delší než kterákoli, kterou jsme // dosud našli, aktualizujte L L = newL // Rekonstruujte nejdelší rostoucí subsekvenci S = pole délky Lk = M [L]pro i v dosahu L-1 na 0: S [i] = X [k] k = P [k]vrátit se S

Protože algoritmus provádí jediné binární vyhledávání na prvek sekvence, lze jeho celkový čas vyjádřit pomocí Velká O notace jako O (n logn). Fredman (1975) pojednává o variantě tohoto algoritmu, kterou připisuje Donald Knuth; ve variantě, kterou studuje, algoritmus testuje, zda každá hodnota X [i] lze použít k prodloužení aktuální nejdelší rostoucí sekvence v konstantním čase před provedením binárního vyhledávání. S touto úpravou používá algoritmus maximálně n log2 n − n log2log2 n + O (n) v nejhorším případě srovnání, které je optimální pro algoritmus založený na srovnání až do konstantního faktoru v O (n) termín.[5]

Délka hranice

Podle Erdős – Szekeresova věta, libovolná sekvence n2+1 odlišná celá čísla má rostoucí nebo klesající subsekvenci délky n + 1.[6][7] U vstupů, u nichž je každá permutace vstupu stejně pravděpodobná, je očekávaná délka nejdelší rostoucí subsekvence přibližně 2√n.[8] V limitu jako n se blíží k nekonečnu, délce nejdelší rostoucí subsekvence náhodně permutované sekvence n položek má distribuci blížící se k Distribuce Tracy – Widom, distribuce největšího vlastního čísla náhodné matice v Gaussův jednotný soubor.[9]

Online algoritmy

Nejdelší rostoucí posloupnost byla také studována v prostředí online algoritmy, ve kterém jsou prvky posloupnosti nezávislých náhodných proměnných s kontinuálním rozdělením F - nebo alternativně prvky a náhodná obměna - jsou prezentovány jeden po druhém algoritmu, který musí rozhodnout, zda zahrnout nebo vyloučit každý prvek, bez znalosti pozdějších prvků. V této variantě problému, která umožňuje zajímavé aplikace v několika kontextech, je možné navrhnout optimální výběrový postup, který vzhledem k náhodnému vzorku velikosti n jako vstup vygeneruje rostoucí sekvenci s maximální očekávanou délkou velikosti přibližně √2n.[10]Délka rostoucí subsekvence vybrané tímto optimálním postupem má rozptyl přibližně stejný √2n/3a jeho omezující distribuce je asymptoticky normální po obvyklém centrování a škálování.[11]Stejné asymptotické výsledky platí s přesnějšími hranicemi pro odpovídající problém v nastavení procesu příchodu Poissona.[12]Další upřesnění v nastavení Poissonova procesu je dáno důkazem a teorém centrálního limitu pro optimální výběrový proces, který platí při vhodné normalizaci v úplnějším smyslu, než by člověk čekal. Důkaz přináší nejen „správnou“ funkční limitní větu také (singulární) kovarianční matice trojrozměrného procesu shrnujícího všechny interakční procesy.[13]

aplikace


Viz také

Reference

  1. ^ Aldous, David; Diaconis, Persi (1999), „Nejdelší rostoucí subsekvence: od třídění trpělivosti k teorému Baik – Deift – Johansson“, Bulletin of the American Mathematical Society, 36 (04): 413–432, doi:10.1090 / S0273-0979-99-00796-X.
  2. ^ A b Schensted, C. (1961), „Nejdelší rostoucí a klesající subsekvence“, Kanadský žurnál matematiky, 13: 179–191, doi:10.4153 / CJM-1961-015-3, PAN  0121305.
  3. ^ Hunt, J .; Szymanski, T. (1977), „Rychlý algoritmus pro výpočet nejdelších společných posloupností“, Komunikace ACM, 20 (5): 350–353, doi:10.1145/359581.359603.
  4. ^ Golumbic, M. C. (1980), Algoritmická teorie grafů a dokonalé grafy, Computer Science and Applied Mathematics, Academic Press, s. 1 159.
  5. ^ Fredman, Michael L. (1975), „O výpočtu délky nejdelší rostoucí subsekvence“, Diskrétní matematika, 11 (1): 29–35, doi:10.1016 / 0012-365X (75) 90103-X.
  6. ^ Erdős, Paul; Szekeres, George (1935), „Kombinatorický problém v geometrii“, Compositio Mathematica, 2: 463–470.
  7. ^ Steele, J. Michael (1995), "Variace na monotónní podsekvenční téma Erdőse a Szekerese", v Aldous, David; Diaconis, Persi; Spencer, Joel; et al. (eds.), Diskrétní pravděpodobnost a algoritmy (PDF), Svazky IMA v matematice a její aplikace, 72, Springer-Verlag, str. 111–131.
  8. ^ Vershik, A. M.; Kerov, C. V. (1977), „Asymptotics of the Plancheral measure of the symetric group and a limiting form for Young tableaux“, Dokl. Akad. Nauk SSSR, 233: 1024–1027.
  9. ^ Baik, Jinho; Deift, Percy; Johansson, Kurt (1999), „O rozdělení délky nejdelší rostoucí posloupnosti náhodných permutací“, Journal of the American Mathematical Society, 12 (4): 1119–1178, arXiv:matematika / 9810105, doi:10.1090 / S0894-0347-99-00307-0.
  10. ^ Samuels, Stephen. M .; Steele, J. Michael (1981), „Optimální sekvenční výběr monotónní sekvence z náhodného vzorku“ (PDF), Annals of Probability, 9 (6): 937–947, doi:10.1214 / aop / 1176994265
  11. ^ Arlotto, Alessandro; Nguyen, Vinh V .; Steele, J. Michael (2015), „Optimální online výběr monotónní subsekvence: centrální limitní věta“, Stochastické procesy a jejich aplikace, 125 (9): 3596–3622, arXiv:1408.6750, doi:10.1016 / j.spa.2015.03.009
  12. ^ Bruss, F. Thomas; Delbaen, Freddy (2001), „Optimální pravidla pro postupný výběr monotónních podsekvencí maximální očekávané délky“, Stochastické procesy a jejich aplikace, 96 (2): 313–342.
  13. ^ Bruss, F. Thomas; Delbaen, Freddy (2004), „Centrální limitní věta pro optimální proces výběru pro monotónní subsekvence maximální očekávané délky“, Stochastické procesy a jejich aplikace, 114 (2): 287–311, doi:10.1016 / j.spa.2004.09.002.

externí odkazy