Análisis y Diseño de Algoritmos
Tema 6: Vuelta Atrás
Titulación: Grado en Ingeniería del
Software
Contenido
• Introducción
• Técnicas de Vuelta Atrás
– Conceptos generales
– El problema de las n-reinas
– El problema del laberinto
• Extensiones
– Backtracking para enumeración
– Backtracking para optimización
• Referencias
2
Introducción
• Características de los
algoritmos voraces
– Son métodos ESQUEMA GREEDY
constructivos para el
cálculo de soluciones a Solucion sol = solInic;
un problema por pasos. while !esSolucion(sol){
– En cada paso del cont = seleccionarMejor(sol);
algoritmo se toma una sol = sol + cont;
decisión que produce }
una solución parcial más
cercana a la solución
completa del problema.
3
Introducción
• El método seleccionarMejor
escoge la mejor de entre
todas las continuaciones ESQUEMA GREEDY
posibles, teniendo en
cuenta algún criterio que Solucion sol = solInic;
sólo se aplica a las while !esSolucion(sol){
soluciones parciales, pero cont = seleccionarMejor(sol);
sol = sol + cont;
que no tiene que ser el
}
mejor para encontrar la
//sol no tiene por qué ser la solución
solución óptima al // óptima
problema.
4
Introducción
• Una vez escogida una
continuación no hay forma
de cambiar de opinión, la ESQUEMA GREEDY
decisión es irreversible.
• La ventaja es la eficiencia Solucion sol = solInic;
while !esSolucion(sol){
del algoritmo.
cont = seleccionarMejor(sol);
• La desventaja es que en sol = sol + cont;
muchos casos se obtienen }
soluciones lejanas a la //sol no tiene por qué ser la solución
óptima. // óptima
5
Vuelta atrás (backtracking)
• En una hoja del árbol de la figura está la solución a un problema.
¿Cómo llegar a ella?
6
Vuelta atrás (backtracking)
• Nosotros vemos los árboles boca abajo
7
Vuelta atrás (backtracking)
• Nosotros vemos los árboles boca abajo y con la raíz reducida a
un punto
8
Vuelta atrás (backtracking)
• Un video de ejemplo:
• [Link]
• Amarillo avance según un criterio sistemático
• Gris oscuro: aún no visitado
• Gris claro zona visitada y retrocedido.
• Segundo 0:32, dónde se va a producir un retroceso importante.
• Segundo 0:44, ya cerca de la salida, pero ha elegido otro camino
y después rectifica.
• Segundo 1:32, tras haber visitado casi todo el cuadrante superior
izquierdo, ha retrocedido para inicial nueva ruta desde el origen.
9
Vuelta atrás (backtracking)
• El backtracking es también un
método algoritmo ESQUEMA VueltaAtrás
constructivo, en el que las
soluciones se obtienen Solucion backtracking(Solucion sol){
mediante un proceso iterativo if (esSolucion(sol)) return sol;
en el que en cada paso se else{
obtiene una solución más Cont setCont = posContinuacion(sol);
cercana a la solución final. Solucion solAux = null;
• A diferencia de los métodos while (!esVacia(setCont) && solAux==null){
voraces, las decisiones cont = selecciona(setCont);
tomadas durante la ejecución setCont = SetCont – {cont};
del algoritmo pueden solAux=backtracking(sol+cont);
deshacerse (puede volverse }
atrás y tomar un camino return solAux;
distinto). }
}
10
Vuelta atrás (backtracking)
Si sol es una solución ESQUEMA VueltaAtrás
terminamos
Solucion backtracking(Solucion sol){
if (esSolucion(sol)) return sol;
Construimos el conjunto de posibles
else{
continuaciones
Cont setCont = posContinuacion(sol);
Si es vacío, nuestra solución parcial no Solucion solAux = null;
lleva a ninguna solución y devolvemos null while (!esVacia(setCont) && solAux==null){
cont = selecciona(setCont);
Si hay alguna posible continuación, la setCont = SetCont – {cont};
escogemos y continuamos de forma recursiva solAux=backtracking(sol+cont);
con ella. }
return solAux;
Si la llamada recursiva nos devuelve una }
solución terminamos, sino continuamos }
con la siguiente posible continuación.
11
Backtracking: árbol de búsqueda
El problema de las ranas
Supón que hay n (=2) ranas macho (M) y n ranas hembra
(H), dispuestas sobre la fila de 2n+1 piedras tal y como
aparece en la figura:
M→ M→ ←H ←H
Cada rana está mirando en la dirección de la flecha, y sólo
pueden moverse en esa dirección
Cada rana puede saltar a la piedra adyacente si está vacía:
M→ M→ ←H ←H
12
Backtracking: árbol de búsqueda
El problema de las ranas
• O puede salta a la segunda piedra adyacente, si está
vacía, saltando sobre otra rana.
M→ M→ ←H ←H
• ¿existe una secuencia de movimientos que
intercambien a las ranas tal como aparecen en el
dibujo?
←H ←H M→ M→
13
Backtracking: árbol de búsqueda
El problema de las ranas
El árbol del espacio de estados es el árbol que construye el algoritmo durante
la búsqueda de la solución.
MM_HH
• La raíz del árbol es el estado _MMHH M_MHH … …
inicial.
MHM_H
• Los nodos del primer nivel
corresponden a la elección hecha MH_MH MHMH_
para la primera componente de _HMMH
MHHM_
la solución. M_HMH
MHH_M
MH_HM
• Los nodos del segundo nivel son _HMHM
las elecciones realizadas para la H_MHM
segunda componente de una HHM_M
solución.
HH_MM
14
Backtracking: árbol de búsqueda
El problema de las ranas
• Hay nodos del árbol que corresponden
a soluciones parciales que pueden
MM_HH
llevar a una solución global. Estos
nodos tienen sucesores en el árbol.
M_MHH
• Hay otros nodos, que deben _MMHH … …
descartarse, porque corresponden a MHM_H
soluciones parciales a partir de las
cuales no es posible encontrar una MH_MH MHMH_
solución global. En estos nodos se _HMMH
realiza el backtracking. MHHM_
MH_HM
• El algoritmo puede parar cuando M_HMH
MHH_M
encuentra una solución o seguir _HMHM
buscando soluciones distintas por
otros caminos. H_MHM
• En la búsqueda de las soluciones, los HHM_M
nodos suelen visitarse utilizando un
recorrido dfs (primero en profundidad) HH_MM
15
Backtracking: árbol de búsqueda
El problema de las ranas
• Cada nodo es un estado
• Entre dos nodos hay una MM_HH
transición entre estados
_MMHH M_MHH … …
• El árbol de estados puede ser
muy grande, pero normalmente MHM_H
no existe de forma explícita, sino MH_MH MHMH_
que los estados se van _HMMH
MHHM_
construyendo a medida que el M_HMH
MH_HM
MHH_M
algoritmo avanza (on-the-fly) _HMHM
• Sólo se tienen almacenados los H_MHM
estados de la pila de recursividad
que en cada momento se está
HHM_M
resolviendo. HH_MM
16
Backtracking: caracterícticas generales
• Cada vez que se hace backtracking se está podando el
árbol: nos ahorramos considerar todas las decisiones
pendientes desde ese punto.
• El coste es que, en el caso peor, el algoritmo tendrá que
recorrer todo el espacio de búsqueda , lo que puede ser
equivalente a un algoritmo de “fuerza bruta”.
• En cualquier caso, la técnica permite encontrar soluciones
“simples” a problemas aparentemente difíciles de resolver.
• Los algoritmos que utilizan backtracking suelen combinar
recursividad e iteración, por lo que hay que tener mucho
cuidado a la hora de manejar los casos bases de la
recursión, y las condiciones de terminación de los bucles.
17
El problema de las n reinas
• Supongamos que
tenemos un tablero de
ajedrez de tamaño nxn.
Queremos colocar n
reinas de manera que no
se ataquen, es decir, que
no haya
– dos reinas en la misma fila
– dos reinas en la misma
columna
– dos reinas en la misma
diagonal
18
Solución al problema
• Como dos reinas no
pueden estar en la
misma filas, las
soluciones pueden ser
listas como l=[3,0,2,4,1]
en las que cada
elemento l[i] representa
la columna de la fila i en
la que está la reina.
19
Solución al problema
• La lista l se construye de forma incremental.
• Partimos de una lista vacía []
• Suponiendo que la lista es [a0,…,ai-1], para añadir
una nueva reina en la fila i,
– escogemos la primera posición ai de una reina que no
ataca a ninguna de las que ya están en el tablero.
– si no es posible, retrocedemos y cambiamos ai-1 para
buscar otra solución
– y así sucesivamente…
20
El problema de las n reinas
código java
public static List<Integer> reinas(int n){
for (int i = 0; i<n; i++){
List<Integer> lista = new ArrayList<Integer>();
[Link](i);
boolean sol = reinas(n,lista);
if (sol) return lista;
}
return null;
}
public static boolean reinas(int n, List<Integer> lista){
if ([Link]()==n) return true;
for (int i = 0; i<n; i++){
if(&& noCome(i,lista)){
[Link](i);
if (reinas(n,lista)) return true;
else [Link](new Integer(i));
}
}
return false;
}
21
El problema de las n reinas
código java
public static boolean noCome(int i, List<Integer> lista){
int j = [Link]();
for (int k = 0; k <[Link](); k++){
if (j-i == k - [Link](k)) return false;
if (i+j == k + [Link](k)) return false;
}
return true;
}
22
Ejemplo (caso n = 4)
x x
x
x x
x x
x
x
x
x x
x x
x
x
x
x
23
El problema del laberinto
salida
• Tenemos un laberinto que
queremos atravesar desde un
punto de entrada hasta un
punto de salida.
• El laberinto está representado
por un array bidimensional
(cuadrado), en el que cada
componente puede ser o no
un obstáculo.
• La solución al problema es un
camino que transcurra desde
la entrada hasta la salida a
través de componentes no
bloqueadas.
entrada
24
El problema del laberinto: Una solución
public class Posicion {
private int x;
private int y;
• Una solución puede public Posicion(int i,int j){
this.x = i; this.y = j;
representarse como una }
public int x(){
lista de posiciones }
return x;
válidas del laberinto, public int y(){
que empieza en la
return y;
}
entrada, y termina en la
public boolean equals(Object o){
return (o instanceof Posicion)&&
salida. ((Posicion)o).x==x &&
((Posicion)o).y==y;
}
public int hashCode(){
return x*7+y*17;
}
public String toString(){
return "("+x+","+y+")";
}
...} 25
El problema del laberinto: Una solución
• Dada una posición, la siguiente en el camino
de salida puede ir hacia el norte, sur, este u
oeste.
public class Posicion {
………
public Posicion siguiente(int dir){
if (dir==0) return new Posicion(i-1,j);
else if (dir==1) return new Posicion(i+1,j);
else if (dir==2) return new Posicion(i,j+1);
else return new Posicion(i,j-1);
}
}
26
El problema del laberinto: Una solución
• El laberinto es un objeto que tiene un array
bidimensional, la entrada, la salida, y un
método para saber si una posición está dentro
del laberinto
public class Laberinto {
private int[][] laberinto;
private Posicion entrada,salida;
public Laberinto(int[][] lab,Posicion ent,Posicion sal){
[Link] = lab;
[Link] = ent;
[Link] = sal;
}
public boolean estaEnLaberinto(Posicion pos){
if (pos.x()<0 || pos.x()>=[Link]) return false;
if (pos.y()<0 || pos.y()>=[Link]) return false;
return true;
}
……
27
El problema del laberinto: Una solución
• La clase laberinto tiene un método solucion()
que produce una lista de posiciones con un
camino en el laberinto desde la entrada hasta
la salida, o null, si no existe ninguna solución
• El método llama a un método local que recorre
el laberinto de forma recursiva.
public class Laberinto {
…..
public List<Posicion> solucion(){
List<Posicion> lista = new ArrayList<Posicion>();
[Link](entrada);
if (solucion(lista)) return lista;
else return null;
}
……
28
El problema del laberinto: Una solución
public class Laberinto {
private boolean solucion(List<Posicion> lista){
if ([Link]()) return false;
Posicion posAct = [Link]([Link]()-1);
if ([Link](salida)) return true;
for (int i=0; i<4; i++){
Posicion posSig = [Link](i);
if (&& // no hay ciclos en el camino
estaEnLaberinto(posSig)&& // la nueva posición es correcta
laberinto[posSig.x()][posSig.y()]!=1){
[Link](posSig);
if (! solucion(lista)) [Link]([Link]()-1);
else return true;
}
}
return false;
}
backtracking
29
El backtracking puede hacer más cosas
• El enfoque y aplicaciones mostradas anteriormente
corresponden a la resolución de problemas de decisión o
satisfacción, es decir,
– determinar si un problema tiene o no solución de una forma
dada
– construir una solución de un tipo específico o determinar que
no existe
• El backtracking puede utilizarse también en otro tipo de
situaciones:
– Problemas de conteo o enumeración: determinar cuantas
soluciones de las características deseadas existen, o
encontrarlas todas
– Problemas de optimización: encontrar una solución que haga
máxima alguna función de calidad.
30
Backtracking para encontrar todas las
soluciones
• En los problemas anteriores, el objetivo era
encontrar una solución válida, por lo que en el
momento en el que se encuentra, la búsqueda
termina.
• Para adaptar este enfoque a problemas de
enumeración hay que continuar la búsqueda
hasta que se han encontrado todas las
soluciones.
• El árbol de búsqueda ha de recorrerse
completamente, visitando todos los nodos
prometedores.
31
Backtracking por enumeración
ESQUEMA VueltaAtrás (encontrar el número de soluciones)
int backtracking(Solucion sol){
if (esSolucion(sol)) return 1;
else{
Cont setCont = posContinuacion(sol);
int num = 0;
while (!esVacia(setCont)){
cont = selecciona(setCont);
setCont = SetCont – {cont};
int num1=backtracking(sol+cont);
num += num1
}
return num;
}
}
32
Backtracking por enumeración
ESQUEMA VueltaAtrás (encontrar todas las soluciones)
void backtracking(List<Solucion> listaSol, Solucion sol){
if (esSolucion(sol)) [Link](sol);
else{
Cont setCont = posContinuacion(sol);
while (!esVacia(setCont)){
cont = selecciona(setCont);
setCont = SetCont – {cont};
backtracking(listaSol, sol+cont);
}
}
}
33
Tamaño del árbol de búsqueda
• El proceso de enumeración puede ser muy
costoso debido al tamaño del árbol de búsqueda.
• Este tamaño puede estimarse como sigue:
– Sea c1 el número de decisiones posibles en el nodo
inicial
– Se elige una decisión al azar, y se repite el
procedimiento obteniéndose ci, 1≤ i ≤ L
– Si ci se toma como promedio de las decisiones
factibles en el nivel i-ésimo, entonces el tamaño T del
árbol es
34
El problema del la n reinas
public static void reinas(int n,List<List<Integer>> todas){
List<Integer> actual = new ArrayList<Integer>();
reinas(n,actual,todas);
}
public static void reinas(int n, List<Integer> actual, List<List<Integer>> todas){
if ([Link]()==n) [Link](actual);
else{
for (int i = 0; i<n; i++){
if(&& noCome(i,actual)){
List<Integer> actualaux = new ArrayList<Integer>(actual);
[Link](i);
reinas(n,actualaux,todas);
}
}
}
}
35
Ejemplo para n = 5
[[0, 2, 4, 1, 3],
[0, 3, 1, 4, 2],
[1, 3, 0, 2, 4],
[1, 4, 2, 0, 3],
[2, 0, 3, 1, 4],
[2, 4, 1, 3, 0],
[3, 0, 2, 4, 1],
[3, 1, 4, 2, 0],
[4, 1, 3, 0, 2],
[4, 2, 0, 3, 1]]
36
Sólo queremos lo mejor
• En el caso de problemas de optimización, nos
interesa la mejor, de entre todas las
soluciones factibles.
• El esquema de la solución es muy similar, ya
que hay que explorar todas las soluciones
válidas posibles.
• Tenemos que arrastrar la mejor solución
conocida en cada momento para compararla
con cada solución que se encuentre.
37
Backtracking para optimización
ESQUEMA VueltaAtrás (la mejor solución)
Solucion backtracking(Solucion sol,Solucion msol, int mcal){
if (esSolucion(sol)) {
int cal = calidad(sol);
if (mcal > cal) return msol;
else return sol;
};
else{
Cont setCont = posContinuacion(sol);
while (!esVacia(setCont)){
cont = selecciona(setCont);
setCont = SetCont – {cont};
Solucion otra=backtracking(sol+cont,msol,mcal);
if (calidad(otra)>mcal) msol = otra; mcal = calidad(otra)
}
return msol;
}
}
38
El problema de la suma de subconjuntos
39
El problema de la suma de subconjuntos
public static SortedSet<Integer> mejorSub(SortedSet<Integer> conj, int d){
SortedSet<Integer> sub = new TreeSet<Integer>();
return mejorSub(conj,sub,d,0);
}
public static SortedSet<Integer> mejorSub(SortedSet<Integer> conj,
SortedSet<Integer> mejor,int d,int cal){
SortedSet<Integer> conjMejor = mejor;
int sumaMejor = cal;
for (int elem:conj){
if ( && noMenor(elem,mejor)&& cal+elem <= d ){
SortedSet<Integer> aux = new TreeSet<Integer>(mejor);
[Link](new Integer(elem));
SortedSet<Integer> otro = mejorSub(conj,aux,d,cal+elem);
int suma = 0;
for (int e:otro) suma+=e;
if (suma > sumaMejor) {
mejor = otro;sumaMejor = suma;
} public static boolean noMenor(int elem, SortedSet<Integer>
} set){
for (int e:set){
} if (elem <= e) return false;
return conjMejor; }
} return true;
}
40
Árbol de Búsqueda
[]
7
3 5
[3] [5] 6 [6] [7]
8 10
[3,5] [3,6] [3,7] [5,6] [5,7] 13 [6,7]
9 11 12
[3,5,6] [3,5,7]
14 15
41
Referencias
• Introduction to The Design & Analysis of
Algorithms. A. Levitin. Ed. Adison-Wesley
• Introduction to Algorithms. T. H. Cormen, C. E.
Leiserson, R. L. Rivest, C. Stein. Ed. The MIT
Press
42
