Algoritmo Voraz

Un algoritmo voraz (greedy) es una clase de algoritmos constructivos que toma en cada paso la decisión que parece localmente óptima y nunca retrocede. Sus raíces se remontan a trabajos combinatorios clásicos (Kruskal 1956 y Prim 1957 para árbol de expansión mínima; Dijkstra 1959 para camino más corto). Cuándo el enfoque voraz produce el óptimo global lo caracteriza la teoría de matroides: el teorema de Rado-Edmonds (Edmonds 1971) afirma que un sistema de subconjuntos es resuelto óptimamente por el algoritmo voraz para todas las funciones de peso si y sólo si es un matroide. Por eso árbol de expansión mínima (Kruskal/Prim), codificación de Huffman (Huffman 1952) y tiempo de finalización ponderado en una sola máquina (reglas SPT/EDD, Smith 1956) admiten solución voraz óptima. En cambio, mochila, bin packing, set covering y VRP tienen soluciones voraces sólo con factor de aproximación conocido (p. ej. Chvátal 1979 ln(n)+1 para set covering) y no son globalmente óptimas. En la práctica los algoritmos voraces cumplen tres roles: (1) heurística constructiva rápida (arranque cálido), (2) familia de algoritmos de aproximación con garantía, (3) solución inicial para búsqueda local o metaheurísticas. Heurísticamente, el TSP voraz (vecino más cercano), el método de ahorros de Clarke-Wright (1964) para VRP y la familia LPT/SPT en scheduling son ejemplos estándar de la industria. Cormen, Leiserson, Rivest y Stein (CLRS, 2009) capítulo 16 es el tratado de referencia.