PDF de programación - Capítulo 6 - VUELTA ATRÁS

Capítulo 6

VUELTA ATRÁS

6.1 INTRODUCCIÓN
Dentro de las técnicas de diseño de algoritmos, el método de Vuelta Atrás (del
inglés Backtracking) es uno de los de más ámplia utilización, en el sentido de que
puede aplicarse en la resolución de un gran número de problemas, muy
especialmente en aquellos de optimización.
Los métodos estudiados en los capítulos anteriores construyen la solución
basándose en ciertas propiedades de la misma; así en los algoritmos Ávidos se va
contruyendo la solución por etapas, siempre avanzando sobre la solución parcial
previamente calculada; o bien podremos utilizar la Programación Dinámica para
dar una expresión recursiva de la solución si se verifica el principio de óptimo, y
luego calcularla eficientemente. Sin embargo ciertos problemas no son susceptibles
de solucionarse con ninguna de estas técnicas, de manera que la única forma de
resolverlos es a través de un estudio exhaustivo de un conjunto conocido a priori de
posibles soluciones, en las que tratamos de encontrar una o todas las soluciones y
por tanto también la óptima.
Para llevar a cabo este estudio exhaustivo, el diseño Vuelta Atrás proporciona
una manera sistemática de generar todas las posibles soluciones siempre que dichas
soluciones sean susceptibles de resolverse en etapas.
En su forma básica la Vuelta Atrás se asemeja a un recorrido en profundidad
dentro de un árbol cuya existencia sólo es implícita, y que denominaremos árbol de
expansión. Este árbol es conceptual y sólo haremos uso de su organización como
tal, en donde cada nodo de nivel k representa una parte de la solución y está
formado por k etapas que se suponen ya realizadas. Sus hijos son las
prolongaciones posibles al añadir 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 solución (una hoja del árbol). Si lo
único que buscabamos era una solución al problema, el algoritmo finaliza aquí;
ahora bien, si lo que buscabamos eran todas las soluciones o la mejor de entre todas
ellas, el algoritmo seguirá explorando el árbol en búsqueda de 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; nos encontramos en lo que
llamamos nodos fracaso. En tal caso, el algoritmo vuelve atrás (y de ahí su

212

TÉCNICAS DE DISEÑO DE ALGORITMOS

nombre) en su recorrido eliminando los elementos que se hubieran añadido en cada
etapa a partir de ese nodo. En este retroceso, si existe uno o más caminos aún no
explorados que puedan conducir a solución, el recorrido del árbol continúa por
ellos.
La filosofía de estos algoritmos no sigue unas reglas fijas en la búsqueda de las
soluciones. Podríamos hablar de un proceso de prueba y error en el cual se va
trabajando por etapas construyendo gradualmente una solución. Para muchos
problemas esta prueba en cada etapa crece de una manera exponencial, lo cual es
necesario evitar.
Gran parte de la eficiencia (siempre relativa) de un algoritmo de Vuelta Atrás
proviene de considerar el menor conjunto de nodos que puedan llegar a ser
soluciones, aunque siempre asegurándonos de que el árbol “podado” siga
conteniendo todas las soluciones. Por otra parte debemos tener cuidado a la hora de
decidir el tipo de condiciones (restricciones) que comprobamos en cada nodo a fin
de detectar nodos fracaso. Evidentemente el análisis de estas restricciones permite
ahorrar tiempo, al delimitar el tamaño del árbol a explorar. Sin embargo esta
evaluación requiere a su vez tiempo extra, de manera que aquellas restricciones que
vayan a detectar pocos nodos fracaso no serán normalmente interesantes. No
obstante, y como norma de actuación general, podríamos decir que las restricciones
sencillas son siempre apropiadas, mientras que las más sofisticadas que requieren
más tiempo en su cálculo deberían reservarse para situaciones en las que el árbol
que se genera sea muy grande.
Vamos a ver como se lleva a cabo la búsqueda de soluciones trabajando sobre
este árbol y su recorrido. En líneas generales, un problema puede resolverse con un
algoritmo Vuelta Atrás cuando la solución puede expresarse como una n-tupla
[x1, x2, ..., xn] donde cada una de las componentes xi de este vector es elegida en
cada etapa de entre un conjunto finito de valores. Cada etapa representará un nivel
en el árbol de expansión.
En primer lugar debemos fijar la descomposición en etapas que vamos a realizar
y definir, dependiendo del problema, la n-tupla que representa la solución del
problema y el significado de sus componentes xi. Una vez que veamos las posibles
opciones de cada etapa quedará definida la estructura del árbol a recorrer. Vamos a
ver a través de un ejemplo cómo es posible definir la estructura del árbol de
expansión.


6.2 LAS n REINAS
Un problema clásico que puede ser resuelto con un diseño Vuelta Atrás es el
denominado de las ocho reinas y en general, de las n reinas. Disponemos de un
tablero de ajedrez de tamaño 8x8, y se trata de colocar en él ocho reinas de manera
que no se amenacen según las normas del ajedrez, es decir, que no se encuentren
dos reinas ni en la misma fila, ni en la misma columna, ni en la misma diagonal.
Numeramos las reinas del 1 al 8. Cualquier solución a este problema estará
representada por una 8-tupla [x1,x2,x3,x4,x5,x6,x7,x8] en la que cada xi representa la
columna donde la reina de la fila i-ésima es colocada. Una posible solución al
problema es la tupla [4,6,8,2,7,1,3,5].

VUELTA ATRÁS



213

Para decidir en cada etapa cuáles son los valores que puede tomar cada uno de
los elementos xi hemos de tener en cuenta lo que hemos denominado restricciones a
fin de que el número de opciones en cada etapa sea el menor posible. En los
algoritmos Vuelta Atrás podemos diferenciar dos tipos de restricciones:



• Restricciones explícitas. Formadas por reglas que restringen los valores que
pueden tomar los elementos xi a un conjunto determinado. En nuestro problema
este conjunto es S = {1,2,3,4,5,6,7,8}.
• Restricciones implícitas. Indican la relación existente entre los posibles valores
de los xi para que éstos puedan formar parte de una n-tupla solución. En el
problema que nos ocupa podemos definir dos restricciones implícitas. En primer
lugar sabemos que dos reinas no pueden situarse en la misma columna y por
tanto no puede haber dos xi iguales (obsérvese además que la propia definición
de la tupla impide situar a dos reinas en la misma fila, con lo cual tenemos
cubiertos los dos casos, el de las filas y el de las columnas). Por otro lado
sabemos que dos reinas no pueden estar en la misma diagonal, lo cual reduce el
número de opciones. Esta condición se refleja en la segunda restricción
implicita que, en
forma de ecuación, puede ser expresada como
|x – x’| ≠ |y – y’|, siendo (x,y) y (x’,y’) las coordenadas de dos reinas en el
tablero.



[1,2,–,–]2

[1,3,–,–]3



[1,–,–,–]1



De esta manera, y aplicando las restricciones, en cada etapa k iremos generando
sólo las k-tuplas con posibilidad de solución. A los prefijos de longitud k de la n-
tupla solución que vamos construyendo y que verifiquen las restricciones expuestas
los denominaremos k-prometedores, pues a priori pueden llevarnos a la solución
buscada. Obsérvese que todo nodo generado es o bien fracaso o bien k-prometedor.
Con estas condiciones queda definida la estructura del árbol de expansión, que
representamos a continuación para un tablero 4x4:



[–,–,–,–]0



[1,4,–,–]6


[2,1,–,–]11

[2,–,–,–]10



[2,3,–,–]12


[2,4,–,–]13

[2,4,1,–]14 [2,4,1,3]15

[1,4,2,–]7
[1,4,3,–]9

[1,3,2,–]4
[1,3,4,–]5

[1,4,2,3]8



214

TÉCNICAS DE DISEÑO DE ALGORITMOS

Como podemos observar se construyen 15 nodos hasta dar con una solución al
problema. El orden de generación de los nodos se indica con el subíndice que
acompaña a cada tupla.
Conforme vamos construyendo el árbol debemos identificar los nodos que
corresponden a posibles soluciones y cuáles por el contrario son sólo prefijos
suyos. Ello será necesario para que, una vez alcanzados los nodos que sean
posibles soluciones, comprobemos si de hecho lo son.
Por otra parte es posible que al alcanzar un cierto nodo del árbol sepamos que
ninguna prolongación del prefijo de posible solución que representa va a ser
solución a la postre (debido a las restricciones). En tal caso es absurdo que
prosigamos buscando por ese camino, por lo que retrocederemos en el árbol (vuelta
atrás) para seguir buscando por otra opción. Tales nodos son los que habíamos
denominado nodos fracaso.
También es posible que aunque un nodo no se haya detectado a priori como
fracaso (es decir, que sea k-prometedor) más adelante se vea que todos sus
descendientes son nodos fracaso; en tal caso el proceso es el mismo que si lo
hubiésemos detectado directamente. Tal es el caso para los nodos 2 y 3 de nuestro
árbol. Efectivamente el nodo 2 es nodo f