Embed Size (px)
Citation preview
Computabilidad y Complejidad de Algoritmos
Programación Dinámica
Preparado por:
Solineth Batista
Maycol Requenez
Universidad de PanamáFacultad de Informática,
Electrónica y Comunicación
Existe una serie de problemas cuyas soluciones pueden ser expresadas recursivamente en términos matemáticos, y posiblemente la manera más natural de resolverlos es mediante un algoritmo recursivo. Sin embargo, el tiempo de ejecución de la solución recursiva, normalmente de orden exponencial y por tanto impracticable, puede mejorarse substancialmente mediante la Programación Dinámica.
Introducción
En el diseño Divide y Vencerás para resolver un problema lo dividimos en subproblemas independientes, los cuales se resuelven de manera recursiva para combinar finalmente las soluciones y así resolver el problema original. El inconveniente se presenta cuando los subproblemas obtenidos no son independientes sino que existe solapamiento entre ellos; entonces es cuando una solución recursiva no resulta eficiente por la repetición de cálculos que conlleva.
Introducción
En estos casos es cuando la Programación Dinámica nos puede ofrecer una solución aceptable. La eficiencia de esta técnica consiste en resolver los subproblemas una sola vez, guardando sus soluciones en una tabla para su futura utilización. La Programación Dinámica no sólo tiene sentido aplicarla por razones de eficiencia, sino porque además presenta un método capaz de resolver de manera eficiente problemas cuya solución ha sido abordada por otras técnicas y ha fracasado.
Introducción
Donde tiene mayor aplicación la Programación Dinámica es en la resolución de problemas de optimización. En este tipo de problemas se pueden presentar distintas soluciones, cada una con un valor, y lo que se desea es encontrar la solución de valor óptimo (máximo o mínimo).
Aplicabilidad
La solución de problemas mediante esta técnica se basa en el llamado principio de óptimo enunciado
por Bellman en 1957 y que dice:
“En una secuencia de decisiones óptima toda subsecuencia ha de ser también óptima”.
Principio de Optimalidad
Ejemplos de AplicacionesKnapsack Problem (Problema de la Mochila)Algoritmo de Needleman–Wunsch
Knapsack Problem
Knapsack Problem
El problema de la mochila (knapsack problem) consiste encontrar un subconjunto de productos que echar en una mochila de modo de maximizar el beneficio y no sobrepasar la capacidad de la mochila.
Se puede resumir el problema de la siguiente forma:
Donde l es la cantidad de objetos disponibles, bi es el beneficio que ofrece el objeto i, pi es el peso del objeto i, xi nos indica si colocamos o no el objeto i dentro de la mochila y P es el peso máximo que soporta la mochila.
maximizar bixiik
l
sujeto a pixiik
l P
con xi {0,1}, k i l
Knapsack ProblemDigamos que tenemos l objetos con pesos p1, …,pl y
beneficios b1, …,bl.Definimos A(i, j) como el valor máximo que puede
ser obtenido con los primeros i objetos pesando a lo más j.
Note que: A(0, j) = 0 y A(i, 0) = 0 para cualquier i ≤ l y j ≤ P. Si pi > j entonces A(i, j) = A(i – 1, j). Si pi ≤ j entonces A(i, j) tiene dos opciones incluir o no
incluir el objeto i. Si no lo incluimos entonces tendrá un valor de A(i – 1, j). Si lo incluimos entonces tendrá un valor de A(i – 1, j – pi) + bi.
Knapsack ProblemExpresado formalmente tenemos la siguiente
definición recursiva.
1
0 si 0 o 0
, 1, si
max 1, , , si
i
i i
i j
A i j A i j p j
A i j A i j j p b p j
Knapsack ProblemEjemplo:
Tenemos una caja que soporta 15 libras en la cual vamos a colocar objetos para vender. Hay disponibles tres objetos:Objeto #1 pesa 9 libras y se vende a $38Objeto #2 pesa 6 libras y se vende a $40Objeto #3 pesa 5 libras y se vende a $24
¿Cuál es la ganancia máxima que podemos obtener?
Knapsack ProblemContinuación ejemplo:
La información recopilada del algoritmo se puede resumir en la siguiente tabla:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15p1 9 0 0 0 0 0 0 0 0 0 38 38 38 38 38 38 38p2 6 0 0 0 0 0 0 40 40 40 40 40 40 40 40 40 78p3 5 0 0 0 0 0 24 40 40 40 40 40 64 64 64 64 78
Knapsack ProblemContinuación ejemplo:
La información recopilada del algoritmo se puede resumir en la siguiente tabla:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15p1 9 0 0 0 0 0 0 0 0 0 38 38 38 38 38 38 38p2 6 0 0 0 0 0 0 40 40 40 40 40 40 40 40 40 78p3 5 0 0 0 0 0 24 40 40 40 40 40 64 64 64 64 78
Needleman–Wunsch Algorithm
Needleman–Wunsch AlgorithmUno de los problemas de todos los días en
Bioinformática es la comparación o alineamiento de secuencias. Necesitamos saber que tan similares son dos secuencias, permitiendo que haya pequeñas diferencias ya sea de reemplazo o de borrado entre una y otra.
El algoritmo de Needleman-Wunsch sirve para realizar alineamientos globales de dos secuencias.
Fue propuesto por primera vez en 1970, por Saul Needleman y Christian Wunsch.
El algoritmo calcula puntajes de similitud global entre dos secuencias.
Needleman–Wunsch Algorithm
EjemploConsideremos el conjunto {A, G, C, T} sobre el
cual definimos dos cadenas s1 = GAATTCAGTTA y s2 = GGATCGA.
El objetivo del algoritmo es alinearlas de tal forma que puedan identificarse huecos, inserciones o cambios en los caracteres de las secuencias.
Para el ejemplo un alineamiento es el siguiente:
s
Needleman–Wunsch Algorithm
El algoritmo de Needleman-Wunsch busca generar el alineamiento para lo cual coloca todas las posibles combinaciones de las dos secuencias s1 y s2 más una fila y columna de ceros para la generación de la recursividad, en una matriz M.
Definiendo a n = |s1| y a m = |s2| entonces la matriz M será de tamaño (m +1) × (n + 1).
Needleman–Wunsch Algorithm
Luego procedemos a rellenar la matriz M para lo cual primero definimos una matriz S de semejanza de caracteres.
Needleman–Wunsch Algorithm
Si definimos Si;j como una función tal que devuelve la similitud de los caracteres de la posición i de s1 y j de s2 y a W como la penalización por hueco que en este caso es simplemente 0, tendremos listo las funciones necesarias para llenar la matriz M.
Para proceder a rellenar M tendrán la siguiente ley de formación:
Donde: Indica la coincidencia o no coincidencia
de los caracteres de las secuencias.
Indica la suma en horizontal más la penalización por hueco.
Indica la suma en vertical más la penalización por hueco.
, 1, 1 , , 1 1,max , ,i j i j i j i j i jM M S M W M W
1, 1 ,i j i jM S
, 1i jM W
1,i jM W
Needleman–Wunsch Algorithm
Needleman–Wunsch Algorithm
Needleman–Wunsch Algorithm
Needleman–Wunsch Algorithm
Needleman–Wunsch Algorithm
Needleman–Wunsch Algorithm
Needleman–Wunsch Algorithm
El procedimiento siguiente es describir el patrón que se dibuja desde el extremo inferior derecho de la matriz M y se avanza a la izquierda o a la izquierda y arriba tomando siempre el valor que le precedió al construir M.
Needleman–Wunsch Algorithm
Needleman–Wunsch Algorithm
Needleman–Wunsch Algorithm
Needleman–Wunsch Algorithm
Needleman–Wunsch Algorithm
G A A T T C A G T T A
| | | | | |
G G A ― T C ― G ― ― A
Dando el alineamiento:
