El problema de encontrar la mayor subsecuencia creciente
La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 8 de febrero de 2015; las comprobaciones requieren 7 ediciones .La tarea de encontrar la subsecuencia creciente más grande es encontrar la subsecuencia creciente más larga en una secuencia dada de elementos.
Planteamiento del problema
Tenga en cuenta que una subsecuencia puede no ser una subcadena (es decir, sus elementos no son necesariamente consecutivos en la secuencia original). Formalmente, para una cadena x de longitud n , es necesario encontrar el número máximo l y la correspondiente secuencia creciente de índices , tal que . La subsecuencia creciente más grande tiene aplicaciones en física, matemáticas, teoría de representación de grupos, teoría de matrices aleatorias. En el caso general, la solución de este problema se conoce en el tiempo n log n en el peor de los casos [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)
Algoritmos relacionados
- El problema de la subsecuencia creciente más grande es similar al problema de encontrar la subsecuencia común más grande que tiene una solución dinámica cuadrática.
- En el caso particular donde la cadena es una permutación de 1..n, el problema tiene una solución en n log log n [2] usando árboles de van Emde Boas .
- Al usar un árbol construido para elementos del alfabeto, es posible resolver el problema en O(n log A), donde A es la cardinalidad del alfabeto, que se determina de antemano. Cuando se implementa mediante árboles equilibrados , no es necesario especificar A antes de tiempo. Por razones obvias, A se limita a la longitud de la cadena.
- También es posible reducir el problema a encontrar el camino más largo en un gráfico acíclico dirigido especificando bordes entre elementos crecientes. Aunque el cálculo del camino más largo tomará un tiempo lineal en el número de aristas, en el peor de los casos puede ser cuadrático de la longitud de la cuerda.
Un ejemplo de un algoritmo eficiente
Presentemos un algoritmo para resolver el problema que se ejecuta en O( n log n ).
Para la cadena x , almacenaremos matrices M y P de longitud n . M[i] contiene el índice del más pequeño de los últimos elementos de subsecuencias crecientes x n j de longitud i , , encontrados en este paso. P[i] almacena el índice del carácter precedente para la subsecuencia ascendente más larga que termina en la i-ésima posición. En cada paso, almacenaremos la longitud máxima actual de la subsecuencia y el índice correspondiente del carácter final, recordando mantener las propiedades de los arreglos. Un paso es una transición al siguiente elemento de la cadena, cada transición no requerirá más que el logaritmo del tiempo (búsqueda binaria en la matriz 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
Obviamente, después de ejecutar el algoritmo, L es la longitud de la subsecuencia deseada, y los elementos mismos se pueden obtener expandiendo recursivamente P desde el elemento índice.
Notas
- ↑ Schensted, C. (1961). "Subsecuencias crecientes y decrecientes más largas". Revista Canadiense de Matemáticas 13: 179-191.
- ↑ Hunt, James W. and Szymanski, Thomas G. Un algoritmo rápido para calcular las subsecuencias comunes más largas // Commun . ACM. - ACM, 1977. - Vol. 20 , núm. 5 . - Pág. 350--353 . — ISSN 0001-0782 .