Backtracking

Este algoritmo se podría pensar como una "corrección" al de fuerza bruta. Consiste en la misma base: recorrer sistemáticamente todas las posibles configuraciones del espacio de soluciones. Pero cuando, en base a una solución parcial, podamos deducir que ya es incorrecta, la eliminamos y saltamos a la siguiente. Es una forma de ahorrarse casos de búsqueda. Cuando ya podes deducir que vas por mal camino, lo abandonas.

Habitualmente, se utiliza un vector $a = (a_{1}, a_{2}, . . ., a_{n})$ para representar una solución candidata, donde cada $a_{i}$ pertenece a un conjunto ordenado y finito $A_{i}$ . El espacio de soluciones final consiste en $A_{1} \times A_{2} \times \dots \times A_{n}$ .

En cada paso se extienden las soluciones parciales $a = (a_{1}, a_{2}, . . ., a_{k})$ , con $k < n$ , agregando un elemento mas $a_{k + 1} \in S_{k + 1} \subseteq A_{k + 1}$ , al final del vector $a$ . Es decir, las nuevas soluciones parciales son sucesores directos de la anterior. Si llegamos a un $S_{k + 1}$ que es vacío, retrocedemos a la solución parcial $(a_{1}, a_{2}, . . ., a_{k - 1})$ .

Se puede pensar en este vector como un árbol, donde cada vértice representa una solución parcial. Un vértice $x$ es hijo de otro vértice $y$ si la solución parcial $x$ se puede extender desde la solución parcial $y$ .

Una forma de escribir el comportamiento de Backtracking en pseudocodigo seria la siguiente:

backtracking(a, k):
	if (a es solución) do:
		solución = a;
		encontro = True;
	else:
		for (a' en Sucesores(a, k)) do:
			backtracking(a', k + 1);
			if (encontro) do:
				return;
			end if;
		end for;
	end if;
	return;