Algoritmos y Estructuras de Datos
Tema IV. Backtracking
Introducción
El método del backtracking (también llamado búsqueda en retroceso) proporciona una
manera sistemática de generar todas las posibles soluciones a un problema dentro de un espacio de
búsqueda. Es posible definir el backtracking como un algoritmo general para encontrar un conjunto
de soluciones a un problema computacional, donde se va creando de forma incremental un conjunto
de candidatos que formarán parte de una solución final. El algoritmo explora los elementos de un
conjunto y selecciona/descarta subconjuntos de candidatos que pertenecen/no-pertenecen a la
solución. ¿Por qué se llaman algoritmos de búsqueda en retroceso?. Porque en el caso de no
encontrar una solución en una subtarea se retrocede a la subtarea original y se prueba otra distinta
(una nueva subtarea distinta a las probadas anteriormente).
Dada una solución s:
1. Si s es solución, se hace algo con ella (depende del problema).
2. Se construyen extensiones de s y se invoca recursivamente al algoritmo con todas ellas.
Ejemplos de problemas que requieren de búsqueda exhaustiva:
❖ Agente viajero: dadas n ciudades con conexiones directas entre ellas, y un costo por
conexión, el problema consiste en recorrer todas las ciudades solo una vez y regresar a la
ciudad de origen, con el menor tiempo o costo posible.
❖ Problema de las 8 reinas: colocar las 8 reinas de un tablero de ajedrez de 8x8 sin que estas
se "vean" entre sí en las direcciones vertical, horizontal y diagonal.
❖ Permutaciones: obtener todas las permutaciones de un arreglo.
❖ Mochila: dada una mochila que soporta un peso máximo P, tomar de un conjunto de objetos
la cantidad de estos que sume el mayor peso posible sin exceder P.
❖ Camino más corto en grafos: dado un grafo, obtener el camino más corto entre dos nodos.
❖ Laberinto: buscar la salida más corta de un laberinto desde una posición inicial.
❖ Sudoku: rellenar una cuadrícula de 9 × 9 celdas, dividida en sub-cuadrículas de 3 × 3 con las
cifras del 1 al 9 partiendo de algunos números ya dispuestos en algunas de las celdas.
Esquemas de backtracking
Al obtener una solución se puede: retornar la solución (cuando cualquier solución es válida),
actualizar la mejor solución encontrada (cuando se quiere sólo la óptima), o bien o guardar o imprimir
la solución encontrada (cuando se quieren todas las soluciones a un problema). Durante el
backtracking se puede rechazar tempranamente una secuencia al saber que no hay solución posible
con el conjunto de alternativas seleccionadas en un paso de backtracking. Así, con un simple
chequeo se puede reducir una gran cantidad de llamadas recursivas. Hay esquemas generales que
pueden aplicarse.
1. Una solución (la primera que se encuentre)
void backtracking(paso) {
inicializarAlternativa(alternativa);
while(seAcabaronLasAternativas(alternativa) || encontreSolucion == true){
obtenerSiguienteAlternativa(alternativa);
if(alternativaValida(alternativa)){
incluirAlternativa(alternativa, solucionParcial);
if (esSolucion(solucionParcial)){
encontreSolucion = true; procesarSolucion(solucionParcial);
} else {
nuevoPaso = generarNuevoPaso(paso);
backtracking(nuevoPaso);
if (!encontreSolucion){
paso = deshacerPaso(nuevoPaso);
excluirAlternativa(alternativa, solucionParcial);
}
}
}
}
}
2. Solución óptima
void backtracking(paso) {
inicializarAlternativa(alternativa);
while(seAcabaronLasAternativas(alternativa)){
obtenerSiguienteAlternativa(alternativa);
if(alternativaValida(alternativa)){
incluirAlternativa(alternativa, solucionParcial);
if(esSolucion(solucionParcial)){
if(esMejor(solucionParcial, solucionOptima))
solucionOptima = solucionParcial;
}else{
nuevoPaso = generarNuevoPaso(paso);
backtracking(nuevoPaso);
paso = deshacerPaso(nuevoPaso);
}
excluirAlternativa(alternativa, solucionParcial);
}
}
}
3. Todas las soluciones
void backtracking(paso) {
inicializarAlternativa(alternativa);
while(seAcabaronLasAternativas(alternativa)){
obtenerSiguienteAlternativa(alternativa);
if(alternativaValida(alternativa)){
incluirAlternativa(alternativa, solucionParcial);
if(esSolucion(solucionParcial)) procesarSolucion(solucionParcial);
else{
nuevoPaso = generarNuevoPaso(paso);
backtracking(nuevoPaso);
paso = deshacerPaso(nuevoPaso);
}
excluirAlternativa(alternativa, solucionParcial);
}
}
}
Ejercicios
La forma básica de resolver un problema aplicando backtracking es analizando los casos
que son solución al problema y de qué forma se obtiene dicha solución. A continuación estudiaremos
algunos casos.
Suma Parcial
Dado un conjunto de valores enteros se quiere encontrar todos los subconjuntos que entre
sus elementos sumen un valor k. Por ejemplo, considerando el conjunto 1, 2, 3 la idea es encontrar
todos los subconjuntos que entre sus elementos sumen k = 4. Para este ejemplo, se toma en cuenta
el orden de los elementos, es decir, el subconjunto 1, 3 sería distinto de 3, 1. Entonces dividiendo el
problema en elementos a considerar se tiene:
❖ Alternativa : Valores 1, 2 y 3.
❖ Subtarea : Suma acumulativa.
❖ Solución : Suma igual a 4.
Para hacer un poco de abstracción, se asumen las funciones asociadas a un conjunto para
agregar un valor y eliminar un elemento en este, y la de imprimir sus valores de forma ordenada.
void findSum(int arr[], int n, int partial, int total){ Conjuntos válidos
if (partial == total)
printSet(); 1111
else 112
for(int i = 0; i < n; i++) 121
if (partial + arr[i] <= total){ 13
addSet(arr[i]); 211
findSum(arr, n, partial + arr[i], total); 22
removeSet(); 31
}
}
int arr[] = { 1, 2, 3 };
int total = 4;
findSum(arr, 3, 0, total);
La idea básica del algoritmo es buscar las sumas parciales de los elementos del arreglo
obtenidas de sumar un elemento actual con la suma acumulada (línea 6). Si dicha suma parcial es
inferior o igual al total buscado entonces se agrega al conjunto solución (línea 7). Ahora, con una
nueva suma parcial se invoca de forma recursiva a la función (línea 8) y de conseguir solución (línea
2) se imprime el conjunto. En caso contrario, la invocación hecha retorna al estado anterior y
regresa/retorna el valor añadido al conjunto de sumas parciales (línea 9). Para la invocación inicial del
algoritmo (línea 14), se requiere el arreglo inicial arr, el tamaño de este, la suma parcial para el estado
inicial (i.e. partial = 0) y el valor destino que se quiere alcanzar.
