Backtracking:Dentro de las tcnicas de diseo de algoritmos, el mtodo de Vuelta Atrs (del ingls Backtracking) es uno de los de ms amplia utilizacin, en el sentido de que puede aplicarse en la resolucin de un gran nmero de problemas, muy especialmente en aquellos de optimizacin. En ocasiones se ven enfrentados aproblemas de optimizacin que solo pueden ser resueltos a travs de un estudio exhaustivo de un conjunto conocido a priori de posibles soluciones, en las que se trata de encontrar una o todas las soluciones y por tanto tambin la ptima. Para llevar a cabo este estudio exhaustivo, el diseo Vuelta Atrs proporciona una manerasistemtica de generar todas las posibles soluciones siempre que dichas soluciones sean susceptibles de resolverse en etapas. Contenido[ocultar]

1 Tcnica de Backtracking 2 Algoritmo Gentico 3 Eficiencia y complejidad del mtodo

4 Recursividad 5 Fuentes

Tcnica de BacktrackingEn su forma bsica la Vuelta Atrs se asemeja a un recorrido en profundidad dentro de un rbol cuya existencia slo es implcita, y que se denomina rbol de expansin. Este rbol es conceptual, en donde cada nodo de nivel k representa una parte de la solucin y est formado por k etapas que se suponen ya realizadas. Sus hijos son las prolongaciones posibles al aadir una nueva etapa. Para examinar el conjunto de posibles soluciones es suficiente recorrer este rbol construyendo soluciones parciales a medida que se avanza en el recorrido. En este recorrido pueden suceder dos cosas. La primera es que tenga xito si, procediendo de esta manera, se llega a una solucin (una hoja del rbol). Si lo nico que buscbamos era una solucin al problema, el algoritmo finaliza aqu; ahora bien, si lo que se busca eran todas las soluciones o la mejor de entre todas ellas, el algoritmo seguir explorando el rbol en bsqueda de soluciones alternativas. Por otra parte, el recorrido no tiene xito si en alguna etapa la solucin parcial construida hasta el momento no se puede completar; s encuentran en lo que llamamos nodos fracaso. En tal caso, el algoritmo vuelve atrs (y de ah su nombre) en su recorrido eliminando los elementos que se hubieran aadido en cada etapa a partir de ese nodo. Si en este retroceso, si existe uno o ms caminos an no explorados que puedan conducir a solucin, el recorrido del rbol contina por ellos.

Algoritmo GenticoEl algoritmo genrico del backtracking es el siguiente: Inicio IniciarOpciones; Repetir SeleccionarNuevaOpcion; Si Aceptable entonces

Inicio AnotarOpcion; Si SolucionIncompleta entonces Backtracking(etapa_siguiente); Si NOT xito entonces CancelarAnotacion; End Else /*Solucin Completa*/ xito = true; End End Until(Exito) OR (UltimaOpcion) End Backtracking.

En este esquema se puede observar que estn presentes tres elementos principales. En primer lugar hay una generacin de descendientes, en donde para cada nodo generamos sus descendientes con posibilidad de solucin. A este paso se le denomina expansin, ramificacin o bifurcacin. A continuacin, y para cada uno de estos descendientes, debe de aplicar lo que se denomina prueba de fracaso (segundo elemento). Finalmente, caso de que sea aceptable este nodo, aplicaran la prueba de solucin (tercer elemento) que comprueba si el nodo que es posible solucin efectivamente lo es. Tal vez lo ms difcil de ver en este esquema es donde se realiza la vuelta atrs, y para ello han de pensar en la propia recursin y su mecanismo de funcionamiento, que es la que permite ir recorriendo el rbol en profundidad. Cuando se desea encontrar todas las soluciones habr que alterar ligeramente el esquema dado, de forma que una vez conseguida una solucin se contine buscando hasta agotar todas las posibilidades. Queda por tanto el siguiente esquema general para este caso: Algoritmo BacktrackingTodaslasSoluciones(etapa) Inicio IniciarOpciones; Repetir SeleccionarNuevaOpcion; Si Aceptable entonces AnotarOpcion; Si SolucionIncompleta entonces BactrackingTodaslasSoluciones(etapa_siguiente); Else ComuncicarSolucion; End; CancelarAnotacion; End;

Until(UltimaOpcion); End BacktrackingTodaslasSoluciones;

Eficiencia y complejidad del mtodoGran parte de la eficiencia (siempre relativa) de un algoritmo de Vuelta Atrs proviene de considerar el menor conjunto de nodos que puedan llegar a ser soluciones, aunque siempre asegurar de que el rbol podado siga conteniendo todas las soluciones. Por otra parte debe tener cuidado a la hora de

decidir el tipo de condiciones (restricciones) que comprueban en cada nodo a fin de detectar nodos fracaso. Evidentemente el anlisis de estas restricciones permite ahorrar tiempo, al delimitar el tamao del rbol a explorar. Sin embargo esta evaluacin requiere a su vez tiempo extra, de manera que aquellas restricciones que vayan a detectar pocos nodos fracaso no sern normalmente interesantes. No obstante, y como norma de actuacin general, podras decir que las restricciones sencillas son siempre apropiadas, mientras que las ms sofisticadas que requieren ms tiempo en su clculo deberan reservarse para situaciones en las que el rbol que se genera sea muy grande. Usualmente los algoritmos Vuelta Atrs(backtracking) son de complejidad exponencial por la forma en la que se busca la solucin mediante el recorrido en profundidad del rbol. De esta forma estos algoritmos van a ser de un orden de complejidad al menos del nmero de nodos del rbol que se generen y este nmero, si no se utilizan restricciones, es de orden de z donde z son las posibles opciones que existen en cada etapa, y n el nmero de etapas que es necesario recorrer hasta construir la solucin (esto es, la profundidad del rbol o la longitud de la n-tupla solucin). El uso de restricciones, tanto implcitas como explcitas, trata de reducir este nmero tanto como sea posible, pero sin embargo en muchos casos no son suficientes para conseguir algoritmos tratables, es decir, que sus tiempos de ejecucin sean de orden de complejidad razonable. Para aquellos problemas en donde se busca una solucin y no todas, es donde entra en juego la posibilidad de considerar distintas formas de ir generando los nodos del rbol. Y como la bsqueda que realiza la Vuelta Atrs es siempre en profundidad, para lograr esto slo debe de ir variando el orden en el que se generan los descendientes de un nodo, de manera que trate de ser lo ms apropiado a nuestra estrategia. Ejemplo 1: Problema de las 8 reinas. Parte de un tablero de ajedrez, el cual tiene un total de 64 casillas (8 filas x 8 columnas). El problema consiste en situar ocho reinas en el tablero de tal forma que no se den jaque entre ellas. Una reina puede dar jaque a aquellas reinas que se siten en la misma fila, columna o diagonal en la que se encuentra dicha reina. La solucin a este rompecabezas pasa, por tanto, en situar una reina en cada fila y en cada columna. Cmo actuar para situar las ocho reinas? Comenzar por la primera columna y situar la primera reina. Al hacer esto, elimina como posibles casillas donde localizar reinas la fila, la columna y las dos diagonales. Teniendo en cuenta estas restricciones, se sita en la segunda columna la segunda reina y se "tachan" las nuevas casillas prohibidas. Seguidamente se procede a poner la tercera reina y as sucesivamente. Suponiendo que se han situado las seis primeras reinas. Puede llegar un momento en el que no se pueda situar la sptima sin que ninguna otra le d jaque. En ese momento, se deshace el movimiento que ha ubicado la sexta reina y busca otra posicin vlida para dicha reina. Si no se pudiera, se vuelve deshacer el movimiento de la sexta reina y se intenta buscar otra localizacin. En el caso de que no sea posible, se sigue hacia atrs intentando colocar la reina quinta. Si se puede colocar, entonces se proceder a dejar en el tablero la sexta de nuevo. Si se ha conseguido sin que le den jaque, se intentar emplazar la sptima y, por ltimo, la octava. En general, si hay algn problema, se deshace el ltimo movimiento y se prueba a localizar una casilla alternativa. Si no se consigue, se vuelve hacia atrs y as sucesivamente. En ella se van dando pasos hacia delante mientras sea posible y se deshacen cuando se ha llegado a una situacin que no conduce a la resolucin del problema original.

RecursividadCmo se puede aplicar la recursividad para solventar este problema? De forma muy sencilla: dado que se ha situado una reina en una posicin correcta en una columna, hay que considerar el problema de situar otra reina en la columna siguiente: resolver el mismo problema con una columna menos. En este momento realizara una llamada recursiva. El caso base? Cuando el tablero se haya reducido a uno de

tamao cero, en cuyo caso no se har nada. Por tanto, se partir de un problema de tamao 8, y se considerarn problemas de tamao menor quitando una columna en cada llamada recursiva hasta que se llegue a un tablero de tamao cero, momento en el cual habr alcanzado el caso base. Si se puede situar una reina en la columna correspondiente, se hace una llamada recursiva, si no, se vuelve hacia atrs y se prueba otras posiciones. El algoritmo de las 8 reinas seria el siguiente: Algoritmo Reinas(k:CARDINAL); (* encuentra todas las maneras de disponer las n reinas *) Inicio Si k>n entonces RETURN end; X[k]:=0; (* iniciar opciones *) Repetir INC(X[k]); (* seleccion de nueva opcion *) Si Valido(k) entonces (* prueba de fracaso *) Si kn entonces Reinas(k+1) (* llamada recursiva *) sino ComunicarSolucion(X) end end Hasta que (X[k]=n); Fin

Donde la funcin Valido es la que comprueba las restricciones implcitas, realizando la prueba de fracaso. Ejemplo2: Laberinto Una matriz bidimensional nxn puede representar un laberinto cuadrado. Cada posicin contiene un entero no negativo que indica si la casilla es transitable (0) o no lo es (). Las casillas [1,1] y [n,n] corresponden a la entrada y salida del laberinto y siempre sern transitables. Dada una matriz con un laberinto, el problema consiste en disear un algoritmo que encuentre un camino, si existe, para ir de la entrada a la salida. Solucin En este problema debe ir avanzando por el laberinto en cada etapa, y cada nodo representar el camino recorrido hasta el momento. Por la forma en la que trabaja el esquema general de Vuelta Atrs puede utilizar una variable global (una matriz) para representar el laberinto e ir apuntando los movimientos que realiza, indicando en cada casilla el orden en el que sta ha sido visitada. Al producirse la vuelta atrs se cuidar de liberar las casillas ocupadas por el nodo del que volvemos (marcndolas de nuevo con 0). Con esto en mente, el algoritmo es sencillo: Algoritmo Laberinto(k:Cardinal;Var fil,col:Integer; Var exito:Boolean); Var

orden:CARDINAL; (*indica hacia donde debe moverse *) Inicio orden:=0; exito:=FALSE; Repetir INC(orden); fil:=fil + mov_fil[orden]; col:=col + mov_col[orden]; Si (1