05 abril 2013

Búsqueda exhaustiva: acercamiento a backtracking (1)

En ocasiones, para encontrar la solución a un problema no hay más remedio que mirar todas las posibilidades. Uno de los "métodos prefabricados" para este tipo de tareas es el de "Backtracking" o "vuelta atrás", que consiste en mirar todas las posibles soluciones, típicamente de forma recursiva, partiendo de una solución parcial que se va completando poco a poco, y descartando las soluciones parciales que parecen no llevar a ningún sitio.

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...  ;-)