Algoritmos voraces

Los algoritmos voraces típicamente se utilizan en la solución de problemas de optimización y se caracterizan por ser:

– Sencillos de diseñar y codificar.
– Miopes: toman decisiones con la información que tienen disponible de forma inmediata, sin tener en cuenta sus efectos futuros.
– Eficientes: dan una solución rápida al problema (aunque ésta no sea siempre la mejor).

Los algoritmos voraces se caracterizan por las propiedades siguientes:

– Tratan de resolver problemas de forma óptima.
– Disponen de un conjunto (o lista) de candidatos.

A medida que avanza el algoritmo vamos acumulando dos conjuntos:

– candidatos considerados y seleccionados
– candidatos considerados y rechazados

Existe una función que comprueba si un cierto conjunto de candidatos constituye una solución de nuestro problema, ignorando si es óptima o no por el momento.

Existe una función que comprueba si un cierto conjunto de candidatos es factible, esto es, si es posible o no completar el conjunto añadiendo otros candidatos para obtener al menos una solución al problema. Una vez más, no nos importa si la solución es óptima o no. Normalmente se espera que al menos se pueda obtener una solución a partir de los candidatos disponibles inicialmente.

Existe una función de selección que indica cuál es el más prometedor de los candidatos restantes no considerados aún.

Implícitamente está presente una función objetivo que da el valor a la solución que hemos hallado (valor que estamos tratando de optimizar).

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 una computadora, 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 completable, 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/costo de una solución (tiempo total del proceso, la longitud del camino, etc.) y que es la que se pretende maximizar o minimizar.

Fuente: Apunte Análisis, diseño e implantación de algoritmos de la facultad de contaduría y administración, UNAM