La forma exacta de plantear el algoritmo depende de la fuente que se consulte. Por ejemplo, en la Wikipedia en inglés (a fecha abril de 2013, por eso de que la Wikipedia es algo cambiante) se puede leer como
procedure bt(c)
if reject(P,c) then return
if accept(P,c) then output(P,c)
s ← first(P,c)
while s ≠ Λ do
bt(s)
s ← next(P,s)
y en la Wikipedia en español como
Algoritmo de Backtracking
proc Backtracking (↕X[1 . . . i ]: TSolución, ↑ok: B)
variables L: ListaComponentes
inicio
si EsSolución (X) entonces ok CIERTO
en otro caso
ok FALSO
L=Candidatos (X)
mientras ¬ok ^ ¬Vacía (L) hacer
X[i + 1] Cabeza (L); L Resto (L)
Backtracking (X, ok)
finmientras
finsi
fin
El libro "Programming Challenges", de Skiena y Revilla lo plantea como
backtrack(int a[], int k, data input)
{
int c[MAXCANDIDATES]; /* candidates for next position */
int ncandidates; /* next position candidate count */
int i; /* counter */
if (is_a_solution(a,k,input))
process_solution(a,k,input);
else {
k = k+1;
construct_candidates(a,k,input,c,&ncandidates);
for (i=0; i
a[k] = c[i];
backtrack(a,k,input);
if (finished) return; /* terminate early */
}
}
}
Mis apuntes de algorítmica de segundo curso de carrera lo planteaban como
PROC B(x: tiposol; k:nat );
preparar_recorrido_nivel_k; { Posibles valores de x_k }
MIENTRAS existe_hermano { Existe otro valor para x_k }
siguiente_hermano_nivel_k;
OPC
solucion(x) : Tratar_sol (x) { Todas / una (1ª) / mejor }
¬ solucion(x) :
OPC
completable(x) : B(x,k+1);
¬ completable(x): SKIP;
FOPC
FOPC
FMIENTRAS
FPROC
Y en la asignatura de Diseño de Algoritmos de la Universidad de Granada lo plantean como
(Algoritmo genérico backtracking)
funcion BACKTRACKING_REC ( k , solucion[n])
para j en Si
si ( PODA (k , j , solucion) == true ) hacer
sol[k]= j
si ( TEST_SOL (solucion) == true ) hacer
devolver solucion
si ( k < n )
BACKTRACKING_REC(k+1,solucion[n])
Cinco formas. Todas se parecen en el fondo, pero todas son lo suficientemente distintas (y lo suficientemente ambiguas) como para "asustar a alguien que empieza. Por eso, voy a tratar de hacer un "planteamiento simplificado" de cómo se podría probar todas las combinaciones posibles de un conjunto de datos.
En un primer acercamiento, voy a empezar por suponer que se recibe un único dato: un array (o una cadena de texto) que se quiere recorrer por completo, y que no se devuelven resultados, sino que se muestran en pantalla.
1: // Backtracking - ejemplo 01 2: // Esqueleto basico 3: using System; 4: 5: public class Backtracking01 6: { 7: public static void BT(int[] datos, int posicion) 8: { 9: // Si "datos" no puede dar una solución válida, salir 10: // Si "datos" ya es solución, devolver o mostrar y terminar 11: 12: // Si no, completar con la siguiente solución parcial 13: // Y volver a ver de forma recursiva 14: } 15: 16: public static void Main() 17: { 18: // Crear datos y llamar a la función de Backtracking 19: } 20: }
Ahora vamos a rellenarlo, dándole un "cometido real". Por ejemplo, podríamos mostrar todas las variaciones posibles de 3 cifras formados por los números 1,2,3: 111, 112, 113... hasta 333. En este caso:
- Podríamos usar como dato una cadena de texto, cuyo tamaño iría aumentando, en vez de un array y un contador.
- La condición de fin que descartara soluciones no válidas sería que la longitud ya fuera 4 o mayor (algo que nunca debería llegar a pasar)
- La condición de finalización sería que la longitud fuera 3.
- Mientras la longitud de la cadena sea menor que 3, generaremos toda una nueva serie de valores de la cadena para probar. Lo haremos partiendo de la cadena actual creando varias nuevas cadenas, añadiéndole cada una de las letras de nuestro "alfabeto". Por ejemplo, de la cadena "21" obtenidríamos "211", "212", "213".
El planteamiento podría ser algo como:
1: // Backtracking - ejemplo 02 2: // Variaciones de 123: 111, 112, 113 hasta 333 3: using System; 4: 5: public class Backtracking02 6: { 7: public static void BT(string textoActual) 8: { 9: // Si "datos" no puede dar una solución válida, salir 10: if (textoActual.Length >= 4) 11: return; 12: 13: // Si "datos" ya es solución, devolver o mostrar y terminar 14: if (textoActual.Length == 3) 15: { 16: Console.WriteLine(textoActual); 17: return; 18: } 19: 20: // Si no, completar con la siguiente solución parcial 21: // Y volver a ver de forma recursiva 22: for (char letra = '1'; letra <= '3'; letra++) 23: BT(textoActual + letra); 24: 25: } 26: 27: public static void Main() 28: { 29: // Crear datos y llamar a la función de Backtracking 30: BT(""); 31: } 32: }
Normalmente, las restricciones sobre las soluciones serán mayores: no querremos todos los posibles valores, sino los que cumplen ciertos criterios. Por ejemplo, si no permitimos que se repitan letras (como en "111") sino obtener sólo los posibles cambios de orden, como "123" o "213".
De igual modo, si no queremos mostrar las soluciones en el momento de obtenerlas, sino almacenarlas para mostrarlas al final o para calcular un valor máximo o mínimo, necesitaremos datos adicionales, ya sea como variables globales o (preferiblemente) como parámetros. Pero eso... mañana... ;-)
No hay comentarios:
Publicar un comentario