1PROCESO DE ADMISIÓN 2019
Centro de Investigación y de Estudios Avanzados del Instituto Politécnico NacionalCinvestav - Tamaulipas
Tema:
Estrategias Algorítmicas - Parte 1
Dr. Mario Garza Fabre
2PROCESO DE ADMISIÓN 2019
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
3PROCESO DE ADMISIÓN 2019
Introducción
4PROCESO DE ADMISIÓN 2019
El objetivo de este módulo es explicar las nociones básicas e ilustrar el funcionamiento de varias estrategias algorítmicas para la resolución de problemas:
o Algoritmos voraces, Búsqueda sistemática, Divide y vencerás, Programación dinámica
Las estrategias que estudiaremos son genéricas y pueden adaptarse a situaciones complicadas que surgen en diversas áreas de aplicación.
En muchos casos, utilizaremos como ejemplos diferentes problemas de optimización.
Objetivo
5PROCESO DE ADMISIÓN 2019
Un problema de optimización puede describirse por:
o Espacio de búsqueda: conjunto ! de soluciones potenciales
o Espacio factible: conjunto ℒ ⊆ ! de soluciones factibles (satisfacen las restricciones específicas del problema)
o Función objetivo: $ ∶ ℒ ⟶ ℝ (criterio que se busca optimizar)
Existen problemas de maximización y de minimización. Estas categorías definen lo que es una solución óptima:
o Maximización: (∗ ∈ ℒ tal que $((∗) = max $ ( ( ∈ ℒ }
o Minimización: (∗ ∈ ℒ tal que $((∗) = min $ ( ( ∈ ℒ }
Problema de Optimización
6PROCESO DE ADMISIÓN 2019
Ejemplo:
Problema de la Mochila 0/1
0/1 Knapsack Problem
¿Qué objetos elegir para maximizar las
ganancias sin exceder la
capacidad de la mochila?
¡Un problema clásico con diversas
aplicaciones muy importantes!
7PROCESO DE ADMISIÓN 2019
• Considerar mochila con capacidad ! y " objetos:o Valor o ganancia de los objetos: # = (#&, … , #")
o Costo o peso de los objetos: * = (*&, … , *")
• Solución potencial: + = (+&, … , +"), donde +, ∈ ., & .
+, = & indica que objeto , se elige, y +, = . lo contrario
• Espacio de búsqueda: / = ., & ", entonces / = 0"
• Espacio factible: 1 = + ∈ / ∑,3&" *,+, ≤! }
• Función objetivo (a maximizar): 6 + = ∑,3&" #,+, = # ⋅ +
Ejemplo:
Problema de la Mochila 0/1
8PROCESO DE ADMISIÓN 2019
Considere una mochila con capacidad de != # $% y los objetos descritos en la siguiente tabla:
¿Cuál es el tamaño del espacio de búsqueda?
¿Cuál es el tamaño del espacio factible?
¿Cuál es la solución óptima y su valor (o ganancia) total?
Ejercicio:
Objeto (&) Valor ((&) Peso ()&)
1 $10 1 kg
2 $20 3 kg
3 $15 2 kg
4 $20 4 kg
9PROCESO DE ADMISIÓN 2019
Análisis de Algoritmos
Un algoritmo representa una solución satisfactoria si:• Siempre produce la respuesta correcta• Es eficiente
Eficiencia / complejidad algorítmica:• Complejidad espacial ⟶ memoria requerida• Complejidad temporal ⟶ “tiempo” de ejecución
Complejidad temporal:• Usualmente no se refiere al tiempo de ejecución real• Número de operaciones elementales (operaciones
aritméticas, comparaciones, ...) realizadas cuando se considera una entrada / problema de tamaño particular
Algoritmo: conjunto finito de instrucciones o reglas bien definidas para realizar un cálculo o resolver un problema.
10PROCESO DE ADMISIÓN 2019
Complejidad Temporal
Usualmente enfocado al análisis del peor caso (aunque hay otras alternativas: mejor caso, caso promedio):
• Cota superior: garantiza que para cualquier entrada de tamaño !, el algoritmo nunca excederá esta estimación
• Un algoritmo es más eficiente si su tiempo de ejecución en el peor caso tiene orden o tasa de crecimiento inferior
La complejidad temporal de un algoritmo es una función:
" ∶ ℤ% ⟶ ℤ%
donde " ! = número (máximo) de operaciones cuando el tamaño de la entrada / problema es !.
11PROCESO DE ADMISIÓN 2019
Lo que realmente es nos interesa:
• Orden o tasa de crecimiento del tiempo de ejecución a medida que el tamaño de la entrada, !, tiende a infinito
• ¿Qué tan rápido crece el tiempo de ejecución con !?
Simplificaciones / abstracciones para facilitar el análisis:
• Ignorar factores constantes y términos menos significativos
• Asumir que ! será suficientemente grande
Notación asintótica (alternativas: Gran-O, Gran-Ω y Gran-Θ):
• Expresa la tasa de crecimiento del tiempo de ejecución de un algoritmo en función del tamaño de su entrada !
• Un algoritmo que es asintóticamente más eficiente será la mejor elección (con posible excepción si ! es pequeña)
Eficiencia Asintótica
12PROCESO DE ADMISIÓN 2019
Notación Gran-O (Big-Oh)
Sean !, #: ℤ& ⟶ ℤ&. Decimos que !()) es +(# ) ), o de
manera alternativa ! ) ∈ +(# ) ), si existen constantes -
y . tales que ! ) < -# ) cuando se cumple que ) > ..
! ) < -# ) para ) > .
.
# )
!())
-# ) Procedimiento general:
1. Identificar problema y su tamaño 1
2. Expresar número máximo de operaciones (peor caso) en función de 1
3. Considerar sólo los términos de mayor orden/grado
4. Descartar factores constantes
13PROCESO DE ADMISIÓN 2019
Para resolver problema de tamaño !, Algoritmo A realiza
"##!$+ "&! + ' operaciones y Algoritmo B realiza !(.
• Exprese la complejidad temporal de estos algoritmos empleando la notación Gran-O
• ¿Qué algoritmo es asintóticamente más eficiente?
• Genere una gráfica donde se muestre el crecimiento de estas dos ecuaciones al variar ! desde 0 hasta 150
Ejercicio:
14PROCESO DE ADMISIÓN 2019
Principales Órdenes de ComplejidadComplejidad Terminología
O(1) Constante
O(log n) Logarítmica
O(n) Lineal
O(n log n)Lineal-logarítmica /
cuasi-lineal
O(n!)Polinómica
(cuadrática, cubica, ...)
O(b") Exponencial
O(n!) Factorial
15PROCESO DE ADMISIÓN 2019
Exacto:
• Siempre resuelve el problema de manera óptima
Heurístico:
• No garantiza resolver el problema de manera óptima
• El objetivo es producir una solución suficientemente buena en tiempo razonable
• En algunas aplicaciones, una solución aproximada puede ser aceptable
Algoritmos Exactos y Heurísticos
16PROCESO DE ADMISIÓN 2019
Algoritmos Voraces
17PROCESO DE ADMISIÓN 2019
• También: algoritmos ávidos, codiciosos o greedy
• Construyen una solución paso a paso: los elementos en cuestión son considerados en un orden particular
• En cada paso se toman decisiones (irrevocables) con respecto al elemento considerado
• Decisiones localmente óptimas: parecen ser las mejores en su momento, pero se ignora el potencial impacto en la solución global
• Método heurístico (generalmente): en la mayoría de los casos sólo producen soluciones sub-óptimas
Algoritmos Voraces
18PROCESO DE ADMISIÓN 2019
Ejemplo:
Calendarización de Trabajos
Considerar un total de ! máquinas disponibles para procesar " trabajos, donde cada trabajo requiere una cantidad específica de tiempo de procesamiento.
Nota: Se considera el caso particular en el que los trabajos son independientes entre ellos, son indivisibles, y todas las máquinas son idénticas.
¿Qué máquina debe atender cada trabajo para minimizar el tiempo total del calendario de procesamiento?
19PROCESO DE ADMISIÓN 2019
• Considerar ! máquinas y un total de " trabajos:
o Tiempo de procesamiento de trabajos: # = (#&, … , #")
• Solución potencial: * = (*&, … , *"), donde *+ ∈ &,… ,! .
*+ = - indica que trabajo + se procesa en máquina -
• Espacio de búsqueda: . = &,… ,! ", y . = !"
• Espacio factible: / = . (no se especifican restricciones)
• Función objetivo (a minimizar):
0 * = &1-1!234(5-), donde 5- = ∑ + *+7-}
#+
Ejemplo:
Calendarización de Trabajos
20PROCESO DE ADMISIÓN 2019
Algoritmo voraz para resolver este problema:
1. Considerar trabajos uno a uno en su orden de llegada
2. Asignar al trabajo bajo consideración la máquina con el menor tiempo total de procesamiento (suma de los tiempos de los trabajos previamente asignados)
3. Mientras existan trabajos sin asignarse, considerar el siguiente trabajo y regresar al paso 2
Ejemplo:
Calendarización de Trabajos
21PROCESO DE ADMISIÓN 2019
Considere el algoritmo voraz propuesto para calendarización de trabajos y aplíquelo a la siguiente instancia del problema:
• ! = # máquinas, $ = % trabajos, & = ((), (%, (), %, %)
Aplique nuevamente el algoritmo considerando que los mismos trabajos llegaron en diferente orden:
• ! = # máquinas, $ = % trabajos, & = ((), %, %, (%, ())
¿Qué tan buenas son las soluciones generadas?
Ejercicio:
22PROCESO DE ADMISIÓN 2019
Análisis del algoritmo voraz y comentarios:
• Complejidad ! "# : para " trabajos se determina cuál de las # máquinas tiene menor carga de trabajo
• Algoritmo muy eficiente, considerando que el tamaño del espacio de búsqueda es exponencial, $ = #
&
• Produce soluciones razonablemente buenas, aunque generalmente serán soluciones sub-óptimas
• Útil cuando los trabajos llegan de manera constante y no se tiene información sobre trabajos futuros
Ejemplo:
Calendarización de Trabajos
23PROCESO DE ADMISIÓN 2019
Considerar un sistema monetario con monedas de !denominaciones diferentes " = "$, … ,"! , y una cantidad de cambio a devolver '.
Ejemplo:
Problema del Cambio Mínimo
¿Cómo devolver el cambio ' de tal manera que el número total de monedas sea mínimo?
Nota: Por simplicidad, se asume una disponibilidad ilimitada de monedas de cada denominación, y que usando estas monedas siempre es posible completar el cambio (.
24PROCESO DE ADMISIÓN 2019
Algoritmo voraz para resolver este problema:
1. Considerar las distintas denominaciones una por una en orden descendente de acuerdo con su valor
2. Para la denominación bajo consideración, agregar tantas monedas como sea posible sin rebasar el cambio !
3. Mientras no se complete el cambio !, considerar la siguiente denominación y regresar al paso 2
Ejemplo:
Problema del Cambio Mínimo
25PROCESO DE ADMISIÓN 2019
Utilizando el algoritmo voraz planteado para el problema del cambio mínimo:
• Calcular el cambio ! = #$ considerando las siguientes denominaciones: % = &', )$, ', )
• Calcule nuevamente el cambio ! = #$, pero ahora con denominaciones: % = &', )$, )
• ¿Qué tan buenas son las soluciones? ¿Observaciones?
Ejercicio: ! 3 minutos
26PROCESO DE ADMISIÓN 2019
Análisis del algoritmo voraz y comentarios:
• Complejidad ! " : donde " = $ (cambio a calcular). En el peor caso sería necesario iterar hasta añadir un total de $monedas (de denominación 1)
• Algoritmo simple, intuitivo y eficiente
• Soluciones óptimas para ciertas denominaciones
• Esto no puede garantizarse en el caso general
Ejemplo:
Problema del Cambio Mínimo
27PROCESO DE ADMISIÓN 2019
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 diseñar un Algoritmo Voraz para resolver este problema?
28PROCESO DE ADMISIÓN 2019
Algoritmo voraz para resolver este problema:
1. Considerar todos los objetos en orden descendente de acuerdo a la razón entre su valor y su costo: ⁄"# $#
2. Incluir el objeto considerado en la mochila si existe capacidad disponible, de lo contrario descartarlo
3. Mientras exista capacidad y objetos disponibles, considerar el siguiente objeto y regresar al paso 2
Ejemplo:
Problema de la Mochila 0/1
29PROCESO DE ADMISIÓN 2019
Considere una mochila con capacidad de != # $% y los objetos descritos en la siguiente tabla:
¿Qué solución produce nuestro algoritmo voraz?
¿Cuál es el valor (o ganancia) total de esta solución?
Comparar con la solución óptima que identificamos previamente: &∗ = (, *, *, ( , + &∗ = ,#
Ejercicio:
Objeto (-) Valor (/-) Peso (0-) 1/- 0-1 $10 1 kg
2 $20 3 kg
3 $15 2 kg
4 $20 4 kg
30PROCESO DE ADMISIÓN 2019
Análisis del algoritmo voraz y comentarios:
• Complejidad ! " : donde " es el número de objetos (asume que los objetos ya se encuentran ordenados)
• Algoritmo muy eficiente, considerando que el tamaño del espacio de búsqueda es exponencial, # = %
&
• Generalmente produce soluciones sub-óptimas
Ejemplo:
Problema de la Mochila 0/1
31PROCESO DE ADMISIÓN 2019
Ejercicio:
• Implementar el algoritmo voraz planteado para el Problema de la Mochila 0/1
• Utilizar cualquier lenguaje de programación
32PROCESO DE ADMISIÓN 2019
Ejemplo:
P. Mochila / Objetos Fraccionables
El problema antes descrito es conocido como Problema de la Mochila 0/1: los objetos no son divisibles y por lo tanto se incluyen o excluyen completamente.
Fractional Knapsack Problem
Esta variante considera objetos divisibles: si el objeto de interés no cabe completamente, se incluye una fracción del mismo.
¿Cómo adaptamos nuestro algoritmo voraz a este escenario?
33PROCESO DE ADMISIÓN 2019
Algoritmo voraz para resolver este problema:
1. Considerar los objetos en orden descendente de acuerdo a la razón entre su valor y su costo: ⁄"# $#
2. Incluir el objeto considerado en la mochila si existe capacidad disponible, de lo contrario incluir sólo la fracción del objeto que es posible almacenar (sólo se obtiene la fracción correspondiente del valor)
3. Mientras exista capacidad y objetos disponibles, considerar el siguiente objeto y regresar al paso 2
Ejemplo:
P. Mochila / Objetos Fraccionables
34PROCESO DE ADMISIÓN 2019
Considere una mochila con capacidad de != # $% y los objetos descritos en la siguiente tabla:
¿Qué solución produce nuestro algoritmo voraz?
¿Qué tan buena es la solución?
¿Observaciones?
Ejercicio:
Objeto (&) Valor ((&) Peso ()&) *(& )&1 $10 1 kg
2 $20 3 kg
3 $15 2 kg
4 $20 4 kg
35PROCESO DE ADMISIÓN 2019
Análisis del algoritmo voraz y comentarios:
• Complejidad ! " : donde " es el número de objetos (asume que los objetos ya se encuentran ordenados)
• Para esta versión específica del problema con objetos fraccionables: ¡Siempre produce soluciones óptimas!
• El valor total de la solución óptima para esta versión del problema siempre será al menos tan alto como el de la solución óptima del Problema de la Mochila 0/1 (¡más adelante veremos como tomar ventaja de esto!)
Ejemplo:
P. Mochila / Objetos Fraccionables
36PROCESO DE ADMISIÓN 2019
Ejercicio:
• Implementar el algoritmo voraz planteado para el Problema de la Mochila con Objetos Fraccionables
• Utilizar cualquier lenguaje de programación
37PROCESO DE ADMISIÓN 2019
• Generalmente sólo producen soluciones sub-óptimas
• No obstante, se ha demostrado que producen soluciones óptimas en algunos casos específicos
• Frecuentemente un algoritmo voraz es la mejor forma de obtener una aproximación rápidamente: regularmente son algoritmos de orden polinómico
• Pueden utilizarse dentro de estrategias más sofisticadas
Algoritmos Voraces (Comentarios)
38PROCESO DE ADMISIÓN 2019
Búsqueda Sistemática
39PROCESO DE ADMISIÓN 2019
• En ocasiones requerimos identificar la solución óptimapara un problema dado
• En muchos casos, la exploración sistemática del espacio de búsqueda puede representar la única forma de obtener una solución óptima
• Estudiaremos tres métodos algorítmicos exactos que se basan en este principio:
1. Búsqueda exhaustiva
2. Búsqueda con retroceso
3. Ramificación y poda
Búsqueda Sistemática
40PROCESO DE ADMISIÓN 2019
También: Enumeración o Fuerza Bruta
Cuando el universo ! de soluciones potenciales es finito, y “razonablemente pequeño”, podemos evaluar todas y cada una de las alternativas de solución.
Búsqueda Exhaustiva
Esto es lo que hicimos en nuestro primer ejercicio para resolver una instancia pequeña del problema de la mochila 0/1.
41PROCESO DE ADMISIÓN 2019
Comúnmente se plantea como el problema de recorrer un árbol de soluciones o árbol de búsqueda:
• Recorrido / búsqueda en profundidad (Depth-First-Search)
• Recorrido / búsqueda en anchura (Breadth-First-Search)
Búsqueda Exhaustiva
42PROCESO DE ADMISIÓN 2019
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 mediante Enumeración / Búsqueda Exhaustiva?
43PROCESO DE ADMISIÓN 2019
Para instancia con ! = # objetos, se explora completa y sistemáticamente el siguiente árbol de soluciones:
Nivel i corresponde a la decisión de incluir o no el i-ésimoobjeto, decisión que se propaga a niveles subsecuentes.
Ejemplo:
Problema de la Mochila 0/1
(0, 0, 0) (0, 0, 1) (0, 1, 0) (0, 1, 1) (1, 0, 0) (1, 0, 1) (1, 1, 0) (1, 1, 1)
(0, 0, ?) (0, 1, ?) (1, 0, ?) (1, 1, ?)
(0, ?, ?) (1, ?, ?)
(?, ?, ?)
Nivel 1
Nivel 2
Nivel 3
44PROCESO DE ADMISIÓN 2019
Recorrido/búsqueda en profundidad (Depth-First-Search): expandir recurrentemente cada nodo en un camino concreto. Cuando no hay más nodos que visitar en dicho camino, regresar y explorar camino alternativo.
Ejemplo:
Problema de la Mochila 0/1
(0, 0, 0) (0, 0, 1) (0, 1, 0) (0, 1, 1) (1, 0, 0) (1, 0, 1) (1, 1, 0) (1, 1, 1)
(0, 0, ?) (0, 1, ?) (1, 0, ?) (1, 1, ?)
(0, ?, ?) (1, ?, ?)
(?, ?, ?)
45PROCESO DE ADMISIÓN 2019
Análisis del enfoque por fuerza bruta y comentarios:
• Exploración exhaustiva de ! = #$ soluciones resulta
en un algoritmo de orden exponencial: % #$
• Esto limita la aplicabilidad de esta estrategia
Ejemplo:
Problema de la Mochila 0/1
46PROCESO DE ADMISIÓN 2019
Ejercicio:
• Implementar el algoritmo de búsqueda exhaustiva (fuerza bruta) descrito anteriormente para resolver de manera óptima el Problema de la Mochila 0/1
• Utilizar cualquier lenguaje de programación
47PROCESO DE ADMISIÓN 2019
• También conocido como Vuelta Atrás o Backtracking
• Toma ventaja de la estructura inherente del problema
• Cuando una solución parcial no puede llevarnos a una solución completa satisfactoria, podemos detener (podar) todas las búsquedas futuras a partir de ella, y retroceder
Búsqueda con Retroceso
(…,1, ?, ?,…)
(…,1, 0, ?,…) (…,1, 1, ?,…)
(…,1, 0, 0,…) (…,1, 0, 1,…) (…,1, 1, 0,…) (…,1, 1, 1,…)
¡Si la solución parcial no es factible, todas las que se generen a partir de ella tampoco lo serán!
48PROCESO DE ADMISIÓN 2019
• La búsqueda con retroceso puede ofrecer una mejora significativa con respecto a la búsqueda exhaustiva
• Evita considerar todas las alternativas de solución
• Más precisamente: evita recorrer caminos del árbol de soluciones que de manera anticipada se conoce no pueden conducirnos a una solución aceptable
• Al descartarse alguno de estos caminos, el algoritmo retrocede en su recorrido para enfocarse en caminos alternativos que si puedan conducir a una solución
Búsqueda con Retroceso
49PROCESO DE ADMISIÓN 2019
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 de manera óptima utilizando Búsqueda con Retroceso?
50PROCESO DE ADMISIÓN 2019
Búsqueda con retroceso para el problema de la mochila:
• Se recorre sistemáticamente y en profundidad el árbol de soluciones, tal como en la búsqueda exhaustiva
• Para cada nodo del árbol que se visita, verificar la factibilidad de la solución parcial que representa (es decir, verificar que la selección actual de objetos respeta la capacidad de la mochila, !)
• Si la solución parcial es factible, continuar con exploración de nodos descendientes. De lo contrario, retroceder (detener exploración a partir de este nodo)
Ejemplo:
Problema de la Mochila 0/1
51PROCESO DE ADMISIÓN 2019
Ejercicio:
• Implementar el algoritmo de búsqueda con retroceso (backtracking) descrito anteriormente para resolver de manera óptima el Problema de la Mochila 0/1
• Utilizar cualquier lenguaje de programación
52PROCESO DE ADMISIÓN 2019
• Estrategia también conocida como: Ramificación y Acotamiento o Branch-and-Bound
• Puede mejorar sustancialmente la eficiencia respecto a la búsqueda exhaustiva y búsqueda con retroceso
• Al igual que la búsqueda con retroceso, realiza una enumeración parcial del espacio de búsqueda
• Utiliza cotas para realizar un proceso de podado y ramificación “más inteligente” del árbol de soluciones
Ramificación y Poda
53PROCESO DE ADMISIÓN 2019
Cota superior: mayor o igual que mayor valor en conjunto
Cota inferior: menor o igual que menor valor en conjunto
Existen cotas más ajustadas que otras. Por ejemplo:
• 15, 28 y 31 son cotas superiores de ! = #, %&, %', %# . Sin
embargo, 15 representa una cota más ajustada
Ramificación y Poda
va
lor
cota superior
cota inferior
un conjunto de valores
54PROCESO DE ADMISIÓN 2019
Podado del árbol de soluciones: se descartan ramas que estamos seguros no conducen a la solución óptima.
Ramificación y Poda
¡Si cualquier solución alcanzable desde un determinado nodo es peor que la mejor solución conocida hasta el momento, no tiene caso expandir (ramificar) el árbol a partir de dicho nodo!
(…,1, ?, ?,…)
(…,1, 0, ?,…) (…,1, 1, ?,…)
(…,1, 0, 0,…) (…,1, 0, 1,…)
55PROCESO DE ADMISIÓN 2019
Podado del árbol de soluciones:
• En todo momento durante la búsqueda, la mejor solución que se ha logrado encontrar representa una cota inferior: la solución óptima necesariamente es al menos tan buena
• Para cada nodo, se calcula una cota superior que estima la calidad de la mejor solución alcanzable a partir de la solución parcial que este nodo representa
• Si la cota superior estimada no supera a la cota inferior, podamos la rama pues no es interesante explorarla
• Se evita expandir nodos que, de acuerdo a la cota superior, no conducen a soluciones mejores que nuestra cota inferior
Ramificación y Poda
56PROCESO DE ADMISIÓN 2019
Cota inferior, consideraciones:
• Está dada por la mejor solución que se ha encontrado
• Actualización: cada vez que al recorrer el árbol de soluciones se logra alcanzar un nodo hoja, la solución completa es evaluada y la cota es actualizada
• Inicialización: Para que el algoritmo pueda realizar podas desde el comienzo, la cota inferior es comúnmente inicializada a la solución aproximadaobtenida por otro algoritmo (ejemplo, algoritmo voraz)
Ramificación y Poda
57PROCESO DE ADMISIÓN 2019
Cota superior, consideraciones:
• Estima mejor solución alcanzable a partir de un nodo
• Su cálculo no debe ser costoso computacionalmente
• Mientras más precisa la cota, mayor la efectividad
o Una cota más ajustada permitirá podar más ramas
• IMPORTANTE: la cota superior nunca debe subestimar la calidad que realmente es alcanzable desde el nodo
¿Por qué?
Ramificación y Poda
58PROCESO DE ADMISIÓN 2019
Ramificación del árbol de soluciones: priorizamos aquellos caminos que parecen más prometedores.
Esto permite encontrar más rápidamente una solución que supere a la mejor conocida y, por lo tanto, actualizar nuestra cota inferior: ¡podado más efectivo!
Ramificación y Poda
¡Expandimosprimero el nodo más interesante!
(…,1, ?, ?,…)
(…,1, 0, ?,…) (…,1, 1, ?,…)
59PROCESO DE ADMISIÓN 2019
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 de manera óptima mediante Ramificación y Poda?
60PROCESO DE ADMISIÓN 2019
Ramificación y Poda para el problema de la mochila:
Extendiendo el algoritmo anteriormente descrito para el enfoque de Búsqueda con Retroceso:
1. Podado del árbol:
o Cota inferior: inicializar con Algoritmo Voraz
o Cota superior: estimar usando Algoritmo Voraz para Problema de la Mochila con Objetos Fraccionables
2. Ramificación del árbol:
o Aprovechar estimación de cota superior: expandir primero el nodo con estimación más prometedora
Ejemplo:
Problema de la Mochila 0/1
61PROCESO DE ADMISIÓN 2019
Análisis de enfoque Ramificación y Poda, comentarios:
• La eficiencia depende de la efectividad de las cotas
• En la práctica, se logran mejoras considerables con respecto a la búsqueda exhaustiva (y con retroceso)
• Sin embargo, en el peor caso la complejidad de este algoritmo sigue siendo de orden exponencial: ! "
#
Ejemplo:
Problema de la Mochila 0/1
62PROCESO DE ADMISIÓN 2019
Ejercicio:
• Implementar un algoritmo de Ramificación y Poda (Branch-and-Bound) para resolver de manera óptima el Problema de la Mochila 0/1
• Utilizar cualquier lenguaje de programación
63PROCESO DE ADMISIÓN 2019
Para muchos problemas, puede ser la única alternativa conocida para obtener una solución exacta (óptima):
• Búsqueda exhaustiva:
o Explora completamente el árbol de soluciones (todas las alternativas de solución)
• Búsqueda con retroceso:
o Evita explorar (poda) ramas del árbol que no conducen a una solución que pueda considerarse aceptable / satisfactoria (factible)
Búsqueda Sistemática (Comentarios)
64PROCESO DE ADMISIÓN 2019
• Ramificación y poda:
o Calcula cotas para guiar la poda de ramas que no conducen a la solución óptima
o Prioriza ramas más prometedoras y usa estrategias de inicialización para ajustar cotas oportunamente
o Mejoras significativas en la práctica (depende del problema y de un diseño efectivo del algoritmo)
Para muchos problemas, el crecimiento exponencial del espacio de búsqueda al considerar instancias “grandes” limita la aplicabilidad de la Búsqueda Sistemática.
Búsqueda Sistemática (Comentarios)
65PROCESO DE ADMISIÓN 2019
Ejercicios Adicionales:
• Diseñe algoritmos voraces y de búsqueda sistemática (fuerza bruta, retroceso, ramificación y poda) para problemas adicionales, por ejemplo:
o Problema del Agente Viajero, TSP (Travelling Salesman Problem)
• Implemente en lenguaje de programación de su elección
66PROCESO DE ADMISIÓN 2019
Estrategias Algorítmicas
- Fin de la Parte 1 -