Los algoritmos voraces suelen ser bastante simples. Se emplean sobre todo para resolver problemas de optimización, como, por ejemplo, encontrar la secuencia óptima para procesar un conjunto de tareas por un computador, hallar el camino mínimo de un grafo, etc.
Habitualmente, los elementos que intervienen son:
-
un conjunto o lista de candidatos (tareas a procesar, vértices del grafo, etc.);
-
un conjunto de decisiones ya tomadas (candidatos ya escogidos);
-
una función que determina si un conjunto de candidatos es una solución al problema (aunque no tiene por qué ser la óptima);
-
una función que determina si un conjunto es completarle, es decir, si añadiendo a este conjunto nuevos candidatos es posible alcanzar una solución al problema, suponiendo que esta exista;
-
una función de selección que escoge el candidato aún no seleccionado que es más prometedor;
-
una función objetivo que da el valor/coste de una solución (tiempo total del proceso, la longitud del camino, etc.) y que es la que se pretende maximizar o minimizar.
Para resolver el problema de optimización hay que encontrar un conjunto de candidatos que optimiza la función objetivo. Los algoritmos voraces proceden por pasos. Inicialmente el conjunto de candidatos es vacío. A continuación, en cada paso, se intenta añadir al conjunto el mejor candidato de los aún no escogidos, utilizando la función de selección. Si el conjunto resultante no es completarle, se rechaza el candidato y no se le vuelve a considerar en el futuro. En caso contrario, se incorpora al conjunto de candidatos escogidos y permanece siempre en él. Tras cada incorporación se comprueba si el conjunto resultante es una solución del problema. Un algoritmo voraz es correcto si la solución así encontrada es siempre óptima. El esquema genérico del algoritmo voraz es:
El nombre voraz proviene de que, en cada paso, el algoritmo escoge el mejor "pedazo" que es capaz de "comer" sin preocuparse del futuro. Nunca deshace una decisión ya tomada: una vez incorporado un candidato a la solución permanece ahí hasta el final; y cada vez que un candidato es rechazado, lo es para siempre.
Ejemplo:
Se desea pagar una cantidad de dinero a un cliente empleando el menor número posible de monedas. Los elementos del esquema anterior se convierten en:
-
candidato: conjunto finito de monedas de, por ejemplo, 1, 5, 10 y 25 unidades, con una moneda de cada tipo por lo menos;
-
solución: conjunto de monedas cuya suma es la cantidad a pagar;
-
completarle: la suma de las monedas escogidas en un momento dado no supera la cantidad a pagar;
-
función de selección: la moneda de mayor valor en el conjunto de candidatos aún no considerados;
-
función objetivo: número de monedas utilizadas en la solución.
Un ejemplo de este tema sería con los Árboles de Huffman; la codificación Huffman es un algoritmo usado para compresión de datos. El término se refiere al uso de una tabla de códigos de longitud variable para codificar un determinado símbolo (como puede ser un carácter en un archivo), donde la tabla ha sido rellenada de una manera específica basándose en la probabilidad estimada de aparición de cada posible valor de dicho símbolo. Fue desarrollado por David A. Huffman mientras era estudiante de doctorado en el MIT, y publicado en "A Method for the Construction of Minimum-Redundancy Codes".
Árbol de Huffman generado para las frecuencias de apariciones exactas del texto "ESTO ES UN EJEMPLO DE UN ARBOL DE HUFFMAN". Las frecuencias y códigos de cada carácter se muestran abajo. Codificar esta frase de 41 caracteres usando este código requiere 156 bits (sin contar con el espacio para el árbol) cuando con bytes de 8 bits requiere 328 bits.
Una sonda espacial ha sido lanzada al espacio para contar cierto tipo de perturbaciones estelares. Ha de contar cuántas se producen en cada minuto, y tiene cada día una ventana de tiempo bastante reducida para enviar los datos a Tierra; por tanto, interesa reducir al máximo el tiempo de transmisión, y para ello se recurre a codificar las muestras mediante un código de Huffman.
En la siguiente tabla se muestran los valores a transmitir, junto con sus frecuencias relativas, su código en una codificación binaria de 3 bits, y su código en un posible código Huffman para estos valores
Puede observarse que, en la codificación binaria, todos los posibles valores reciben códigos del mismo número de bits, mientras que en la codificación Huffman, cada valor tiene un número diferente de bits: los códigos más frecuentes poseen dos bits, mientras que los menos frecuentes poseen cuatro bits.
En este ejemplo, la media de bits por símbolo que cabría esperar de esta codificación, en cadenas de valores más largas, es de 2,4.
Para su comparación, la entropía del conjunto de símbolos es de 2,366; es decir, el mejor método de compresión sería capaz de codificar estos valores utilizando 2,366 bits por símbolo.
Es posible, también, apreciar cómo se pueden extraer sin ninguna ambigüedad los valores originales a partir de la cadena codificada mediante Huffman.
Hay que añadir que la codificación de Huffman no puede ser aplicada a imágenes en blanco y negro porque es incapaz de producir compresión sobre un alfabeto binario.
Referencias:
-
Algoritmos voraces. (s. f.). cica. https://thales.cica.es/rd/Recursos/rd99/ed99-0033-04/voraz_introd.html
-
De Aguilera, M., Sosa, A., & De Aguilera, R. (2018). Comunicación, discursos, algoritmos, poder. Ámbitos. Revista Internacional de Comunicación, 40, 161-167. https://doi.org/10.12795/ambitos.2018.i40.20