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).

Programación Dinámica

Programación dinámica

En informática, la programación dinámica es un método para reducir el tiempo de ejecución de un algoritmo mediante la utilización de subproblemas superpuestos y subestructuras óptimas, como se describe a continuación.

El matemático Richard Bellman inventó la programación dinámica en 1953.

Introducción

Una subestructura óptima significa que se pueden usar soluciones óptimas de subproblemas para encontrar la solución óptima del problema en su conjunto. Por ejemplo, el camino más corto entre dos vértices de un Grafo se puede encontrar calculando primero el camino más corto al objetivo desde todos los vértices adyacentes al de partida, y después usando estas soluciones para elegir el mejor camino de todos ellos. En general, se pueden resolver problemas con subestructuras óptimas siguiendo estos tres pasos:

1. Dividir el problema en subproblemas más pequeños.
2. Resolver estos problemas de manera óptima usando este proceso de tres pasos recursivamente.
3. Usar estas soluciones óptimas para construir una solución óptima al problema original.

Los subproblemas se resuelven a su vez dividiéndolos en subproblemas más pequeños hasta que se alcance el caso fácil, donde la solución al problema es trivial.

Decir que un problema tiene subproblemas superpuestos es decir que se usa un mismo subproblema para resolver diferentes problemas mayores. Por ejemplo, en la Sucesión de Fibonacci (F3 = F1 + F2 y F4 = F2 + F3) calcular cada término supone calcular F2. Como para calcular F5 hacen falta tanto F3 como F4, una mala implementación para calcular F5 acabará calculando F2 dos o más veces. Esto sucede siempre que haya subproblemas superpuestos: una mala implementación puede acabar desperdiciando tiempo recalculando las soluciones óptimas a subproblemas que ya han sido resueltos anteriormente.

Esto se puede evitar guardando las soluciones que ya hemos calculado. Entonces, si necesitamos resolver el mismo problema más tarde, podemos obtener la solución de la lista de soluciones calculadas y reutilizarla. Este acercamiento al problema se llama Memorización (en inglés "Memorization"). Si estamos seguros de que no volveremos a necesitar una solución en concreto, la podemos descartar para ahorrar espacio. En algunos casos, podemos calcular las soluciones a problemas que de antemano sabemos que vamos a necesitar.

es ligeramente mejor en consumo de espacio y llamadas a funciones, pero a veces resulta poco intuitivo encontrar todos los subproblemas necesarios para resolver un problema dado.

Originalmente, el término de programación dinámica se refería a la resolución de ciertos problemas y operaciones fuera del ámbito de la Ingeniería Informática, al igual que hacía la Programación lineal. Aquel contexto no tiene relación con la Programación en absoluto; el nombre es una coincidencia. El término también lo usó en los años 40 Richard Bellman, un matemático norteamericano, para describir el proceso de resolución de problemas donde hace falta calcular la mejor solución consecutivamente.

Algunos lenguajes de programación funcionales, sobre todo Haskell, pueden usar la Memorización automáticamente sobre funciones con un conjunto concreto de argumentos, para acelerar su proceso de evaluación. Esto sólo es posible en funciones que no tengan efectos secundarios, algo que ocurre en Haskell pero no tanto en otros lenguajes.

Principio de optimalidad

Cuando hablamos de optimizar nos referimos a buscar alguna de las mejores soluciones de entre muchas alternativas posibles. Dicho proceso de optimización puede ser visto como una secuencia de decisiones que nos proporcionan la solución correcta. Si, dada una subsecuencia de decisiones, siempre se conoce cuál es la decisión que debe tomarse a continuación para obtener la secuencia óptima, el problema es elemental y se resuelve trivialmente tomando una decisión detrás de otra, lo que se conoce como estrategia voraz.

A menudo, aunque no sea posible aplicar la estrategia voraz, se cumple el principio de optimalidad de Bellman que dicta que «dada una secuencia óptima de decisiones, toda subsecuencia de ella es, a su vez, óptima». En este caso sigue siendo posible el ir tomando decisiones elementales, en la confianza de que la combinación de ellas seguirá siendo óptima, pero será entonces necesario explorar muchas secuencias de decisiones para dar con la correcta, siendo aquí donde interviene la programación dinámica.

Contemplar un problema como una secuencia de decisiones equivale a dividirlo en subproblemas más pequeños y por lo tanto más fáciles de resolver como hacemos en Divide y Vencerás, técnica similar a la de programación dinámica. La programación dinámica se aplica cuando la subdivisión de un problema conduce a:

• Una enorme cantidad de subproblemas.
• Subproblemas cuyas soluciones parciales se solapan.
• Grupos de subproblemas de muy distinta complejidad.

Ejemplos

Coeficientes binomiales

El algoritmo recursivo que calcula los coeficientes binomiales resulta ser de complejidad exponencial por la repetición de los cálculos que realiza. No obstante, es posible diseñar un algoritmo con un tiempo de ejecución de orden O(nk) basado en la idea del Triángulo de Pascal, idea claramente aplicable mediante programación dinámica. Para ello es necesaria la creación de una tabla bidimensional en la que ir almacenando los valores intermedios que se utilizan posteriormente.

La idea recursiva de los coeficientes binomiales es la siguiente:

 =  +  si 0 < k < n

 =  = 1

La idea para construir la tabla de manera eficiente y sin valores inútiles es la siguiente:

	0	1	2	3	...	k-1	k
0	1
1	1	1
2	1	2	1
3	1	3	3	1
...	...	...	...	...	...
...	...	...	...	...	...	...
n-1						C(n-1,k-1)	C(n-1,k)
n							C(n,k)

El siguiente algoritmo memorizado de estrategia Bottom-up tiene complejidad polinómica y va rellenando la tabla de izquierda a derecha y de arriba abajo:

   FUNC CoeficientesPolinomiales ( ↓ n, k: NATURAL): NATURAL
Variables
    tabla: TABLA DE NATURAL
    i, j: NATURAL
Inicio
    PARA i ← 0 HASTA n HACER
        tabla[i][0] ← 1
    FINPARA
    PARA i ← 1 HASTA n HACER
        tabla[i][1] ← i
    FINPARA
    PARA i ← 2 HASTA k HACER
        tabla[i][i] ← 1
    FINPARA
    PARA i ← 3 HASTA n HACER
        PARA j ← 2 HASTA i-1 HACER
            SI j <= k ENTONCES
                tabla[i][j] ← tabla[i-1][j-1] + tabla[i-1][j]
            FINSI
        FINPARA
    FINPARA
    devolver tabla[n][k]
   Fin

Por supuesto, el problema de los Coeficientes Binomiales también puede resolverse mediante un enfoque Top-down.

El viaje más barato por el río

En un río hay n embarcaderos, en cada uno de los cuales se puede alquilar un bote para ir a otro embarcadero que esté más abajo en el río. Suponemos que no se puede remontar el río. Una tabla de tarifas indica los costes de viajar entre los distintos embarcaderos. Se supone que puede ocurrir que un viaje entre i y j salga más barato haciendo escala en k embarcaderos que yendo directamente.

El problema consistirá en determinar el coste mínimo para un par de embarcaderos.

Vamos a llamar a la tabla de tarifas, T. Así, T[i,j] será el coste de ir del embarcadero i al j. La matriz será triangular superior de orden n, donde n es el número de embarcaderos.

La idea recursiva es que el coste se calcula de la siguiente manera:

C(i, j) = T[i, k] + C(k, j)

A partir de esta idea, podemos elaborar una expresión recurrente para la solución:

              0   si i = j
C(i, j)=
           Min(T(i,k) + C(k,j), T(i,j))   si i < k <= j

Un algoritmo que resuelve este problema es el siguiente, donde T es la matriz de tarifas, origen y destino los embarcaderos del que se parte y al que se llega respectivamente, y C la matriz en la que almacenaremos los resultados de los costes. La función MenorDeLosCandidatos devuelve el menor coste entre dos puntos, utilizando como base la recurrencia anteriormente expuesta.

   FUNC Embarcaderos ( ↓ origen, destino, n: NATURAL, ↓ T: MATRIZ DE NATURAL): NATURAL
Variables
    C: MATRIZ DE NATURAL
    i, j: NATURAL
Inicio
    PARA i ← 1 HASTA n HACER
        C[i][i] ← 0
    FINPARA
    PARA i ← 1 HASTA n HACER
        PARA j ← 1 HASTA n HACER
            C[i][j] ← menorDeLosCandidatos(i, j, n, T, C)
        FINPARA
    FINPARA
    devolver C[n] [n]
   Fin

   FUNC menorDeLosCandidatos ( ↓ origen, destino, n: NATURAL, ↓ T, C: MATRIZ DE NATURAL): NATURAL
Variables
    temp: NATURAL
Inicio
    temp ← MAX_NATURAL
    PARA i ← origen+1 HASTA n HACER
        temp ← min(temp, T[origen][i] + C[i][destino]
    FINPARA
    devolver temp
   Fin

Referencias

• Xumari, G.L. Introduction to dynamic programming. Wilwy & Sons Inc., New York. 1967.

HEAP SORT

Proviene del inglés y significa ordenamiento por montículos. Es un algoritmo de ordenación no recursivo, no estable, con complejidad computacional O (n log n).

Este algoritmo consiste en almacenar todos los elementos del vector a ordenar en un stack(heap), y luego extraer el nodo que queda como nodo raíz del montículo (cima) en sucesivas iteraciones obteniendo el conjunto ordenado. Basa su funcionamiento en una propiedad de los montículos, por la cual, la cima contiene siempre el menor elemento (o el mayor, según se haya definido el montículo) de todos los almacenados en él.

Descripción

1. Construir un Heap sobre el arreglo a ordenar (BUILD_HEAP), en orden contrario al orden de ordenación. Por ejemplo, para ordenar ascendentemente un arreglo se construye un HEAP sobre él de forma descendiente (el mayor elemento queda en la raíz)
2. Intercambiar la raíz del Heap, posición 0, con la ultima posición en el Heap.
3. Disminuir el tamaño del Heap.
4. Reconstruir el Heap aplicando Heapify en la primera posición.
5. Repetir los pasos 2, 3 y 4 mientras el tamaño del Heap sea mayor que uno.

Complejidad del algoritmo

• La operación (1), BUILD_HEAP, es O(n log n).
• Las operaciones (2) y (3) son O(1).
• La operación (4), HEAPIFY tiene O(log n).
• Las operaciones (2), (3) y (4) se ejecutan n-1 veces por lo que el algoritmo es 0(nlog n).

Pseudocódigo

HEAPSORT( T[ ] A, entero n) { 
 BUILD_HEAP(A, n);           (1) 
 mientras(n > 1) 
 { Intercambiar(A, 0, n- 1); (2) 
   n--;                      (3) 
 HEAPIFY(A, 0, n);           (4) 
 } 
} 

Github

https://github.com/ingenierajessica/Algoritmos/blob/master/Heap%20Sort.ipynb

Conceptos

Árbol binario

Un árbol binario es una estructura de datos de árbol en la que cada nodo padre puede tener como máximo dos hijos.

Propiedades

• Fue el primer algoritmo que surgió de los que ordenan en O(n log n).
• Ordena en el lugar
  • No utiliza memoria auxiliar
• No es Estable

Ejemplos

Material de Apoyo

Algoritmo de ordenamiento: Heap Sort

Radix Sort

¿Que es Radix Sort?

¿Qué es Radix Sort (Ordenamiento)?

Es un algoritmo de ordenamiento conocido en el mundo de la programación que ordena enteros a partir de sus dígitos de forma individual.

El siguiente ejemplo funciona con una lista desordenada de números.

1. En primer lugar los va ordenando tomando en consideración el número menos significativo (la unidad) del más pequeño al más grande. Como se muestra en el punto 1.
2. Luego, a partir de la lista que obtuvimos en el paso anterior, ordenamos los números de menor a mayor considerando esta vez la decena de cada uno de ellos. Como se observa en el punto 2.
3. Finalmente comprobamos que la lista fue ordenada satisfactoriamente mediante este procedimiento.

Pseudocódigo

radixSort(array)
  d <- maximum number of digits in the largest element
  create d buckets of size 0-9
  for i <- 0 to d
    sort the elements according to ith place digits using countingSort

countingSort(array, d)
  max <- find largest element among dth place elements
  initialize count array with all zeros
  for j <- 0 to size
    find the total count of each unique digit in dth place of elements and
    store the count at jth index in count array
  for i <- 1 to max
    find the cumulative sum and store it in count array itself
  for j <- size down to 1
    restore the elements to array
    decrease count of each element restored by 1

Github 

https://github.com/ingenierajessica/Algoritmos/blob/master/Counting%20Sort.ipynb

Ejemplo

Otros ejemplos

Material de Apoyo

• 7. Counting Sort, Radix Sort, Lower Bounds for Sorting
• https://youtu.be/XiuSW_mEn7g