Backtracking.


Para aplicar el método backtrack, la solución deseada debe ser expresable como  una n-tupla (x1, ..., xn) en la que xi  se elige de algún conjunto finito Si. A menudo  el problema a resolver trata de encontrar  un  vector  que  maximiza  (o  minimiza)  una función criterio P(x1, ..., xn). A veces, también se trata  de  encontrar  todos  los vectores que satisfagan P.

Supongamos que mi es el tamaño del conjunto Si. Entonces hay m  =  m1m2 ×... ×mn n-tuplas posibles candidatos a satisfacer la función P. El enfoque de la  fuerza  bruta propondría formar todas esas tuplas y evaluar cada una de ellas con P, escogiendo  la que diera un mejor valor. El algoritmo backtrack tiene como virtud el proporcionar  la misma solución pero en mucho menos de m intentos. Su  idea  básica  es  construir  el mismo vector escogiendo una componente cada  vez,  y  usando  funciones  de  criterio modificadas Pi(x1, ..., xn), que a veces  se  llaman  funciones  de  acotación,  para testear si el vector que se esta formando tiene posibilidad de  éxito.  La  principal ventaja de este método es que si se constata que a partir del vector parcial (x1, x2, ..., xi) no se podrá constituir una solución, entonces pueden ignorarse por completo mi+1 ×... ×mn  posibles test de vectores.

Esa exploración se lleva a cabo en lo que se denomina un Arbol de Estados. Cuando un árbol  de estados ha sido concebido para  un  problema cualquiera, podemos resolver ese problema generando sistemáticamente sus estados, determinando cuales de estos son estados solución,  y  finalmente  determinando  que estados solución son estados respuesta. Fundamentalmente hay dos formas diferentes de generar los estados del problema. Las dos comienzan con el nodo raíz y generan  otros nodos. Un nodo que ha sido generado, pero para el que no se han  generado  aun  todos sus nodos hijos, se llama un nodo  vivo.  El  nodo  vivo  cuyos  hijos  están  siendo generados actualmente se llama un E-nodo (nodo que esta siendo  expandido).  Un  nodo muerto es un nodo generado que o no se va a expandir o que todos  sus  hijos  ya  han sido generados. En ambos métodos de generar estados del problema tendremos una  lista de nodos vivos. En el primero de estos dos métodos, tan pronto como un nuevo hijo  C, del E-nodo en curso R, ha sido generado, este hijo se convierte en  un  nuevo  E-nodo. R se convertirá de nuevo en E-nodo cuando el subarbol  C  haya  sido  explorado completamente. Esto corresponde a una generación primero en profundidad de los estados del problema. En el segundo método de generación de estados, el  E-nodo  permanece  como  E-nodo hasta que se hace nodo muerto. En ambos métodos, se  usaran  funciones  de  acotación para matar nodos vivos sin tener que generar todos sus nodos  hijos. 

La  generación  de  nodos  primero  en profundidad con  funciones  de  acotación  se  llama  Backtracking.  Los  métodos  de generación de estados en los que los E-nodos quedan como E-nodos hasta que se  mueren originan los Métodos Branch and Bound que estudiaremos mas adelante.

THE PROBLEMA DE LAS N REINAS

Un clásico problema combinatorio es el de colocar N reinas en una tablero de 8 por 8 de modo que no haya dos que se ataquen, es decir, que no haya dos  entre  ellas en la misma fila, columna o diagonal. Numeremos las filas y columnas del tablero  del 1 al N. Las reinas pueden también numerarse del 1 al 8. Como cada reina debe estar en una fila diferente, sin perdida de generalidad podemos suponer  que  la  reina  i  se coloca en la fila i. Obviamente para N = 2 no hay solucion, y para N = 4 el problema tendría la solución de la siguiente figura

Solución para el problema de las 4 reinas



HTML PAGE DIRECTOR :Papaioannou Panagiotis