Algoritmo Greedy

Un algoritmo greedy è una classe di algoritmi costruttivi che a ogni passo prende la decisione localmente ottima e non torna mai indietro. Le radici risalgono a lavori combinatori classici (Kruskal 1956 e Prim 1957 per albero ricoprente minimo; Dijkstra 1959 per cammino minimo). Quando l'approccio greedy produce l'ottimo globale è caratterizzato dalla teoria dei matroidi: il teorema di Rado-Edmonds (Edmonds 1971) afferma che un sistema di sottoinsiemi è risolto ottimamente dall'algoritmo greedy per tutte le funzioni peso se e solo se è un matroide. Per questo albero ricoprente minimo (Kruskal/Prim), codifica di Huffman (Huffman 1952) e tempo di completamento pesato su singola macchina (regole SPT/EDD, Smith 1956) ammettono soluzione greedy ottima. Al contrario, zaino, bin packing, set covering e VRP hanno soluzioni greedy con solo fattore di approssimazione noto (es. Chvátal 1979 ln(n)+1 per set covering) e non sono globalmente ottime. In pratica gli algoritmi greedy svolgono tre ruoli: (1) euristica costruttiva rapida (warm-start), (2) famiglia di algoritmi di approssimazione con garanzia, (3) soluzione iniziale per ricerca locale o metaeuristiche. Euristicamente, il TSP greedy (vicino più prossimo), il metodo di savings di Clarke-Wright (1964) per VRP e la famiglia LPT/SPT nello scheduling sono esempi standard di settore. Cormen, Leiserson, Rivest e Stein (CLRS, 2009) capitolo 16 è il trattato di riferimento.