Búsqueda con retroceso
Introducción
 El problema de las ocho reinas
 El problema de la suma de
subconjuntos
 Coloreado de grafos
 Ciclos hamiltonianos
 Atravesar un laberinto
 El problema de la mochila 0-1

Búsqueda con retroceso Pág. 1
Búsqueda con retroceso:
Introducción

Problemas que consideraremos:
– Problemas de Decisión: Búsqueda de las
soluciones que satisfacen ciertas
restricciones.
– Problemas de Optimización: Búsqueda de la
mejor solución en base a una función objetivo.
– Cada solución es el resultado de una secuencia
de decisiones.
– En algunos problemas de este tipo se conoce un
criterio óptimo de selección en cada decisión:
técnica voraz.
– En otros problemas se cumple el principio de
optimalidad de Bellman y se puede aplicar la
técnica de la programación dinámica.
– Existen otros problemas en los que no hay más
remedio que buscar.
Búsqueda con retroceso Pág. 2
Búsqueda con retroceso:
Introducción

Planteamiento del problema:
– Se trata de hallar todas las soluciones que
satisfagan un predicado Sol.
– La solución debe poder expresarse como una
tupla (x1,…,xn) donde cada xi pertenece a un
dominio Ci.
– Si |Ci|=ti, entonces hay
n
t
 ti
i 1
n-tuplas candidatas para satisfacer Sol.
– Método de fuerza bruta: examinar las t n-tuplas
y seleccionar las que satisfacen Sol.
– Búsqueda con retroceso (backtracking, en
inglés): formar cada tupla de manera progresiva,
elemento a elemento, comprobando para cada
elemento xi añadido a la tupla que (x1,…,xi)
puede conducir a una tupla completa
satisfactoria.
Búsqueda con retroceso Pág. 3
Búsqueda con retroceso:
Introducción
– Deben existir unas funciones objetivo parciales o
predicados acotadores Completable(x1,…,xi).
Dicen si (x1,…,xi) puede conducir a una solución.
– Diferencia entre fuerza bruta y búsqueda con
retroceso:
si se comprueba que (x1,…,xi) no puede
conducir a ninguna solución, se evita formar
las ti+1tn tuplas que comienzan por
(x1,…,xi)
– Para saber si una n-tupla es solución, suele haber
dos tipos de restricciones:
 explícitas: describen el conjunto Ci de
valores que puede tomar xi (todas las tuplas
que satisfacen estas restricciones definen un
espacio de soluciones posibles);
 implícitas: describen las relaciones que
deben cumplirse entre los xi (qué soluciones
posibles satisfacen el predicado objetivo Sol).
Búsqueda con retroceso Pág. 4
Búsqueda con retroceso:
Introducción

Ejemplo: el problema de las ocho reinas
– El problema consiste en colocar ocho reinas en
un tablero de ajedrez sin que se den jaque (dos
reinas se dan jaque si comparten fila, columna o
diagonal).
1 2
1
2
3
4
5
6
7
8
Búsqueda con retroceso Pág. 5
3 4
5
6 7 8
Búsqueda con retroceso:
Introducción
– Formulación 1:
64 
   4.426.165.368
 8 
– Formulación 2: Puesto que no puede haber más
de una reina por fila, podemos replantear el
problema como:
“colocar una reina en cada fila del tablero de
forma que no se den jaque”.
En este caso, para ver si dos reinas se dan jaque
basta con ver si comparten columna o diagonal.
Por lo tanto, toda solución del problema puede
representarse con una 8-tupla (x1,…,x8) en la que
xi es la columna en la que se coloca la reina que
está en la fila i del tablero.
 El espacio de soluciones consta de
88 8-tuplas (16.777.216 8-tuplas)
– Formulación 3: Puesto que no puede haber más
de una reina por columna, sólo hace falta que
consideremos las 8-tuplas (x1,…,x8) que sean
permutaciones de (1,2,...,8)
 El espacio de soluciones consta de
8! 8-tuplas (40.320 8-tuplas)
Búsqueda con retroceso Pág. 6
Búsqueda con retroceso:
Introducción

Volviendo al planteamiento general:
– Para facilitar la búsqueda, se adopta una
organización en árbol del espacio de soluciones.

En el ejemplo, con la 2ª formulación y
para el problema de las cuatro reinas
(en un tablero 44):
Búsqueda con retroceso Pág. 7
Búsqueda con retroceso:
Introducción
algoritmo BackTracking(ent k:entero;
entsal X:vector[1..n]de valor)
{Pre: X[1..k-1] es completable}
variable v:valor
para todo v en Ci hacer
X[k]:=v;
si completable(X,k) entonces
si Sol(X,k) entonces
guardar(X,k)
fsi;
si k<n entonces
BackTracking(k+1,X)
fsi;
fsi
fpara
La llamada inicial es:
...
BackTracking(1,X);
...
Búsqueda con retroceso Pág. 8
Búsqueda con retroceso:
Introducción

Nótese que el árbol no se construye
explícitamente sino implícitamente
mediante las llamadas recursivas del
algoritmo de búsqueda.

El algoritmo no hace llamadas
recursivas cuando:
– k = n+1, o cuando
– el nodo generado no es completable (PODA).
Backtracking :
búsqueda primero en
profundidad (DFS) en un árbol y con
detección de soluciones parciales no
completables (poda)

El algoritmo anterior halla todas las
soluciones y además éstas pueden ser
de longitud variable (< n+1).
Búsqueda con retroceso Pág. 9
Búsqueda con retroceso:
Introducción

Variantes:
– Limitar el número de soluciones a una sola
añadiendo un parámetro booleano de salida que
indique si se ha encontrado una solución.
– Forzar a que sólo los nodos hoja puedan
significar solución (realizando la recursión sólo si
no se ha encontrado un nodo solución):
– Resolver problemas de optimización: además de
la solución actual en construcción hay que
guardar la mejor solución encontrada hasta el
momento.
Se mejora la eficiencia de la búsqueda si el
predicado “completable” permiten eliminar los
nodos de los que se sabe que no pueden llevar a
una solución mejor que la ahora disponible
(poda; métodos de ramificación y acotación).
Búsqueda con retroceso Pág. 10
Búsqueda con retroceso:
Introducción

Sobre la eficiencia:
– Depende de:
 el número de nodos del árbol de búsqueda
que se visitan: v(n)
 el trabajo realizado en cada nodo
(normalmente un polinomio): p(n)
– Coste de: Completable y Sol

en general: O(p(n) v(n))
– Mejoras:
 Si se consigue que los predicados acotadores
reduzcan mucho el número de nodos
generados (aunque un buen predicado
acotador precisa mucho tiempo de
evaluación; compromiso…)
– Si lo reducen a un solo nodo generado
(solución voraz): O(p(n)  n) nodos a
generar en total
– Normalmente:
• O(p(n)  2n) ó O(p(n)  n!)
Búsqueda con retroceso Pág. 11
El problema de la suma de
subconjuntos

Problema:
– Dados un conjunto W={w1,…,wn} de n números
positivos y otro número positivo M, se trata de
encontrar todos los subconjuntos de W cuya
suma es M.
– Ejemplo: si W={11,13,24,7} y M=31, entonces la
solución es {11,13,7} y {24,7}.

Primera representación de la solución:
– La solución puede representarse simplemente
con los índices de los elementos de W.
– En el ejemplo: (1,2,4) y (3,4).
– En general, todas las soluciones son k-tuplas
(x1,x2,…,xk), 0<k<n+1.
– Restricciones sobre las soluciones:
 Explícitas:

xi  j

j es un entero y
Implicitas:
i  j  xi  x j
k
 w xi
 M
i1
xi  xi  1 , 1  i  n
Búsqueda con retroceso Pág. 12
1 j n

El problema de la suma de
subconjuntos

Segunda representación de la solución:
– Cada solución puede representarse con una
n-tupla (x1,x2,…,xn), tal que xi  {0,1}, 1≤i≤n,
de forma que:
 xi = 0 si wi no se elige y
 xi = 1 si wi se elige.
– En el ejemplo anterior: (1,1,0,1) y (0,0,1,1).

Conclusión:
– Pueden existir varias formas de formular un
problema, con distintas representaciones de las
soluciones (aunque siempre verificando éstas un
conjunto de restricciones explícitas e implícitas).
– En el problema que consideramos, ambas
representaciones nos llevan a un espacio de
estados que consta de 2n tuplas.
Búsqueda con retroceso Pág. 13
El problema de la suma de
subconjuntos

Arbol del espacio de soluciones (n=4)
para la primera representación (tuplas
de tamaño variable):
– Un arco del nivel i al nivel i+1 representa un
valor para xi.
– El espacio de soluciones está definido por todos
los caminos desde la raíz hasta cualquier hoja del
árbol.
1
x1=1
x1=2
x3=4 x3=4
x3=3
12 13
14
x4=4
16
Búsqueda con retroceso Pág. 14
4
x2=3 x2=4
x2=2
x2=3 x =4
2
7
x1=3
3
2
6
x1=4
8
9
10
x3=4
15
x2=4
11
5
El problema de la suma de
subconjuntos

Arbol del espacio de soluciones (n=4)
para la segunda representación (tuplas
de tamaño fijo):
– Los arcos del nivel i al nivel i+1 están etiquetados
con el valor de xi (1 ó 0).
– Todos los caminos desde la raíz a una hoja
definen el espacio de soluciones (24 hojas que
representan las 16 posibles 4-tuplas).
1
x1=1
x1=0
2
3
x2=1
x2=0
18
x3=1
19
x3=0
26
x4=1
30
x2=1
4
x3=1
27
x3=0
20
28
29
24
21
25
22
Búsqueda con retroceso Pág. 15
5
x3=1
x3=0
12
x4=0
x4=0
x4=0
x4=0
x4=1
x4=1
x4=1
x4=1
31
x2=0
23
16
x3=1
13
x4=0
x4=1
17
14
x3=0
6
x4=0
x4=1
15
10
7
x4=0
x4=1
11
8
x4=0
9
El problema de la suma de
subconjuntos

Estudiemos una solución de búsqueda
con retroceso basada en la segunda
representación (tuplas de tamaño fijo).
– El elemento x[i] del vector solución toma el valor
1 ó 0 dependiendo de si el número w[i] se
incluye o no en la solución.
– Función acotadora (completable):
La tupla (x[1],…x[k]) sólo puede conducir a una
solución si:
Además la tupla (x[1],…x[k]) no
puede conducir a una solución si:
– Es decir, una función acotadora es:
Búsqueda con retroceso Pág. 16
El problema de la suma de
subconjuntos
algoritmo sumasub(ent s,k,r:entero;
entsal X: vector[1..n]de nat)
{k: siguiente variable a decidir
Los w[j] están en orden creciente
s=
k -1
n
 j = 1 w[j]*x[j]; r=  j =k w[j]
s+w[k]M; s+
}

n
i =1
w[i]M
X[k]:=1;
si s+w[k]=M entonces escribir(X[1..k])
sino
si s+w[k]+w[k+1]M entonces
sumasub(s+w[k],k+1,r-w[k],X)
fsi
fsi
si (s+r-w[k]  M) y (s+w[k+1]  M) entonces
X[k]:=0;
sumasub(s,k+1,r-w[k],X)
fsi
fin
Búsqueda con retroceso Pág. 17
El problema de la suma de
subconjuntos
La llamada inicial es:
...
n
sumasub(0,1,  i = 1w[i])
...
Nótese que el algoritmo evita calcular

k
w[i
i =1
]x[ i ] y

n
w[i
i =k + 1
]
cada vez guardando esos valores en s y r.
A esto se le llama MARCAJE.
– Coste:
n
 con marcaje: O(2 )

sin marcaje: O(n 2n)
Búsqueda con retroceso Pág. 18
El problema de la suma de
subconjuntos
– Ejemplo: n=6, M=30, W=(5,10,12,13,15,18)
Los rectángulos son s,k,r en cada llamada.
A=(1,1,0,0,1); B=(1,0,1,1); C=(0,0,1,0,0,1).
Se construyen 26 nodos (del total de 27-1=127)
0,1,73
x[1]=1
5,2,68
0,2,68
x[2]=0
x[2]=1
5,3,58
15,3,58
x[3]=1
27,4,46
x[3]=0
15,4,46
x[3]=1
17,4,46
10,3,58
x[3]=0
15,5,33
B
12,4,46
10,5,33
12,5,33
13,5,33
12,6,18
13,6,18
x[4]=0
5,5,33
x[5]=1
A
0,4,46
10,4,46
5,4,46
x[4]=1
x[4]=0
0,3,58
x[5]=1
20,6,18
C
Búsqueda con retroceso Pág. 19
0,5,33
Coloreado de grafos

Problema de decisión:
– Dados un grafo G y un número entero positivo
m, ¿es G m-coloreable?
– Es decir, ¿se puede pintar con colores los nodos
de G de modo que no haya dos vértices
adyacentes con el mismo color y se usen sólo m
colores?

Problema de optimización:
– Dado un grafo G, ¿cuál es su número cromático?
– Es decir, ¿cuál es el menor número m de colores
con el que se puede colorear G?
Búsqueda con retroceso Pág. 20
Coloreado de grafos

Un subproblema muy famoso:
– Dado un mapa, ¿pueden pintarse sus regiones
(autonomías, países, o lo que sea) de tal forma
que no haya dos regiones adyacentes de igual
color y no se empleen más de 4 colores?
5
4
2
3
1
2
1
5
3
4
– Cada región se modela con un nodo y si dos
regiones son adyacentes sus correspondientes
nodos se conectan con un arco.
– Así se obtiene siempre un grafo “plano” (puede
dibujarse en un plano sin cruzar sus arcos).
– El mapa de la figura requiere 4 colores.
– Desde hace muchos años se sabía que 5 colores
eran suficientes para pintar cualquier mapa, pero
no se había encontrado ningún mapa que
requiriera más de 4.
– Recientemente, después de varios cientos de
años, se ha demostrado que 4 colores siempre
son suficientes.
Búsqueda con retroceso Pág. 21
Coloreado de grafos

El problema que consideraremos aquí:
– Dado un grafo cualquiera, determinar todas las
formas posibles en las que puede pintarse
utilizando no más de m colores.
– Representación elegida: matriz de adyacencias.
– Justificación de la elección: sólo necesitaremos
saber si un arco existe o no.
– Representación de los colores: enteros de 1 a m.
– Representación de la solución: vector de colores.
– Espacio de estados para n=3 y m=3.
x[1]=1
x[2]=1
x[3]=1
x[2]=2
x[2]=3
x[3]=
3
x[3]
=2
Búsqueda con retroceso Pág. 22
x[1]=2
x[1]=3
Coloreado de grafos
algoritmo m_col(ent k:entero;
entsal X:vector[1..n]de nat)
{Se usa una variable global g de tipo grafo.}
para v:=1..m hacer
X[k]:=v
si completable(X,k) entonces
si k=n entonces escribir(X)
sino m_col(k+1,X)
fsi
fsi
fpara
fin
funcion Completable(entsal x:sol;
ent k:entero)
variables b:booleano; j:entero
b:=verdad; j:=1;
mientras (j<k)  b hacer
si g[k,j] y (x[k]=x[j]) entonces
b:=falso
sino j:=j+1
fsi
fmientras
retorna(b)
Búsqueda con retroceso Pág. 23
Ciclos hamiltonianos

Problema: encontrar todos los ciclos
hamiltonianos de un grafo.
– Sea G=(V,A) un grafo no dirigido, conexo con n
vértices.
– Un ciclo hamiltoniano es un camino que visita
una vez cada vértice y vuelve al vértice inicial.
Es decir, v1v2…vn+1 tal que:
 viV, i=1,…,n+1,
 (vi,vi+1)A, i=1,…,n,
 v1=vn+1,
 vivj, i,j=1,…,n tales que i  j.

No se conoce un algoritmo eficiente
para resolver el problema.

Nótese la relación entre el problema del
cálculo de un hamiltoniano y el
problema del viajante de comercio
Búsqueda con retroceso Pág. 24
Ciclos hamiltonianos

Ejemplos:
1
2
3
4
8
7
6
5
Hamiltoniano: 1-2-8-7-6-5-4-3-1
1
5
2
3
4
No contiene ningún hamiltoniano.
Búsqueda con retroceso Pág. 25
Ciclos hamiltonianos

Solución de búsqueda con retroceso:
– En el vector solución (x1,…,xn), xi representa el
vértice visitado en i-ésimo lugar en el ciclo.
– Cálculo de los posibles valores para xk si x1,…,xk1 ya tienen valores asignados:



k=1: x1 puede ser cualquiera de los n
vértices, pero para evitar escribir el mismo
ciclo n veces obligamos que x1=1;
1<k<n: xk puede ser cualquier vértice
distinto de x1,…,xk-1 y conectado por un arco
con xk-1.
k=n: xn sólo puede ser el vértice que queda
sin visitar y debe estar conectado por sendos
arcos con x1 y xn-1.
Búsqueda con retroceso Pág. 26
Ciclos hamiltonianos
– Grafo: matriz de adyacencias (sólo necesitaremos
saber si un arco existe o no)
– solución: vector de vértices.
algoritmo hamiltoniano(ent k:entero;
entsal X:vector[1..n] de nat)
{Se usa una variable global g de tipo grafo.}
para v:=1..n hacer
X[k]:=v;
si completable(k,X) entonces
si k=n entonces
escribir(X)
sino hamiltoniano(k+1,X)
fsi
fsi
fpara
funcion completable(ent k:entero;
ent X:vector[1..n] de nat)
b:=g[X[k-1],X[k]];
para i:=1..k-1 mientras b hacer
si X[i]=X[k] entonces b:=falso fsi
fpara
si k=n  g[X[n],X[1]] entonces
b:=falso
fsi
retorna b
x[1]:=1;
hamiltoniano(2,x);
Búsqueda con retroceso Pág. 27
Atravesar un laberinto

Problema:
– Nos encontramos en una entrada de un laberinto
y debemos intentar atravesarlo.
– Representación: matriz de dimensión nn de
casillas marcadas como libre u ocupada por una
pared.
– Es posible pasar de una casilla a otra moviéndose
sólamente en vertical u horizontal.
– Se debe ir de la casilla (1,1) a la casilla (n,n).
Búsqueda con retroceso Pág. 28
Atravesar un laberinto
– Diseñaremos un algoritmo
de búsqueda con retroceso
de forma que se marcará
en la misma matriz del
laberinto un camino
solución (si existe).
– Si por un camino recorrido
se llega a una casilla desde
la que es imposible
encontrar una solución,
hay que volver atrás y
buscar otro camino.
N MN
M
MN
MN M
MN
N MN N
N N MN M
NM
MN M
MN M
N
NM
M
N MN M N
N MN < <
M < < <
N< <
– Además hay que marcar las casillas por donde
ya se ha pasado para evitar meterse varias veces
en el mismo callejón sin salida, dar vueltas
alrededor de columnas…
Búsqueda con retroceso Pág. 29
Atravesar un laberinto

Estructura de datos:
tipos
casilla = (libre,pared,camino,imposible)
laberinto = vector[1..n,1..n] de casilla
 Solución de búsqueda
...
HayCamino(1,1,lab)
...
con retroceso:
funcion HayCamino(ent x,y:entero;
entsal lab:laberinto)
{Pre: Hemos encontrado un camino desde (1,1)
hasta (x,y).
Post: Devuelve cierto ssi se puede extender
hasta (n,n)}
Búsqueda con retroceso Pág. 30
Atravesar un laberinto
funcion HayCamino(ent x,y:entero;
entsal lab:laberinto)
{devuelve cierto ssi existe camino}
si (x<1)(x>n)(y<1)(y>n)
lab[x,y]libre entonces
devuelve falso
sino
lab[x,y]:=camino;
si (x=n)(y=n) entonces
escribir(lab);
devuelve cierto;
sino
b:= HayCamino(x+1,y,lab) 
HayCamino(x,y+1,lab) 
HayCamino(x-1,y,lab) 
HayCamino(x,y-1,lab);
si b entonces
lab[x,y]:= imposible;
fsi
devuelve b;
fsi
fsi
fin
Búsqueda con retroceso Pág. 31
El problema de la mochila 0-1

Recordar…
– Se tienen n objetos y una mochila.
– El objeto i tiene peso pi y la inclusión del objeto i
en la mochila produce un beneficio bi.
– El objetivo es llenar la mochila, de capacidad C,
de manera que se maximice el beneficio.
 bi x i
maximizar
1 i  n
sujeto a
 pi xi
C
1 i  n
con

x i  { 0 , 1} , bi  0 , pi  0 , 1  i  n
Es el primer problema de optimización
que vamos a resolver con Backtracking.
Búsqueda con retroceso Pág. 32
El problema de la mochila 0-1
– Tuplas de tamaño fijo:
xi=0 si el objeto i-ésimo no se introduce
xi=1 si el objeto se introduce
1
x1=0
x1=1
2
17
x2=0
x2=1
3
10
x3=0
x3=1
4
x4=0
5
x2=0
x3=0
7
18
x3=1
11
8
9
12
14
13
15
25
x3=0
x3=1
19
x4=1
x4=1
x4=1
x4=1
x4=0
x4=0
x4=0
x4=0
6
x2=1
16
20
x3=0
22
x4=1
x4=0
21
23
26
x4=1
x4=0
24
27
29
x4=1
x4=0
28
Elegimos ésta última representación.
Búsqueda con retroceso Pág. 33
x3=1
30
x4=1
31
El problema de la mochila 0-1
Problema de optimización
(maximización): Solo nos interesa la
mejor solución
 En todo momento guardamos el coste
de la mejor solución encontrada hasta
el momento MS (que es una cota
inferior de la mejor solución)
 Sólo buscaremos donde podamos
mejorar respecto a la mejor solución
(poda basada en la mejor solución,
PBMS)

Búsqueda con retroceso Pág. 34
El problema de la mochila 0-1

Formalmente:
– Sea X[1..k-1] la asignación en curso.
– Sea ben el beneficio de la mejor solución que
hemos encontrado en lo que llevamos de
búsqueda (si aun no hemos encontrado ninguna
ben=0)
– c(X,k) es el beneficio de la “mejor” solución que se
puede obtener extendiendo X[1..k-1]
– cota(X,k) es una cota superior de c(X,k).
Es decir, cota(X,k)  c(X,k), para todo X[1..k-1]
– Si cota(X,k)  ben, entonces hacemos backtracking
(podamos)
– ¿cómo calcular cota(X,k) en el problema de la
mochila?
 relajar el requisito de integridad en las
decisiones que aún no hemos hecho:
xi{0,1}, ki n se sustituye por 0xi 1, kin
 aplicar el algoritmo voraz
Búsqueda con retroceso Pág. 35
El problema de la mochila 0-1
tipo vectReal=vector[1..n] de real
{Pre: i1..n:peso[i]>0, benef[i]>0,
i1..n-1:benef[i]/peso[i]benef[i+1]/peso[i+1]}
función cota(benef,peso:vectReal;
cap,ben:real; k:entero)
devuelve real
{cap=capacidad aún libre de la mochila;
ben=beneficio actual;
k=índice del primer objeto a considerar}
principio
si k>n or cap=0.0
entonces devuelve ben
sino
si peso[k]>cap entonces
dev ben+cap/peso[k]*benef[k]
sino
dev cota(benef,peso,cap-peso[k],
ben+benef[k],k+1)
fsi
fsi
fin
Búsqueda con retroceso Pág. 36
El problema de la mochila 0-1
tipo solución=vector[1..n] de 0..1
{variables globales:
benef,peso:vectReal; cap:real}
algoritmo búsqueda(ent solAct:solución;
ent benAct,pesAct:real;
ent k:entero;
e/s sol:solución;
e/s ben:real)
para v:=1 hasta 0 hacer
solAct[k]:=v;
benAct:=benAct+v*benef[k];
pesAct:=pesAct+v*peso[k];
si pesActcap  ben<cota(benef,peso,
cap-pesAct,benAct,k+1) entonces
si k=n entonces
si benAct>ben entonces
sol:=solAct; ben:=benAct
fsi
sino búsqueda(solAct,benAct,pesAct,
k+1,sol,ben)
fsi
fsi
fpara
fin
Búsqueda con retroceso Pág. 37
El problema de la mochila 0-1
algoritmo mochila01(ent benef,peso:vectReal;
ent cap:real;
sal sol:solución;
sal ben:real)
variables obj:entero; solAct:solución
principio
ben:=0.0;
búsqueda(solAct,0.0,0.0,1,sol,ben)
fin

Mejora adicional:
– encontrar una solucion factible (no
necesariamente óptima) con un algoritmo voraz.
Sea r su coste.
– Obviamente r es una cota inferior de la solución
del problema.
– Por lo tanto, podemos inicializar ben:=r

ejercicio: Pensar un algoritmo voraz
que encuentre una solución factible.
Búsqueda con retroceso Pág. 38
El problema de la mochila 0-1

Ejemplo:
–
–
–
–
benef=(11,21,31,33,43,53,55,65)
peso=(1,11,21,23,33,43,45,55)
cap=110
n=8
164.88
1
1
11
1
12
32
1
33
63
1
56
96
0
1
1
89 162.44
139
1
0
66
106
164.66
99
149
0
162
101
151
0
151
1
0
157.11
0
159.79
0
154.88
68
108
0 157.55
159.33
0
158
157.63
160.18
0
139
149
0
1161.63 0
163.81
0
1
0
35
65
109
159
0
0
0
159.76
0
0
155.11
0
157.44
160.22
1
0
159
Búsqueda con retroceso Pág. 39
ben=159
sol=(1,1,1,0,1,1,0,0)
El problema de la mochila 0-1
– De los 29-1 nodos del espacio de estados, sólo se
generaron 33.
– Se podía haber reducido a 26 simplemente
sustituyendo la condición
ben < cota(...)
en el algoritmo “búsqueda” por:
ben < cota(...)
Búsqueda con retroceso Pág. 40
Backtracking genérico para
problemas de optimización

ahora para problemas de minimización
– X[1..k]: asignación actual (solución que estamos
tratando de construir)
– MejorSol: Mejor solución encontrada hasta el
momento (se inicializa a Null)
– MS: Coste de la mejor solución encontrada hasta
el momento (es una cota superior de la solución
óptima). Se inicializa a infinito.
– c’(X,k): devuelve una cota inferior del mejor coste
que se puede obtener a partir de la asignación
actual
– Si c’(X,k)  MS, entonces no sirve de nada seguir
con la asignación actual (podamos, es decir,
hacemos backtracking)
– Es decir, sólo hacemos llamada recursiva si:
completable(X,k) y c’(X,k)<MS
Búsqueda con retroceso Pág. 41
Backtracking genérico para
problemas de optimización
algoritmo BackTracking(ent k:entero;
entsal X:vector[1..n]de valor)
{Pre: X[1..k-1] es completable,
c’(X,k-1)<MS}
para todo v en Ci hacer
X[k]:=v;
si (completable(X,k) 
c’(X,k)<MS) entonces
si Sol(X,k) entonces
MejorSol:= X;
MS:= Coste(X)
fsi;
si k<n entonces
BackTracking(k+1,X)
fsi;
fsi
fpara
Búsqueda con retroceso Pág. 42
Mejoras al esquema de
Backtracking

Arboles dinámicos:
– Hasta ahora hemos considerado árboles de búsqueda
estáticos:
 siguiendo cualquier rama nos encontrábamos las
variables en el mismo orden.
 recorriendo un nivel de izquierda a derecha nos
encontrábamos los valores en el mismo orden
– Arboles dinámicos: ordenes variables

Anticipación (look ahead):
– Cada variable xi guarda la lista de los valores de su
dominio Ci
– Cada vez que se asigna un valor a una variable, se
eliminan de todas las variables no asignadas los valores
incompatibles con la asignación
– Si a alguna variable no le quedan valores posibles,
BACKTRACKING

Eliminación de simetrías:
– En muchos problemas reales existen simetrías que
hacen que varias soluciones sean esencialmente la
misma (via rotaciones, proyecciones,...)
– Encontrar la misma solución varias veces es ineficiente
– Solución: añadir nuevas restricciones que prohiban
soluciones repetidas
Búsqueda con retroceso Pág. 43
Mejoras al esquema de
Backtracking

Vamos a desarrollar un backtracking para las nreinas que introduzca estas mejoras:
– X: vector[1..n] de nat
 x[i]=0, la columna i, aun no tiene reina asignada
 x[i]= j (j<>0), la reina de la columna i esta situada
en la fila j
– tipo dominios es vector[1..n] de lista de nat
 Si L es una variable de tipo dominios,
 L[i] es la lista de los valores posibles para la
variable x[i]
 Inicialmente:
L[i]={1,2,...,n} para i=2..n
L[1]={1,2,...,n/2} (para eliminar simetrías)
Búsqueda con retroceso Pág. 44
N- reinas
algoritmo n-reinas(ent k:entero;
ent L:dominios;
entsal X:vector[1..n]de nat)
{k: numero de variables asignadas,
X: asignación actual
L: valores compatibles con la
asignación actual}
L2:=L
i:=Seleccionar_Variable(X,L); {selección
arbitraria}
para v  L[i] hacer {orden arbitrario}
X[i]:=v;
si anticipación(X,i,v,L2) entonces
si k=n entonces escribir(X)
sino n-reinas(k+1,L2,X)
fsi
fsi
L2:=L;
fpara
X[i]:=0;
fin
Búsqueda con retroceso Pág. 45
N- reinas
funcion anticipacion(ent X:sol;
ent i,v:entero; entsal L2:dominios)
variables b:booleano; j:entero
b:=cierto; j:=1;
mientras (j<n+1)  b hacer
si X[j]=0 entonces
para uL[j] hacer
si u=v  |i-j|=|u-v| entonces
borrar(L[j],v)
fpara
b:=falso
sino j:=j+1
fsi
fmientras
retorna(b)
Para n-reinas:
– seleccionar la variable a la que le queden menos
valores
– asignar los valores en orden aleatorio
Búsqueda con retroceso Pág. 46
Descargar

Búsqueda con retroceso