22 abril 2013

Optimizaciones básicas de código

Cuando no basta con resolver un problema, sino que además la solución tiene que ser rápida, convendrá trabajar en dos etapas:


  1. En una primera fase, tendremos que resolver el problema, de la forma más simple posible, para garantizar que no hay errores, y deberemos hacer pruebas para intentar garantizar que se comporta bien en la mayor cantidad de casos posibles.
  2. En una segunda fase, si es necesario, buscaremos optimizaciones para mejorar su velocidad.

Vamos a ver un ejemplo básico: un programa que calcule números primos y alguna cosa más.

Nuestro programa calculará la suma de los "emirps" hasta un cierto número. Un "emirp" es un número que es primo, que también es primo cuando se invierte el orden de sus cifras, y que no es igual al número invertido. Por ejemplo, 13 y 31 son "emirps", pero 23 no lo es, porque al invertirlo se obtiene 32, que no es primo. Lo mismo ocurre con 11, que al invertirlo... se queda como estaba.

Un programa (en C#) que resolviera esto podría ser así:


 1: using System;
 2: 
 3: public class Emirps
 4: {
 5:     public static long reversed(long n)
 6:     {
 7:         string txt = Convert.ToString(n);
 8:         string txtReversed = "";
 9:         for (int i=0; i<txt.Length; i++)
10:             txtReversed = txt[i] + txtReversed;
11: 
12:         return Convert.ToInt64(txtReversed);
13:     }
14: 
15: 
16:     public static bool IsPrime(long number)
17:     {
18:         long dividers=0;
19: 
20:         for(long i=1; i <= number; i++)
21:             if(number%i==0)
22:                 dividers++;
23: 
24:         if (dividers == 2)
25:             return true;
26:         else
27:             return false;
28:     }
29: 
30: 
31:     public static bool IsEmirp(long number)
32:     {
33:         return ((number != reversed(number))
34:                 && IsPrime(number)
35:                 && IsPrime(reversed(number)));
36:     }
37: 
38: 
39:     public static void Main()
40:     {
41:         Console.Write("Enter number: ");
42:         long n = Convert.ToInt64(Console.ReadLine());
43: 
44:         long sum = 0;
45: 
46:         long startTime = Environment.TickCount;        
47: 
48:         for (long i=11; i<=n; i++)
49:             if (IsEmirp(i))
50:                 sum += i;
51: 
52:         long endTime = Environment.TickCount;
53:         long timeUsed = endTime - startTime;
54: 
55:         Console.WriteLine("Sum: "+ sum);
56:         Console.WriteLine("Milliseconds: "+timeUsed);
57:     }
58: }


Las ideas principales son:

  • El cuerpo del programa ("Main") es poco más que un "for" que suma los números hasta el que nos indiquen, si son Emirps.
  • La función "IsEmirp" aplica la definición "tal cual": debe ser distinto de el número al revés, debe ser primo y si le damos la vuelta también debe ser primo.
  • Las función "IsPrime" comprueba si el número es primo, y lo hace de la forma más ¿natural? pero también más lenta: un número es primo si sólo es divisible por sí mismo y por 1, así que buscamos todos sus divisores, y, si sólo encontramos dos, es que era primo.
  • La función "reversed" calcula el número "dado la vuelta": convierte a una cadena y va recolocando dígito a dígito en orden inverso.


Vamos a ver tiempos:

  • Para n pequeños, el tiempo es despreciable.
  • Para n=99999, un Intel i7 3630 QM, 2.40 Ghz tarda 58.234 seg
  • Si duplicamos el número, el tiempo se multiplica casi por 6: para n=222222, tarda 329.954 seg


Una primera optimización muy simple, que a veces se pasa por alto, y que puede ser muy efectiva, es cambiar el orden de las condiciones múltiples en los "if". La mayoría de lenguajes actuales usan "evaluación en cortocircuito": en cuanto se sabe que la condición no puede ser cierta (porque uno de las sub-condiciones que se compara es falsa), no se sigue analizando el resto de sub-condiciones.

En este caso, podemos probar a cambiar el orden del "if" y ver qué ocurre:


31:     public static bool IsEmirp(long number)
32:     {
33:         return (IsPrime(number)
34:                 && IsPrime(reversed(number))
35:                 && (number != reversed(number)));
36:     }


Obtenemos:

  • Para n=99999: 55.218 seg
  • Para n=222222: 311.656 seg

En este caso, como ninguna de las sub-condiciones es claramente más rápida (todavía) que la otra, la ganancia es mínima: apenas un 5% (y sí, es desconcertante que sea más rápido comprobar si es primo que si es el mismo número cuando se le da la vuelta).


Una segunda optimización es no recalcular valores que ya hemos calculado previamente: por ejemplo, calculamos dos veces el valor de "reversed(number)"; podríamos calcularlo una sola vez


31:     public static bool IsEmirp(long number)
32:     {
33:         long rev = reversed(number);
34:         return (IsPrime(number)
35:                 && IsPrime(rev)
36:                 && (number != rev));
37:     }


Pero en este caso, no hay ninguna mejora, porque el cálculo de "reversed" es más lento que el de "IsPrime".


Normalmente, las mayores mejoras vienen de analizar el algoritmo que estamos usando: ¿necesitamos realmente calcular todos los divisores y contarlos para saber si el número es primo? No. En cuanto encontremos un divisor (que no sea 1 ni el número), podemos afirmar que no era primo, y dejar de analizar, así que podríamos reescribir la función así:


16:     public static bool IsPrime(long number)
17:     {
18:         for(long i=2; i < number; i++)
19:             if(number%i==0)
20:                 return false;
21: 
22:         return true;
23:     }


En este caso, la ganancia sí es muy grande:

  • Para n=99999: 5.516 seg
  • Para n=222222: 36.570 seg

Ahora es casi 10 veces más rápido. Y con un pequeño cambio lo podemos hacer más rápido aún: si no es divisible por 2, tampoco lo será entre 4 ni entre ningún número par, así que podemos comprobar los divisores impares, saltando de 2 en 2:


16:     public static bool IsPrime(long number)
17:     {
18:         if(number%2==0)
19:             return false;
20:         for(long i=3; i < number; i+=2)
21:             if(number%i==0)
22:                 return false;
23: 
24:         return true;
25:     }



Y obtenemos:

  • Para n=99999: 2.766 seg
  • Para n=222222: 18.344 seg

Con ese pequeño cambio vuelve a ser casi el doble de rápido. Pero estamos volviendo a calcular números primos que ya habíamos calculado antes. Podemos ir crear una lista con los números primos, y luego buscar si están en la lista:


 1: using System;
 2: using System.Collections.Generic;
 3: 
 4: public class Emirps
 5: {
 6:     public static List<long> ListOfPrimes = new List<long>();
 7: 
 8:     public static void GeneratePrimes(long max)
 9:     {
10:         ListOfPrimes.Add(2);
11:         for (int n = 3; n <= max; n += 2)
12:         {
13:             int i;
14:             for (i = 3; i <= n; i += 2)
15:                 if (n % i == 0)
16:                     break;
17:             if (i>=n)
18:                 ListOfPrimes.Add(n);
19:         }
20:                 
21:     }
22: 
23: 
24:     public static long reversed(long n)
25:     {
26:         string txt = Convert.ToString(n);
27:         string txtReversed = "";
28:         for (int i = 0; i < txt.Length; i++)
29:             txtReversed = txt[i] + txtReversed;
30: 
31:         return Convert.ToInt64(txtReversed);
32:     }
33: 
34: 
35:     public static bool IsPrime(long number)
36:     {
37:         return (ListOfPrimes.BinarySearch(number) > -1);
38:     }
39: 
40: 
41:     public static bool IsEmirp(long number)
42:     {
43:         long reverse = reversed(number);
44:         return (IsPrime(number)
45:                 && IsPrime(reverse)
46:                 && (number != reverse));
47:     }
48: 
49: 
50:     public static void Main()
51:     {
52:         Console.Write("Enter number: ");
53:         long n = Convert.ToInt64(Console.ReadLine());
54: 
55:         long sum = 0;
56: 
57:         long startTime = Environment.TickCount;
58: 
59:         GeneratePrimes(n);
60: 
61:         for (long i = 11; i <= n; i++)
62:             if (IsEmirp(i))
63:                 sum += i;
64: 
65:         long endTime = Environment.TickCount;
66:         long timeUsed = endTime - startTime;
67: 
68:         Console.WriteLine("Sum: " + sum);
69:         Console.WriteLine("Milliseconds: " + timeUsed);
70:     }
71: }



Y obtenemos:

  • Para n=99999: 0.985 seg
  • Para n=222222: 4.422 seg
  • Para n=999999: 77.515 seg

Es casi 100 veces más rápido que el original. Pero aún es fácilmente mejorable: para calcular números primos existe un algoritmo muy eficiente, que ni siquiera supone hacer divisiones. Se trata de la "criba de Erastótenes". Si la aplicamos, el programa se convierte en:

 1: using System;
 2: using System.Collections.Generic;
 3: 
 4: public class Emirps
 5: {
 6:     public static bool[] IsTaggedAsPrime;
 7: 
 8:     public static void GeneratePrimes(long max)
 9:     {
10:         IsTaggedAsPrime = new bool[max + 1];
11:         for (int i = 1; i <= max; i++)
12:             IsTaggedAsPrime[i] = true;
13: 
14:         // Sieve of Eratosthenes
15:         for (int i = 2; i <= (long) Math.Sqrt(max); i++)
16:             if (IsTaggedAsPrime[i])
17:                 for (int j = i*i; j <= max; j+=i)
18:                     IsTaggedAsPrime[j] = false;
19:     }
20: 
21: 
22:     public static long reversed(long n)
23:     {
24:         string txt = Convert.ToString(n);
25:         string txtReversed = "";
26:         for (int i = 0; i < txt.Length; i++)
27:             txtReversed = txt[i] + txtReversed;
28: 
29:         return Convert.ToInt64(txtReversed);
30:     }
31: 
32: 
33:     public static bool IsPrime(long number)
34:     {
35:         try
36:         {
37:             return IsTaggedAsPrime[number];
38:         }
39:         catch (IndexOutOfRangeException)
40:         {
41:             return false;
42:         }
43:     }
44: 
45: 
46:     public static bool IsEmirp(long number)
47:     {
48:         long reverse = reversed(number);
49:         return (IsPrime(number)
50:                 && IsPrime(reverse)
51:                 && (number != reverse));
52:     }
53: 
54: 
55:     public static void Main()
56:     {
57:         Console.Write("Enter number: ");
58:         long n = Convert.ToInt64(Console.ReadLine());
59: 
60:         long sum = 0;
61: 
62:         long startTime = Environment.TickCount;
63: 
64:         GeneratePrimes(n);
65: 
66:         for (long i = 11; i <= n; i++)
67:             if (IsEmirp(i))
68:                 sum += i;
69: 
70:         long endTime = Environment.TickCount;
71:         long timeUsed = endTime - startTime;
72: 
73:         Console.WriteLine("Sum: " + sum);
74:         Console.WriteLine("Milliseconds: " + timeUsed);
75:     }
76: }

Y obtenemos:

  • Para n=99999: 0.047 seg
  • Para n=222222: 0.438 seg
  • Para n=999999: 0.516 seg
Es decir, con números grandes (999.999) es casi 150 veces más rápido que la versión anterior. Todavía se podrían hacer pequeñas mejoras, pero lo nuestro fuente ahora es cerca de 10.000 veces más rápido que al principio... lo hemos acelerado lo suficiente como para ganarnos un descanso por hoy... ;-D


21 abril 2013

Algoritmos voraces

Hemos visto cómo hacer una búsqueda exhaustiva, que pruebe todas las posibles soluciones a un problema, para encontrar la óptima:

Pero en ocasiones, la solución óptima es demasiado costosa de calcular, ya sea por el gasto de memoria o de tiempo. En nuestro ejemplo anterior, para comprobar si las palabras de 8 letras que podíamos formar pertenecían a un diccionario formado por 8 palabras hacíamos cerca de 110.000 llamadas recursivas. Aunque aplicamos "podas" para no ramificar por caminos que no vayan a llevar a soluciones válidas, un problema real con datos de mayor tamaño puede ser inabordable en un tiempo limitado.

Por eso, a veces es preferible buscar una aproximación rápida. Una de las formas de conseguirlo es lo que se conoce como "algoritmos voraces" (greedy methods), que consisten en esperar que un máximo local nos lleve a un máximo global, o al menos a un valor suficientemente bueno.

La idea es no probar todas las posibilidades, sino la que parece más prometedora en cada paso. Y ese valor que hemos tomado se acepta como bueno y no se vuelve a reevaluar . Por ejemplo, para el problema de la mochila, podríamos pensar que, como se trata de obtener una mochila global con el mayor valor posible, podemos ir tomando en cada pasada el elemento de mayor valor:


  1: using System;
  2: using System.Collections.Generic;
  3: 
  4: public class Voraz01
  5: {
  6: 
  7:     class ElementoMochila
  8:     {
  9:         private float valor, peso;
 10:         public float Valor
 11:         {
 12:             get { return valor; }
 13:             set { valor = value; }
 14:         }
 15:         public float Peso
 16:         {
 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:         {
 34:             get { return valor; }
 35:         }
 36:         public float Peso
 37:         {
 38:             get { return peso; }
 39:         }
 40:         public Mochila()
 41:         {
 42:             elementos = new List<ElementoMochila>();
 43:         }
 44:         public void Add(ElementoMochila e)
 45:         {
 46:             peso += e.Peso;
 47:             valor += e.Valor;
 48:             elementos.Add(e);
 49:         }
 50:         public bool Contains(ElementoMochila e)
 51:         {
 52:             return elementos.Contains(e);
 53:         }
 54:         public void MostrarContenido()
 55:         {
 56:             foreach (ElementoMochila e in elementos)
 57:                 Console.WriteLine("  V: " + e.Valor + ", P: " + e.Peso);
 58:         }
 59:         public Mochila NuevaMochila(ElementoMochila nuevoElemento)
 60:         {
 61:             Mochila m2 = new Mochila();
 62:             foreach (ElementoMochila e in elementos)
 63:                 m2.Add(e);
 64:             m2.Add(nuevoElemento);
 65:             return m2;
 66:         }
 67:     }
 68: 
 69: 
 70:     static void BuscarPorMejorValor(Mochila mochilaActual,
 71:         List<ElementoMochila> elemPosibles,
 72:         int maximoPeso,
 73:         ref Mochila mejorMochila)
 74:     {
 75:         int cantidadInicialDatos = elemPosibles.Count;
 76:         // Damos varias pasadas
 77:         for (int pasada = 0; pasada < cantidadInicialDatos; pasada++)
 78:         {
 79:             // Escogiendo cada vez el candidato de mejor valor que quepa
 80:             int mejorCandidato = 0;
 81:             for (int posCandidato = 1; posCandidato < elemPosibles.Count;
 82:                 posCandidato++)
 83:             {
 84: 
 85:                 if ((elemPosibles[posCandidato].Peso <=
 86:                         maximoPeso - mejorMochila.Peso)
 87:                         && (elemPosibles[posCandidato].Valor
 88:                         > elemPosibles[mejorCandidato].Valor))
 89:                 {
 90:                     mejorCandidato = posCandidato;
 91:                 }
 92:             }
 93:             // Al final de la pasada, añado a la mochila el mejor candidato
 94:             // si es que se ha encontrado alguno válido
 95:             if (elemPosibles[mejorCandidato].Peso <=
 96:                         maximoPeso - mejorMochila.Peso)
 97:             {
 98:                 mejorMochila.Add(elemPosibles[mejorCandidato]);
 99:                 elemPosibles.RemoveAt(mejorCandidato);
100:             }
101:         }
102:     }
103: 
104:     public static void Main()
105:     {
106:         // Crear datos y llamar a la función de Backtracking
107:         List<ElementoMochila> elementosPosibles = new List<ElementoMochila>();
108:         elementosPosibles.Add(new ElementoMochila(200, 12));
109:         elementosPosibles.Add(new ElementoMochila(500, 6));
110:         elementosPosibles.Add(new ElementoMochila(400, 7));
111:         elementosPosibles.Add(new ElementoMochila(800, 3));
112:         elementosPosibles.Add(new ElementoMochila(1200, 20));
113:         elementosPosibles.Add(new ElementoMochila(1000, 10));
114: 
115:         int maximoPesoMochila = 23;
116: 
117:         Mochila mochilaVacia =
118:             new Mochila();
119: 
120:         Mochila mejorSolucion =
121:              new Mochila();
122: 
123: 
124:         BuscarPorMejorValor(mochilaVacia, elementosPosibles,
125:             maximoPesoMochila, ref mejorSolucion);
126: 
127:         // Y mostrar todas las soluciones almacenadas
128:         Console.WriteLine("Valor: " + mejorSolucion.Valor);
129:         mejorSolucion.MostrarContenido();
130:     }
131: }


El resultado sería, para esos datos:


 Valor: 2000
  V: 1200, P: 20
  V: 800, P: 3


Pero el resultado óptimo, calculado mediante backtracking, es:


 Valor: 2300
   V: 500, P: 6
   V: 800, P: 3
   V: 1000, P: 10


Si primero tomamos el elemento de mayor valor (2000), pero este pesa mucho, quizá no deje espacio para otros elementos que también son valiosos.

En ocasiones, el algoritmo se puede afinar para llevar a una solución mejor. Por ejemplo, para el problema de la mochila existe la alternativa de no tomar el elemento que tiene un mayor valor, sino el que tiene la mejor relación entre su valor y su peso.  La función apenas cambia:


 70:     static void BuscarPorMejorValor(Mochila mochilaActual,
 71:         List<ElementoMochila> elemPosibles,
 72:         int maximoPeso,
 73:         ref Mochila mejorMochila)
 74:     {
 75:         int cantidadInicialDatos = elemPosibles.Count;
 76:         // Damos varias pasadas
 77:         for (int pasada = 0; pasada < cantidadInicialDatos; pasada++)
 78:         {
 79:             // Escogiendo cada vez el candidato de mejor valor que quepa
 80:             int mejorCandidato = 0;
 81:             for (int posCandidato = 1; posCandidato < elemPosibles.Count;
 82:                 posCandidato++)
 83:             {
 84: 
 85:                 if ((elemPosibles[posCandidato].Peso <=
 86:                         maximoPeso - mejorMochila.Peso)
 87:                         && ((float) elemPosibles[posCandidato].Valor
 88:                             / elemPosibles[posCandidato].Peso
 89:                         > (float) elemPosibles[mejorCandidato].Valor
 90:                             / elemPosibles[mejorCandidato].Peso))
 91:                 {
 92:                     mejorCandidato = posCandidato;
 93:                 }
 94:             }
 95:             // Al final de la pasada, añado a la mochila el mejor candidato
 96:             // si es que se ha encontrado alguno válido
 97:             if (elemPosibles[mejorCandidato].Peso <=
 98:                         maximoPeso - mejorMochila.Peso)
 99:             {
100:                 mejorMochila.Add(elemPosibles[mejorCandidato]);
101:                 elemPosibles.RemoveAt(mejorCandidato);
102:             }
103:         }
104:     }


Pero el resultado es muy bueno:


 Valor: 2300
   V: 800, P: 3
   V: 500, P: 6
   V: 1000, P: 10


Se puede observar que por backtracking obteníamos los elementos ordenados "del primero al último" en orden de introducción al problema, y aquí los hemos obtenido ordenados por relación valor/peso, pero el resultado global ha sido el mismo... en una ínfima parte de tiempo.


No en todos los problemas se puede encontrar una solución voraz que lleve a una solución óptima, y generalmente la "bondad" de la solución depende de la pericia del programador, pero en muchos problemas reales, la pérdida de optimalidad es aceptable por la (enorme) ganancia de tiempo y de otros recursos computacionales (sobre todo, memoria, que es algo fácil de agotar cuando se hace una enorme cantidad de llamadas recursivas).

19 abril 2013

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