Backtraking

La técnica de backtracking esta muy asociada a la recursividad, o mas propiamente, a la estructura recursiva de la mayoría de tipos de datos: listas, árboles, etc.

Esta técnica consiste básicamente en :

• Enumerar sistemáticamente las alternativas que existen en cada momento para dar con la solución a un problema.
  
  
• Se prueba una alternativa, guardando memoria del resto de alternativas.
  
  
• Si no damos con la solución, podemos dar marcha atrás (backtracking) y probar otra alternativa.
  
  

Para entender el concepto pongamos un ejemplo muy típico de la vida real. Supongamos que nos quedamos sin leche en la nevera y decidimos salir urgentemente a comprar un cartón de leche. Tenemos dos alternativas para solucionar el problema:

• Ir a la tienda de la esquina.
  
  
• Ir al supermercado.
  
  

Ahora probamos la alternativa 1.1, y nos vamos a la tienda de la esquina. Ops !! Me olvidé de que hoy es Domingo, así que la tienda esta cerrada. Afortunadamente, guardo memoria de otra alternativa, así que doy marcha atrás y elijo ir al supermercado. Como las Grandes Superficies siempre están abiertas, entro en el supermercado pero, ¿Dónde esta la leche?. Se plantean otras dos alternativas:

• Ir al refrigerador de los yogures.
  
  
• Ir al pasillo de alimentación.
  
  

Elijo la alternativa 2.1, pero en el refrigerador no hay leche. De nuevo, recuerdo la otra posibilidad, ir al pasillo de alimentación donde encuentro el cartón de leche. ¡ Problema resuelto !.

Esta técnica tan trivial resulta especialmente útil para los problemas de búsqueda en estructuras de datos. Especialmente si no existe a priori ningún criterio de búsqueda mejor o peor. El inconveniente es que hay que explorar sistemáticamente todas las alternativas, lo que resulta muy lento en general.

Como hemos visto, un algoritmo de backtracking tiene ciertos requerimientos:

• Un espacio de búsqueda, esto es un conjunto de posibilidades o "estados" del problema a resolver. En general, un estado puede estar definido por el elemento de la estructura de datos que queremos tratar en cada instante. Por ejemplo, en un árbol, cada uno de sus nodos.
  
  
• Un estado inicial, el punto de partida del problema.
  
  
• Un conjunto de estados finales. Estos se definen mediante alguna característica, criterio o condición. Por ejemplo, todos los nodos de un árbol que almacenen un número entero igual a 10.
  
  
• Una memoria de estados. Generalmente una pila donde guardamos los estados de búsqueda, es decir las alternativas posibles en cada momento.
  
  

Así, una algoritmo de backtracking tendrá la siguiente estructura genérica:

Definiremos este interfaz de forma que la clase Backtracking podrá recorrer cualquier estructura de datos que implemente este interfaz.

La clase que realiza backtracking hasta encontrar una solución será:

El constructor nos servirá para indicar el elemento que corresponde con el estado inicial. El siguiente método contiene el algoritmo de backtracking. Como argumento, recibe cualquier objeto que actúe como criterio para distinguir un estado final. El resultado del método será null si no se encuentra una solución, y si algún elemento es solución, retorna dicho elemento.

Utilizaremos la clase definida para ver un ejemplo más concreto. Disponemos de un árbol binario que contiene en sus nodos la siguiente información:

El problema se trata de encontrar el nombre asociado a un DNI concreto. Tendremos que definir una clase que implemente el interface EstadoDeBacktracking:

Hemos implementado los dos métodos del interfaz:

• EsSolucion: En el que nuestro objeto criterio es el DNI a encontrar. El resultado será true si el DNI encontrado coincide con el DNI del Nodo actual.
  
  
• IntroducirNuevasAlternativas: Colocará en la pila los dos hijos del nodo raiz.
  
  

El siguiente método buscará la persona por el DNI obteniendo su nombre o el literal "desconocido":