PDF de programación - Búsqueda con retroceso

Búsqueda con retroceso

v Introducción
v El problema de las ocho reinas
v El problema de la suma de

subconjuntos

v Coloreado de grafos
v Ciclos hamiltonianos
v Atravesar un laberinto
v El recorrido del caballo de ajedrez
v El problema de la mochila 0-1
v Reconstrucción de puntos

a partir de las distancias

v Árboles de juego: tic-tac-toe

2
16

26
36
44
52
56
74

85
95

J. Campos - C.P.S.

Esquemas algorítmicos - Búsqueda con retroceso

Búsqueda con retroceso:
Introducción

v Problemas que consideraremos:

– Búsqueda de la mejor o del conjunto de todas

las soluciones que satisfacen ciertas
condiciones.

– Cada solución es el resultado de una secuencia

de decisiones.

– Existe una función objetivo que debe ser

satisfecha por cada selección u optimizada (si
sólo queremos la mejor).

– 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.

J. Campos - C.P.S.

Esquemas algorítmicos - Búsqueda con retroceso

Búsqueda con retroceso:
Introducción

v Planteamiento del problema:

– Se trata de hallar todas las soluciones que

satisfagan un predicado P.

– La solución debe poder expresarse como una

tupla (x1,…,xn) donde cada xi pertenece a un Ci.

– Si |Ci|=ti, entonces hay

n
ti
i =1

t =


n-tuplas candidatas para satisfacer P.

– Método de fuerza bruta: examinar las t n-tuplas

y seleccionar las que satisfacen P.

– 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.

J. Campos - C.P.S.

Esquemas algorítmicos - Búsqueda con retroceso

Búsqueda con retroceso:
Introducción

– Deben existir unas funciones objetivo parciales o

predicados acotadores Pi(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:

u 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);

u implícitas: describen las relaciones que

deben cumplirse entre los xi (qué soluciones
posibles satisfacen el predicado objetivo P).

J. Campos - C.P.S.

Esquemas algorítmicos - Búsqueda con retroceso

·



·
Búsqueda con retroceso:
Introducción

v 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).

Fuerza bruta:



Ł

64
8


= 4.426.165.368
ł

– 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.

J. Campos - C.P.S.

Esquemas algorítmicos - Búsqueda con retroceso

Búsqueda con retroceso:
Introducción

– Restricciones explícitas:

Ci = {1,2,3,4,5,6,7,8}, 1=i=8

El espacio de soluciones consta de

88 8-tuplas (16.777.216 8-tuplas)

– Restricciones implícitas:

no puede haber dos reinas en la misma
columna ni en la misma diagonal

– En particular, se deduce que todas las soluciones

son permutaciones de la 8-tupla (1,2,3,4,5,6,7,8).

El espacio de soluciones se reduce de
88 8-tuplas (16.777.216) a 8! 8-tuplas (40.320)

1 2

3 4

5

6 7 8

1
2
3
4
5
6
7
8

Una solución: (4,6,8,2,7,1,3,5)

J. Campos - C.P.S.

Esquemas algorítmicos - Búsqueda con retroceso



Búsqueda con retroceso:
Introducción

v Volviendo al planteamiento general:

– Para facilitar la búsqueda, se adopta una

organización en árbol del espacio de soluciones.

v En el ejemplo, para el problema de las

cuatro reinas (en un tablero 4· 4):

x1=1

x1=2

18

2

1

x1=3

x1=4

34

50

x2=2

x2=3
8

3

x2=4

x2=1

x2=4

x2=1

x2=4

x2=1

13

19

29

35

45

51

x2=3
24

x2=2
40

x2=2
56

x2=3

61

x3= 3

4 2

4 2

3

3

4 1

4 1

3

2

4 1

4 1

2

2

3 1

3 1

2

4

6

9

11

14

16

20

22

25

27

30

32

36

38

41

43

46

48

52

54

57

59

62

64

x4= 4

4

2

3

3

2

4

4

3

1

1

3

4

2

4

1

2

2

3

3

1

2

2

1

5

7

10

12

15

17

21

23

26

28

31

33

37

39

42

44

47

49

53

55

58

60

63

65

El espacio de soluciones está definido por todos los
caminos desde la raíz a cada hoja (hay 4! hojas).

J. Campos - C.P.S.

Esquemas algorítmicos - Búsqueda con retroceso

Búsqueda con retroceso:
Introducción

v Esquema algorítmico:

– Sea (x1,…,xi) un camino de la raíz hasta un nodo

del árbol del espacio de estados.

– Sea G(x1,…,xi) el conjunto de los valores posibles
de xi+1 tales que (x1,…,xi+1) es un camino hasta un
nodo del árbol.

– Suponemos que existe algún predicado acotador

A tal que A(x1,…,xi+1) es falso si el camino
(x1,…,xi+1) no puede extenderse para alcanzar un
nodo de respuesta (i.e., una solución).

– Por tanto, los candidatos para xi+1 son los valores

de G tales que satisfacen A.

– Supongamos, finalmente, que existe un
predicado R que determina si un camino
(x1,…,xi+1) termina en un nodo respuesta (i.e., es
ya una solución).

J. Campos - C.P.S.

Esquemas algorítmicos - Búsqueda con retroceso

Búsqueda con retroceso:
Introducción

algoritmo retroceso(ent k:entero;
algoritmo retroceso(ent k:entero;

entsal solución:vector[1..n]de elmto)
entsal solución:vector[1..n]de elmto)

{Pre: solución[1..k-1] es ‘prometedora’}
{Pre: solución[1..k-1] es ‘prometedora’}
variable nodo:elmto
variable nodo:elmto
principio
principio

para todo nodo en G(solución,1,k-1) hacer
para todo nodo en G(solución,1,k-1) hacer

solución[k]:=nodo;
solución[k]:=nodo;
si A(solución,1,k)
si A(solución,1,k)

entonces
entonces

si R(solución,1,k)
si R(solución,1,k)

entonces guardar(solución,1,k)
entonces guardar(solución,1,k)

fsi;
fsi;
retroceso(k+1,solución)
retroceso(k+1,solución)

fsi
fsi
fpara
fpara

fin
fin

La llamada inicial es:

...
...
retroceso(1,solución);
retroceso(1,solución);
...
...

J. Campos - C.P.S.

Esquemas algorítmicos - Búsqueda con retroceso

Búsqueda con retroceso:
Introducción

v En el ejemplo de las cuatro reinas:

· ·

· · · ·

·

(a)

(b)

(c)

(d)

· · · ·

(e)

· · ·

(f)

(g)

· ·

(h)

1

x1=1

2

x1=2

18

x2=2

x2=3
8

3

x2=4

x2=1

13

19

x2=3
24

x3=

2

4 2

3

9

11

14

16

x4=

3

15

x2=4

29

1

30

3

31

(16 nodos frente a
los 65 del árbol completo)

J. Campos - C.P.S.

Esquemas algorítmicos - Búsqueda con retroceso

Búsqueda con retroceso:
Introducción

v De nuevo, en general:

– 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:

u k = n+1, o cuando
u ningún nodo generado por G satisface A.

– Backtracking =

= búsqueda de primero en profundidad y

con predicados acotadores

J. Campos - C.P.S.

Esquemas algorítmicos - Búsqueda con retroceso

Búsqueda con retroceso:
Introducción

– El algoritmo anterior halla todas las soluciones y

además éstas pueden ser de longitud variable.

v 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):

si R(solución,1,k)

entonces guardar(solución,1,k)
sino retroceso(k+1,solución)

fsi

– 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 los
predicados acotadores 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).

J. Campos - C.P.S.

Esquemas algorítmicos - Búsqueda con retroceso

Búsqueda con retroceso:
Introducción

v Sobre la eficiencia:

– Depende de:

u el tiempo necesario para generar un

elemento solución[k],

u el número de elementos solución que
satisfacen las restricciones explícitas G,

u el tiempo de ejecución de los predicados

acotadores A, y

u el número de elementos solución[k] que

satisfacen los predicados A.

– Mejoras:

u 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(n) nodos a generar
en total
– En el peor caso, O(p(n)· 2n) ó O(p(n)· n!),
con p(n) un polinomio

u Si es posible: reordenar las selecciones de
forma que |C1|<|C2|<
<|Cn|, y así cabe
esperar que se explorarán menos caminos.
Esquemas algorítmicos - Búsqueda con retroceso

J. Campos - C.P.S.


Búsqueda con retroceso:
Introducción

– Estimación a priori del número de nodos

generados:

u Idea: generar un camino aleatorio en el

árbol del espacio de estados.

u Sea xi el nodo del camino aleatorio en el

nivel i y sea mi el número de hijos de xi que
satisfacen el predicado acotador A.

u El siguiente nodo del camino aleatorio se

obtiene aleatoriamente de entre esos mi.
u La genera