Introducción.
- Se emplea en muchos problemas de
optimización donde la búsqueda responde a
una estrategia que respete ciertas
restricciones.
- Realiza 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, la óptima.
- Vuelta Atrás (VA) proporciona una manera
sistemática de generar todas las posibles
soluciones, siempre que dichas soluciones
sean susceptibles de resolverse en etapas..
- VA se asemeja a un recorrido en profundidad
dentro de un árbol de búsqueda, cuya
existencia sólo es implícita, ya que sólo
haremos uso de su organización (árbol), en
que cada nodo de nivel k representa una parte
de la solución formada por k etapas que se
suponen ya realizadas. Sus hijos son las
prolongaciones al añadir una nueva etapa.
- Para examinar el conjunto de posibles
soluciones, basta con recorrer el árbol
construyendo soluciones parciales a medida
que se avanza en el recorrido. Si el recorrido
tiene éxito ® Solución (hoja del árbol). Se
puede continuar buscando otras soluciones o la
mejor de todas ellas o bien parar la búsqueda.
- El recorrido no tiene éxito si en alguna de las
etapas, la solución parcial construida no se
puede completar ® Nodo fracaso. En este
caso VA retrocederá en el recorrido a uno o
más caminos no explorados que puedan
conducir a una solución.
- Es un proceso de “prueba y error”, en el que
se va trabajando por etapas, construyendo
gradualmente la solución. Esta forma de
trabajo “de probar”, crece en cada etapa de
forma exponencial por lo que para ciertos
problemas debe ser evitado este método de
resolución.
- La eficiencia de un algoritmo VA proviene de
considerar el menor conjunto de nodos que
pueden llegar a ser soluciones.
- Las condiciones a comprobar sobre cada
nodo a fin de detectar nodos fracaso deben
ser tal que permitan ahorrar tiempo al
delimitar el tamaño del árbol a explorar. Esta
evaluación requiere un tiempo extra, por lo
que deben ser evaluaciones sencillas que no
requieren más tiempo en su cálculo que el
que nos llevaría analizar la parte del árbol
que se puede evitar.
-
Las evaluaciones más costosas se reservan
para casos desesperados en que el árbol
generado es muy grande.
Búsqueda de soluciones sobre un
árbol
En general para poder aplicar el método, la
solución a nuestro problema debe poder
expresarse como una n-tupla (x1,x2, ...,xn)
donde los xi representan elecciones de algún
conjunto finito Si.
Es decir, cada componente xi se elige en
cada etapa de entre un conjunto finito de
valores.
Cada etapa es un nivel en el árbol.
Para generar el árbol de búsqueda
Descomponer en etapas la solución.
Dar significado a cada xi de la n-tupla
solución.
Dar las opciones posibles en cada etapa, y
así estará definida la estructura del árbol a
recorrer.
El problema consiste, muchas veces, en
encontrar los valores de un vector que
maximiza, minimiza o satisface una función
objetivo.
Forma de trabajo bajo Vuelta Atrás.
Exploración del conjunto de posibles
soluciones de manera metódica y ordenada,
intentando dividir dichas soluciones en etapas.
Se realiza una descomposición representada
en forma de árbol.
Donde, Árbol (estructura conceptual no real):
Nodo: representa un fragmento de solución
que está formada por las k etapas previas ya
resueltas.
Sucesores: posibles prolongaciones del nodo al
añadir una nueva etapa.
Para recorrer el conjunto de posibles
soluciones basta con recorrer este árbol.
Diferencias con Algoritmos voraces.
La elección de un sucesor en una etapa no
implica su elección definitiva.
Diferencias con Programación Dinámica.
Son más sutiles.
En PD cuando todos los subproblemas se
resuelven directamente, el estudio directo de
todos los casos es en realidad Vuelta Atrás.
En PD se almacenan los resultados para no
tener que recalcular y en Vuelta Atrás no se
puede hacer, pues son muchísimos los casos.
0 comentarios:
Publicar un comentario