PDF de programación - Programación II - Tema 10. Ramificación y Poda

Programación II
Bloque temático 1. Lenguajes de programación
Bloque temático 2. Metodología de programación
Bloque temático 3. Esquemas algorítmicos

Tema 4. Introducción a los Algoritmos
Tema 5. Algoritmos voraces, heurísticos y aproximados
Tema 6. Divide y Vencerás
Tema 7. Ordenación
Tema 8. Programación dinámica
Tema 9. Vuelta atrás

Tema 10.Ramificación y poda

Tema 11.Introducción a los Algoritmos Genéticos
Tema 12.Elección del esquema algorítmico

Programación II

Tema 10. Ramificación y Poda

© Mario Aldea Rivas

16/05/11

Tema 10.Ramificación y Poda



1



10.1. Introducción
10.2. Esquema genérico de un algoritmo RyP
10.3. Ejemplo de ramificación y poda
10.4. Eficiencia de los algoritmos RyP
10.5. Laberinto
10.6. Puzzle de desplazamiento
10.7. El problema de la asignación
10.8. Bibliografía

Programación II

Tema 10. Ramificación y Poda

© Mario Aldea Rivas

16/05/11

2

10.1 Introducción
El método RyP (Branch and Bound) es una variante del de Vuelta
Atrás y, por tanto, es aplicable a problemas:

10.1 Introducción

• cuya solución se expresa como una secuencia de decisiones
• en cada decisión se elige entre un conjunto finito de valores

RyP da lugar a algoritmos de complejidad exponencial

• por lo que normalmente se utiliza en problemas complejos que

no pueden resolverse en tiempo polinómico (NP-completos)

Al igual que VA, RyP realiza una exploración sistemática del árbol
de búsqueda, pero:

• no utiliza recursividad para generar el árbol
• el árbol existe como una cola de nodos vivos

- ordenada en base a una función de coste que proporciona

una estimación de lo prometedor que es cada nodo

Programación II

© Mario Aldea Rivas

16/05/11

3

Tema 10. Ramificación y Poda

10.1 Introducción
Introducción (cont.)

En RyP distinguiremos tres tipos de nodos:

• nodos vivos: todavía no han sido ramificados
• nodo en expansión (e-nodo): está siendo ramificado en este

momento (sólo puede haber uno en cada etapa)

• nodos muertos: ya han sido ramificados o han sido

descartados (podados)

A

C

K

G

F

J

B

I

E

H

D

L

e-nodo

nodo vivo
nodo muerto

cola nodos vivos:

I

H

G

K

E

Programación II

Tema 10. Ramificación y Poda

© Mario Aldea Rivas

16/05/11

4

10.1 Introducción
Introducción (cont.)

La clave de los algoritmos RyP está en la utilización de la función
de coste

• coste de un nodo: estimación (nunca pesimista) del valor de la
mejor solución que podríamos encontrar ramificando ese nodo

coste de un nodo = valor del nodo +
estimación de lo que le falta para ser solución

La función de coste se utiliza para dos cosas:

1.Ordenar la cola de nodos vivos de mejor a peor coste

- con lo que se ramifican primero los nodos más prometedores
2.Podar las ramas que no puedan conducirnos a una solución

que mejore la mejor solución encontrada hasta el momento

Programación II

Tema 10. Ramificación y Poda

© Mario Aldea Rivas

16/05/11

5

10.1 Introducción
Introducción (cont.)

RyP realiza de forma iterativa las siguientes etapas:
1. selección: se extrae de la cola el nodo vivo más prometedor (el

de mejor valor de su función de coste)
• será el nodo en expansión o e-nodo

2. ramificación y poda

• se ramifica el e-nodo creando cada uno de sus nodos hijo
• se podan (descartan) los nodos hijo desde los que no se puede

mejorar la mejor solución alcanzada hasta el momento

• los nodos no podados se insertan en la cola de nodos vivos

3. se repiten los pasos hasta que:

• la cola se quede vacía
• o el mejor nodo vivo no permita mejorar la mejor solución

encontrada hasta el momento

Programación II

© Mario Aldea Rivas

16/05/11

6

Tema 10. Ramificación y Poda

10.2 Esquema genérico de un algoritmo RyP

10.2 Esquema genérico de un algoritmo RyP
Estructuras utilizadas:
• Clase Nodo:
- cada nodo (solución parcial) del árbol de búsqueda
- tiene el métodos coste y compareTo (basado en coste)
• Cola ordenada colaNodosVivos
- mantiene los nodos vivos ordenados en función de su coste
- implementación eficiente con montículo (PriorityQueue)
- inserciones y extracciones O(log n)

Algoritmo genérico de un algoritmo RyP:
método algoritmoRyP() retorna Nodo
// mejor solución inicial (con el peor valor posible)
mejorSol = nuevo Nodo(peores valores posibles)
// crea el nodo inicial y le pone como primer nodo en expansión
eNodo = nuevo Nodo(valores iniciales)

Programación II

Tema 10. Ramificación y Poda

© Mario Aldea Rivas

16/05/11

7

10.2 Esquema genérico de un algoritmo RyP
Esquema genérico de un algoritmo RyP (cont.)

// lazo mientras queden nodos
hacer
// ramifica el e-nodo y poda o encola sus hijos
para cada posibilidad de ramificación hacer
nHijo = un hijo del eNodo
// ¿poda?
si nHijo.coste mejor que mejorSol.coste entonces
// el nodo NO se poda
si nHijo es solución entonces
// actualiza la mejor solución
mejorSol = nHijo
sino
// el nodo no es solución: se encola en base a su coste
colaNodosVivos.añade(nHijo)
fsi
fsi // si (no podar)
fhacer // ramificación
// obtiene el siguiente nodo en expansión
eNodo = colaNodosVivos.extraePrimero()
mientras eNodo != null y eNodo.coste mejor que mejorSol.coste
retorna mejorSol
fmétodo

Programación II

Tema 10. Ramificación y Poda

© Mario Aldea Rivas

16/05/11

10.3 Ejemplo de ramificación y poda

10.3 Ejemplo de ramificación y poda

Problema del cambio: monedas={v1=1,v2=3} cCambiar=5

el nodo {} se ramifica

{}

{1}

{3}

cola nodos vivos:

{3}
2

{1}

3

los nodos se ordenan de menor a mayor "coste"

coste= número de monedas en el nodo +

monedas de valor máximo que
faltarían para alcanzar cCambiar

el nodo {3} se extrae de la cola y se realizan sus ramificaciones válidas

{}

{1}

{3}

{3,1}

cola nodos vivos:

{3,1}

3

{1}

3

Programación II

© Mario Aldea Rivas

16/05/11

8

9

Tema 10. Ramificación y Poda

10.3 Ejemplo de ramificación y poda
Ejemplo de ramificación y poda (cont.)

el nodo {3,1} se extrae de la cola y se realizan sus ramificaciones válidas

{}

{1}

{3}

{3,1}

{3,1,1} es solución

{3,1,1}

cola nodos vivos:
mejor solución encontrada: {3,1,1}

{1}

3

3

el algoritmo ha finalizado, puesto que el primer elemento de la
cola de nodos vivos {1} no tiene mejor coste que la mejor solución
encontrada (no es posible mejorar la mejor solución encontrada
ramificando {1})

Programación II

Tema 10. Ramificación y Poda

© Mario Aldea Rivas

16/05/11

10

10.4 Eficiencia de los algoritmos RyP

10.4 Eficiencia de los algoritmos RyP
Eficiencia temporal de peor caso:
• igual que para VA: O(vn)
Si la función de coste es buena

0

1

• el algoritmo se dirige rápidamente a la
solución podando muchas ramas
• O(vn) es un valor muy pesimista
• para obtener un valor promedio más

próximo a la realidad es necesario hacer medidas

v0 nodos

v1 nodos

v2 nodos

...

vn-1 nodos

2

...

v-1

...

...

...

Eficiencia espacial:

• depende de máxima longitud de la cola de nodos vivos
• difícil de valorar a priori

- también es necesario hacer medidas

Programación II

Tema 10. Ramificación y Poda

© Mario Aldea Rivas

16/05/11

11

10.5 Laberinto

10.5 Laberinto
Se trata de encontrar el camino más corto entre la entrada y la
salida de un laberinto

• representado mediante una matriz filas×columnas

El problema era abordable utilizando Vuelta Atrás, por lo que
también lo será con RyP
Es necesario definir la función coste de un nodo:

• se calculará como la suma del número de

pasos dados hasta él

• más la distancia “Manhattan” desde él

hasta la salida
- es el valor del teórico camino más

corto que pasaría por ese nodo

- quizá no exista tal camino

-1
-1
-1
-1
-1
-1
-1
-1
-1

-1
-1
-1
-1

-1
-1
-1
0
-1
-1
-1

-1
-1
-1
-1
0
0
0
0
-1

-1
-1
-1
-1
-1
-1
-1
1
-1
-2
0 0
-1
0
2
-1
0
0
-1
3
0
-1
0
0
7
4 5 6
-1
0
-1
0
-1
0 0
0
-1
-1
0
-1
-1
-1
-1
-1
0
0
0 0 0 0 0
00
-1
-1
-1
-1
-1
-1
coste=7+2+3=12

-1

-1

-1

Programación II

© Mario Aldea Rivas

16/05/11

-1
-1
-1
-1
-1
-1
-1
-1
-1

12

Tema 10. Ramificación y Poda

10.5 Laberinto
Laberinto (cont.)
Suponemos que en principio no se conoce la situación de la salida

• todos los nodos tienen el mismo coste:

- búsqueda “a ciegas” (similar a utilizar Vuelta Atrás)

• una vez encontrada la salida se puede comenzar a podar y a

seleccionar los nodos en base a su coste

Cada nodo debe contener la información suficiente para saber
como se llegó a él y como se puede continuar avanzando:

• copia del laberinto (con los pasos dados hasta llegar a él)

El algoritmo va apuntando la mejor solución encontrada hasta el
momento (mejorSol)
• se inicializa con un coste infinito

Programación II

Tema 10. Ramificación y Poda

© Mario Aldea Rivas

16/05/11

13

10.5 Laberinto

Pseudocódigo
método caminoMasCortoLaberinto(entero xIni,
entero yIni, entero[][] laberinto)
mejorSol.coste = ∞ // mejor solución inicial
// crea el nodo inicial (posición de salida) y le pone
// como primer e-nodo
eNodo = nuevo Nodo(laberinto,xIni,yIni,pasos=1)
// lazo mientras queden nodos
hacer
// ramifica el e-nodo (una rama para cada posible
// movimiento) y poda o encola sus hijos
para mov en (izq.,arriba,abajo,derecha) hacer
(xNew, yNew) = movimiento(mov,eNodo.x,eNodo.y)
si eNodo.laberinto[yNew][xNew] es camino entonces
// crea el hijo con su propia copia del lab.
nHijo = nuevo Nodo(eNodo.laberinto,
xNew,yNew,eNodo.pasos+1)

Programación II

Tema 10. Ramificación y Poda

© Mario Aldea Rivas

16/05/11

14

10.5 Laberinto

Pseudocódigo (cont.)

si nHijo.coste < mejorSol.coste entonces
// el nodo NO se poda
si nHijo es solución entonces
si es la primera solución encontrada entonces
reordena colaNodosVivos en base al coste
fsi
// actualiza la mejor solución
mejorSol = nHijo
sin