BACKTRACKING

​

(VUELTA ATRÁS)

El backtracking es una Técnica de diseño algoritmico usada para encontrar soluciones a problemas que tienen una solución completa, en los que el orden de los elementos no importa, y en los que existen una serie de variables a cada una de las cuales debemos asignarle un valor teniendo en cuenta unas restricciones dadas

Hay que encontrar una solución intentándolo con una de varias opciones. Si la elección es incorrecta, el cómputo retrocede o vuelve a comenzar desde el punto de decisión anterior y lo intenta con otra opción. matemático D. H. Lehmer

Este esquema algorítmico es utilizado para resolver problemas en los que la solución consta de una serie de decisiones adecuadas hacia nuestro objetivo. El backtracking está muy relacionado con la búsqueda combinatoria. De manera más exacta podemos indicar que los problemas a considerar son los siguientes:

1. Problemas de Decisión: Búsqueda de las soluciones que satisfacen ciertas restricciones.

2. Problemas de Optimización: Búsqueda de la mejor solución en base a una función objetivo.

La técnica de Backtracking es usada en muchos ámbitos de la programación, por ejemplo, para el cálculo de expresiones regulares o para tareas de reconocimiento de texto y de sintaxis de lenguajes regulares. También es usado

En juegos, incluso en la implementación de algunos lenguajes de programación, tales como Planner o Prolog y da soporte a muchos algoritmos en inteligencia artificial.

Aplicaciones

Eficiencia y costes

• Si existe una solución, la calcula.
• Es un esquema sencillo de implementar.
• Adaptable a las características específicas de cada problema.

​

• Coste exponencial O(jⁱ) en la mayoría de los casos.

• Si el Espacio de Búsqueda es infinito, la solución, aunque exista, no se encontrará nunca.

• Por término medio consume mucha memoria al tener que almacenar las llamadas recursivas.

​

El backtracking es un esquema algorítmico que nos va a permitir resolver una gran variedad de tipos de problemas, pero, por término medio, es sumamente costoso (en cuanto a complejidades temporales se refiere) debido al tamaño

que adoptan sus espacios de búsqueda. Aplicándole una serie de mejoras podremos conseguir que dicho espacio mengüe para reducir en lo posible las altas complejidades que suelen tener.

NIVEL 0

NIVEL 1

NIVEL 2

HOJAS SOLUCIÓN FALLO

DECISIONES

Los algoritmos de Vuelta Atrás generan un árbol con un recorrido en profundidad (Espacio de búsqueda)

– Cada nivel representa una parte de la solución o soluciones

– Cada nodo intermedio es una solución parcial

– La solución (decisiones) es el recorrido desde la raíz hasta la solución

• 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.

ESQUEMA GENERAL

Backtracking (var s: array [1.. max_nivel] of tipo_sol)

nivel:= 1;

fin:= false;

repeat

s[nivel]:= Generar (nivel, s);

if Solución (nivel, s) then

fin:= true;

else if Criterio (nivel, s) then

nivel:= nivel + 1;

else while not MasHermanos (nivel, s) do

Retroceder (nivel, s);

until fin=true;

Esquema general (sin recursividad). Suponiendo que existe al menos una solución y que queremos obtener una cualquiera.

PROBLEMA DE LA MOCHILA

PROBLEMA DE LA MOCHILA

1º Representación de la solución

PROBLEMA DE LA MOCHILA

2º Representación del Árbol

PROBLEMA DE LA MOCHILA

2º Representación del Árbol

PROBLEMA DE LA MOCHILA

3º Codificación (Esquema Recursivo)

const N = … ; //Número de Objetos

const CAPACIDAD = …; //Capacidad de la Mochila

​

TYPE objeto = RECORD peso, beneficio : int END;

objetos = ARRAY[1..N] OF Objeto;

solucion_actual, mochila_final = ARRAY[1..N] OF int;

​

void mochila(int solucion[], int nivel, Objeto objetos[], int mochila_final[], int *peso_final,

int *benef_final)

{ int i=0;

if (nivel > NUM_OBJETOS - 1) return;

do {

solucion[nivel] = i;

if (valido(solucion, nivel, objetos))

{

if (nivel == NUM_OBJETOS - 1)

actualizarSolucion(solucion, objetos,mochila_final,peso_final,benef_final);

else

mochila(solucion, nivel+1,objetos,mochila_final,peso_final,benef_final);

}

i++;

}while(solucion[etapa] != 1);

solucion[etapa] = -1;

}

PROBLEMA DE LA MOCHILA

3º Codificación (Esquema Recursivo)

void actualizarSolucion(int solucion[], Objeto objetos[], int mochila_final[], int *peso_final, *benef_final)

{

Int peso_total = 0;

Int benef_total = 0;

​

for(int i=0;i < NUM_OBJETOS;i++)

{

if (solucion[i] == 1)

{

benef_total += objetos[i].beneficio;

peso_total += objetos[i].peso;

}

}

if (benef_total > *benef_final)

{

for(int i=0;i < NUM_OBJETOS;i++)

mochila _final[i] = solucion[i];

*benef_final = benef_total;

*peso_final = peso_total;

}

}

PROBLEMA DE LAS N REINAS

Todos sabemos que por donde pisa el caballo de Atila jamás vuelve a crecer el pasto. El caballo fue directamente hacia el jardín de n x n casillas. Empezó su paseo por una casilla cualquiera y volvió a ella, es decir, hizo un recorrido cerrado. No visitó dos veces una misma casilla, se movió de una casilla a otra vecina en forma horizontal o vertical, pero nunca en diagonal. Por donde pisó el caballo, el pasto jamás volvió a crecer. Luego de terminado el recorrido en algunas casillas todavía había pasto (señal de que en ellas no había estado el caballo). Escriba un algoritmo que deduzca el recorrido completo que hizo el caballo.

PROBLEMA: EL CABALLO DE ATILA

�

Debes tratar de Colocar las 3 ranas marrones en el lado izquierdo, y las tres verdes en el derecho.

Las ranas pueden saltar a la piedra de al lado o por encima de otra rana de distinto color

PROBLEMA: LAS RANAS

 V   a las Ranas verdes     M   a las ranas Marrones     0 al hueco

Hace mucho tiempo un granjero fue al mercado y compró un lobo una cabra y una col. Para volver a su casa tenía que cruzar un río donde disponía de una barca para cruzar a la otra orilla pero con el inconveniente de que en la barca solo caben él y una de sus compras.

Sabe que si el lobo se queda solo en la orilla con la cabra este se la comerá y que si la cabra se queda sola con la col se la comerá.

El reto del granjero es cruzar él mismo y sus compras hasta la otra orilla del río evitando que el lobo se quede sólo con la cabra y se la coma o que la cabra se quede sola con la col y se la coma

PROBLEMA: EL PASTOR, LA CABRA, EL LOBO Y LA COL

Estabilidad

​

Se desea proporcionar a las personas una forma de encontrar una pareja estable. Para ello se dispone de dos matrices de números naturales: H[1..N][1..N] y M[1..N][1..N] tales que H[i][j] indica la preferencia de un hombre i por una mujer j y M[i][j] la preferencia de una mujer i por un hombre j, para i y j entre 1 y N. Establecida una asignación de N parejas, si existe algún hombre y alguna mujer que, sin estar emparejados entre sí, se prefieren mutuamente a sus respectivas parejas, entonces la asignación es inestable; si no se da tal caso la asignación es estable. Desarrollar un algoritmo que encuentre las posibles parejas estables.

A B C D E 1 2 3 4 5

2 1 2 1 5 E D A C D

5 2 3 3 3 A E D B B

1 3 5 2 2 D B B D C

3 4 4 4 1 B A C A E

4 5 1 5 4 C C E E A

 En este caso, un ej. de asignación inestable seria: A1 B3 C2 D4 E5

Algoritmo:

• Elegir a cada hombre como candidato, uno por vez.
• Al primer hombre candidato se lo junta con la primera mujer de su lista.
• Se pasa al próximo hombre como candidato y se lo junta con la primera mujer de su lista, si no esta en pareja.
• Si la mujer esta en pareja, dicha mujer elige dependiendo de su lista.
• Al hombre que abandona se le asigna la próxima mujer de su lista.
• Estos ciclos continúan hasta que algún candidato encuentra a una mujer que no estaba en pareja.

​

Estas son las asignaciones que se logran ejecutando el algoritmo anterior, al ejemplo

 A A B A B C A B C D A B C D E

2 2 1 2 1 2 2 1 2 1 2 1 2 1 5

3 5 2 3 5 2 3 3 3

1 3 5 2

4