PDF de programación - Exploración de grafos

Exploración de grafos
Exploración de grafos

 Backtracking
 Backtracking

 Grafos
Grafos
Recorridos sobre grafos
 Recorridos sobre grafos
 Búsqueda primero en profundidad
Búsqueda primero en profundidad
 Búsqueda primero en anchura
Búsqueda primero en anchura
Backtracking (“vuelta atrás”)
Backtracking (“vuelta atrás”)
(“vuelta atrás”)
(“vuelta atrás”)
 Descripción general
Descripción general
Espacio de soluciones
 Espacio de soluciones
 Implementación
Implementación
 Ejemplos
Ejemplos
Branch & & Bound
 Descripción general
Descripción general
Estrategias de ramificación
 Estrategias de ramificación
 Implementación
Implementación
 Ejemplos
Ejemplos

 Branch

Bound (“ramificación y poda”)
(“ramificación y poda”)

3030

Backtracking
Backtracking

Supongamos que tenemos que tomar una serie de
Supongamos que tenemos que tomar una serie de
decisiones pero…
decisiones pero…
 No disponemos de suficiente información como para
No disponemos de suficiente información como para
saber cuál elegir.
saber cuál elegir.
 Cada decisión nos lleva a un nuevo conjunto de
Cada decisión nos lleva a un nuevo conjunto de
Cada decisión nos lleva a un nuevo conjunto de
 Cada decisión nos lleva a un nuevo conjunto de
decisiones.
decisiones.
 Alguna secuencia de decisiones (y puede que más de
Alguna secuencia de decisiones (y puede que más de
una) puede solucionar nuestro problema.
una) puede solucionar nuestro problema.

Necesitamos un método de búsqueda
Necesitamos un método de búsqueda
que nos permita encontrar una solución…
que nos permita encontrar una solución…

3131

Backtracking
Backtracking

Características
Características de un
resoluble con backtracking (o branch & bound)
resoluble con backtracking (o branch & bound)

de un problema
problema

 La La solución

solución puede

puede expresarse

expresarse como

como unauna nn--tupla
tupla,,

3
cada xi eses seleccionado

(x1,x2,x3,…,xn)
n
seleccionado de un

1

2

donde
donde cada

de un conjunto

conjunto finito

finito Si..

problema se se puede

 El El problema
aquella
aquella tupla
determinado
determinado criterio

tupla queque optimiza

criterio P(x1, ...,xn)..

puede formular

formular como
optimiza ((maximiza

como la la búsqueda
maximiza o o minimiza

búsqueda de de
minimiza) un
) un

3232

Backtracking
Backtracking

Resolución por fuerza bruta
Resolución por fuerza bruta

 En principio, podemos solucionar nuestro problema
En principio, podemos solucionar nuestro problema
probando todas las combinaciones (x1,x2,x3,…,xn)..
probando todas las combinaciones

Ejemplo
Ejemplo
Generando todas las posibles combinaciones de n bits
Generando todas las posibles combinaciones de n bits
podemos resolver el problema de la mochila 0/1 para n
podemos resolver el problema de la mochila 0/1 para n
objetos.
objetos.

T(n) = 2 T(n-1) + 1 ∈ O(2n)

3333

Backtracking
Backtracking

Resolución por fuerza bruta
Resolución por fuerza bruta
T(n) = 2 T(n-1) + 1 ∈ O(2n)

voidvoid combinaciones_binarias

combinaciones_binarias (vector<

(vector<intint> &V,

> &V, intint pos)pos)

{ {

ifif (pos==
ifif (pos==

(pos==V.size
(pos==V.size

V.size())())
V.size())())

procesa_combinación
procesa_combinación(V);(V);

elseelse {{

V[pos]=0;
V[pos]=0;

0

0

1

1

0

1

combinaciones_binarias (V,pos+1);
combinaciones_binarias
(V,pos+1);

0

1

0

1

0

1

0

1

V[pos]=1;
V[pos]=1;

combinaciones_binarias (V,pos+1);
combinaciones_binarias
(V,pos+1);

000 001 010 011 100 101 110 111

}}

}}

3434

Backtracking
Backtracking

Resolución por fuerza bruta
Resolución por fuerza bruta

 Implícitamente,

Implícitamente, se impone una
conjunto de posibles soluciones (espacio de soluciones).
conjunto de posibles soluciones (espacio de soluciones).

se impone una estructura de árbol

estructura de árbol sobre el
sobre el

La forma en la que se generan las soluciones es equivalente a
 La forma en la que se generan las soluciones es equivalente a
 La forma en la que se generan las soluciones es equivalente a
La forma en la que se generan las soluciones es equivalente a
realizar un
realizar un recorrido
posibles soluciones del problema.
posibles soluciones del problema.

recorrido del árbol, cuyas hojas corresponden a
del árbol, cuyas hojas corresponden a

¿Se puede mejorar el proceso?
¿Se puede mejorar el proceso?
Backtracking
 Backtracking
Branch & & Bound
 Branch
Bound

3535

Backtracking
Backtracking

¿Se puede mejorar el proceso?
¿Se puede mejorar el proceso?

SíSí, si eliminamos la necesidad de llegar
, si eliminamos la necesidad de llegar
hasta todas las hojas del árbol.
hasta todas las hojas del árbol.

¿Cuándo?
¿Cuándo?

Cuando para un nodo interno del árbol podemos
Cuando para un nodo interno del árbol podemos
Cuando para un nodo interno del árbol podemos
Cuando para un nodo interno del árbol podemos
asegurar que no alcanzamos una solución (esto es, no
asegurar que no alcanzamos una solución (esto es, no
nos lleva a nodos hoja útiles), entonces podemos podar
nos lleva a nodos hoja útiles), entonces podemos podar
la rama completa del árbol.
la rama completa del árbol.

¿Cómo?
¿Cómo?

Realizamos una vuelta atrás (“
Realizamos una vuelta atrás (“backtracking

backtracking”).”).

VENTAJA: Alcanzamos antes la solución.
VENTAJA
: Alcanzamos antes la solución.

3636

Backtracking
Backtracking

Diferencias con otras técnicas
Diferencias con otras técnicas

 En los

algoritmos greedy

En los algoritmos
greedy, se construye la solución
, se construye la solución
aprovechando la posibilidad de calcularla a trozos:
aprovechando la posibilidad de calcularla a trozos:
un candidato nunca se descarta una vez elegido.
un candidato nunca se descarta una vez elegido.
un candidato nunca se descarta una vez elegido.
un candidato nunca se descarta una vez elegido.
Con Con backtracking
backtracking, sin embargo, la elección de un
, sin embargo, la elección de un
candidato en una etapa no es irrevocable.
candidato en una etapa no es irrevocable.

El tipo de problemas en los que aplicaremos
 El tipo de problemas en los que aplicaremos
backtracking no se puede descomponer en
backtracking
no se puede descomponer en
subproblemas
subproblemas independientes, por lo que
independientes, por lo que
la la técnica “divide y vencerás”

técnica “divide y vencerás” no resulta aplicable.
no resulta aplicable.

3737

Backtracking
Backtracking

 Solución

Solución: : (x1,x2,x3,…,xn), xi ∈ Si..

 Espacio

Espacio de de soluciones

soluciones de de tamaño

tamaño ΠΠ||Si||

 Solución parcial

Solución parcial:: (x1,x2,…,xk,?,?,...,?), xi ∈ Si. .
VVector
ector solución para e
todas sus componentes.
todas sus componentes.

solución para el que aún no se han establecido
l que aún no se han establecido

 Función de poda/acotación

Función de poda/acotación: :
Función que nos permite identificar cuándo una solución
Función que nos permite identificar cuándo una solución
parcial no conduce a una solución del problema.
parcial no conduce a una solución del problema.

3838

Backtracking
Backtracking

Restricciones
Restricciones asociadas

asociadas a los

a los problemas
problemas

 Restricciones

Restricciones explícitas
valores
valores de de laslas variables
soluciones
soluciones del del problema

variables xi ((definen
problema ΠΠSi))

explícitas:: Restringen

definen el el espacio

espacio de de

Restringen los

los posibles
posibles

p.ejp.ej..

xi ≥ 0 ⇒ Si = {números reales no negativos}
xi ∈ {0,1} ⇒ Si = {0,1}
li ≤ xi ≤ ui ⇒ Si = {a: li ≤ a ≤ ui}

 Restricciones

variables xi ((determinan las

Restricciones implícitas
relaciones entre
entre
laslas variables
tuplas que satisfacen el
que satisfacen el
criterio
criterio P(x1, ...,xn): nos indican cuándo una solución
cuándo una solución
parcial nos puede llevar a una solución).
parcial nos puede llevar a una solución).

implícitas: : Establecen
determinan las tuplas

Establecen relaciones

3939

Backtracking
Backtracking

4040
4040

3535
3535

3030
3030

2525
2525

2020
2020

1515
1515

1010
1010

55
55

xx22
xx22

3x3x11 + 2x+ 2x2 2 << 80 80
3x3x11 + 2x+ 2x2 2 << 80 80

solución
Posible solución
Posible
Posible
Posible
xx11 = 0, x
xx11

= 0, x22= 25, Z = 375.00
= 25, Z = 375.00
= 25, Z = 375.00
= 25, Z = 375.00

Solución
Solución
Solución
Solución
xx11 = 15, x
xx11

óptima
óptima
óptima
óptima

= 15, x22= 17.5, Z = 412.50
= 17.5, Z = 412.50
= 17.5, Z = 412.50
= 17.5, Z = 412.50

2x2x11 + 4x+ 4x2 2 << 100
2x2x11 + 4x+ 4x2 2 << 100
100
100

Conjunto
Conjunto
Conjunto
Conjunto
Soluciones
Soluciones
Soluciones
Soluciones
Factibles
Factibles
Factibles
Factibles

MAX 10x11 + 15x+ 15x22 ((objetivo
MAX 10x + 15x+ 15x ((objetivo
objetivo))
objetivo))
MAX 10x
MAX 10x

Posible solución
Posible
solución
Posible
Posible
xx11 = 26.67, x
xx11 = 26.67, x

= 26.67, x22 = 0, Z = 266.67
= 26.67, x22 = 0, Z = 266.67
= 0, Z = 266.67
= 0, Z = 266.67

5 10 15 20 25 30 35 40 45 50 x1
5 10 15 20 25 30 35 40 45 50 x1
5 10 15 20 25 30 35 40 45 50
5 10 15 20 25 30 35 40 45 50

Backtracking
Backtracking
El problema de las 8 reinas
El problema de las 8 reinas

Problema combinatorio clásico:
Problema combinatorio clásico:

Colocar ocho reinas en un
Colocar ocho reinas en un
tablero de ajedrez de modo
tablero de ajedrez de modo
que no haya dos que se ataquen;
que no haya dos que se ataquen;
(que estén en la misma fila,
(que estén en la misma fila,
columna o diagonal).
columna o diagonal).
columna o diagonal).
columna o diagonal).

Como cada reina debe estar
 Como cada reina debe estar
en una fila diferente, sin pérdida
en una fila diferente, sin pérdida
de generalidad podemos suponer
de generalidad podemos suponer
que la reina i se coloca en la fila i.
que la reina i se coloca en la fila i.

Todas las