Aplicaciones de la subcuencia de mayor aumento

Question

¿Qué tan útil es el problema de LIS (Longest Increasing Subsequence) al abordar otros problemas de CS? Hay algunos algoritmos, que usan la clasificación por paciencia, la programación dinámica o con árboles de decisión. ¿Cómo se usan en la vida real, tal vez en flujos de datos o algo así?

Para recordarle, I poner en negrita la secuencia más larga creciente

{, 8, 4, 12, , 10, , 14, 1, , 5 , 13, 3, , 7, }.

Como beneficio adicional, ¿hay alguna forma de utilizar el resultado que a sequence of length mn + 1 will have an increasing subsequence of length m or a decreasing subsequence of length n? P.ej. Nuestra lista es de longitud 16, por lo que debe haber una secuencia creciente de longitud 5 o una secuencia decreciente de longitud 5. En nuestro caso 0,2,6,9,11,15.

También una secuencia creciente de longitud 8 o una secuencia decreciente de longitud 3: en nuestro caso 12,10,1.

Answer 1

Una aplicación en el mundo real interesante de LIS es la paciencia de diferencias, un algoritmo diffing por Bram Cohen (el creador de BitTorrent) que se utiliza en el sistema de control de versiones Bazaar.

El algoritmo de diferencia regular implica calcular el LCS (Longest Common Subsequence) entre dos documentos. Si bien es eficiente, este enfoque tiene un problema, que es - los resultados a menudo no son muy amigables para los humanos.

Un ejemplo sencillo de cómo un diff regular puede fallar:

void func1() { 
    x += 1 
+} 
+ 
+void functhreehalves() { 
+ x += 1.5 
} 

void func2() { 
    x += 2 
} 

La ventaja de la paciencia algoritmo Dif es que permite calcular las diferencias con mayor precisión, de una manera más estrecha correspondiente a la forma en un ser humano se realizaría.

En el caso anterior paciencia Dif spots mejor la diferencia:

void func1() { 
    x += 1 
} 

+void functhreehalves() { 
+ x += 1.5 
+} 
+ 
void func2() { 
    x += 2 
} 

En pocas palabras, el algoritmo es:

1. Encuentra líneas únicas que son comunes a ambos documentos.
2. Tome todas esas líneas del primer documento y pídalas según su apariencia en el segundo documento.
3. Calcule el LIS de la secuencia resultante (haciendo un Patience Sort), obteniendo la secuencia de líneas más larga que coincida, una correspondencia entre las líneas de dos documentos.
4. Vuelva a ejecutar el algoritmo en cada rango de líneas entre las ya emparejadas.

Eche un vistazo a the code.