Euristiche costruttive¶
Parte 4 · Algoritmi euristici · Capitolo 30 · 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
Prerequisiti
-
Da questo modulo, il capitolo «Algoritmi euristici: definizioni»: bound primali e duali, il gap e le quattro istanze di riferimento.
-
Da questo modulo, i capitoli sui problemi: il KP, il BPP, \(P\,||\,C_{\max}\), il TSP e il VCP.
Obiettivi
Alla fine di questo capitolo saremo in grado di:
-
applicare l'algoritmo greedy al KP con i tre ordinamenti (profitto, peso, efficienza);
-
eseguire FF, FFD e BFD per il BPP, e LIST e LPT per \(P\,||\,C_{\max}\);
-
costruire un giro del TSP con il nearest neighbour e con le euristiche di inserimento;
-
applicare la costruzione randomizzata, l'inserimento con regret e il metodo pilota;
-
confrontare i risultati con i bound duali, e spiegare quando un'euristica costruttiva fallisce.
30.1 Euristiche costruttive¶
Definizione 30.1: Euristica costruttiva
Un'euristica costruttiva è un algoritmo euristico che costruisce una soluzione ammissibile passo dopo passo: parte dalla soluzione parziale vuota e la estende con un elemento alla volta, finché la soluzione non è completa.
-
Gli elementi dipendono dal problema: gli oggetti selezionati per lo zaino, gli assegnamenti degli oggetti ai contenitori e dei lavori alle macchine, gli archi di un giro.
-
La qualità del risultato dipende da come si sceglie, a ogni passo, l'elemento da aggiungere (Sezione 30.3).
-
Panoramica
Euristiche costruttive
-
I problemi e le ipotesi · Il paradigma greedy
Il paradigma greedy
-
30.4 Il problema dello zaino 0/1: quale ordinamento?
-
30.5 Il problema del bin packing: prima ordinare, poi riempire
Best Fit Decreasing · Che cosa dà l'ordinamento, e che cosa non dà
-
30.6 Scheduling su macchine parallele: prima i lavori più lunghi
Longest processing time first
-
30.7 Il problema del commesso viaggiatore: accodare o inserire?
Nearest neighbour multi-start · Euristiche di inserimento · Un confronto su un'istanza più grande
-
30.8 Colorazione dei vertici: greedy e DSATUR
DSATUR · Che cosa garantisce la colorazione greedy · DSATUR come euristica
-
30.9 Costruzione randomizzata
-
30.10 Look-ahead e regret
Look-ahead: il metodo pilota
-
30.11 Che cosa danno le euristiche costruttive, e che cosa non danno
-
Errori tipici · In sintesi
In sintesi
Avanti: I problemi e le ipotesi · Il paradigma greedy
Esercizi su questo capitolo: Euristiche costruttive
Nel laboratorio interattivo: Euristiche per il bin packing, List scheduling e LPT, Colorazione: greedy e DSATUR, TSP: nearest neighbour e 2-opt.