Subseción común máxima LCS (Programación Dinámica)

Descripción

La subsucesión común máxima de dos arreglos (pueden ser cadenas), es la subsucesión que se encuentra tanto en el primer arreglo, como en el segundo, y es de longitud máxima. Al igual que en el problema anterior, los elementos de la subsucesión no necesariamente son adyacentes. Esta subsucesión es útil en problemas genéticos, principalmente para encontrar relaciones entre cadenas de ADN.

Un enfoque simple es crear todas las subsucesiones del primer arreglo y revisar si pertenecen al segundo. El problema es que existe una cantidad exponencial de estas subsucesiones, por lo que este método no es muy útil.

Podemos utilizar técnicas de programación dinámica para obtener un algoritmo polinomial, gracias a que está subsucesión tienes subestructuras óptimas. Teniendo dos sucesiones, la subsucesión común máxima la obtenemos de alguno de los siguientes dos casos:

• Si el último elemento de las sucesiones son iguales, entonces ese elemento pertenece a la subsucesión máxima y el resto de los elementos los obtenemos del restante de las sucesiones. Por ejemplo, si tenemos las cadenas ‘abd’ y ‘akd’, ‘d’ forma parte de la subsucesión y el resto lo obtenemos de ‘ab’ y ‘ak’.
• Si estos elementos son distintos, entonces podemos obtener la subsucesión máxima quitando algunos de los dos. Para ver cual de los dos quitamos, necesitamos saber la subsucesión máxima de ambos casos y nos quedamos con la mayor.

GitHub

https://github.com/ingenierajessica/Algoritmos/blob/master/Algoritmo%20Subsecuencia%20Com%C3%BAn%20m%C3%A1s%20larga.ipynb

Ejemplo

 Problema

Dadas dos sucesiones de caracteres, encuentra la longitud de la subsucesión común máxima entre ambas. Por ejemplo, la subsucesión común máxima de las siguientes dos sucesiones:

abcdgh
aedfhres adh, de longitud 3.

Entrada

Cada caso en la entrada consiste en un par de líneas. La primera línea contiene la primera cadena, y la segunda línea a la segunda cadena. Cada cadena está en una línea por separado y consiste a lo más de 1,000 caracteres.

Salida
Por cada par de línea en la entrada, la salida deberá tener una línea con un entero que cumpla con lo pedido. 


Solución: Utilizamos las propiedades anteriores para codificar el algoritmo de la subsucesión común máxima e imprimimos el tamaño de esta.

Código

En el primer par de líneas tenemos las variables que vamos a utilizar. Como el tamaño máximo del problema es mayor a 255, no podemos utilizar una cadena convencional (en Pascal). Por suerte, muchos compiladores recientes nos permiten utilizar arreglos de caracteres como cadenas en algunas funciones.

En la función max (líneas 4 a 8) calculamos el mayor de dos número. Lo único que hacemos es compararlos y devolver el de mayor valor. Aunque esta función no parece muy útil, hace que los códigos sean más legibles.

En seguida tenemos la función en la que calculamos el tamaño de la subsucesión. Como parámetros tenemos m y n que son los tamaños de las cadenas, y como variables tenemos i y j para los ciclos, y x e y para guardar los valores del renglón anterior y del renglón actual. Comenzamos inicializando el renglón a ceros (línea 14). Para cada renglón, empezamos respaldando el renglón anterior (línea 17), y revisamos todos los caracteres del renglón. Si los dos caracteres son iguales, tomamos el tamaño máximo sin ese caracter y lo incrementamos en uno; en caso de que sean diferentes, tomamos el mayor de remover cualquiera de los dos.

Entre las líneas 25 y 32 tenemos la parte principal del código. Lo que hacemos en esta parte es leer las cadenas (líneas 28 y 29), e imprimir la longitud de subsucesión común máxima. Repetimos esto hasta que lleguemos al final del archivo.

Posibles Cambios

Si además del tamaño, queremos saber cual es la cadena, podemos hacerlo guardando información extra en cada casilla. Al calcular el tamaño máximo, guardamos en la casilla cual fue la anterior. Para construir la cadena, empezamos por la última casilla (posición (m, n)) y nos vamos regresando a cada casilla anterior. Cuando al regresar nos movemos en diagonal es porque ese elemento es parte de la subsucesión. Terminamos cuando lleguemos a la primera casilla (posición (0,0)). Por esta razón, necesitamos guardar toda la matriz en lugar de sólo los últimos renglones. Como estamos recorriendo la matriz del final al inicio, los elementos los obtendremos en orden inverso.

Podemos también ahorrarnos la matriz auxiliar para el recorrido si nos fijamos en los valores de la matriz (de forma similar a lo que haremos en la siguiente sección).