La Carne Adentro

ESQUEMA DE VUELTA ATRAS : Backtracking




Caracterización de los problemas :


1/ se trata generalmente de problemas de optimización, con o sin restricciones.
2/ la solución es expresable en forma de secuencia de decisiones.
3/ 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.4/ 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 BUSQUEDA – 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 jnn valores distintos.


Topología :
Habitualmente el espacio debú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ñadirmá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ásamplio 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.



Coste :

El espacio de búsqueda de la figura tiene
• jk hojas y
• su número de nodos es
k
n_nodos = ( ji ( O(jk)i=0
El tiempo necesario para recorrerlo es del mismo orden. Segunda implicación : el coste exponencial en el caso peor de Vuelta Atrás.





decisión 1 v1 v2 v3 ......... vj




decisión 2 v1 v2 ... vj v1 v2 ... vj v1 v2 ... vj
.
.
. altura k
.
.
decisión k v1 v2 ... vj ......... v1 v2 ... vjElección del EB :
• Puede que exista más de un espacio para el mismo problema.
• Por regla general se elige el más pequeño o el de generación menos costosa, aunque un espacio dado no tiene porqué satisfacer ambos criterios simultáneamente.





EL ESQUEMA


• Vuelta Atrás hace un recorrido en profundidad del espacio de búsqueda partiendo de la raíz.
• El recorrido en profundidadregresa sobre sus pasos, retrocede, cada vez que encuentra un camino que se ha acabado o por el que no puede continuar.
• En un recorrido en profundidad o en un recorrido en anchura de un espacio de búsqueda se conoce de antemano el orden en que se van a generar, recorrer, sus nodos Son recorridos ciegos porque fijado un nodo del espacio se sabe cual es el siguiente que se va a generar.Operaciones sobre el EB :

preparar_recorrido, existan_hermanos y siguiente_hermano.
• Todas asumen que la solución en curso, implementada sobre un vector x, contiene k-1 decisiones almacenadas en las posiciones de la 1 a la k-1 en el vector x.
• El valor de k indica la profundidad a la que se encuentra el recorrido.
• La decisión contenida en x(k-1( corresponde al último nodo...