En informática , el problema de subsecuencia creciente más largo es encontrar una subsecuencia de una secuencia dada en la que los elementos de la subsecuencia están ordenados, de menor a mayor, y en la que la subsecuencia es lo más larga posible. Esta subsecuencia no es necesariamente contigua ni única. Más largos subsecuencias crecientes son estudiados en el contexto de diferentes disciplinas relacionadas con las matemáticas , incluyendo algorítmica , teoría de la matriz al azar , teoría de la representación , y la física . [1] El problema de subsecuencia creciente más largo se puede resolver en el tiempo O ( n log n), donde n denota la longitud de la secuencia de entrada. [2]
Ejemplo
En los primeros 16 términos de la secuencia binaria de Van der Corput
- 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15
una subsecuencia creciente más larga es
- 0, 2, 6, 9, 11, 15.
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 larga está estrechamente relacionado con el problema de subsecuencia común más larga , que tiene una solución de programación dinámica de tiempo cuadrática : la subsecuencia creciente más larga de una secuencia S es la subsecuencia común más larga de S y T , donde T es el resultado de ordenar S . Sin embargo, para el caso especial en el que la entrada es una permutación de los enteros 1, 2, ..., n , este enfoque puede hacerse mucho más eficiente, lo que lleva a límites de tiempo de la forma O ( n log log n ). [3]
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 (asumiendo que la secuencia original no permutada se ordena 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, los algoritmos de subsecuencia creciente más largos pueden usarse para resolver el problema de la camarilla de manera eficiente en los gráficos de permutación. [4]
En la correspondencia de 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 decreciente. [2]
Algoritmos eficientes
El algoritmo que se describe a continuación resuelve el problema de subsecuencia creciente más largo de manera eficiente con matrices y búsqueda binaria . Procesa los elementos de la secuencia en orden, manteniendo la subsecuencia creciente más larga encontrada hasta ahora. Denote los valores de secuencia como X [0], X [1], etc. Luego, después de procesar X [ i ], el algoritmo tendrá valores almacenados en dos matrices:
- M [ j ]: almacena el índice k del valor más pequeño X [ k ], de modo que hay una subsecuencia creciente de longitud j que termina en X [ k ] en el rango k ≤ i (Es necesario aclarar esta afirmación ). Tenga en cuenta que j ≤ (i + 1) , porque j ≥ 1 representa la longitud de la subsecuencia creciente, y k ≥ 0 representa el índice de su terminación.
- P [ k ]: almacena el índice del predecesor de X [ k ] en la subsecuencia creciente más larga que termina en X [ k ].
Además, el algoritmo almacena una variable L que representa la longitud de la subsecuencia creciente más larga encontrada hasta ahora. Debido a que el algoritmo siguiente usa numeración basada en cero , para mayor claridad, M se rellena con M [0], que no se usa de modo que M [ j ] corresponde a una subsecuencia de longitud j . Una implementación real puede omitir M [0] y ajustar los índices en consecuencia.
Tenga en cuenta que, en cualquier punto del algoritmo, la secuencia
- X [M [1]], X [M [2]], ..., X [M [L]]
esta incrementando. Porque, si hay una subsecuencia creciente de longitud j ≥ 2 que termina en X [M [ j ]], entonces también hay una subsecuencia de longitud j -1 que termina en un valor menor: es decir, la que termina en X [P [M [ j ]]]. Por lo tanto, podemos hacer búsquedas binarias en esta secuencia en tiempo logarítmico.
El algoritmo, entonces, procede de la siguiente manera:
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/1/1d/LISDemo.gif/400px-LISDemo.gif)
P = matriz de longitud NM = matriz de longitud N + 1L = 0para i en el rango de 0 a N-1: // Búsqueda binaria del mayor positivo j ≤ L // tal que X [M [j]]lo = 1 hola = L mientras lo ≤ hi: mid = ceil ((lo + hi) / 2) si X [M [medio]] lo = mid + 1 otra cosa : hola = mid-1 // Después de buscar, lo es 1 mayor que el // longitud del prefijo más largo de X [i] newL = lo // El predecesor de X [i] es el último índice de // la subsecuencia de longitud newL-1 P [i] = M [newL-1] M [newL] = i si nuevoL> L: // Si encontramos una subsecuencia más larga que cualquiera que hayamos // encontrado todavía, actualiza L L = nuevoL// Reconstruir la subsecuencia creciente más largaS = matriz de longitud Lk = M [L]para i en el rango L-1 a 0: S [i] = X [k] k = P [k]volver S
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 Big O como O ( n log n ). Fredman (1975) analiza una variante de este algoritmo, que atribuye a Donald Knuth ; en la variante que estudia, el algoritmo prueba si cada valor X [ i ] puede usarse para extender la secuencia creciente más larga actual, en tiempo constante, antes de hacer la búsqueda binaria. Con esta modificación, el algoritmo utiliza como máximo n log 2 n - n log 2 log 2 n + O ( n ) comparaciones en el peor de los casos, que es óptimo para un algoritmo basado en comparación hasta el factor constante en el O ( n ) término. [5]
Límites de longitud
De acuerdo con el teorema de Erdős-Szekeres , cualquier secuencia de n 2 +1 enteros distintos tiene una subsecuencia creciente o decreciente de longitud n + 1. [6] [7] Para entradas en las que cada permutación de la entrada es igualmente probable, el La longitud esperada de la subsecuencia creciente más larga es aproximadamente 2 √ n . [8] En el límite cuando n se acerca al infinito, la longitud de la subsecuencia creciente más larga de una secuencia permutada aleatoriamente de n elementos tiene una distribución que se acerca a la distribución de Tracy-Widom , la distribución del valor propio más grande de una matriz aleatoria en la unitaria gaussiana conjunto . [9]
Algoritmos online
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 F - o, alternativamente, los elementos de una permutación aleatoria - se presentan uno a la vez a un algoritmo que debe decidir si incluir o excluir cada elemento, sin conocimiento de los elementos posteriores. En esta variante del problema, que permite aplicaciones interesantes en varios contextos, es posible idear un procedimiento de selección óptimo que, dada una muestra aleatoria de tamaño n como entrada, generará una secuencia creciente con una longitud máxima esperada de tamaño aproximadamente √ 2n . [10] La longitud de la subsecuencia creciente seleccionada por este procedimiento óptimo tiene una varianza aproximadamente igual a √ 2n / 3 , y su distribución límite es asintóticamente normal después del centrado y escalado habituales. [11] Los mismos resultados asintóticos se mantienen con límites más precisos para el problema correspondiente en el contexto de un proceso de llegada de Poisson. [12] Un refinamiento adicional en la configuración del proceso de Poisson se da a través de la demostración de un teorema del límite central para el proceso de selección óptimo que se mantiene, con una normalización adecuada, en un sentido más completo de lo que cabría esperar. La demostración produce 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. [13]
Solicitud
- Parte del sistema MUMmer (Buscador de coincidencias únicas máximas) para alinear genomas completos.
- Se utiliza en sistemas de control de versiones como Git, etc.
- Se utiliza en Patience Diff, un algoritmo de diferenciación (calcula y muestra las diferencias entre el contenido de los archivos), que se utiliza en el "Bazaar" (Bazaar es un sistema de control de versiones que le ayuda a realizar un seguimiento del historial del proyecto a lo largo del tiempo y a colaborar fácilmente con otros ..)
Ver también
- Clasificación de paciencia , una técnica eficaz para encontrar la longitud de la subsecuencia creciente más larga
- Monoide plactico , un sistema algebraico definido por transformaciones que preservan la longitud de la subsecuencia creciente más larga
- Anatoly Vershik , un matemático ruso que estudió las aplicaciones de la teoría de grupos a las subsecuencias crecientes más largas
- Subsecuencia común más larga
- La subsecuencia alterna más larga
Referencias
- ^ Aldous, David ; Diaconis, Persi (1999), "Las subsecuencias crecientes más largas: de la clasificación de la paciencia al teorema de Baik-Deift-Johansson", Boletín de la Sociedad Matemática Americana , 36 (04): 413-432, doi : 10.1090 / S0273-0979-99 -00796-X.
- ^ a b Schensted, C. (1961), "Las subsecuencias crecientes y decrecientes más largas", Canadian Journal of Mathematics , 13 : 179-191, doi : 10.4153 / CJM-1961-015-3 , MR 0121305.
- ^ Hunt, 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 .
- ^ Golumbic, MC (1980), Teoría algorítmica de gráficos y gráficos perfectos , Ciencias de la computación 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.), Probabilidad discreta y algoritmos (PDF) , Volúmenes IMA en matemáticas y sus aplicaciones, 72 , Springer-Verlag, págs. 111-131.
- ^ Vershik, AM ; Kerov, CV (1977), "Asintótica de la medida Plancheral del grupo simétrico y una forma limitante para cuadros de Young", Dokl. Akad. Nauk SSSR , 233 : 1024–1027.
- ^ Baik, Jinho; Deift, 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, Stephen. 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
- ^ Arlotto, Alessandro; Nguyen, Vinh V .; Steele, J. Michael (2015), "Selección en línea óptima 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
- ^ 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.
- ^ 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.
enlaces externos
- La subsecuencia creciente más larga del algoritmo
- Subsecuencia creciente simplificada más larga
- Encontrar el recuento de las subsecuencias aumentadas más largas
- La dieta de Poldo