Algoritmos voraces

Scientia et Technica Año XIII, No 37, Diciembre de 2007. Universidad Tecnológica de Pereira. ISSN 0122-1701

449

ALGORITMOS VORACES
Algorithms voracious
RESUMEN Los algoritmos voraces son usados esencialmente para resolver problemas de optimización, aunque también pueden aproximarse a una solución a problemas considerados computacionalmente difíciles, Son algoritmos muy fácil de diseñar eimplementar y de gran eficiencia. PALABRAS CLAVES: Algoritmia, Problemas Np ABSTRACT The voracious algorithms are used essentially for solve optimization problems, even also they can approximate to a solution for problem considered difficult computationally, they are algorithms very easy to design and implement and of great efficiency. KEY WORDS: Prim's voracious algorithms, Fuman and KruskalAlgorithmia, Np Problems. Algoritmos Voraces Prim, Fuman y Kruskal GUILLERMO SOLARTE MARTINEZ Ingeniero de Sistemas. Profesor Auxiliar. Universidad Tecnológica de Pereira. roberto@utp.edu.co LUIS EDUARDO MUÑOZ GUERRERO Ingeniería de Sistemas M.Sc. Profesor Auxiliar. Universidad Tecnológica de Pereira. luismunoz@utp.edu.co

1. INTRODUCCIÓN Este artículo se realiza una exposición de algunos problemasque admiten el uso de esta técnica voraz y los algoritmos que mediante dicha técnica los resuelve. Para esto utilizamos el lenguaje Phyton para realizar nuestra presentación y para cada uno de ellos se realiza el cálculo de la función de complejidad. Por ultimo se presenta la teoría de Matroid como soporte teórico para la corrección de algunos algoritmos voraces en la solución de problemas deoptimización. Algunos ejemplos de problemas que se pueden solucionar utilizando un algoritmo voraz son:

anteriores. Los algoritmos voraces se caracterizan por las siguientes propiedades:  Existe una función que comprueba si un cierto conjunto de candidatos constituye una solución del problema, ignorando si es o no óptimo por el momento. La segunda función, Comprueba si un cierto conjunto decandidatos es factible, es decir si es posible o no completar el conjunto añadiendo otros candidatos para obtener al menos una solución del problema. La tercera función, Realiza una selección, que indica en cualquier momento cual es el más prometedor de los candidatos restantes, que no han sido seleccionados ni rechazados. Por ultimo existe una función objetivo queda el valor de la solución hallada, porejemplo la longitud de la ruta que se ha construido o el número de monedas utilizadas para cambiar una cantidad, a diferencia de las funciones mencionadas anteriormente, la función objetivo no aparece explícitamente en el algoritmo voraz, algunas veces la función de selección suele estar relacionada con la función objetivo, por ejemplo si se intenta maximizar es posible que se seleccione elcandidato restante que posea mayor valor individual, como el problema de cambio de moneda; si por el contrario se intenta minimizar el coste, quizá se seleccione de los candidatos disponibles el menor valor. Sin embargo, en algunas ocasiones puede haber varias





   En un grafo ponderando para dar la ruta más corta para ir de un nodo a otro. Suponiendo que el sistema monetario de un paísesta formado por un numero finito de denominaciones, para cualquier cantidad dad, suministrada en el menor numero posibles de monedas.

En tales contexto, un algoritmo voraz funciona seleccionado la arista o la moneda que parezca más prometedora en un determinado instante, nunca reconsidera su decisión sea cual fuera la situación que pueda surgir más adelante. No hay necesidad de evaluaralternativas, ni de emplear sostificados procedimientos de seguimientos que permitan deshacer las decisiones
Fecha de Recepción: 31 Mayo de 2007 Fecha de Aceptación: 22 Octubre de 2007

450

Scientia et Technica Año XIII, No 37, Diciembre de 2007. Universidad Tecnológica de Pereira.

funciones de selección disponibles así que hay que escoger la adecuada para lograr que el algoritmo funcione...