Vai al contenuto

Euristiche costruttive

Prerequisiti

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;

  • colorare un grafo con la colorazione greedy e con \(DSATUR\);

  • 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.

2.1 Euristiche costruttive

Definizione 2.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 2.3).

  • Panoramica

    Euristiche costruttive

    Apri

  • I problemi e le ipotesi · Il paradigma greedy

    Il paradigma greedy

    Apri

  • 2.4 Il problema dello zaino 0/1: quale ordinamento?

    Apri

  • 2.5 Il problema del bin packing: prima ordinare, poi riempire

    Best Fit Decreasing · Che cosa dà l'ordinamento, e che cosa non dà

    Apri

  • 2.6 Scheduling su macchine parallele: prima i lavori più lunghi

    Longest processing time first

    Apri

  • 2.7 Il problema del commesso viaggiatore: accodare o inserire?

    Nearest neighbour multi-start · Euristiche di inserimento · Un confronto su un'istanza più grande

    Apri

  • 2.8 Colorazione dei vertici: greedy e DSATUR

    DSATUR · Che cosa garantisce la colorazione greedy · DSATUR come euristica

    Apri

  • 2.9 Costruzione randomizzata

    Apri

  • 2.10 Look-ahead e regret

    Look-ahead: il metodo pilota

    Apri

  • 2.11 Che cosa danno le euristiche costruttive, e che cosa non danno

    Apri

  • Errori tipici · In sintesi

    In sintesi

    Apri


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.