Método voraz

Algoritmo por Método Voraz

Concepto

Un algoritmo por método voraz (también conocido como ávido o devorador) es aquel que, para resolver un determinado problema, sigue una metaheurística (métodoheurístico para resolver un tipo de problema computacional general, usando los parámetros dados por el usuario sobre unos procedimientos genéricos y abstractos de una manera que se espera eficiente)consistente en elegir la opción en cada paso local con la finalidad de llegar a una solución general óptima.
Este esquema algorítmico es el que menos dificultades plantea a la hora de diseñar ycomprobar su funcionamiento. Normalmente se aplica a los problemas de optimización.
Consiste en que cada elemento a considerar se evalúa una única vez, siendo descartado o seleccionado, de tal forma quesi es seleccionado forma parte de la solución, y si es descartado, no forma parte de la solución ni volverá a ser considerado para la misma.
El término voraz se deriva de la forma en que los datosde entrada se van tratando, realizando la elección de desechar o seleccionar un determinado elemento una sola vez.
Al contrario que con otros métodos algorítmicos, no siempre es posible dar unasolución a un problema empleando un algoritmo voraz. No todos los problemas son resolubles con algoritmos voraces.
Los algoritmos voraces tienden a ser bastante eficientes y pueden implementarse deforma relativamente sencilla. Su eficiencia se deriva de la forma en que trata los datos, llegando a alcanzar muchas veces una complejidad de orden lineal. Sin embargo, la mayoría de los intentos decrear un algoritmo voraz correcto fallan a menos que exista previamente una prueba precisa que demuestre la correctitud de algoritmo. Cuando una estrategia voraz falla al producir resultados óptimos entodas las entradas, en lugar de algoritmo suele denominarse heurística. Las heurísticas resultan cuando la velocidad es más importante que los resultados exactos (por ejemplo, cuando resultados...