PDF de programación - Backtracking

Backtracking

Diseño y Análisis de Algoritmos

Backtracking

Contenidos

Contenidos

1

Introducción

2 Árboles de búsqueda

3 N reinas

4 Otros problemas

5 Ramificación y poda

6 Poda alfa-beta

7 Esquemas generales

URJC

DAA

2 / 67

Backtracking

Introducción

Introducción

URJC

DAA

3 / 67

Backtracking - Vuelta atrás

Backtracking

Introducción

Estrategia para encontrar soluciones a problemas con restricciones
definidos sobre espacios discretos (de elevado tamaño)

Construye soluciones parciales progresivamente, las cuales deben
cumplir las restricciones del problema

El recorrido (en profundidad) tiene éxito si, procediendo de esta
forma, se puede definir por completo una solución (en una hoja de un
árbol de recursión)

Puede detenerse al encontrar una solución o seguir hasta encontrar
todas

Si en alguna etapa la solución parcial construida hasta el momento no
se puede completar, se vuelve atrás deshaciendo la solución parcial,
hasta un punto donde puede seguir explorando posibles soluciones

Es un método de “fuerza bruta” pero “inteligente”

URJC

DAA

4 / 67

Ejemplo - 4 reinas

Backtracking

Introducción

URJC

DAA

5 / 67

Backtracking

Árboles de búsqueda

Árboles de búsqueda

URJC

DAA

6 / 67

Permutaciones de {a, b, c}

Backtracking

Árboles de búsqueda

URJC

DAA

7 / 67

acbbccbcabaacab(a,b,c)(a,c,b)(b,a,c)(b,c,a)(c,a,b)(c,b,a) Permutaciones de {a, b, c}

Backtracking

Árboles de búsqueda

URJC

DAA

8 / 67

acbbccbcabaacab(a,b,c)(a,c,b)(b,a,c)(b,c,a)(c,a,b)(c,b,a)primerelementosegundoelementotercerelemento3 llamadas2 llamadas1 llamadapermutación Permutaciones de {a, b, c}

Backtracking

Árboles de búsqueda

¿Cuántas llamadas recursivas se hacen en cada nivel?

3, 2, 1 (se podrían controlar con bucles)
Pero lo más fácil es generar siempre 3 posibles llamadas, y usar un
vector de valores booleanos para ver si realmente se debe realizar la
llamada recursiva
El vector de booleanos se puede pasar por valor o referencia

Referencia: habrá que deshacer los cambios al retroceder (C o Java)

Valor: no será necesario deshacer cambios

El nivel de la llamada indica la posición del nuevo elemento a añadir

Al llegar al último nivel (a las hojas) tenemos completada la
permutación

URJC

DAA

9 / 67

Implementación - I

Backtracking

Árboles de búsqueda

= new boolean[n];

1 void permutaciones(int n){
int[] perm = new int[n];
2
3
boolean[] libres
4
5
6
7
8
9 }

for(int i=0; i<n; i++)

libres[i] = true;

perms(n, 0, perm, libres);

for(int i=0; i<v.length; i++)
System.out.print(v[i]+" ");

10
11 void imprimir(int[] v){
12
13
14
15
16 }

System.out.println();

URJC

DAA

10 / 67

Implementación - II

Backtracking

Árboles de búsqueda

for(int k=0; k<n; k++)

if(xs[k]){

solucion[i] = k;
xs[k] = false;

1 void perms(int n, int i, int[] solucion, boolean[] xs){
2
3
4
5
6
7
8
9
10
11
12
13
14 }

perms(n, i+1, solucion, xs);

if(i==n-1)

imprimir(solucion);

else

xs[k] = true;

}

n: número de elementos (profundidad del árbol)
i: posición del elemento a insertar
solucion: permutación parcial construida
xs: indica los elementos incluidos en la solución parcial

URJC

DAA

11 / 67

Backtracking

Árboles de búsqueda

Partes de {a, b, c}

Solución - árbol binario

URJC

DAA

12 / 67

01010{c}{b}{ }1{b,c}01010{a,c}{a,b}{a}1{a,b,c}01 Backtracking

Árboles de búsqueda

Partes de {a, b, c}

Solución - árbol binario

URJC

DAA

13 / 67

01{c}{b}{ }{b,c}010{a,c}{a,b}{a}1{a,b,c}01010101se incluye: ase incluye: bse incluye: c Backtracking

Árboles de búsqueda

Partes de {a, b, c}

Solución - árbol binario

Árbol binario

En cada nodo decides si un elemento estará presente o no

Simplemente crea un vector un vector de valores booleanos

[1, 0, 1] = {a, c}

No es necesario deshacer los cambios

URJC

DAA

14 / 67

Backtracking

Árboles de búsqueda

Implementación - I
Solución - árbol binario

boolean[] subc = new boolean[c.length];

partes1(c.length, 0, c, subc);

1 void partesConj1(int[] c){
2
3
4
5 }
6
7 void imprimir(int[] c, boolean[] v){
8
9
10
11
12
13 }

System.out.print(c[i]+" ");

for(int i=0; i<v.length; i++)

if(v[i])

System.out.println();

URJC

DAA

15 / 67

Backtracking

Árboles de búsqueda

Implementación - II
Solución - árbol binario

if(k==0)

else

subc[i] = false;

subc[i] = true;

for(int k=0; k<=1; k++){

1 void partes1(int n, int i, int[] c, boolean[] subc){
2
3
4
5
6
7
8
9
10
11
12
13 }

partes1(n, i+1, c, subc);

if(i==n-1)

imprimir(c,subc);

else

}

n: número de elementos (profundidad del árbol)
i: elemento a considerar (nivel del árbol)
c: vector de elementos
subc: valores booleanos que definen los subconjuntos

URJC

DAA

16 / 67

Backtracking

Árboles de búsqueda

Partes de {a, b, c}

Solución - subconjunto en cada nodo

URJC

DAA

17 / 67

acbc{c}{b}{ }{b,c}{a,c}{a,b}{a}{a,b,c}bcc Backtracking

Árboles de búsqueda

Partes de {a, b, c}

Solución - subconjunto en cada nodo

La etiqueta de la rama indica qué elemento a insertar

URJC

DAA

18 / 67

acbc{c}{b}{ }{b,c}{a,c}{a,b}{a}{a,b,c}bcc0 elementos1 elemento2 elementos3 elementos Backtracking

Árboles de búsqueda

Partes de {a, b, c}

Solución - subconjunto en cada nodo

El árbol de recursión no es binario

En el nivel i las soluciones tienen i elementos

Crea un vector con los índices de los elementos que se van incluyendo

[0, 2] = {a, c}

Tiene la mitad de nodos (factor constante) que el árbol binario del
primer algoritmo

Se obtiene un subconjunto en cada nodo (no solo en las hojas)

URJC

DAA

19 / 67

Backtracking

Árboles de búsqueda

Partes de {a, b, c}

Solución - subconjunto en cada nodo

Ahora es necesario llevar dos índices

Posición en la solución del elemento a incluir
Índice del elemento a incluir (qué elemento se incluye)

URJC

DAA

20 / 67

0212122jj+1n-1j+2...-1 Backtracking

Árboles de búsqueda

Implementación - I
Solución - subconjunto en cada nodo

1 void partesConj2(int[] c){
2
3
4
5 }
6
7 void imprimir(int[] c, int[] subc, int fin){
8
9
10
11
12 }

System.out.print (c[subc[i]]+" ");

for(int i=0; i<=fin; i++)

int[] subc = new int[c.length];

partes2(c.length, 0, -1, c, subc);

System.out.println();

URJC

DAA

21 / 67

Backtracking

Árboles de búsqueda

Implementación - II
Solución - subconjunto en cada nodo

imprimir(c, subc, i-1);

1 void partes2(int n, int i, int j, int[] c, int[] subc){
2
3
4
5
6
7
8
9 }

partes2(n, i+1, k, c, subc);

for(int k=j+1; k<n; k++){

subc[i] = c[k];

}

n: número de elementos (profundidad máxima del árbol)

i: posición en la solución del elemento a incluir

j: índice del elemento a incluir (qué elemento se incluye)

c: conjunto (vector) original

subc: subconjuntos hallados

URJC

DAA

22 / 67

Backtracking

N reinas

N reinas

URJC

DAA

23 / 67

Backtracking

N reinas

N reinas
Problema de las N reinas

Dado un “tablero ajedrez” de n × n celdas, se pide ubicar n reinas de
modo que no se amenacen

No pueden estar en la misma fila
No pueden estar en la misma columna
No pueden estar en la misma diagonal (principal o secundaria)

Ejemplo más famoso de problema que puede resolverse aplicando
backtracking

URJC

DAA

24 / 67

8 reinas

Backtracking

N reinas

Para n = 8 hay 92 soluciones posibles

Aunque 12 únicas

Las demás pueden obtenerse aplicando simetrías, rotaciones y
traslaciones

El problema puede solicitar encontrar una solución o todas

URJC

DAA

25 / 67

N reinas

Backtracking

N reinas

Solución obvia pero absurda:

Probar las 2n2

formas de colocar reinas en el tablero

1,84 · 1019 para n = 8
65536 para n = 4

Pero los conjuntos solución solo deben contener n elementos

Esto reduciría nuestro espacio de búsqueda an2



n

4,42 · 1010 para n = 8
1820 para n = 4

URJC

DAA

26 / 67

N reinas

Backtracking

N reinas

Además solo puede haber una reina por cada columna:

Esto reduce las posibilidades a nn (hay n formas de colocar una reina
en una columna, y hay n columnas)

16777216 para n = 8
256 para n = 4

Pero además, no puede haber dos reinas en la misma fila

Esto convierte nuestro problema en la búsqueda de una permutación
con n! posibilidades (lo cual sigue siendo elevado)

40320 para n = 8
24 para n = 4

URJC

DAA

27 / 67

N reinas

Backtracking

N reinas

Formato de la solución:

(fila de la columna 1, fila de la columna 2,. . . ,fila de la columna n)

(2, 4, 1, 3) en la figura

Todas las filas son diferentes y tienen que estar representadas

Tendremos que buscar las permutaciones válidas

URJC

DAA

28 / 67

Árbol de búsqueda para N = 4

Backtracking

N reinas

Podemos emplear un algoritmo para buscar permutaciones

Al llegar a una hoja se “han colocado” las cuatro reinas y podemos
probar si la solución es válida
Pero, podemos comprobar si la solución parcial puede llegar a ser
solución final antes de llegar a una hoja

Podaríamos el árbol ahorrando cálculos

URJC

DAA

29 / 67

1234234344324234232134344314134131124244214124121123233213123121 Árbol de búsqueda para N = 4

Backtracking

N reinas

Solo se muestra el árbol hasta encontrar la primera solución válida

URJC

DAA

30 / 67

122341341332342 Árbol de búsqueda podado para N = 4

Backtracking

N reinas

URJC

DAA

31 / 67

1234234344324234232134344314134131124244214124121123233213123121solución no válidasolución parcial válidasolución completa válidanodo no explorado Implementación

Backtracking

N reinas

Para verificar que una solución parcial es válida usamos:

f: filas libres
dp: diagonales principales libres (columna − fila + n − 1)
ds: diagonales secundarias libres (columna + fila)

c: solución parcial

URJC

DAA

32 / 67

filasdiagonalessecundariasdiagonalesprincipales012365432100123456c - f + n - 1c + ff Implementación - I

Backtracking

N reinas

int[] c = new int[n];

boolean[] f = new boolean[n];
for(int i=0; i<n; i++)

f[i] = true;

1 void n_reinas(int n){
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 }

dp[i] = true;

ds[i] = true;