Existe un buen número de métodos que los matemáticos y científicos emplean cuando deben resolver problemas complejos. Uno de los más versátiles y simples de entender es el denominado “algoritmo voraz” (Greedy algorithm). A pesar de que no siempre es capaz de encontrar una respuesta óptima, se lo utiliza con frecuencia dado que es muy rápido. Te contamos en qué consiste, qué ventajas tiene y cómo utilizarlo.
Para resolver un problema se deben seguir una serie de pasos. Estos pasos deben estar claramente definidos, sin importar que vayan a ser ejecutados por un ordenador o por un humano. La correcta definición de esos pasos garantiza que si se aplica el sistema dos veces a un determinado problema, la solución será la misma. Esta verdadera “receta” se llama algoritmo, y no es otra cosa que una secuencia de pasos ordenados y finitos con los que podemos resolver un problema determinado en un tiempo mínimo. El vocablo “algoritmo” proviene del latín “dixit algorithmus”, y éste a su vez del nombre de un matemático persa llamado Muhammad ibn Musa al-Jwarizmi.
El algoritmo voraz
Hay problemas que a pesar de tener un planteo sumamente sencillo, carecen de una solución que pueda ser considerada trivial. Imaginemos, por ejemplo, un viajante de comercio que debe recorrer 25 ciudades distribuidas por el interior de España: ¿de que forma debería hacerlo para completar su trabajo recorriendo el menor número de kilómetros posible? El problema seguramente es de interés para un gran número de empresas, se puede definir claramente en pocas palabras, pero su solución demandaría a un ordenador varios años de trabajo.
Esto se debe a que la cantidad de recorridos posibles es de 25! (25 factorial, o sea, 1 x 2 x 3 x 4 x 5 x … x 24 x 25), es decir, hay 15.511.210.043.330.985.984.000.000 recorridos para probar y descartar antes de saber cual es el óptimo. Analizando mil millones de recorridos por segundo, demoraríamos 491.857.244 años en averiguar cuál es el recorrido óptimo para nuestro viajante. Esto sirve para darnos cuenta de la importancia que tiene un algoritmo rápido, aun cuando no siempre sea capaz de encontrar el mejor resultado posible.
El denominado “algoritmo voraz” sigue una estrategia sencilla pero eficaz. Simplemente, se trata de elegir la opción óptima en cada paso local, con la esperanza de llegar a una solución general óptima. En el ejemplo de nuestro viajante de comercio, cada paso podría ser tan simple como -estando en la ciudad “A”- dirigirse a la más cercana que aún no hayamos visitado. Una vez allí, repetir el procedimiento una y otra vez hasta que hayamos completado el recorrido. Seguramente no obtendremos un resultado óptimo, pero puede encontrarse un camino bastante bueno en un tiempo despreciable.
Este tipo de algoritmo, a veces llamado ávido, devorador o goloso, es el que menos dificultades presenta a los investigadores que deben diseñar y comprobar el funcionamiento de diferentes estrategias. El nombre “voraz” se debe a que, en cada paso, el algoritmo escoge el mejor “pedazo” que es capaz de “comer“ sin preocuparse de los pasos que restan hasta encontrar la solución. Un algoritmo de este tipo nunca deshace una decisión ya tomada: una vez incorporado, un “candidato a la solución” (ir de la ciudad “A” a la “B”, por ejemplo) formará parte de la solución. Y cada candidato rechazado es eliminado definitivamente.
Una vez aclarado el hecho de que los algoritmos voraces proceden por pasos, podemos ver en detalle cómo es su estructura. Se parte de un conjunto de candidatos que se encuentra vacío, es decir, no hay ninguna solución. Luego, en cada paso, se intenta añadir al conjunto el mejor candidato entre las soluciones que aún no han sido escogidas, a través de una función de selección. Luego de cada incorporación se comprueba si el conjunto de candidatos resultante es una solución del problema. Su esquema genérico es el siguiente:
función voraz(C:conjunto):conjunto { C es el conjunto de todos los candidatos } S <= vacio { S es el conjunto en el que se construye la solución} mientras ¬solución(S) y C <> vacío hacer x <= el elemento de C que maximiza seleccionar(x) C <= C {x} si completable(S U {x}) entonces S <= S U {x} si solución(S) entonces devolver S si no devolver no hay solución
Para comprender exactamente su funcionamiento podemos aplicarlo a otro problema sencillo: Supongamos que disponemos de un grupo compuesto por cuatro tipos billetes de banco: diez billetes de 5, cinco de 10, tres de 20 y dos de 50. Tenemos que hacer un pago de 100 euros con el menor número de billetes posible ¿que billetes debemos escoger? La solución obvia consiste en utilizar dos billetes de cincuenta euros, pero ¿como llegaría a esa solución un ordenador? Muy simple: utilizando el algoritmo voraz.
Al plantear ese problema, el “candidato” (c) sería un conjunto finito de billetes, la “solución” (S) el conjunto de billetes buscados y cuya suma es la cantidad a pagar, “completable” es la suma de billetes escogidos en un momento dado y que no supera la cantidad a pagar, y la “función de selección” no es otra cosa que la encargada de seleccionar el billete de mayor valor disponible en el conjunto de candidatos aún no seleccionados.
En el primer paso se elegiría uno de los billetes de mayor valor disponibles (uno de 50). Luego de comprobar que no se llegó a la solución se tomaría nuevamente uno de los billetes de mayor valor disponibles (el restante de 50) y se comprobaría que hemos llegado a la solución. Simple de implementar, ¿verdad?.
