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