En informática , el problema de subsecuencia creciente más larga tiene como objetivo encontrar una subsecuencia de una secuencia dada en la que los elementos de la subsecuencia estén ordenados en orden ascendente y en la que la subsecuencia sea lo más larga posible. Esta subsecuencia no es necesariamente contigua o única. Las subsecuencias crecientes más largas se estudian en el contexto de diversas disciplinas relacionadas con las matemáticas , incluida la algorítmica , la teoría de matrices aleatorias , la teoría de la representación y la física . [1] [2] El problema de subsecuencia creciente más larga se puede resolver en el tiempo , donde denota la longitud de la secuencia de entrada. [3]
Esta subsecuencia tiene una longitud de seis; la secuencia de entrada no tiene subsecuencias crecientes de siete miembros. La subsecuencia creciente más larga en este ejemplo no es la única solución: por ejemplo,
0, 4, 6, 9, 11, 15
0, 2, 6, 9, 13, 15
0, 4, 6, 9, 13, 15
Hay otras subsecuencias crecientes de igual longitud en la misma secuencia de entrada.
Relaciones con otros problemas algorítmicos
El problema de subsecuencia creciente más largo está estrechamente relacionado con el problema de subsecuencia común más largo , que tiene una solución de programación dinámica de tiempo cuadrática : la subsecuencia creciente más larga de una secuencia es la subsecuencia común más larga de y donde está el resultado de la clasificación. Sin embargo, para el caso especial en el que la entrada es una permutación de los números enteros, este enfoque puede hacerse mucho más eficiente, lo que lleva a límites de tiempo de la forma [4]
La camarilla más grande en un gráfico de permutación corresponde a la subsecuencia decreciente más larga de la permutación que define el gráfico (suponiendo que la secuencia original no permutada esté ordenada del valor más bajo al más alto). De manera similar, el conjunto independiente máximo en un gráfico de permutación corresponde a la subsecuencia no decreciente más larga. Por lo tanto, se pueden utilizar algoritmos de subsecuencia creciente más larga para resolver el problema de camarilla de manera eficiente en gráficos de permutación. [5]
En la correspondencia Robinson-Schensted entre permutaciones y cuadros de Young , la longitud de la primera fila del cuadro correspondiente a una permutación es igual a la longitud de la subsecuencia creciente más larga de la permutación, y la longitud de la primera columna es igual a la longitud de la subsecuencia creciente más larga de la permutación. subsecuencia decreciente. [3]
Algoritmos eficientes
El algoritmo que se describe a continuación resuelve eficientemente el problema de subsecuencia creciente más larga con matrices y búsqueda binaria . Procesa los elementos de la secuencia en orden, manteniendo la subsecuencia creciente más larga encontrada hasta el momento. Denote los valores de la secuencia como etc. Luego, después del procesamiento, el algoritmo habrá almacenado un número entero y valores en dos matrices:
— almacena la longitud de la subsecuencia creciente más larga encontrada hasta el momento.
— almacena el índice del valor más pequeño tal que hay una subsecuencia creciente de longitud que termina en en el rango Explícitamente, supongamos que denota el conjunto de todos los índices tal que existe una subsecuencia creciente de longitud que termina en Entonces es el índice en para que se minimiza; es decir, y (o equivalentemente, y para cada ); si varios índices satisfacen esta condición, entonces es el más grande.
Para aclarar, "existe una subsecuencia creciente de longitud que termina en " significa que existen índices que terminan en tales que
Tenga en cuenta que porque representa la longitud de la subsecuencia creciente y representa el índice de su terminación.
La longitud de es mayor que la longitud de pero es posible que el algoritmo no utilice todos los elementos de esta matriz (de hecho, si la secuencia creciente más larga tiene longitud, el algoritmo solo los utiliza). Si sin embargo se usa/definió entonces (y además, en la iteración también se mantendrá). no está definido ya que las secuencias de longitud no tienen índice final ( puede tener cualquier valor).
— almacena el índice del predecesor de en la subsecuencia creciente más larga que termina en
La longitud de es igual a la de
Si entonces, while no está definido ya que no tiene predecesor ( puede ser cualquier valor).
Debido a que el siguiente algoritmo utiliza numeración de base cero , para mayor claridad se completa con lo que no se utiliza para que corresponda a una subsecuencia de longitud. Una implementación real puede omitir y ajustar los índices en consecuencia.
Tenga en cuenta que, en cualquier punto del algoritmo, la secuencia
aumenta. Porque, si hay una subsecuencia creciente de longitud que termina en entonces también hay una subsecuencia de longitud que termina en un valor más pequeño: es decir, la que termina en Por lo tanto, podemos hacer búsquedas binarias en esta secuencia en tiempo logarítmico.
El algoritmo entonces procede de la siguiente manera:
P = matriz de longitud NM = matriz de longitud N + 1M[0] = -1 // indefinido por lo que se puede establecer en cualquier valorL = 0para i en el rango 0 a N-1: //N-1 incluido // Búsqueda binaria del positivo más pequeño l ≤ L // tal que X[M[l]] > X[i] lo = 1 hola = L + 1 mientras lo < hola: medio = bajo + piso((hola-bajo)/2) // bajo <= medio < alto si X[M[medio]] >= X[i] hola = medio else : // si X[M[mediado]] < X[i] lo = medio + 1 // Después de buscar, lo == hi es 1 mayor que el // longitud del prefijo más largo de X[i] nuevoL = lo // El predecesor de X[i] es el último índice de // la subsecuencia de longitud newL-1 P[i] = M[nuevaL-1] M[nuevaL] = yo si nuevoL > L: // Si encontramos una subsecuencia más larga que cualquiera que hayamos encontrado // encontrado todavía, actualiza L L = nuevoL// Reconstruir la subsecuencia creciente más larga// Consta de los valores de X en los índices L:// ..., P[P[M[L]]], P[M[L]], M[L]S = matriz de longitud Lk = M[L]para j en el rango L-1 a 0: //0 incluido S[j] = X[k] k = P[k]devoluciones
Debido a que el algoritmo realiza una única búsqueda binaria por elemento de secuencia, su tiempo total se puede expresar usando la notación O grande mientras Fredman (1975) analiza una variante de este algoritmo, que atribuye a Donald Knuth ; en la variante que estudia, el algoritmo prueba si cada valor puede usarse para extender la secuencia creciente más larga actual, en tiempo constante, antes de realizar la búsqueda binaria. Con esta modificación, el algoritmo utiliza como máximo comparaciones en el peor de los casos, lo que es óptimo para un algoritmo basado en comparaciones hasta el factor constante en el término. [6]
Ejecución de ejemplo
Límites de longitud
Según el teorema de Erdős-Szekeres , cualquier secuencia de números enteros distintos tiene una subsecuencia creciente o decreciente de longitud [7] [8] Para entradas en las que cada permutación de la entrada es igualmente probable, la longitud esperada de la subsecuencia creciente más larga es aproximadamente [9] [2]
En el límite cuando se acerca al infinito, el teorema de Baik-Deift-Johansson dice que la longitud de la subsecuencia creciente más larga de una secuencia de elementos permutada aleatoriamente tiene una distribución que se aproxima a la distribución de Tracy-Widom , la distribución del valor propio más grande de una secuencia aleatoria matriz en el conjunto unitario gaussiano . [10]
Algoritmos en línea
La subsecuencia creciente más larga también se ha estudiado en el contexto de algoritmos en línea , en los que los elementos de una secuencia de variables aleatorias independientes con distribución continua (o, alternativamente, los elementos de una permutación aleatoria ) se presentan uno por uno a un algoritmo que debe decidir si incluir o excluir cada elemento, sin conocer los elementos posteriores. En esta variante del problema, que permite aplicaciones interesantes en varios contextos, es posible diseñar un procedimiento de selección óptimo que, dada una muestra aleatoria de tamaño como entrada, generará una secuencia creciente con la longitud máxima esperada de tamaño aproximadamente [11 ]
La longitud de la subsecuencia creciente seleccionada mediante este procedimiento óptimo tiene una varianza aproximadamente igual a y su distribución límite es asintóticamente normal después del centrado y escalado habituales. [12]
Los mismos resultados asintóticos son válidos con límites más precisos para el problema correspondiente en el contexto de un proceso de llegada de Poisson. [13]
Un refinamiento adicional en la configuración del proceso de Poisson se logra mediante la demostración de un teorema de límite central para el proceso de selección óptimo que se cumple, con una normalización adecuada, en un sentido más completo de lo que uno esperaría. La prueba arroja no sólo el teorema del límite funcional "correcto" sino también la matriz de covarianza (singular) del proceso tridimensional que resume todos los procesos que interactúan. [14]
Ver también
Anatoly Vershik : matemático ruso (1933-2024) que estudió las aplicaciones de la teoría de grupos a las subsecuencias crecientes más largas en permutaciones aleatorias. [15]
Clasificación por paciencia : algoritmo de clasificación: una técnica eficiente para encontrar la longitud de la subsecuencia creciente más larga
Monoide plactico - monoide de enteros positivos módulo de equivalencia Knuth Pages displaying wikidata descriptions as a fallback- un sistema algebraico definido por transformaciones que preservan la longitud de la subsecuencia creciente más larga
Referencias
^ Aldous, David ; Diaconis, Persi (1999), "Subsecuencias crecientes más largas: de la clasificación por paciencia al teorema de Baik-Deift-Johansson", Boletín de la Sociedad Matemática Estadounidense , 36 (4): 413–432, doi : 10.1090/S0273-0979-99 -00796-X.
^ ab Romik, Dan (2015). Las sorprendentes matemáticas de las subsecuencias crecientes más largas . doi :10.1017/CBO9781139872003. ISBN9781107075832.
^ Caza, J.; Szymanski, T. (1977), "Un algoritmo rápido para calcular las subsecuencias comunes más largas", Communications of the ACM , 20 (5): 350–353, doi : 10.1145/359581.359603 , S2CID 3226080.
^ Golumbic, MC (1980), Teoría de grafos algorítmicos y gráficos perfectos , informática y matemáticas aplicadas, Academic Press, p. 159.
^ Fredman, Michael L. (1975), "Sobre el cálculo de la longitud de las subsecuencias crecientes más largas", Matemáticas discretas , 11 (1): 29–35, doi : 10.1016/0012-365X(75)90103-X.
^ Erdős, Paul ; Szekeres, George (1935), "Un problema combinatorio en geometría", Compositio Mathematica , 2 : 463–470.
^ Steele, J. Michael (1995), "Variaciones sobre el tema de la subsecuencia monótona de Erdős y Szekeres", en Aldous, David ; Diaconis, Persi ; Spencer, Joel ; et al. (eds.), Algoritmos y probabilidad discreta (PDF) , Volúmenes IMA en Matemáticas y sus aplicaciones, vol. 72, Springer-Verlag, págs. 111-131.
^ Vershik, soy ; Kerov, CV (1977), "Asintótica de la medida de Plancheral del grupo simétrico y una forma limitante para cuadros de Young", Dokl. Akád. Nauk SSSR , 233 : 1024-1027.
^ Baik, Jinho; Deft, Percy; Johansson, Kurt (1999), "Sobre la distribución de la longitud de la subsecuencia creciente más larga de permutaciones aleatorias", Journal of the American Mathematical Society , 12 (4): 1119–1178, arXiv : math/9810105 , doi : 10.1090/ S0894-0347-99-00307-0.
^ Samuels, Esteban. METRO.; Steele, J. Michael (1981), "Selección secuencial óptima de una secuencia monótona a partir de una muestra aleatoria" (PDF) , Annals of Probability , 9 (6): 937–947, doi : 10.1214/aop/1176994265 , archivado (PDF) ) del original el 30 de julio de 2018
^ Arlotto, Alessandro; Nguyen, Vinh V.; Steele, J. Michael (2015), "Selección óptima en línea de una subsecuencia monótona: un teorema del límite central", Procesos estocásticos y sus aplicaciones , 125 (9): 3596–3622, arXiv : 1408.6750 , doi :10.1016/j.spa .2015.03.009, S2CID 15900488
^ Bruss, F. Thomas ; Delbaen, Freddy (2001), "Reglas óptimas para la selección secuencial de subsecuencias monótonas de longitud máxima esperada", Procesos estocásticos y sus aplicaciones , 96 (2): 313–342, doi : 10.1016/S0304-4149(01)00122- 3.
^ Bruss, F. Thomas ; Delbaen, Freddy (2004), "Un teorema del límite central para el proceso de selección óptimo para subsecuencias monótonas de longitud máxima esperada", Procesos estocásticos y sus aplicaciones , 114 (2): 287–311, doi : 10.1016/j.spa.2004.09 .002.
^ Romik, Dan (2015). "La sorprendente matemática de las subsecuencias crecientes más largas" . Instituto de Libros de Texto de Estadística Matemática. Nueva York: Cambridge University Press. ISBN978-1-107-42882-9.
enlaces externos
La subsecuencia creciente más larga del algoritmo
Subsecuencia creciente más larga simplificada
Encontrar el recuento de subsecuencias aumentadas más largas