30.11 Che cosa danno le euristiche costruttive, e che cosa non danno¶

Parte 4 · Algoritmi euristici · Capitolo 30 · Capitolo 30: Euristiche costruttive · Dispensa, volume 4 (PDF) · Slide (1/2) · Slide (2/2) · Esercizi: Euristiche costruttive · App: Euristiche per il bin packing · App: List scheduling e LPT · App: Colorazione: greedy e DSATUR · App: TSP: nearest neighbour e 2-opt

La tabella raccoglie i risultati sulle quattro istanze di riferimento, con i bound duali del capitolo «Algoritmi euristici: definizioni» (\(\UB\) per il KP, \(\LB\) per gli altri problemi) e il gap della migliore soluzione euristica.

problema	euristica	valori	bound duale	gap	\(z(I)\)
KP	\(GR_p\), \(GR\), \(GR_w\)	\(17\), \(16\), \(10\)	\(\UB=17\)	\(0\%\)	\(17\)
BPP	FF, FFD, BFD	\(4\), \(3\), \(3\)	\(\LB=3\)	\(0\%\)	\(3\)
\(P\,\|\|\,C_{\max}\)	\(LIST\) (lista inversa), \(LPT\)	\(12\), \(11\)	\(\LB=9\)	\(22.2\%\)	\(9\)
TSP	\(NN\), multi-start \(NN\), \(NI\), \(FI\), \(CI\)	\(25\), \(18\), \(18\), \(18\), \(18\)	\(\LB=17\)	\(5.9\%\)	\(18\)

Un bound primale, e niente di più. Un'euristica costruttiva restituisce una soluzione ammissibile, e il suo valore è un bound primale. Per il KP e il BPP il miglior valore euristico coincide con il bound duale, e la soluzione è dimostrata ottima; per il TSP il giro di lunghezza \(18\) è ottimo, ma il bound duale \(17\) non può dimostrarlo; per \(P\,||\,C_{\max}\) il gap del \(22.2\%\) è reale. L'euristica stessa non sa mai in quale di queste situazioni si trova.
Una scelta non si rivede mai. Ogni euristica di queste note si ferma appena la soluzione è completa, e ogni decisione presa lungo il percorso è definitiva. Nello schedule di \(LPT\), il lavoro \(7\) va sulla macchina \(1\) quando i tre carichi sono uguali, e il makespan \(11\) è fissato in quel momento; nel giro di \(NN\) dalla città \(1\), l'arco \((5,1)\) di lunghezza \(9\) è la conseguenza delle primissime scelte. Guardando il diagramma di Gantt o il giro, una soluzione migliore sembra vicina; ma un'euristica costruttiva non ha alcun meccanismo per tornare indietro.
L'ordine decide tutto. Gli esempi di queste note mostrano la stessa lezione su quattro problemi: ordinare gli elementi nell'ordine giusto (efficienza, pesi decrescenti, prima i lavori più lunghi) è la principale scelta di progetto; tuttavia nessun ordine è il migliore su ogni istanza (Esempio 30.1, Esempio 30.4), ed eseguire più ordini, più punti di partenza o più costruzioni randomizzate, tenendo la soluzione migliore, è una protezione economica ed efficace.
Economiche, e utili come punto di partenza. Le euristiche costruttive sono veloci, e raramente si usano da sole: le loro soluzioni sono i punti di partenza dei metodi che cercano di migliorare una soluzione completa.

Un'euristica costruttiva costruisce una soluzione, un elemento alla volta, scegliendo a ogni passo l'elemento che sembra migliore adesso. L'ordine delle scelte decide la qualità del risultato, e una scelta, una volta fatta, non si rivede mai.

Avanti: Errori tipici · In sintesi