Damián Lunes 1 de Enero del 2007

El backtracking es una técnica usada en computación que en pocas palabras va explorando un problema por todo un árbol de combinaciones en donde forzosamente alguna de las posibles combinaciones es solución del problema. Es casi la técnica humana cuando se quiere resolver un problema nuevo y no tan obvio, en donde sólo se conocen las reglas del problema y se tiene que ir probando por caminos diferentes para encontrar la solución.

En éste artículo se va a dar una aproximación a la estrategia.

Esta técnica existió mucho antes que los lenguajes de programación y la computadora moderna. La implementación de esta técnica, en lenguajes que no están hechos para ella, se hace comúnmente mediante funciones recursivas. Hay otros lenguajes como Prolog en donde el lenguaje hace nativamente una implementación de la técnica. La razón por la que se usan funciones recursivas es que la “pila de ejecución” del programa se encarga de preservar ordenados y en memoria los estados anteriores, así que es más fácil volver sobre tus propios pasos.

Lo primero que se hace para identificar un problema digno de backtracking es pensar cómo lo resolverías tú como humano, si tu mejor solución es empezar con algunas condiciones iniciales e ir probando caminos hasta llegar a un punto en donde no hay solución y regresar entonces un poco para explorar por otro lado, quizá estes haciendo backtracking. Lo más importante para hacer un backtraking es hacer un “retroceso mínimo” o sea, no destruir todo si no pudiste encontrar una solución, sino sólo borrar lo necesario para poder seguir explorando sin perder todo el camino que has recorrido.

El caso más similar a lo que se debe hacer para implementar un backtracking es pensar en la manera como se sale de un laberinto, primero amarras un hilo en el principio del laberinto y vas decidiendo sobre cada bifurcación hacia donde vas a seguir; al momento de encontrar un callejón sin salida sabes que debes regresar y buscar por el lado contrario, y si los dos lados no te llevan a la salida entonces podrías marcar esa bifurcación con alguna señal, regresar más y buscar otro camino. Es lo que se haría en muy pocas palabras, porque nunca se debería regresar hasta el principio al encontrar un callejón sin salida, se debería retroceder lo menos posible siguiendo al hilo que indica lo que se ha recorrido y no se debería volver a entrar a caminos en marcados.

El algoritmo para salir de ahí se podría definir recursivamente de esta manera (considerando que sólo hay dos opciones en cada bifurcación: izquierda o derecha) :

Avanza por el camino de la derecha desde cierta posición.
avanza_derecha (posicion)
Avanza por el camino de la derecha desde cierta posición.
avanza_izquierda (posicion)
Indica si ya se alcanzó la salida
es_la_salida (posicion)
Indica si ya no se puede seguir desde cierta posición.
es_callejon_sin_salida (posicion) 

Booleano sal_del_laberinto (posicion_actual)
   if es_la_salida (posicion_actual) then
      return VERDADERO
   else
      nueva_posicionavanza_derecha (posicion_actual)
      if es_callejon_sin_salida (nueva_posicion) then
         return FALSO
      else
         if sal_del_laberinto (nueva_posicion) then
             return VERDADERO
         else
             nueva_posicionavanza_izquierda (posicion_actual)
             return sal_del_laberinto (nueva_posicion)
         endif
      endif
   endif
end

Estarán de acuerdo que es muy engorroso hacerlo así, pero sabemos que con todas las precauciones en algún momento saldremos del laberinto, esa es la forma en como se debe pensar un backtracking, nunca se deben recorrer caminos que ya han sido recorridos y retroceder lo menos posible para explorar más a profundidad. Lo que hace tan poderosa a la ténica es que la computadora tiene muchísima más memoria que un humano y no piensa, entonces ella no titubea.

En teoría de gráficas la técnica de backtracking es parecida a la “búsqueda a profundidad” (depth-first search) aunque no necesariamente equivalente. Para los que están familiarizados con las estructuras discretas, imaginen que hay un árbol y cada nodo del árbol es una bifurcación del laberinto; algunas hojas del árbol son las soluciones al problema y algunas otras son callejones sin salida. Entonces para recorrer un árbol lo que se hace (que finalmente es una gráfica) es ir bajando desde la raíz a sus nodos y tratar de abarcar lo más que se pueda por cada camino.

Una aclaración importantísima es que backtracking no es equivalente a recursión, resolver por recursión ciertos problemas (por ej. las torres de Hanoi) no tiene nada que ver muchas veces con usar backtracking. Se está usando backtracking cuando no se sabe exactamente la solución a un problema y se tiene que “andar a ciegas” buscando posibles soluciones, no se buscan soluciones aleatoriamente sino que se planea una estrategia sistemática que agote posibilidades. Cuando se piensa un problema de manera recursiva, únicamente se busca abstraer un caso base del que se pueda partir para resolver todo el problema; en backtracking no hay un caso base, hay condiciones de solubilidad, que no sirven para resolver el problema en sí, sirven para saber que se ha encontrado una solución o no.

Si el problema no es tan general como salir de un laberinto, en el cual no se puede deducir nada estando dentro de él, entonces es posible mejorar el backtracking agregando condiciones de insolubilidad evitando así combinaciones ociosas que definitivamente no van a llegar nunca a una solución, esto se llama “poda” del backtracking. También se puede mejorar el backtracking eligiendo ciertas combinaciones iniciales que nos “den la corazonada” de que así se logrará resolver el problema explorando menos combinaciones, esto se llama “heurística”.

Un ejemplo interesante en el que se puede usar backtracking es:

Imagina que tienes fábricas en distintas ciudades, y cada fábrica tiene al menos otra que está conectada con ella por una carretera. Ahora quieres poner estaciones de servicio en algunas fábricas de tal manera que todas las fábricas tengan al menos una estación de servicio adyacente. Las fábricas que tienen estación de servicio no necesitan tener otra estación adyacente.

La pregunta sería: ¿en qué fábricas se deben instalar estaciones de servicio para lograr tener el mínimo número de estaciones de servicio posibles?

En este problema se puede “podar” el backtracking muy fácilmente evitando que siga buscando una solución cuando ya se alcanzó el mínimo actual y una buena heurística es empezar colocando estaciones de servicio en las fábricas que tengan un mayor número de fábricas adyacentes.

• Algoritmia y programación
•