Backtraking

BACKTRACKING: EJEMPLOS

Bibliografía:
- Fundamentals of Computers Algorithms, Horowitz - Sahni.
- Estructuras de Datos y Algoritmos, Aho - Hopcroft - Ullman.
- Algorithms in C, Sedgewick.


EJEMPLO 1:

Un problema clásico es el problema del viajante: dadas n ciudades conectadas todas con todas, “encontrar el camino que recorra todas las ciudades con mínimo costo”.
Se parte de unaciudad cualquiera, y se obtiene el siguiente espacio de soluciones:

(1)


(1,2) (1,3) ....... (1,n)


(1,2,3) (1,2,n) .......... (1,n,2) ......
..................

(1,2,3,4,...,n) En este nivel se tienen todos los posibles caminos
juntocon su costo asociado.

Criterios de poda: cuando se encuentra el primer camino se guarda el camino y su costo como posible solución. Si se encuentra uno mejor se redefine la solución. Si por una rama se detecta que el costo parcial es mayor al costo de la solución alcanzada hasta el momento, entonces podo ese subárbol (pero no a sus hermanos).


Esquema general

void back (estado d,solucion *sol) \\estado d: nodo del árbol
{ \\solución sol: que retorna
if (hoja(d))
Calcular la solución (d,sol);
else
{
int nrohijo = 1;
estado siguiente;
while ( hijos (d, nrohijo, &siguiente ) )
{
if ( !podado(siguiente,sol) )
back(siguiente,sol);
++nrohijo;
}
}
}

EJEMPLO 2:

Dada una secuencia de n enteros, se desea saber si existe una particiónen dos subconjuntos S1 y S2 disjuntos, tal que la suma de sus elementos sea la misma, es decir:

Dado S= {s1,s2,...,sn}
Se desea encontrar dos subconjuntos S1 y S2
tal que: S1(S2 =( y ( sj = ( si
j(S1 i(S2

Esta partición podría existir como no. Analicemos todo el espacio de soluciones para un ejemploconcreto:

S={2, 3, 4, 5, 9, 6, 7 }
S1= {2, 3, 4, 9}
S2= {5, 6, 7}

S


S1= {2} {3} ... {7}
S2= {3,4,5,9,6,7} {2,4,5,9,6,7} {2,3,4,5,9,6}



{2,3} {2,4} ... {2,7} ... {7,2} ... {7,6}{4,5,9,6,7} {3,5,9,6,7} {3,4,5,9,6} {3,4,5,9,6} {2,3,4,5,9}

... ... ... ... ...
{2,3,4}
{5,9,6,7}

1( nivel 1
2( nivel n
.... ....
n(n-1)
... n! O(nn)

Sobre esto pueden hacerse mejoras:
- Evitar generar los mismos subconjuntos: Se puede observar en el árbol que algunas particiones están repetidas, por ejemplo {2,7}{3,4,5,9,6} y{7,2}{3,4,5,9,6}. Para evitar esto se podrían ordenar los elementos de menor a mayor antes de empezar la búsqueda, y luego si parece {7,2}vemos que 7 >2, esta partición ya fue hecha y seguir en esta rama sería en vano, por lo que se abandona la búsqueda en esa rama, y de esta manera se va podando el árbol.
- Al ir generando los conjuntos se tiene información que permite ir podando. Por ejemplo si enun estado S1 > S2, entonces seguir agregando valores a S1, aumentará la diferencia, esto permite podar esa rama, y no sólo eso, sino también sus hermanos, porque son mayores aún. Esto se debe a que los números fueron ordenados de menor a mayor antes de comenzar el backtracking. Por ejemplo si se genera sucesivamente S1 ={7,5}, {7,6}y {7,9}, vemos que su suma aumenta.


Cuando podar un hijoimplica podar sus hermanos, la variante al esquema general sería:

void back (estado d, solucion *sol) \\estado: nodo del árbol
{ \\solución: que retorna
if (hoja(d))
Calcular la solución (d,sol);
else
{ int nrohijo= 1;
estado siguiente;
while ( hijos (d, nrohijo, &siguiente ) && !podado(siguiente,sol) )
{
back(siguiente,sol);
++nrohijo;
}
}
}


EJEMPLO 3:...