Búsqueda exhaustiva: acercamiento a backtracking (2)

(Si no has leído el principio de este artículo, probablemente lo necesitarás para entender lo que sigue).

Vamos a acercarnos un poco más a cómo es una búsqueda exhaustiva "real".

Hemos visto cómo generar todas las posibles variaciones de las cifras 1, 2 y 3. Lo habitual es que los datos obtenidos deban cumplir alguna condición, lo que hace que ciertas soluciones no sean válidas. En ese caso, podremos mirar si vamos a obtener un dato válido antes de llamar a la función recursiva o, en el peor de los casos, al comienzo del análisis de un caso.

Por ejemplo, si queremos sólo ver las permutaciones de 1, 2 y 3 (cambios de orden, sin permitir que ninguna de las cifras se repita), podríamos filtrar directamente en el momento de hacer la llamada recursiva: sólo añadimos una cifra si no está contenida todavía en nuestro número:

 1: // Backtracking - ejemplo 03
 2: // Permutaciones de 123: 123, 132, 213, ...
 3: using System;
 4: 
 5: public class Backtracking03
 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:             if ( ! textoActual.Contains ( ""+letra) )
24:                 BT(textoActual + letra);
25:         
26:     }
27: 
28:     public static void Main()
29:     {
30:         // Crear datos y llamar a la función de Backtracking
31:         BT("");
32:     }
33: }

Si las condiciones son más complejas, puede ser preferible analizarlas al comienzo de cada "pasada" por la función. Por ejemplo, si queremos mostrar todas las permutaciones de 1234 que no sean pares y que tengan un "2" en la segunda posición, podríamos hacer:

 1: // Backtracking - ejemplo 04
 2: // Permutaciones de 1234 que tengan un 2 en la segunda posición 
 3: // y no sean múltiplos de 2
 4: using System;
 5: 
 6: public class Backtracking04
 7: {
 8:     public static void BT(string textoActual)
 9:     {
10:         // Si "datos" no puede dar una solución válida, salir
11:         
12:         // Puede no ser vaĺida si la segunda cifra es 2
13:         if ((textoActual.Length >= 2) && (textoActual[1] != '2'))
14:             return;
15:             
16:         // O si tiene toda la longitud pero no es múltiplo de 2
17:         if ((textoActual.Length == 4) && 
18:                 (Convert.ToInt32(textoActual) % 2 == 0))
19:             return;
20:         
21:         // O si ya hemos superado la longitud máxima (no debería ocurrir)    
22:         if (textoActual.Length >= 5)
23:             return;
24:             
25:         // Si "datos" ya es solución, devolver o mostrar y terminar
26:         if (textoActual.Length == 4)
27:         {
28:             Console.WriteLine(textoActual);
29:             return;
30:         }
31:         
32:         // Si no, completar con la siguiente solución parcial
33:         // Y volver a ver de forma recursiva
34:         for (char letra = '1'; letra <= '4'; letra++)
35:             if ( ! textoActual.Contains ( ""+letra) )
36:                 BT(textoActual + letra);
37:         
38:     }
39: 
40:     public static void Main()
41:     {
42:         // Crear datos y llamar a la función de Backtracking
43:         BT("");
44:     }
45: }

Vamos a ver un caso más real: vamos a formar todas las palabras posibles, que contengan ciertas letras y que a la vez estén contenidas en un diccionario. Lo podríamos hacer así:

 1: // Backtracking - ejemplo 05
 2: // Palabras de un diccionario a partir ciertas letras
 3: using System;
 4: using System.Collections.Generic;
 5: 
 6: public class Backtracking05
 7: {
 8: 
 9:     public static void BT(string pruebaActual,
10:         List<string> soluc, List<string> validas,
11:         string letras, int posicion)
12:     {
13:         // Si no se puede obtener una solución válida, salir
14:         if (letras.Length == 0)
15:             return;
16: 
17:         // Si "datos" ya es solución, devolver o mostrar y terminar
18:         if (validas.Contains(pruebaActual)
19:                 && ( ! soluc.Contains(pruebaActual)))
20:             soluc.Add(pruebaActual);
21: 
22:         // Si no, completar con la siguiente solución parcial
23:         // Y volver a ver de forma recursiva
24:         for (int i=0; i<letras.Length; i++)
25:         {
26:             BT(pruebaActual+letras[i], soluc, validas,
27:                 letras.Remove(i,1), posicion+1);
28:         }
29: 
30: 
31:     }
32: 
33:     public static void Main()
34:     {
35:         // Crear datos y llamar a la función de Backtracking
36:         List<string> palabrasValidas = new List<string>(
37:             new string[]{
38:             "A", "ALA", "ALADA", "ALOHA", "HOLA", "LA", "LAS", "SALA"
39:             });
40:         Console.WriteLine("Contiene SALA? " +
41:             palabrasValidas.Contains("SALA"));
42:         string conjuntoLetras = "ALHZADST";
43:         List<string> solucion = new List<string>();
44:         BT("", solucion, palabrasValidas, conjuntoLetras, 0);
45: 
46:         // Y mostrar todas las soluciones almacenadas
47:         foreach (string texto in solucion)
48:             Console.WriteLine(texto);
49:     }
50: }

Puede no ser evidente hasta qué punto puede consumir recursos un programa de este tipo. Para descubrirlo, podemos añadir un contador, que se vaya actualizando en cada pasada, y mostrar su resultado al final:

 1: // Backtracking - ejemplo 05b
 2: // Palabras de un diccionario a partir ciertas letras
 3: // Versión con contador
 4: using System;
 5: using System.Collections.Generic;
 6: 
 7: public class Backtracking05b
 8: {
 9: 
10:     static int llamadas = 0;
11:     
12:     public static void BT(string pruebaActual,
13:         List<string> soluc, List<string> validas,
14:         string letras, int posicion)
15:     {
16:         llamadas++;
17:         
18:         // Si no se puede obtener una solución válida, salir
19:         if (letras.Length == 0)
20:             return;
21: 
22:         // Si "datos" ya es solución, devolver o mostrar y terminar
23:         if (validas.Contains(pruebaActual)
24:                 && ( ! soluc.Contains(pruebaActual)))
25:             soluc.Add(pruebaActual);
26: 
27:         // Si no, completar con la siguiente solución parcial
28:         // Y volver a ver de forma recursiva
29:         for (int i=0; i<letras.Length; i++)
30:         {
31:             BT(pruebaActual+letras[i], soluc, validas,
32:                 letras.Remove(i,1), posicion+1);
33:         }
34: 
35: 
36:     }
37: 
38:     public static void Main()
39:     {
40:         // Crear datos y llamar a la función de Backtracking
41:         List<string> palabrasValidas = new List<string>(
42:             new string[]{
43:             "A", "ALA", "ALADA", "ALOHA", "HOLA", "LA", "LAS", "SALA"
44:             });
45:         Console.WriteLine("Contiene SALA? " +
46:             palabrasValidas.Contains("SALA"));
47:         string conjuntoLetras = "ALHZADST";
48:         List<string> solucion = new List<string>();
49:         BT("", solucion, palabrasValidas, conjuntoLetras, 0);
50: 
51:         // Y mostrar todas las soluciones almacenadas
52:         foreach (string texto in solucion)
53:             Console.WriteLine(texto);
54:             
55:         Console.WriteLine("Llamadas a la función: "+ llamadas);
56:     }
57: }

El resultado puede ser ser mucho más alto de lo que esperamos. En este ejemplo, con tan pocas letras, se nos informará de que se han realizado 109.601 llamadas a la función (sí, más de cien mil).

Para mejorarlo, podemos "podar" esa ramificación de la función, no permitiéndole avanzar cuando sepamos de antemano que no podemos llegar a una solución válida. Por ejemplo, si la secuencia que estamos probando no es el comienzo de ninguna de las palabras válidas de nuestro diccionario, no seguimos buscando por ese camino:

 1: // Backtracking - ejemplo 05c
 2: // Palabras de un diccionario a partir ciertas letras
 3: // Versión "podada"
 4: using System;
 5: using System.Collections.Generic;
 6: 
 7: public class Backtracking05c
 8: {
 9: 
10:     static int llamadas = 0;
11:     
12:     public static void BT(string pruebaActual,
13:         List<string> soluc, List<string> validas,
14:         string letras, int posicion)
15:     {
16:         llamadas++;
17:         
18:         // Si no se puede obtener una solución válida, salir
19:         if (letras.Length == 0)
20:             return;
21:         // (Si ninguna palabra comienza con esta prueba, no seguimos)
22:         int palabrasQueEmpiezanPorLaActual = 0;
23:         foreach(string palabra in validas)
24:             if (palabra.StartsWith(pruebaActual))
25:                 palabrasQueEmpiezanPorLaActual ++;
26:         if (palabrasQueEmpiezanPorLaActual == 0)
27:             return;
28: 
29:         // Si "datos" ya es solución, devolver o mostrar y terminar
30:         if (validas.Contains(pruebaActual)
31:                 && ( ! soluc.Contains(pruebaActual)))
32:             soluc.Add(pruebaActual);
33: 
34:         // Si no, completar con la siguiente solución parcial
35:         // Y volver a ver de forma recursiva
36:         for (int i=0; i<letras.Length; i++)
37:         {
38:             BT(pruebaActual+letras[i], soluc, validas,
39:                 letras.Remove(i,1), posicion+1);
40:         }
41: 
42: 
43:     }
44: 
45:     public static void Main()
46:     {
47:         // Crear datos y llamar a la función de Backtracking
48:         List<string> palabrasValidas = new List<string>(
49:             new string[]{
50:             "A", "ALA", "ALADA", "ALOHA", "HOLA", "LA", "LAS", "SALA"
51:             });
52:         Console.WriteLine("Contiene SALA? " +
53:             palabrasValidas.Contains("SALA"));
54:         string conjuntoLetras = "ALHZADST";
55:         List<string> solucion = new List<string>();
56:         BT("", solucion, palabrasValidas, conjuntoLetras, 0);
57: 
58:         // Y mostrar todas las soluciones almacenadas
59:         foreach (string texto in solucion)
60:             Console.WriteLine(texto);
61:             
62:         Console.WriteLine("Llamadas a la función: "+ llamadas);
63:     }
64: }

Esto reduce la cantidad de llamadas a la función a... ¡126!  Casi mil veces menos. El programa no será mil veces más rápido, porque está haciendo comprobaciones adicionales, pero indudablemente será más rápido y consumirá menos memoria.

Terminemos con un "problema típico": el "Problema de la mochila". Se trata de llevar en una mochila una serie de objetos. Cada objeto tiene un cierto valor (económico, por ejemplo), y queremos llevar el mayor valor total posible, pero la limitación es que la mochila tiene un límite de peso, así que debemos escoger con cuidado qué objetos introducir. Para plantear una solución exhaustiva, podemos crearnos clases auxiliares que representen el conjunto de la mochila y cada uno de sus elementos, de modo que una solución podría ser:

  1: // Backtracking - ejemplo 06
  2: // Problema de la mochila
  3: using System;
  4: using System.Collections.Generic;
  5: 
  6: public class Backtracking06
  7: {
  8: 
  9:     class ElementoMochila
 10:     {
 11:         private float valor, peso;
 12:         public float Valor { 
 13:             get { return valor; }
 14:             set { valor = value; } 
 15:         }
 16:         public float Peso { 
 17:             get { return peso; }
 18:             set { peso = value; } 
 19:         }
 20:         public ElementoMochila(float valorInicial, float pesoInicial)
 21:         {
 22:             valor = valorInicial;
 23:             peso = pesoInicial;
 24:         }
 25:     }
 26:     
 27:     
 28:     class Mochila
 29:     {
 30:         private float valor, peso;
 31:         List<ElementoMochila> elementos;
 32:         public float Valor { 
 33:             get { return valor; }
 34:         }
 35:         public float Peso { 
 36:             get { return peso; }
 37:         }
 38:         public Mochila()
 39:         {
 40:             elementos = new List<ElementoMochila>();
 41:         }
 42:         public void Add(ElementoMochila e)
 43:         {
 44:             peso += e.Peso;
 45:             valor += e.Valor;
 46:             elementos.Add(e);
 47:         }
 48:         public bool Contains(ElementoMochila e)
 49:         {
 50:             return elementos.Contains(e);
 51:         }        
 52:         public void MostrarContenido()
 53:         {
 54:             foreach (ElementoMochila e in elementos)
 55:                 Console.WriteLine("  V: " + e.Valor + ", P: "+ e.Peso);
 56:         }
 57:         public Mochila NuevaMochila(ElementoMochila nuevoElemento)
 58:         {
 59:             Mochila m2 = new Mochila();
 60:             foreach (ElementoMochila e in elementos)
 61:                 m2.Add(e);
 62:             m2.Add(nuevoElemento);
 63:             return m2;
 64:         }
 65:     }
 66:     
 67:     
 68:     static void BT(Mochila mochilaActual,
 69:         List<ElementoMochila> elemPosibles,
 70:         int maximoPeso,
 71:         ref Mochila mejorMochila)
 72:     {      
 73:         // Si no se puede obtener una solución válida, salir
 74:         if (mochilaActual.Peso > maximoPeso)
 75:             return;
 76: 
 77:         // Si "datos" ya es solución, devolver o mostrar y terminar
 78:         if (mochilaActual.Valor > mejorMochila.Valor)
 79:                 mejorMochila = mochilaActual;
 80: 
 81:         // Si no, completar con la siguiente solución parcial
 82:         // Y volver a ver de forma recursiva
 83:         foreach (ElementoMochila e in elemPosibles)
 84:         {
 85:             if (! mochilaActual.Contains(e))
 86:             {
 87:                 BT(mochilaActual.NuevaMochila(e), elemPosibles,
 88:                     maximoPeso, ref mejorMochila);
 89:             }
 90:         }
 91:     }
 92: 
 93:     public static void Main()
 94:     {
 95:         // Crear datos y llamar a la función de Backtracking
 96:         List<ElementoMochila> elementosPosibles =  new List<ElementoMochila>();
 97:         elementosPosibles.Add( new ElementoMochila(200, 12) );
 98:         elementosPosibles.Add( new ElementoMochila(500, 6) );
 99:         elementosPosibles.Add( new ElementoMochila(400, 7) );
100:         elementosPosibles.Add( new ElementoMochila(800, 3) );
101:         elementosPosibles.Add( new ElementoMochila(5000, 20) );
102:         elementosPosibles.Add( new ElementoMochila(100, 10) );
103:         
104:         int maximoPesoMochila = 18;
105:         
106:         Mochila mochilaVacia = 
107:             new Mochila();
108:             
109:        Mochila mejorSolucion = 
110:             new Mochila();
111:         
112: 
113:         BT(mochilaVacia, elementosPosibles, 
114:             maximoPesoMochila, ref mejorSolucion);
115: 
116:         // Y mostrar todas las soluciones almacenadas
117:         Console.WriteLine("Valor: "+mejorSolucion.Valor);
118:         mejorSolucion.MostrarContenido();
119:     }
120: }

Hay algoritmos que buscan aproximar la solución de problemas como éste, tomando cada vez la "solución más prometedora", de forma que se obtenga una solución rápida y "buena", pero que quizá no sea óptima.

Pero eso queda para otro día...