Problema de la subsecuencia más larga

En Ciencias de la Computación, el problema de la subsecuencia creciente máxima consiste en encontrar una subsecuencia de una secuencia dada donde los elementos de la subsecuencia están ordenados, de menor a mayor, y la subsecuencia sea tan larga como sea posible. Esta subsecuencia no es necesariamente continua, o única. La subsecuencias crecientes máximas son estudiadas por varias disciplinas relacionadas con las matemáticas, incluyendo algoritmos, física y teorías de matriz aleatoria.[1]​ El problema de la subsecuencia creciente máxima es soluble en O(n log n), donde n denota el tamaño de la secuencia de entrada.[2]​

Ejemplo

En los primeros 16 términos de la secuencia de Van der Corput binaria

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

una subsecuencia creciente máxima es

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

Esta subsecuencia tiene longitud seis; la subsecuencia de entrada no tiene subsecuencias crecientes de tamaño siete. La subsecuencia creciente máxima en este ejemplo no es única: por ejemplo,

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

son otras subsecuencias creciente de igual longitud para la misma subsecuencia de entrada.

Relación con otros problemas algorítmicos

El problema de la subsecuencia creciente máxima está estrechamente relacionado con el problema de subsecuencia común más larga, que tiene una solución de programación dinámica en tiempo cuadrático: la subsecuencia creciente máxima de una secuencia S es la subsecuencia común máxima de S y T, donde T es el resultado de ordenar S. Sin embargo, para el caso especial en que la entrada es una permutaciòn de enteros 1, 2, ..., n, esta propuesta puede ser ejecutada mucho más eficientemente , llegando a un tiempo de la forma O(n log log n).[3]​

El clique mayor en un grafo de permutación está definido por la subsecuencia decreciente máxima de la permutación que define al grafo; la subsecuencia decreciente máxima es equivalente en complejidad computacional, utilizado el opuesto de los números de entrada, a la subsecuencia creciente máxima. Así, los algoritmos de la subsecuencia creciente máxima pueden ser usados para resolver el problema del clique eficientemente en permutation graphs.[4]​

En la correspondencia Robinson–Schensted entre permutaciones y la tabla de Young, la longitud de la primera fila de la tabla correspondiente a la permutaciónes 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 más larga.[2]​

Algoritmos eficientes

El algoritmo descrito abajo resuelve el problema de la subsecuencia creciente más larga eficientemente con arreglos y búsqueda binaria. Se procesa la secuencia de elementos en orden, manteniendo la subsecuencia creciente máxima encontrada hasta el punto actual. Denotando los valores de la secuencia como X[0], X[1], etc. Entonces, luego de procesar X[i], el algoritmo tendrá almacenado valores en dos arreglos:

M[j] — almacena el índice k del menor valor X[k] tal que existe una

subsecuencia creciente de longitud j que termina en X[k] en el rango k ≤ i. Note que j ≤ k ≤ i, pues j representa la longitud de la subsecuencia creciente, y k representa el índice de su terminación. No puede haber una subsecuencia creciente de longitud 13 terminando en el índice 11. k ≤ i por definición.

P[k] — almacena el índice del predecesor de X[k] en la subsecuencia creciente

máxima que termina en X[k]. Además, el algoritmo cuenta con una variable L representando la longitud de la subsecuencia creciente máxima que se va calculando. Dado que el algoritmo usa numeración con base cero, para mayor claridad M es iniciada con M[0], que será aprovechado de tal forma que M[j] corresponde a la subsecuencia de longitud j. Una implementación real puede saltarse M[0] y ajustar los índices.

Note que, en cualquier punto del algoritmo, la secuencia

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

es nodecreciente. Para, si existe una subsecuencia creciente de longitud i terminando en X[M[i]], entonces existe también una subsecuencia de longitud i-1 terminando en un valor más pequeño: concretamente el que termina en X[P[M [i]]]. Así, es posible una búsqueda binaria en esta secuencia en tiempo logarítmico.

El algoritmo, entonces, procede de la siguiente forma: 

 P = array of length N
 M = array of length N + 1

 L = 0
 for i in range 0 to N-1:
   // Búsqueda binaria para el positivo más grande j ≤ L
   // tal que X[M[j]] < X[i]
   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

   // Luego de buscar, lo es 1 más que la
   // 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

   if newL > L:
     // Si encontramos una subsecuencia mayor que cualquiera
     // de las ya encontradas, actualizar L
     L = newL

 // Reconstruir la subsecuencia creciente máxima
 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

Dado que el algoritmo realiza solo una búsqueda binaria por elemento de la secuencia, su tiempo total puede ser expresado usando notación O grande como O(n log n).Fredman (1975) analizó una variante para este algoritmo, que se la acredita a Donald Knuth; en la variante estudiada por él, el algoritmo examina cuando cada valor X[i]puede ser usado para extender la subsecuencia creciente máxima actual, en tiempo constante, previo a la búsqueda binaria. Con esta modificación, el algoritmo usa a lo sumo n log2 n - n log2log2 n + O(n) comparaciones en el peor caso, que es óptimo para un algoritmo basado en comparaciones para el factor constante en el término O(n).[5]​

Límites de tamaño

De acuerdo con el Teorema de Erdős–Szekeres, cualquier secuencia de n2+1 enteros diferentes tiene una subsecuencia creciente o decreciente de longitud n + 1.[6]​[7]​ Para entradas donde cada permutación de la entrada es igualmente probable, la longitud esperada de la subsecuencia creciente máxima es aproximadamente 2√n.[8]​ En el límite como n tiende al infinito, la longitud de la subsecuencia creciente más larga de una secuencia permutada de forma aleatoria de n elementos tiene una distribución aproximada a la distribución Tracy–Widom.[9]​

Véase también

Referencias

  1. ↑ Aldous, David; Diaconis, Persi (1999), «Longest increasing subsequences: from patience sorting to the Baik–Deift–Johansson theorem», Bulletin of the American Mathematical Society 36 (04): 413-432, doi:10.1090/S0273-0979-99-00796-X ..
  2. ↑ a b Schensted, C. (1961), «Longest increasing and decreasing subsequences», Canadian Journal of Mathematics 13: 179-191, MR 0121305, doi:10.4153/CJM-1961-015-3 ..
  3. ↑ Hunt, J.; Szymanski, T. (1977), «A fast algorithm for computing longest common subsequences», Communications of the ACM 20 (5): 350-353, doi:10.1145/359581.359603. .
  4. ↑ Golumbic, M. C. (1980), Algorithmic Graph Theory and Perfect Graphs, Computer Science and Applied Mathematics, Academic Press, p. 159 ..
  5. ↑ Fredman, Michael L. (1975), «On computing the length of longest increasing subsequences», Discrete Mathematics 11 (1): 29-35, doi:10.1016/0012-365X(75)90103-X ..
  6. ↑ Erdős, Paul; Szekeres, George (1935), «A combinatorial problem in geometry», Compositio Mathematica 2: 463-470 ..
  7. ↑ Steele, J. Michael (1995), «Variations on the monotone subsequence theme of Erdős and Szekeres», en Aldous, David; Diaconis, Persi; Spencer, Joel et al., eds., Discrete Probability and Algorithms, IMA Volumes in Mathematics and its Applications 72, Springer-Verlag, pp. 111-131, archivado desde [http://www- stat.wharton.upenn.edu/~steele/Publications/PDF/VOTMSTOEAS.pdf el original] el 20 de febrero de 2017, consultado el 30 de junio de 2019  ..
  8. ↑ Vershik, A. M.; Kerov, C. V. (1977), «Asymptotics of the Plancheral measure of the symmetric group and a limiting form for Young tableaux», Dokl. Akad. Nauk USSR 233: 1024-1027 ..
  9. ↑ Baik, Jinho; Deift, Percy; Johansson, Kurt (1999). «On the distribution of the length of the longest increasing subsequence of random permutations». Journal of the American Mathematical Society 12 (4): 1119-1178. arXiv:math/9810105. doi:10.1090/S0894-0347-99-00307-0. .

Enlaces externos