PDF de programación - Tema 6. Ramificación y poda - Parte I. Estructuras de Datos

Programa de teoría
Parte I. Estructuras de Datos.

1. Abstracciones y especificaciones.
2. Conjuntos y diccionarios.
3. Representación de conjuntos mediante árboles.
4. Grafos.

Parte II. Algorítmica.

1. Análisis de algoritmos.
2. Divide y vencerás.
3. Algoritmos voraces.
4. Programación dinámica.
5. Backtracking.
6. Ramificación y poda.

A.E.D.

Tema 6. Ramificación y poda.

PARTE II: ALGORÍTMICA

Tema 6. Ramificación y poda.

6.1. Método general.
6.2. Análisis de tiempos de ejecución.
6.3. Ejemplos de aplicación.

6.3.1. Problema de la mochila 0/1.
6.3.2. Problema de la asignación.

A.E.D.

Tema 6. Ramificación y poda.

1

2

1

6.1. Método general.

• La ramificación y poda (branch and bound) se

suele utilizar en problemas de optimización discreta
y en problemas de juegos.

• Puede ser vista como una generalización (o mejora)

de la técnica de backtracking.

• Similitud:

• Diferencias:

– Igual que backtracking, realiza un recorrido

sistemático en un árbol de soluciones.

– Estrategia de ramificación: el recorrido no tiene por

qué ser necesariamente en profundidad.

– Estrategia de poda: la poda se realiza estimando en

cada nodo cotas del beneficio óptimo que podemos
obtener a partir del mismo.

A.E.D.

Tema 6. Ramificación y poda.

3

6.1. Método general.

Estimación de cotas a partir de una solución parcial

• Problema: antes de
explorar s, acotar el
beneficio de la
mejor solución
alcanzable, M.

2

0

1

0

................

1

1

x1

3

x2
s= (x1, x2)

0
s

• CI(s) ≤ Valor(M) ≤ CS(s)

¿?

(inexplorado)
M

M= (x1, x2, x3, x4,..., xn)
Valor(M) = ¿?

A.E.D.

Tema 6. Ramificación y poda.

4

2

6.1. Método general.

• Para cada nodo i tendremos:

– CS(i): Cota superior del beneficio (o coste) óptimo

que podemos alcanzar a partir del nodo i.

– CI(i): Cota inferior del beneficio (o coste) óptimo

que podemos alcanzar a partir del nodo i.

– BE(i): Beneficio estimado (o coste) óptimo que se

puede encontrar a partir del nodo i.

• Las cotas deben ser “fiables”: determinan cuándo

se puede realizar una poda.

• El beneficio (o coste) estimado ayuda a decidir

qué parte del árbol evaluar primero.

A.E.D.

Tema 6. Ramificación y poda.

5

6.1. Método general.

Estrategia de poda

• Supongamos un problema de maximización.
• Hemos recorrido varios nodos, estimando para cada

uno la cota superior CS(j) e inferior CI(j).

CI(j)

CS(j)

1

0

3

9

2

.............

1

0

3

x1

x2

1

2

5

15
.............

4

12

25

.............

• ¿Merece la pena seguir explorando por el nodo 2?
• ¿Y por el 5?

A.E.D.

Tema 6. Ramificación y poda.

6

3

6.1. Método general.

• Estrategia de poda (maximización). Podar un nodo i

si se cumple que:

CS(i) ≤ CI(j), para algún nodo j generado
o bien
CS(i) ≤ Valor(s), para algún nodo s solución final

• Implementación. Usar una variable de poda C:

C = max({CI(j) | ∀ j generado}, {Valor(s) | ∀ s solución final})
– Podar i si: CS(i) ≤ C

• ¿Cómo sería para el caso de minimización?

A.E.D.

Tema 6. Ramificación y poda.

7

6.1. Método general.

Estrategias de ramificación

• Igual que en backtracking, hacemos un recorrido en un

árbol de soluciones (que es implícito).

• Distintos tipos de recorrido: en profundidad, en

anchura, según el beneficio estimado, etc.

• Para hacer los recorridos se utiliza una lista de nodos

vivos.

• Lista de nodos vivos (LNV): contiene todos los nodos

que han sido generados pero que no han sido
explorados todavía. Son los nodos pendientes de tratar
por el algoritmo.

A.E.D.

Tema 6. Ramificación y poda.

8

4

6.1. Método general.

Estrategias de ramificación

• Idea básica del algoritmo:

– Sacar un elemento de la lista LNV.
– Generar sus descendientes.
– Si no se podan, meterlos en la LNV.

LNV

2
7 9

3

5
8 15

2

4
16 25

12

x
BE CS

CI

• ¿En qué orden se sacan y se meten?
• Según cómo se maneje esta lista, el recorrido será de

uno u otro tipo.

A.E.D.

Tema 6. Ramificación y poda.

9

6.1. Método general.

Estrategia de ramificación FIFO (First In First Out)
• Si se usa la estrategia FIFO, la LNV es una cola y el

recorrido es:

a) En profundidad
b) En anchura
c) NS/NC

1

Sacar

LNV

Meter

2

3

4

5

6

7

A.E.D.

Tema 6. Ramificación y poda.

1

2

3

4

3

4

5

5

6

7

10

5

6.1. Método general.

Estrategia de ramificación LIFO (Last In First Out)
• Si se usa la estrategia LIFO, la LNV es una pila y el

LNV

Meter
Sacar

recorrido es:

a) En profundidad
b) En anchura
c) NS/NC

2

1

4

3

6

5

7

1

2

2

2

3

4

4

A.E.D.

Tema 6. Ramificación y poda.

5

6

7

11

6.1. Método general.

• Las estrategias FIFO y LIFO realizan una búsqueda “a

ciegas”, sin tener en cuenta los beneficios.

• Usamos la estimación del beneficio: explorar
primero por los nodos con mayor valor estimado.

• Estrategias LC (Least Cost): Entre todos los nodos
de la lista de nodos vivos, elegir el que tenga mayor
beneficio (o menor coste) para explorar a continuación.

LNV

2
6 9

3

5
8 15

2

4
7 25

6

A.E.D.

Tema 6. Ramificación y poda.

12

6

6.1. Método general.

Estrategias de ramificación LC

• En caso de empate (de beneficio o coste estimado)

deshacerlo usando un criterio FIFO ó LIFO.

• Estrategia LC-FIFO: Seleccionar de LNV el nodo que
tenga mayor beneficio y en caso de empate escoger el
primero que se introdujo (de los que empatan).

• Estrategia LC-LIFO: Seleccionar el nodo que tenga

mayor beneficio y en caso de empate escoger el
último que se introdujo (de los que empatan).

• ¿Cuál es mejor?
• Se diferencian si hay muchos “empates” a beneficio

estimado.

A.E.D.

Tema 6. Ramificación y poda.

13

6.1. Método general.

• Resumen:

– En cada nodo i tenemos: CI(i), BE(i) y CS(i).
– Podar según los valores de CI y CS.
– Ramificar según los valores de BE.

• Ejemplo. Recorrido con ramificación y poda,

usando LC-FIFO.
– Suponemos un problema de minimización.
– Para realizar la poda usamos una variable C = valor de
la menor de las cotas superiores hasta ese momento, o
de alguna solución final.

– Si para algún nodo i, CI(i) ≥ C, entonces podar i.

A.E.D.

Tema 6. Ramificación y poda.

14

7

6.1. Método general.

• Ejemplo. Recorrido con ramificación y poda,

usando LC-FIFO.

1

2 8 15

2

2 7 13

3

3 7 13

4

4 6 10

5

8

9

5 7 11

3 5 8

6 7 8

6

5

7

6

10

4

11

5

A.E.D.

Tema 6. Ramificación y poda.

C
15

13

10

5

5

4

5

1

2

4

3

8

5

LNV

3

3

5

5

15

6.1. Método general.

• Esquema algorítmico de ramificación y poda.
– Inicialización: Meter la raíz en la LNV, e inicializar la

variable de poda C de forma conveniente.

– Repetir mientras no se vacíe la LNV:

• Sacar un nodo de la LNV, según la estrategia de

ramificación.

de poda.

• Comprobar si debe ser podado, según la estrategia

• En caso contrario, generar sus hijos. Para cada uno:

– Comprobar si es una solución final y tratarla.
– Comprobar si debe ser podado.
– En caso contrario, meterlo en la LNV y actualizar

C de forma adecuada.

A.E.D.

Tema 6. Ramificación y poda.

16

8

6.1. Método general.

RamificacionYPoda (raiz: Nodo; var s: Nodo) // Minimización

LNV:= {raiz}
C:= CS(raiz)
s:= ∅
mientras LNV ≠ ∅ hacer

x:= Seleccionar(LNV)
LNV:= LNV - {x}
si CI(x) < C entonces

// Estrategia de ramificación

para cada y hijo de x hacer

si Solución(y) AND (Valor(y)<Valor(s)) entonces

// Estrategia de poda

sino si NO Solución(y) AND (CI(y) < C) entonces

s:= y
C:= min (C, Valor(y))

LNV:= LNV + {y}
C:= min (C, CS(y))

finsi
finpara

finmientras

A.E.D.

Tema 6. Ramificación y poda.

17

6.1. Método general.

• Funciones genéricas:

– CI(i), CS(i), CE(i). Cota inferior, superior y coste

estimado, respectivamente.

– Solución(x). Determina si x es una solución final válida.
– Valor(x). Valor de una solución final.
– Seleccionar(LNV): Nodo. Extrae un nodo de la LNV

según la estrategia de ramificación.

– para cada y hijo de x hacer. Iterador para generar todos

los descendientes de un nodo. Equivalente a las
funciones de backtracking.

y:= x
mientras MasHermanos(y) hacer

Generar(nivel(x)+1, y)
si Criterio(y) entonces ...

A.E.D.

Tema 6. Ramificación y poda.

18

9

6.1. Método general.

Algunas cuestiones

• Se comprueba el criterio de poda al meter un nodo y al

sacarlo. ¿Por qué esta duplicación?

• ¿Cómo actualizar C si el problema es de maximizar? ¿Y

cómo es la poda?

• ¿Qué información se almacena en la LNV?

LNV: Lista[Nodo]
tipo

Nodo = registro

finregistro

tupla: TipoTupla
nivel: entero
CI, CE, CS: real

// P.ej. array [1..n] de entero

Almacenar para no
recalcular. ¿Todos?

A.E.D.

Tema 6. Ramificación y poda.

19

6.1. Método general.

• ¿Qué pasa si para un nodo i tenemos que

CI(i)=CS(i)?

• ¿Cómo calcular las cotas?

• ¿Qué pasa con las cotas si a partir de un nodo puede

que no exista ninguna solución válida (factible)?

A.E.D.

Tema 6. Ramificación y poda.

20

10

6.2. Análisis de tiempos de ejecución.
• El tiempo de ejecución depende de:

– Número de nodos recorridos: depende de la

efectividad de la poda.

– Tiempo gastado en cada nodo: tiempo de hacer

las estimaciones de coste y tiempo de manejo de la
lista de nodos vivos.

• En el caso promedio se suelen obtener mejoras

respecto a backtracking...

• En el peor caso, se generan tantos nodos como en

backtracking El tiempo puede ser peor según lo que
se tarde en calcular las cotas y manejar la LNV.

• ¿Cuántos nodos, como máximo, puede tener la LNV?

A.E.D.

Tema 6. Ramificación y poda.

21

6.2. Análisis de tiempos de ejecución.
• Problema: complejidad exponencial tanto en tiempo

como en uso de memoria.

• ¿Cómo hacer más eficiente un algoritmo de RyP?

– Hacer estimaciones y cotas muy precisas Poda

muy exhaustiva del árbol Se recorren menos
nodos pero se tardará mucho en hacer estimaciones.
– Hacer estimaciones y cotas poco precisas No

se hace mucha poda Se gasta poco tiempo en
cada nodo, pero el número de nodos es muy elevado.

• Se debe buscar un equilibrio ent