Längst wachsende Folge - Wikipedia

In der Informatik besteht das Problem der am längsten wachsenden Subsequenz darin, eine Subsequenz einer gegebenen Sequenz zu finden, in der die Elemente der Subsequenz in der sortierten Reihenfolge vom niedrigsten bis zum höchsten sind und in der die Subsequenz solange ist möglich. Diese Teilsequenz ist nicht notwendigerweise zusammenhängend oder eindeutig. Am längsten zunehmende Untersequenzen werden im Zusammenhang mit verschiedenen mathematikbezogenen Disziplinen untersucht, darunter Algorithmik, Zufallsmatrixtheorie, Repräsentationstheorie und Physik. ^[1] Das am längsten zunehmende Untersequenzproblem ist in der Zeit O lösbar ( n log n ), wobei n die Länge der Eingabesequenz bezeichnet. ^[2]

Beispiel [ edit

In den ersten 16 Termen die binäre Van der Corput-Sequenz

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

ist eine am längsten zunehmende Untersequenz

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

Diese Untersequenz hat eine Länge von sechs; Die Eingabesequenz hat keine sieben Mitglieder, die zunehmende Untersequenzen haben. Die am längsten wachsende Teilsequenz in diesem Beispiel ist nicht eindeutig: Zum Beispiel

0, 4, 6, 9, 11, 15 oder

0, 2, 6, 9, 13, 15 oder

0, 4, 6, 9, 13, 15

sind andere Zunahmen Teilsequenzen gleicher Länge in derselben Eingangssequenz.

Beziehungen zu anderen algorithmischen Problemen [ edit ]

Das am längsten zunehmende Subsequenzproblem hängt eng mit dem am längsten verbreiteten Subsequenzproblem zusammen, das eine quadratische zeitdynamische Programmierlösung hat: die längste zunehmende Untersequenz einer Sequenz S ist die längste übliche Untersequenz von S und T wobei T S das Ergebnis der Sortierung ist . Für den Sonderfall, in dem die Eingabe eine Permutation der ganzen Zahlen 1, 2, ..., und ist, kann dieser Ansatz jedoch wesentlich effizienter gemacht werden, was zu Zeitgrenzen der Form O ( n log log n ). ^[3]

Die größte Clique in einem Permutationsgraphen ist definiert durch die am längsten abnehmende Teilsequenz der Permutation, die den Graphen definiert; Die am längsten abnehmende Teilsequenz entspricht der rechnerischen Komplexität durch Negation aller Zahlen der am längsten zunehmenden Teilsequenz. Daher können am längsten zunehmende Teilsequenzalgorithmen verwendet werden, um das Cliquenproblem effizient in Permutationsgraphen zu lösen. ^[4]

In der Robinson-Schensted-Entsprechung zwischen Permutationen und Young-Tableaux entspricht die Länge der ersten Reihe des Tableaus der Länge der am längsten zunehmenden Teilfolge der Permutation, und die Länge der ersten Spalte ist gleich der Länge der am längsten abnehmenden Teilfolge. ^[2]

Effiziente Algorithmen [

Der unten beschriebene Algorithmus löst das am längsten wachsende Teilfolgenproblem effizient mit Arrays und binärer Suche. Es verarbeitet die Sequenzelemente in der Reihenfolge, wobei die am längsten wachsende Teilsequenz erhalten bleibt, die bisher gefunden wurde. Die Sequenzwerte werden als X [0]X [1] usw. bezeichnet. Nach der Verarbeitung von X [ i ] hat der Algorithmus Werte in zwei Arrays gespeichert:

M j ] - speichert den Index k mit dem kleinsten Wert X [ k so dass es eine zunehmende Folge von Längen gibt j endend bei X [ k ] im Bereich k ≤ i . Man beachte, dass j ≤ (i + 1) weil j ≥ 1 die Länge der zunehmenden Teilsequenz darstellt und k ≥ 0 stellt den Index seiner Beendigung dar.

P [ k ] - speichert den Index des Vorgängers von X [ k ] in der am längsten wachsenden Teilsequenz, die bei X [ endet. k ].

Zusätzlich speichert der Algorithmus eine Variable L, die die Länge der bisher am längsten zunehmenden Teilsequenz darstellt. Da der Algorithmus unten eine auf Null basierende Nummerierung verwendet, wird M aus Gründen der Klarheit mit M [0] aufgefüllt, was ungenutzt bleibt, so dass M [ j ] einer Untersequenz der Länge j entspricht. Eine echte Implementierung kann M [0] überspringen und die Indizes entsprechend anpassen.

Man beachte, dass an jedem Punkt des Algorithmus die Reihenfolge gilt

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

nimmt zu. Wenn es eine zunehmende Untersequenz der Länge gibt j ≥ 2, die bei X [M[ j ]] endet, dann gibt es auch eine Untersequenz der Länge j -1 endet bei einem kleineren Wert: nämlich bei X [P [M[ j ]]. Daher können wir in dieser Reihenfolge in logarithmischer Zeit binäre Suchen durchführen.

Der Algorithmus geht dann wie folgt vor:

  P = Array der Länge N  M = Array der Länge N + 1   L = 0   für  i  in Reichweite  0  bis  N-1:    // Binäre Suche nach dem größten positiven Wert j ≤ L    // so dass X [M[j]] <= X [i]    lo = 1    hi = L     während  lo ≤ hi:      mid = ceiling ((lo + hi) / 2)       wenn  X [M[mid]] <= X [i]:        lo = mid + 1       else :        hi = mid-1     // Nach der Suche ist lo um 1 größer als    // Länge des längsten Präfixes von X [i]    newL = lo     // Der Vorgänger von X [i] ist der letzte Index von    // die Teilsequenz von length newL-1    P [i] = M [newL-1]    M [newL] = i      wenn  neu L> L:      // Wenn wir eine Folge gefunden haben, die länger ist als die, die wir haben      // gefunden, Update L      L = newL   // Rekonstruiere die am längsten wachsende Teilsequenz  S = Array der Länge L  k = M [L]   für  i  in Reichweite  L-1  bis  0:    S [i] = X [k]    k = P [k]    return  S 

Da der Algorithmus eine einzelne binäre Suche pro Sequenzelement ausführt, kann seine Gesamtzeit unter Verwendung der O-Notation als O ausgedrückt werden ( n log n ). Fredman (1975) diskutiert eine Variante dieses Algorithmus, die er Donald Knuth zuschreibt. In der von ihm untersuchten Variante testet der Algorithmus, ob jeder Wert X i ] verwendet werden kann, um die aktuell am längsten zunehmende Sequenz in konstanter Zeit vor der binären Suche zu erweitern. Bei dieser Modifikation verwendet der Algorithmus höchstens n log ₂ n - n log ₂ log _{2 [19659034] n + O ( n )} Vergleiche im schlimmsten Fall, was für einen vergleichsabhängigen Algorithmus bis zum konstanten Faktor im O (19459007) n optimal ist ]) Ausdruck. ^[5]

Längengrenzen [ edit ]

Nach dem Satz von Erdős-Szekeres ist jede Folge von n ² +1 verschiedenen Integern hat eine zunehmende oder abnehmende Teilsequenz der Länge n + 1. ^[6][7] Bei Eingaben, bei denen jede Permutation des Eingangs gleich wahrscheinlich ist, beträgt die erwartete Länge der am längsten zunehmenden Teilsequenz ungefähr 2 √ n . ^[8] In der Grenze, in der n sich dem Unendlichen nähert, hat die Länge der am längsten zunehmenden Untersequenz einer zufällig permutierten Sequenz von n Elementen eine Verteilung, die sich der Tracy-Widom-Verteilung nähert, der Verteilung des größten Eigenwerts einer Zufallsmatrix im einheitlichen Gaußschen Ensemble. ^[9]

Online-Algorithmen [ edit ]

Die am längsten wachsende Teilsequenz wurde auch im Zusammenhang mit Online-Algorithmen untersucht wobei die Elemente einer Folge unabhängiger Zufallsvariablen mit kontinuierlicher Verteilung F - oder alternativ die Elemente einer zufälligen Permutation - einzeln einem Algorithmus präsentiert werden, der entscheiden muss, ob jedes Element ein- oder ausgeschlossen werden soll, ohne Kenntnis der späteren Elemente. In dieser Variante des Problems, die interessante Anwendungen in verschiedenen Kontexten zulässt, kann ein optimales Auswahlverfahren erarbeitet werden, das bei einer Zufallsstichprobe der Größe n als Eingabe eine ansteigende Sequenz mit maximalem Wert erzeugt erwartete Länge der Größe ungefähr √ 2n . ^[10] Die Länge der durch dieses optimale Verfahren ausgewählten zunehmenden Teilsequenz hat eine Varianz von ungefähr √ 2n / 3 und ihre begrenzende Verteilung ist nach der üblichen Zentrierung asymptotisch normal und Skalierung. ^[11] Dieselben asymptotischen Ergebnisse gelten mit genaueren Grenzen für das entsprechende Problem bei der Einstellung eines Poisson-Ankunftsprozesses. ^[12] Eine weitere Verfeinerung der Poisson-Prozesseinstellung wird durch den Beweis eines zentralen Grenzwertsatzes für gegeben der optimale Auswahlprozess was bei einer geeigneten Normalisierung in einem vollständigeren Sinne gilt, als man erwarten würde. Der Beweis liefert nicht nur den "korrekten" funktionellen Grenzwertsatz aber auch die (singuläre) Kovarianzmatrix des dreidimensionalen Prozesses, die alle interagierenden Prozesse zusammenfasst. ^[13]

Siehe auch [ edit ]

Referenzen [ edit ]

1. ^ Aldous, David; Diaconis, Persi (1999), "Am längsten wachsende Untersequenzen: Von der Geduldssortierung zum Satz von Baik-Deift-Johansson", Bulletin der American Mathematical Society 36 (04): 413 –432, doi: 10.1090 / S0273-0979-99-00796-X .
2. ^ ^{a b} b Schensted, C. (1961) ), "Am längsten zunehmende und abnehmende Untersequenzen", Canadian Journal of Mathematics 13 : 179–191, doi: 10.4153 / CJM-1961-015-3, MR 0121305
3. ^ Hunt, J .; Szymanski, T. (1977), "Ein schneller Algorithmus zum Berechnen längster gemeinsamer Untersequenzen", Kommunikationen der ACM 20 (5): 350–353, doi: 10.1145 / 359581.359603
4. ^ Golumbic, MC (1980), Algorithmic Graph Theory and Perfect Graphs Informatik und Angewandte Mathematik, Academic Press, p. 159 .
5. ^ Fredman, Michael L. (1975), "Zur Berechnung der Länge der am längsten zunehmenden Untersequenzen", Discrete Mathematics 11 (1 ): 29–35, doi: 10.1016 / 0012-365X (75) 90103-X .
6. ^ Erdős, Paul; Szekeres, George (1935), "Ein kombinatorisches Problem in der Geometrie", Compositio Mathematica 2 : 463–470 CS1 maint: Mehrere Namen: Autorenliste (link) [19659078].
7. ^ Steele, J. Michael (1995), "Variationen über das monotone Subsequenz-Thema von Erdős und Szekeres", in Aldous, David; Diaconis, Persi; Spencer, Joel; et al. Discrete Probability and Algorithms (PDF) IMA Volumes in Mathematics und ihre Anwendungen, 72 Springer-Verlag, S. 111–131 .
8. ^ Vershik, AM; Kerov, C. V. (1977), "Asymptotika des plancheralischen Maßes der symmetrischen Gruppe und eine Begrenzungsform für Young Tableaux", Dokl. Akad. Nauk SSSR 233 : 1024–1027 .
9. ^ Baik, Jinho; Deift, Percy; Johansson, Kurt (1999), "Über die Verteilung der Länge der am längsten zunehmenden Teilsequenz zufälliger Permutationen", Journal der American Mathematical Society 12 (4): 1119– 1178, arXiv: math / 9810105 doi: 10.1090 / S0894-0347-99-00307-0 .
10. ^ Samuels, Stephen. M .; Steele, J. Michael (1981), "Optimal sequentielle Auswahl einer monotonen Sequenz aus einer Zufallsstichprobe", Annalen der Wahrscheinlichkeit 9 (6): 937–947, doi: 10.1214 / aop / 1176994265
11. ^ Arlotto, Alessandro; Nguyen, Vinh V .; Steele, J. Michael (2015), "Optimale Online-Auswahl einer monotonen Subsequenz: ein zentraler Grenzwertsatz", Stochastische Prozesse und ihre Anwendungen 125 (9): 3596–3622 , arXiv: 1408.6750 doi: 10.1016 / j.spa.2015.03.009
12. ^ Bruss, F. Thomas; Delbaen, Freddy (2001), "Optimale Regeln für die sequentielle Auswahl monotoner Teilsequenzen von maximal erwarteter Länge", Stochastische Prozesse und ihre Anwendungen 96 (2): 313–342 19659095]
13. ^ Bruss, F. Thomas; Delbaen, Freddy (2004), "Ein zentraler Grenzwertsatz für das optimale Auswahlverfahren für monotone Teilsequenzen mit maximal erwarteter Länge", Stochastische Prozesse und ihre Anwendungen 114 (2): 287 –311, doi: 10.1016 / j.spa.2004.09.002 .

Externe Links [ edit ]