Introducción

Hay problemas de optimización cuya solución se determina a través del recorrido de un grafo.

En esos casos, el recorrido del grafo se realiza con un criterio o un fin concreto: encontrar el circuito hamiltoniano de coste mínimo o el camino mínimo entre el nodo origen y el nodo destino.

Ejemplo: Embarcaderos.

Dado un grafo, hay que determinar el camino mínimo entre el nodo 1 y el nodo n.

Pero, en otras ocasiones, los nodos de un grafo se utilizan para representar las posibles soluciones de un problema. En estos casos, la búsqueda de la solución se obtiene a través de un recorrido exhaustivo por todos los nodos del grafo. Esta es la idea central de los algoritmos de Vuelta Atrás (Backtracking).

Vuelta Atrás es una técnica general de resolución de problemas, aplicable a problemas de optimización, pero también nos proporciona el conjunto de todas las soluciones que satisfacen ciertas restricciones o una solución (la primera) que satisfaga ciertas restricciones.

Lógicamente, esta estrategia podría ser muy ineficiente si la búsqueda se realiza a ciegas (sin ningún criterio) y el grafo es grande. Para aminorar esta dificultad, debemos asegurarnos de que ese recorrido se hace adecuadamente por ejemplo:

• evitando la posibilidad de visitar un nodo dos veces, pues esa solución ya habría sido examinada,

• intentando estructurar el espacio a explorar, tratando de descartar posibles soluciones no satisfactorias.

Solución y restricciones

Consideremos problemas cuyas soluciones se construyen por etapas. Por tanto una solución se expresa en forma de tupla < x1, x2, …, xn > donde cada xi $\in$ Si representa la decisión tomada en la decisión i-ésima, de entre un conjunto finito de alternativas.

Se establecen dos tipos de restricciones:

• Restricciones explícitas: son las reglas que definen el dominio Si de la decisión xi.

• Restricciones implícitas: son las reglas que definen las relaciones que debe haber entre las distintas xi de una misma secuencia de decisiones o tupla.

Árbol de búsqueda

En base a la clasificación de las restricciones se definen los siguientes conceptos.-

• ESPACIO DE ESTADOS POSIBLES: conjunto de todas las secuencias, parciales y completas, que cumplen restricciones explícitas.

• ESPACIO DE SOLUCIONES POSIBLES: conjunto de todas las secuencias completas que cumplen restricciones explícitas.

• ESPACIO DE SOLUCIONES FACTIBLES: conjunto de todas las secuencias completas que cumplen restricciones explícitas e implícitas.

Función de poda

Hay otro elemento imprescindible para la aplicabilidad de este método que es la función de poda. Esta permite determinar cuando una secuencia (o tupla) parcial nunca va a conducir a una solución factible, siendo inútil por tanto seguir buscando a partir de ella.

Una vez definido el árbol y todos los elementos que intervienen, el algoritmo consiste en realizar un recorrido del árbol (recorrido en profundidad) hasta encontrar la primera solución factible, o bien recorrer el árbol completo para obtener todas las soluciones factibles o la solución óptima.

El coste de este tipo de algoritmos de búsqueda exhaustiva está en el orden del tamaño del espacio de soluciones, que suele ser cuando menos exponencial. Su utilidad práctica reside en la efectividad de la función de poda que se aplique: cuanto más elaborada, más nodos se podan y menos árbol se recorre. Sin embargo, aplicar la función de poda a cada nodo puede no llegar a compensar la poda que realiza. Este aspecto es difícil de analizar teóricamente y solo se puede llegar a un criterio apropiado en base a medidas empíricas en ejemplos concretos.

Mochila

Solución y Restricciones

Mochila con una capacidad C, n objetos, P[1..n] pesos de los n objetos y B[1..n] beneficios de los n objetos.

Solución como secuencia de decisiones:

$$< x_1, x_2, …, x_n >$$

Restricciones explícitas:

$$(\forall i)(x_i \in {0,1}:1 \le i \le n)$$

Restricciones implícitas:

$$\sum_{i=1}^{n}x_iP_i \le C$$

Árbol de búsqueda

Funcionamiento del método

En un determinado momento, el algoritmo se encontrará en un cierto nivel k del árbol de búsqueda, con una secuencia/tupla parcial < x1, ..., xk, -, …, - >

SITUACIÓN 1: La tupla parcial <x1, ..., xk, -, …, -> es factible

entonces se puede añadir un nuevo elemento a la tupla y asignando un valor a xk+1 => AMPLIAR LA TUPLA

Lo que en términos de recorrido en el árbol sería visitar un nodo hijo

SITUACIÓN 2: La tupla parcial <x1, ..., xk, -, …, -> NO es factible

entonces se realiza una PODA.

Esto quiere decir que a xk se le asigna otro valor de entre las posibles alternativas, lo que en términos de recorrido en el árbol sería visitar un nodo hermano

SITUACIÓN 3: La tupla parcial <x1, ..., xk, -, …, -> NO es factible

pero no quedan más alternativas para xk, entonces al realizar la PODA, hay que analizar la decisión xk-1 con alternativas pendientes, lo que en términos de recorrido en el árbol sería subir un nivel en el árbol (vuelta atrás)

Si en xk-1 no hubiera más alternativas pendientes, se volvería a xk-2 , si ahí tampoco las hubiera, se volvería a xk-3 y así sucesivamente.

Cuando se consiga replantear una decisión anterior se vuelve paso a paso hacia adelante.