Algoritmo de Búsqueda con Retroceso

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.

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

Búsqueda con retroceso: Introducción
(Gp:) 1
(Gp:) 2
(Gp:) 3
(Gp:) 4
(Gp:) 5
(Gp:) 6
(Gp:) 7
(Gp:) 8
(Gp:) 1
(Gp:) 2
(Gp:) 3
(Gp:) 4
(Gp:) 5
(Gp:) 6
(Gp:) 7
(Gp:) 8

Formulación 1:

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: Introducción
(Gp:)
(Gp:) 64
(Gp:) 8
(Gp:) ??
(Gp:) ??
(Gp:) ??
(Gp:) ??
(Gp:) ??
(Gp:) ??
(Gp:) ?
(Gp:) 4
(Gp:) .
(Gp:) 426
(Gp:) .
(Gp:) 165
(Gp:) .
(Gp:) 368

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: Introducción

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+1).

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: 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: Introducción

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