Los algoritmos de vuelta atrás o retroceso (backtracking en inglés) se basan en recorrer el espacio completo de las soluciones posibles al problema planteado. Esta técnica es la aplicación directa del método de búsqueda conocido como primero en profundidad. Típicamente, los algoritmos de vuelta atrás no realizan ningún tipo de optimización y recorren el árbol de soluciones completo. Sin embargo, es posible aplicarles una poda para no descender en aquellas ramas que, de antemano, se sabe que no conducen a una solución. Una mejora de los algoritmos de vuelta atrás son los algoritmos de Ramificación y poda.
Si bien este tipo de algoritmos son por lo general ineficientes, en ocasiones
es el único camino posible. Además, pueden considerarse otros métodos
algorítmicos, como los algoritmos voraces o la programación dinámica, como
optimizaciones de este método.
El algoritmo básico de vuelta atrás es el siguiente:
- Tomar una opción de entre las posibles
- Para cada elección, considerar toda opción posible recursivamente
- Devolver la mejor solución encontrada.
Esta metodología es lo suficientemente genérica como para ser aplicada
en la mayoría de problemas. Por el contrario, incluso teniendo cuidado en la
implementación, es muy probable que un algoritmo de vuelta atrás sea de tiempo
exponencial y no polinómico. Además, el análisis de estos algoritmos puede
resultar bastante complejo.
Backtracking
Método
General
- El backtracking (método de retroceso ó vuelta atrás) es una técnica general de resolución de problemas, aplicable tanto a problemas de optimización, juegos y otros tipos.
- El backtracking realiza una búsqueda exhaustiva y sistemática en el espacio de soluciones. Por ello, suele resultar ineficiente.
- La solución de un problema de backtracking se puede expresar como una tupla (x1, x2, .... xn), satisfaciendo unas restricciones P(x1, x2, ..., xn) y tal vez optimizando una cierta función objetivo.
- En cada momento, el algoritmo se encontrará en un cierto nivel k, con una solución parcial (x1, ..., xk). Si se puede añadir un nuevo elemento a la solución xk+1, se genera y se avanza al nivel k+1.
- Si no, se prueban otros valores de xk.
- Si no existe ningún valor posible por probar, entonces se retrocede al nivel anterior k-1.
- Se sigue hasta que la solución parcial sea una solución completa del problema, o hasta que no queden más posibilidades.
- El resultado es equivalente a hacer un recorrido en profundidad en el árbol de soluciones. Sin embargo, este árbol es implícito, no se almacena en ningún lugar.
- Ejemplo. Dado un conjunto de números enteros {13, 11, 7}, encontrar si existe algún subconjunto cuya suma sea exactamente 20.
- Posibilidad 1) En cada nivel i decidir si el elemento i está o no en la solución. Representación de la solución: (x1, x2, x3), donde xi= (0, 1).
- Cada nodo representa un paso del algoritmo, una solución parcial en cada momento dado. El árbol indica un orden de ejecución (recorrido en profundidad) pero no se almacena en ningún lugar.
- Una solución es un nodo hoja con valor de suma 20.
- Posible mejora: En cada nodo llevamos el valor de la suma hasta ese punto. Si el valor es mayor que 20 retroceder al nivel anterior.
Caracterización de los Problemas
- Se trata generalmente de problemas de optimización, con o sin restricciones.
- La solución es expresable en forma de secuencia de decisiones.
- Existe una función denominada factible que permite averiguar si una secuencia de decisiones, la solución en curso actual, viola o no las restricciones.
- Existe una función, denominada solución, que permite determinar si una secuencia de decisiones factible es solución al problema planteado.
Método de Resolución
Vuelta Atrás es un esquema que de forma sistemática y organizada, genera
y recorre un espacio que contiene todas las posibles secuencias de decisiones.
Este espacio se denomina el espacio de búsqueda del problema, el espacio
de soluciones.
Primera implicación: Si existe solución, seguro que la encuentra.
El Espacio
De Búsqueda – EB
Dimensiones:
·
La altura del espacio: hay k decisiones que tomar para formar una solución.
·
La anchura del espacio: cada decisión tiene asociado un dominio formado por j valores
distintos.
Topología:
Habitualmente el espacio de búsqueda es un árbol, aunque puede ser un
grafo, como en el caso de los grafos de juego.
Terminología:
·
Todos los
nodos que forman parte de cualquier camino que va desde la raíz del EB a
cualquier nodo del EB representan una secuencia de decisiones.
Una secuencia de decisiones es factible si no viola las restricciones.
Una secuencia de
decisiones es prolongable si es posible añadir más decisiones a la secuencia y
no prolongable en caso contrario.
·
Que una secuencia sea no prolongable equivale a que el último nodo de la
secuencia es una hoja del EB.
·
Para muchos problemas se tiene que una solución es cualquier secuencia
de decisiones factible y no prolongable Þ sólo cuando se está en una hoja se tiene una solución.
·
En otros casos el concepto de
solución es más amplio y cualquier secuencia factible, prolongable o no
prolongable, se considera solución.
·
La secuencia de decisiones factible formada por los nodos en el camino
que va desde la raíz a v se denomina solución en curso, y v es el nodo en curso
Topología
Habitualmente el espacio de búsqueda es un árbol, aunque puede ser
un grafo, como en el caso de los grafos de juego.
Es por ello que asemeja a un recorrido en profundidad dentro
de un grafo dirigido. El grafo en cuestión suele ser un árbol, o por lo
menos no contiene ciclos. Sea cual sea su estructura, existe sólo
implícitamente. El objetivo del recorrido es encontrar soluciones para algún
problema. Esto se consigue construyendo soluciones parciales a medida que progresa
el recorrido; estas soluciones parciales limitan las regiones en las que se
puede encontrar una solución completa.
El recorrido tiene éxito si, procediendo de esta forma, se puede definir por
completo una solución. En este caso el algoritmo puede bien detenerse (si lo
único que se necesita es una solución del problema) o bien seguir buscando
soluciones alternativas (si deseamos examinarlas todas).
Por otra parte, el
recorrido no tiene éxito si en alguna etapa la solución parcial construida
hasta el momento no se puede completar.
Ejemplo de la topología de la Vuelta Atrás
En tal caso, el recorrido vuelve atrás exactamente igual que en un
recorrido en profundidad, eliminando sobre la marcha los elementos que se
hubieran añadido en cada fase. Cuando vuelve a un nodo que tiene uno o más
vecinos sin explorar, prosigue el recorrido de una solución.
Ejemplo de un Algoritmo de Blaktracking
proc Backtracking (↕X[1 . . . i ]: TSolución, ↑ok: B)
variables L: ListaComponentes
inicio
si EsSolución (X) entonces
ok CIERTO
de lo contrario
ok FALSO
L=Candidatos (X)
mientras ¬ok ^ ¬Vacía (L) hacer
X[i + 1] Cabeza (L); L Resto (L)
Backtracking (X, ok)
fin mientras
fin si
fin
Codigo Suministrado por http://es.wikipedia.org
Video de Interes:
