5 estrategiasalgoritmicas parte3 publicar · 2019. 6. 28. · subsecuencia: secuencia que puede...

1PROCESO DE ADMISIÓN 2019

Centro de Investigación y de Estudios Avanzados del Instituto Politécnico NacionalCinvestav - Tamaulipas

Tema:

Estrategias Algorítmicas - Parte 3

Dr. Mario Garza Fabre


Parte 1:

• Introducción

• Algoritmos voraces

• Búsqueda sistemática (Búsqueda exhaustiva, Búsqueda con retroceso, Ramificación y poda)

Parte 2:

• Divide y vencerás / Decrementa y vencerás

Parte 3:

• Programación dinámica

• Resumen y comentarios finales

Contenido


Programación Dinámica


• Existen problemas cuyas soluciones pueden ser expresadas recursivamente en términos matemáticos

• Posiblemente la manera más natural de resolver tales problemas es mediante un algoritmo recursivo

• El diseño Divide y Vencerás resulta apropiado en muchos de estos casos, como lo vimos anteriormente

• El inconveniente es cuando el problema se define en términos de subproblemas con solapamiento / traslape

Introducción


Solapamiento / traslape entre subproblemas:

Introducción

• Subproblemas no son independientes, comparten sub-subproblemas

• Resolvemos un número exponencial de subproblemas, cuando en realidad el número de subproblemas distintos es polinómico

• La solución repetida de subproblemas resulta en algoritmos muy ineficientes


Un ejemplo claro es el del cálculo (recursivo) del n-ésimotérmino de la sucesión de Fibonacci:

• Cálculo repetido de términos de la sucesión (subproblemas)

• Crecimiento exponencial del número de llamadas a la función y operaciones realizadas: ¡algoritmo ineficiente!

f(! − #) f(! − $) f(! − $) f(! − $)

f(! − %) f(! − #) f(! − #) f(! − $)

f(! − &) f(! − %)

f(!)

f(! − $)

Ejemplo:

Sucesión de Fibonacci

f! = f!(&+ f!(%f) = )

f& = &


La programación dinámica, al igual que el enfoque divide y vencerás, resuelve un problema al combinar soluciones a subproblemas más pequeños:

• Divide y vencerás: para subproblemas independientes

• Programación dinámica: aplicable cuando existe traslape / solapamiento entre subproblemas

Idea general: resolver subproblemas una única vez y almacenar las soluciones para su futura reutilización



Dos posibles enfoques:

• Enfoque descendente (top-down)

• Enfoque ascendente (bottom-up)



Enfoque descendente (top-down):

• Algoritmo recursivo → definición natural del problema

• Memoización (memoization) para mejorar eficiencia:

o Memoización: almacenar resultados de funciones, evitando repetir cálculos para entradas previamente procesadas

• Puede resultar más eficiente que el enfoque ascendente si sólo un subconjunto de los posibles subproblemas necesitan resolverse



Enfoque ascendente (bottom-up):

• Algoritmo iterativo

• Se construye una tabla exhaustiva de soluciones

• Se comienza con casos (subproblemas) triviales. Se obtienen soluciones óptimas para problemas cada vez más grandes a partir de soluciones ya tabuladas

• Puede ser más eficiente que el enfoque descendente si todos los posibles subproblemas necesitan resolverse (evita costos asociados con llamadas recursivas)



Sucesión de Fibonacci: (0, ) 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 …

Relación de recurrencia: f! = f!#$+ f!#%, con f& = & y f$ = $

Implementar algoritmo de programación dinámica para calcular el n-ésimo número de Fibonacci:

1. Enfoque descendente (top-down) – memoización

2. Enfoque ascendente (bottom-up) – tabulación

Comparar eficiencia (tiempo / subproblemas resueltos) con respecto al algoritmo recursivo (sin memoización).

Ejercicio:


Características necesarias del problema:

1. Subestructura óptima / optimalidad de subproblemas

Solución óptima al problema debe poder definirse en función de soluciones óptimas a subproblemas más simples

2. Problemas solapados / traslapados

Espacio de subproblemas debe ser pequeño (polinómico). Los mismos subproblemas pueden ser comunes a múltiples subproblemas más grandes, de manera que un algoritmo recursivo resolvería los mismos subproblemas una y otra vez


Principio de Optimalidad de Bellman:

Dada una secuencia óptima de decisiones, toda subsecuencia de ella es, a su vez, óptima


Desarrollo de un algoritmo de programación dinámica (enfoque ascendente, bottom-up):

1. Caracterizar la estructura de una solución óptima

2. Definir recursivamente el valor de una solución óptima

3. Calcular el valor de una solución óptima de manera ascendente (calcular y almacenar valor para subproblemas

pequeños, avanzar a subproblemas cada vez más grandes)

4. Construir una solución óptima a partir de la información previamente calculada y almacenada



Ejemplo:

Problema de la Mochila 0/1

Mochila de capacidad !

y " objetos:

o Valor: # = (#&, … , #")

o Costo: * = (*&, … , *")

¿Qué objetos elegir para maximizar las ganancias sin exceder la capacidad

de la mochila?

¿Cómo resolver usando

Programación Dinámica?


a) NO se incluye:

Valor de solución óptima para subproblema con los

primeros ! − # objetos y capacidad $

b) Si se incluye:

Valor de solución óptima para subproblema con los

primeros ! − # objetos y capacidad $−%&

+

Valor de !-ésimo objeto

OBSERVACIONES:

El !-ésimo objeto (último) puede incluirse o no. ¿Cuál de estas dos alternativas nos conduce a la solución óptima?

▶ Comparamos valor máximo alcanzable:

Ejemplo:


$ $− %& %&


Plantear solución óptima al problema en términos de la solución óptima de subproblemas:

• Sea !(#, %) la ganancia máxima posible (óptima) al

considerar sólo los primeros # objetos y capacidad %, 0 ≤ # ≤ ), 0 ≤ % ≤* (la meta es calcular !(),*))• Caso trivial (# = ,, no objetos o % = ,, no capacidad):

! ,, % = , y ! #, , = ,• Caso general (% > , y # > ,):

!(#, %) = .! # − 0, % , 1# > %234 ! # − 0, % , ! # − 0, % − 1# +6# , 1# ≤ %

Ejemplo:



Analicemos más detenidamente el caso general (! > # y $ > #):

%($, !) = *% $ − ,, ! , -$ > !./0 % $ − ,, ! , % $ − ,, ! − -$ +2$ , -$ ≤ !

Se excluye el $-ésimo objeto:

• Cuando no cabe en la mochila (-$ > !), o cuando si cabe (-$ ≤ !) pero no conviene incluirlo: % $ − ,, ! > 4 5 − 1, 7 − 89 + :9

• Valor máximo alcanzable: mismo que al considerar sólo los primeros $ − , objetos y misma capacidad disponible !

Se incluye el $-ésimo objeto:

• Cabe (-$ ≤ !) y conviene incluirlo: 4 5 − 1, 7 < % $ − ,, ! − -$ +2$• Valor máximo alcanzable: valor al considerar los primeros $ − ,

objetos y capacidad reducida ! − -$, más valor de objeto 2$

Ejemplo:



• Basado en esta recurrencia construimos la tabla !(#, %)

o Una fila para cada objeto ' (0 ≤ ' ≤ *)

o Una columna para cada capacidad + (0 ≤ + ≤ ℳ)

• El llenado de la tabla se comienza por casos triviales

• A partir de los valores tabulados para subproblemas

pequeños, se calculan los valores correspondientes a

subproblemas cada vez más grandes

• ! -,. corresponde al valor de la solución óptima

Ejemplo:



Ejemplo:


!\# 0 1 2 3 4 5

0

1

2

3

4

$ !, # =

$(!, #) = )*, ! = * + # = *$ ! − -, # , .! > #012 $ ! − -, # , $ ! − -, # − .! +4! , .! ≤ #

Datos del problema:

• 6= 7• 8 = 9 objetos• 4 = -*, @*, -7, @*• . = -, A, @, 9

Tabla $(!, #) con 8+ - renglones y 6+- columnas


Ejemplo:


!\# 0 1 2 3 4 5

0 0 0 0 0 0 0

1 0

2 0

3 0

4 0

$ !, # =

$(!, #) = )*, ! = * + # = *$ ! − -, # , .! > #012 $ ! − -, # , $ ! − -, # − .! +4! , .! ≤ #

Datos del problema:

• 6= 7• 8 = 9 objetos• 4 = -*, @*, -7, @*• . = -, A, @, 9

Se comienza por los casos triviales


Ejemplo:


!\# 0 1 2 3 4 5

0 0 0 0 0 0 0

1 0 10

2 0

3 0

4 0

$ !, # =

$(!, #) = )*, ! = * + # = *$ ! − -, # , .! > #012 $ ! − -, # , $ ! − -, # − .! +4! , .! ≤ #

Datos del problema:

• 6= 7• 8 = 9 objetos• 4 = -*, @*, -7, @*• . = -, A, @, 9

Celda: $(-, -)Si cabe: (BC= 1) ≤ E = 1F G − 1, E = F 0, 1 = 0F G − 1, E − BI + JI = $ *, * + -* = 10


Ejemplo:


!\# 0 1 2 3 4 5

0 0 0 0 0 0 0

1 0 10 10

2 0

3 0

4 0

$ !, # =

$(!, #) = )*, ! = * + # = *$ ! − -, # , .! > #012 $ ! − -, # , $ ! − -, # − .! +4! , .! ≤ #

Datos del problema:

• 6= 7• 8 = 9 objetos• 4 = -*, @*, -7, @*• . = -, A, @, 9

Celda: $(-, @)Si cabe: (BC= 1) ≤ E = 2G H − 1, E = G 0, 2 = 0G H − 1, E − BJ + KJ = $ *, - + -* = 10


Ejemplo:


!\# 0 1 2 3 4 5

0 0 0 0 0 0 0

1 0 10 10 10 10 10

2 0 10

3 0

4 0

$ !, # =

$(!, #) = )*, ! = * + # = *$ ! − -, # , .! > #012 $ ! − -, # , $ ! − -, # − .! +4! , .! ≤ #

Datos del problema:

• 6= 7• 8 = 9 objetos• 4 = -*, @*, -7, @*• . = -, A, @, 9

Celda: $(@, -)No cabe: (BC= 3) > E = 1G H − 1, E = $ -, - = 10


Ejemplo:


!\# 0 1 2 3 4 5

0 0 0 0 0 0 0

1 0 10 10 10 10 10

2 0 10 10 20

3 0

4 0

$ !, # =

$(!, #) = )*, ! = * + # = *$ ! − -, # , .! > #012 $ ! − -, # , $ ! − -, # − .! +4! , .! ≤ #

Datos del problema:

• 6= 7• 8 = 9 objetos• 4 = -*, @*, -7, @*• . = -, A, @, 9

Celda: $(@, A)Si cabe: (BC= 3) ≤ E = 3F G − 1, E = F 1, 3 = 10F G − 1, E − BI + JI = $ -, * + @* = 20


Ejemplo:


!\# 0 1 2 3 4 5

0 0 0 0 0 0 0

1 0 10 10 10 10 10

2 0 10 10 20

3 0

4 0

$ !, # =

$(!, #) = )*, ! = * + # = *$ ! − -, # , .! > #012 $ ! − -, # , $ ! − -, # − .! +4! , .! ≤ #

Datos del problema:

• 6= 7• 8 = 9 objetos• 4 = -*, @*, -7, @*• . = -, A, @, 9Ejercicio:Llenar el resto de la tabla.


¿Cómo reconstruir solución a partir de la tabla !(#, %)?

• Solución: ' = ('), … , '+), donde ,- ∈ 0,1

• Iniciar con # = + y % =1, de modo que ! #, % en la esquina inferior derecha corresponde al valor óptimo

• Si ! #, % = ! # − ), % : '# = 3 y continuar en ! # − ), %

• De lo contrario, ! #, % = ! # − ), % − 4# +6#:

'# = ) y continuar en ! # − ), % − 4#

• Continuar hasta alcanzar 8 = 0: ¡solución completa!

Ejemplo:



Ejemplo:


!\# 0 1 2 3 4 5

0 0 0 0 0 0 0

1 0 10 10 10 10 10

2 0 10 10 20 30 30

3 0 10 15 25 30 35

4 0 10 15 25 30 35

$ !, # =

Datos del problema:

• '= (

• ) = * objetos

• 1 = 23, 43, 2(, 43

• 5 = 2, 6, 4, *

7 = (3, 2, 2, 3)

Reconstruimos la solución óptima a partir de la tabla


Análisis del algoritmo de Programación Dinámica:

• Complejidad ! "# : considerando el número de subproblemas que se resuelven en total

• Reconstruir la solución óptima a partir de la tabla$ %, ' implica un tiempo adicional, ! "

• Mejora significativa respecto a otros enfoques, por ejemplo búsqueda sistemática con complejidad ! ("

• Limitaciones:

o Aplicable sólo cuando # y )% son enteros, 1 ≤ , ≤ -

o No tan eficiente si # es grande

Ejemplo:



Implementar algoritmo de programación dinámica para resolver el Problema de la Mochila 0/1:

• Enfoque ascendente (bottom-up) – tabulación

Resolver para ! = #$ objetos y capacidad %= $&:

Ejercicio:

' 1 2 3 4 5 6 7 8 9 10 11 12

(' 12 10 8 11 14 7 9 15 19 5 6 8

)' 4 6 5 7 3 1 6 5 7 2 4 2


• LCS (longest common subsequence)

• Problema: identificar la subsecuencia más larga que es común en dos secuencias dadas

Ejemplo:

Subsecuencia Común Más Larga (SCML)

C I N V E S T A V

I N V E S T

A V

E S T A

C I N E

I N S T A

C I N V E S T A V

Su

bse

cu

en

cia

s

• Subsecuencia no es lo mismo que subcadena:

o Subcadena: secuencia contigua de caracteres

o Subsecuencia: no necesariamente contiguos, mismo orden


Ejemplo:


Subsecuencia: secuencia que puede obtenerse a partir de otra secuencia al eliminar algunos (o ninguno) de los elementos (sin alterar el orden de elementos restantes).

Dadas dos secuencias ! y ", decimos que una secuencia # es subsecuencia común de ! y " si # es una subsecuencia tanto de ! como de ".

Subsecuencia común más larga (SCML): subsecuencia común con más elementos (no necesariamente única). Ejemplo, para ! = “CINVESTAV” y " = “BIENVENIDOS”:

# = “INVES”


Aplicaciones importantes en áreas diversas. Por ejemplo, en Bioinformática:

• Alineamiento de pares de secuencias (ADN, proteínas)

Ejemplo:


InserciónSupresión

Mutación

Humano vs Chimpancé


OBSERVACIONES: (Caso 1)

Dos secuencias ! y " que SI coinciden en último elemento:

• El último elemento (“A”) de ! y " será también el último elemento de la SCML, #

• El prefijo #’ corresponderá a la SCML de los prefijos !’ y "’

• Por lo tanto, podemos plantear la solución óptima # en términos de la solución óptima al subproblema #’

Ejemplo:


C A S A C O S A ? A

!’ "’ #’

! = " = # =


OBSERVACIONES: (Caso 2)

Dos secuencias ! y " que NO coinciden en último elemento:

• No es posible determinar el último elemento de #, pero podemos descartar el último elemento de ! o el de "

• Por lo tanto, la solución óptima # corresponderá a lasolución óptima de alguno de estos dos subproblemas (aquel subproblema cuya SCML tenga mayor longitud)

Ejemplo:


C A S A C O C O

!’ "

! = " =

C A S A C O C O ?! = " = # =

Subproblema 1:

C A S A C O C O

! "’

! = " =

Subproblema 2:


Subestructura óptima (¡formalizando observaciones!):

Sean ! = #$, … , #' y ( = )$, … ,)* secuencias, y sea

+ = ,$, … , ,- una SCML de . y ℬ.

1. Si #' = )*:

o ,- = #' = )* y +-0$ es SCML de !'0$ y (*0$

2. Si #' ≠ )*:

o ,- ≠ #' implica que + es SCML de !'0$ y (

o ,- ≠ )' implica que + es SCML de ! y (*0$

Ejemplo:


Dada una secuencia 2 = 3$, … , 3' , el 4-ésimo prefijo de

5 esta dado por 24 = 3$, … , 34 , para 6 = 0, 1, … ,9.


Plantear solución óptima al problema en términos de la solución óptima de subproblemas:

• Sean ! = #$, … , #' y ( = )$, … ,)* secuencias

• Sea +(-, .) la longitud de una SCML de prefijos !- y (., donde 0 ≤ - ≤ ', 0 ≤ . ≤ * (la meta es +(',*))

• Definición recursiva:

+ -, . = 23, - = 3 4 . = 3+ - − $, . − $ + $, -, . > 3 8 #- = ).9:; + - − $, . , + -, . − $ , -, . > 3 8 #- ≠ ).

Ejemplo:



• Basado en esta recurrencia construimos la tabla !(#, %)

o Una fila para cada prefijo '# (0 ≤ * ≤ +)

o Una columna para cada prefijo ,% (0 ≤ - ≤ .)

• Enfoque ascendente (bottom-up):

o Llenado de la tabla se comienza por casos triviales

o A partir de los valores tabulados para subproblemas

pequeños, se calculan los valores correspondientes a subproblemas cada vez más grandes

• !(/,0) corresponde al valor de la solución óptima

Ejemplo:



Ejemplo:

Subsecuencia Común Más Larga (SCML)! 0 1 2 3 4 5 6" #! B D C A B A

0 $"1 A

2 B

3 C

4 B

5 D

6 A

7 B

% ", ! =

% ", ! = (), " = ) * ! = )% " − ,, ! − , + ,, ", ! > ) / $" = #!012 % " − ,, ! , % ", ! − , , ", ! > ) / $" ≠ #!

Tabla %(", !) con :+ , renglones y ; + , columnas

B = C,D, E, D,F, C, DG = D,F, E, C, D, C


Ejemplo:


0 $" 0 0 0 0 0 0 0

1 A 0

2 B 0

3 C 0

4 B 0

5 D 0

6 A 0

7 B 0

% ", ! =

% ", ! = (), " = ) * ! = )% " − ,, ! − , + ,, ", ! > ) / $" = #!012 % " − ,, ! , % ", ! − , , ", ! > ) / $" ≠ #!

4 = 5,6, 7, 6,8, 5, 69 = 6,8, 7, 5, 6, 5

Se comienza por los casos triviales


Ejemplo:


0 $" 0 0 0 0 0 0 0

1 A 0 0

2 B 0

3 C 0

4 B 0

5 D 0

6 A 0

7 B 0

% ", ! =

% ", ! = (), " = ) * ! = )% " − ,, ! − , + ,, ", ! > ) / $" = #!012 % " − ,, ! , % ", ! − , , ", ! > ) / $" ≠ #!

4 = 5,6, 7, 6,8, 5, 69 = 6,8, 7, 5, 6, 5Celda: %(,, ,)($< = =) ≠ #< = > :012 % ), , , % ,, ) = 0


Ejemplo:


0 $" 0 0 0 0 0 0 0

1 A 0 0 0 0 1

2 B 0

3 C 0

4 B 0

5 D 0

6 A 0

7 B 0

% ", ! =

% ", ! = (), " = ) * ! = )% " − ,, ! − , + ,, ", ! > ) / $" = #!012 % " − ,, ! , % ", ! − , , ", ! > ) / $" ≠ #!

4 = 5,6, 7, 6,8, 5, 69 = 6,8, 7, 5, 6, 5Celda: %(,, ;)$= = > = #? = > :% ), @ + , = 1


Ejemplo:


0 $" 0 0 0 0 0 0 0

1 A 0 0 0 0 1

2 B 0

3 C 0

4 B 0

5 D 0

6 A 0

7 B 0

% ", ! =

% ", ! = (), " = ) * ! = )% " − ,, ! − , + ,, ", ! > ) / $" = #!012 % " − ,, ! , % ", ! − , , ", ! > ) / $" ≠ #!

4 = 5,6, 7, 6,8, 5, 69 = 6,8, 7, 5, 6, 5

Ejercicio:Llenar el resto de la tabla.


¿Cómo reconstruir solución a partir de la tabla !(#, %)?

Ejemplo:


% 0 1 2 3 4 5 6

# '% B D C A B A

0 (# 0 0 0 0 0 0 0

1 A 0 0 0 0 1 1 1

2 B 0 1 1 1 1 2 2

3 C 0 1 1 2 2 2 2

4 B 0 1 1 2 2 3 3

5 D 0 1 2 2 2 3 3

6 A 0 1 2 2 3 3 4

7 B 0 1 2 2 3 4 4

Desde ! ),* , retroceder hasta llegar a fila # = , o columna - = ,: ¡solución completa!

Opción 1: Almacenar información adicional sobre el subproblema específico usado para llenar cada celda.

Opción 2: En cada paso analizar condiciones y determinar qué subproblema específico se utilizó.


Análisis del algoritmo de Programación Dinámica:

• Complejidad ! "# : número de subproblemas que se resuelven para dos secuencias de longitud " y #

• Reconstruir la solución óptima a partir de la tabla $(&, ()implica un tiempo adicional, ! "+ #

• Mejora muy significativa respecto al enfoque de fuera bruta, cuya complejidad es ! +"# :

o existen +" posibles subsecuencias en la primera secuencia, mismas que se verifican en la segunda secuencia en tiempo ! #

Ejemplo:



Implementar algoritmo de programación dinámica para calcular una Subsecuencia Común Más Larga:

• Enfoque ascendente (bottom-up) – tabulación

Utilizar programa para resolver el siguiente problema:

! = “CENTRODEINVESTIGACIONYDEESTUDIOSAVANZADOS”

# = “CINVESTAVUNIDADTAMAULIPAS”

Para este problema, la longitud de la SCML es: 15

Ejercicio:


• Permite el diseño de algoritmos eficientes cuando: o El problema puede dividirse en subproblemas más simples

o La solución óptima se puede plantear en términos de la solución óptima a los subproblemas

o Los subproblemas presentan traslape / solapamiento

• Resuelve cada subproblema una única vez y guarda resultado para evitar recalcularlo en el futuro

• Principal dificultad: caracterización de subproblemas, de modo que se cumplan las propiedades necesarias

Programación Dinámica (Comentarios)


Ejercicios Adicionales:

• Investigar cómo se aplica la Programación Dinámica en la solución de problemas adicionales, por ejemplo:

o Producto de secuencia de matrices (matrix chain-product)

o Problema del cambio mínimo

o Cálculo de coeficientes binomiales

o Algoritmo de Floyd-Warshall (caminos más cortos)

• ¿Qué ventajas ofrece este diseño algorítmico?

• Implementar algunos de estos algoritmos en el lenguaje de programación de su preferencia


Resumen y Comentarios Finales


Se han revisado las nociones básicas de estrategias algorítmicas genéricas para la resolución de problemas:

• Algoritmos voraces

• Búsqueda sistemática

o Búsqueda exhaustiva

o Búsqueda con retroceso

o Ramificación y poda

• Divide y vencerás

o Decrementa y vencerás

• Programación dinámica



Los algoritmos que se diseñan siguiendo estas estrategias pueden ser exactos o heurísticos, dependiendo de si garantizan o no producir siempre una solución óptima.

Esta clasificación es en el caso general, pero hay excepciones para problemas o condiciones específicas.


Algoritmo Exacto Heurístico

Algoritmo voraz

Búsqueda sistemática

Divide y vencerás

Programación dinámica


Dependiendo de las características del problema, algunas estrategias pueden resultar más apropiadas y permitir el diseño de algoritmos más eficientes(complejidad temporal, complejidad espacial).

El correcto entendimiento del problema es esencial para identificar alternativas adecuadas de solución.

La habilidad para crear algoritmos eficientes, que aprovechen al máximo las ventajas de cada paradigma de diseño, es algo que se desarrolla con la práctica.



• Técnicas de Diseño de Algoritmos

Rosa Guerequeta y Antonio Vallecillo

Servicio de Publicaciones de la Universidad de Málaga.

http://www.lcc.uma.es/~av/Libro/

• Algorithm Design: Foundations, Analysis, and Internet Examples

Michael T. Goodrich and Roberto Tamassia, Wiley

Presentaciones: http://ww3.algorithmdesign.net/handouts/

Capítulos gratis: http://ww3.algorithmdesign.net/sample.html

• Introduction to Algorithms

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. Third Edition. MIT Press.

Bibliografía Recomendada


Estrategias Algorítmicas

- Fin de la Parte 3 -

5 estrategiasalgoritmicas parte3 publicar · 2019. 6. 28. · subsecuencia: secuencia que puede...

Documents