Esquemas Backtracking

Esquemas de Backtracking V2.2
Guía original elaborada por el Prof. Rhadamés Carmona (18.Marzo.2009, adaptación Junio 2011)

Una solución (la primera que se encuentre)
Acción Backtracking(paso)
Inicializar_alternativa(alternativa)
Repetir
Obtener_siguiente_alternativa(alternativa)
Si (alternativa_valida(alternativa)) entonces
Guardar(alternativa)
NuevoPaso =ProcesarAlternativa(paso, solución)
Si EsSolución(solución) entonces
encontró = verdadero
Procesar_solución(solución)
Sino
Backtracking(NuevoPaso)
Si no encontró Entonces
Paso = DeshacerAlternativa(NuevoPaso, solución)
FinSi
FinSi
FinSi
Hasta se_acabaron_las_aternativas(alternativa) o encontró==verdasdero
FinAcción

Óptima solución (mejorsolución según un criterio solicitado)
Acción Backtracking(paso)
Inicializar_alternativa(alternativa)
Repetir
Obtener_siguiente_alternativa(alternativa)
Si (alternativa_valida(alternativa)) entonces
Guardar(alternativa)
NuevoPaso = ProcesarAlternativa(paso, solución)
Si EsSolución(solución) entonces
Si EsMejor(solución, optima_solución) entoncesoptima_solución = solución
FinSi
Sino
Backtracking(NuevoPaso)
FinSi
Paso = DeshacerAlternativa(NuevoPaso, solución)
FinSi
Hasta se_acabaron_las_aternativas(alternativa)
FinAcción

Todas las soluciones
Acción Backtracking(paso)
Inicializar_alternativa(alternativa)
Repetir
Obtener_siguiente_alternativa(alternativa)
Si(alternativa_valida(alternativa)) entonces
Guardar(alternativa)
NuevoPaso = ProcesarAlternativa(paso, solución)
Si EsSolucion(solución) entonces
ProcesarEstaSolucion(solución)
Sino
Backtracking(NuevoPaso)
FinSi
Paso = DeshacerAlternativa(NuevoPaso, solución)
FinSi
Hasta se_acabaron_las_aternativas(alternativa)
FinAcción
Otra manera de expresar los casos genéricos delBacktracking:
Esquema para una solución:
Acción ensayar (TipoPaso paso)
Lógico acertado;
Repetir
seleccionar_candidato;
Si aceptable entonces
anotar_candidato;
Si solución_incompleta entonces
ensayar(paso_siguiente);
Si no acertado entonces
borrar_candidato
Fsi;
Fsi;
Sino
anotar_solución;
acertado = verdadero;
Fsi;Hasta (acertado = cierto) o (candidatos_agotados);
FinAcción ;

Esquema para todas las soluciones:
Acción ensayar (TipoPaso paso)
Mientras hay_candidato hacer
seleccionar candidato;
Si aceptable entonces
anotar_candidato;
Si solución_incompleta entonces
ensayar(paso_siguiente);    
sino
almacenar_solución;
FinSi;borrar_candidato; //para no seleccionarlo en otra prueba
FinSi;
FinMientras;
FinAcción;

Ejemplo 1.a: Imprimir todas las permutaciones de un arreglo de N elementos.
En este caso, la solución más intuitiva no requiere del uso del esquema general. El problema de hallar las permutaciones de n elementos puede tener diversos usos, por ejemplo, ordenar los n elementos del arreglo, eneste caso se realiza la permutación y se verifica si alguna de las permutaciones resulta en el arreglo ordenado.

Acción Permutar(Ref Arreglo A[1..N] de Elem, Entero paso)

Entero I;

// ¿Es Solución?
Si (paso == N) entonces // ¿Es solución?
// imprimir solución
Para i=1 hasta N hacer
Escribir(A[i]);
FinPara
Sino
Para i=paso hasta N hacer // barremostodas las alternativas
Intercambiar(A[paso], A[i]); // seleccionamos alternativa
Permutar (A, paso +1); // permutamos un subarreglo
Intercambiar (A[paso], A[i]); // deshacemos alternativa
FinPara
FinSi
FinAcción

Ejemplo 1.b: Imprimir todas las permutaciones de un arreglo de N elementos.
En este caso, utilizamos el esquema de todas las soluciones, comentando en azul los pasos....