Backtracking

Introducción

Vuelta atrás, conocido como Backtracking es una estrategia para encontrar soluciones a problemas que satisfacen restricciones. El término «backtrack» fue acuñado por primera vez por el matemático estadounidense D. H. Lehmer en la década de 1950.

Descripción del algoritmo

En su forma primaria, la idea de backtracking se asemeja a un recorrido en profundidad dentro de un grafo dirigido. El grafo en cuestión suele ser un árbol, o por lo menos no contiene ciclos. Sea cual sea su estructura, existe sólo implícitamente. El objetivo del recorrido es encontrar soluciones para algún problema.

Esto se consigue construyendo soluciones parciales a medida que progresa el recorrido; estas soluciones parciales limitan las regiones en las que se puede encontrar una solución completa. El recorrido tiene éxito si, procediendo de esta forma, se puede definir por completo una solución.

En este caso el algoritmo puede bien detenerse o bien seguir buscando soluciones alternativas . Por otra parte, el recorrido no tiene éxito si en alguna etapa la solución parcial construida hasta el momento no se puede completar. En tal caso, el recorrido vuelve atrás exactamente igual que en un recorrido en profundidad, eliminando sobre la marcha los elementos que se hubieran añadido en cada fase. Cuando vuelve a un nodo que tiene uno o más vecinos sin explorar, prosigue el recorrido de una solución.

Pseudocódigo

El pseudocódigo del algoritmo de Vuelta atráses el siguiente:

proc Backtracking (↕X[1 . . . i ]: TSolución, ↑ok: B)
variables L: ListaComponentes
inicio
si EsSolución (X) entonces ok CIERTO
en otro caso
ok FALSO
L=Candidatos (X)
mientras ¬ok ^ ¬Vacía (L) hacer
X[i + 1] Cabeza (L); L Resto (L)
Backtracking (X, ok)
finmientras
finsi
fin

Podemos visualizar el funcionamiento de una técnica de backtracking como la exploración en profundidad de un grafo. Cada vértice del grafo es un posible estado de la solución del problema. Cada arco del grafo representa la transición entre dos estados de la solución (i.e., la toma de una decisión).

Típicamente el tamaño de este grafo será inmenso, por lo que no existirá de manera explícita. En cada momento sólo tenemos en una estructura nodos que van desde el estado inicial al estado actual. Si cada secuencia de decisiones distinta da lugar a un estado diferente, el grafo es un árbol (el árbol de estados).