Greedy Algorithm
Un algoritmo voraz realiza en cada paso la elección localmente óptima sin retroceder; es simple y eficiente pero no garantiza un óptimo global.
Propósito
Resolver problemas de optimización de forma rápida y aproximada, exigiendo demostrar la propiedad de elección voraz.
Mecanismo
Cada paso toma el óptimo local esperando uno global. Su aplicabilidad requiere la propiedad de elección voraz (un óptimo local se extiende a uno global) más subestructura óptima. Clásicos: codificación de Huffman, Dijkstra, Kruskal, mochila fraccionaria.
Casos de uso
- Diseño de algoritmos
- Optimización aproximada
- Problemas de planificación