I problemi e le ipotesi · Il paradigma greedy

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

30.2 I problemi e le ipotesi

• Illustriamo le euristiche sui quattro problemi del capitolo «Algoritmi euristici: definizioni»: il problema dello zaino 0/1 (KP), il problema del bin packing (BPP), il problema del commesso viaggiatore (TSP) e \(P\,||\,C_{\max}\); la colorazione greedy e \(DSATUR\) si applicano al problema della colorazione dei vertici (VCP). Le loro definizioni e ipotesi sono nelle rispettive pagine; qui richiamiamo la notazione.

• Come nelle altre note, \(\mathscr{A}(I)\) indica il valore della soluzione calcolata dall'euristica \(\mathscr{A}\) sull'istanza \(I\), e \(z(I)\) il valore ottimo. Per \(P\,||\,C_{\max}\), \(L_h=\sum_{j\in J_h}t_j\) è il carico della macchina \(h\), e il vettore \(mach\) memorizza la macchina \(mach_j\) di ogni lavoro \(j\); per il BPP, il vettore \(bin\) memorizza il contenitore \(bin_j\) di ogni oggetto \(j\), e \(rc\) indica una capacità residua.

• Gli esempi usano le quattro istanze di riferimento del capitolo «Algoritmi euristici: definizioni», di cui sono noti i valori ottimi:

problema	istanza di riferimento	ottimo
KP	\(p=(10,7,6,4)\), \(w=(5,4,3,3)\), \(c=9\)	\(\{1,2\}\), \(z(I)=17\)
BPP	\(w=(4,4,5,3,2,3)\), \(c=7\)	\(\{1,4\},\{2,6\},\{3,5\}\), \(z(I)=3\)
\(P\,||\,C_{\max}\)	\(t=(5,5,4,4,3,3,3)\), \(m=3\)	\(\{1,3\},\{2,4\},\{5,6,7\}\), \(z(I)=9\)
TSP	\(5\) città, distanze qui sotto	\(\sigma=(1,3,5,2,4)\), \(z(I)=18\)

• Nelle figure, le cinque città dell'istanza di riferimento del TSP sono disegnate sempre nelle stesse posizioni, su un pentagono, nell'ordine \((1,3,5,2,4)\) del giro ottimo: il giro ottimo è quindi il bordo del pentagono, e ogni giro che usa una diagonale ne è visibilmente diverso. La figura riporta le distanze dell'istanza e, in grassetto, il suo giro ottimo.

\[ \begin{array}{c|ccccc} \hline {d_{ij}} & {1} & {2} & {3} & {4} & {5} \\ \hline {1} & --- & {5} & {2} & {2} & {9} \\ {2} & {5} & --- & {4} & {3} & {4} \\ {3} & {2} & {4} & --- & {4} & {7} \\ {4} & {2} & {3} & {4} & --- & {7} \\ {5} & {9} & {4} & {7} & {7} & --- \\ \hline \end{array} \]

30.3 Il paradigma greedy

• Una soluzione di ciascuno dei quattro problemi è fatta di elementi: gli oggetti selezionati per lo zaino, gli assegnamenti degli oggetti ai contenitori e dei lavori alle macchine, gli archi di un giro. Un'euristica costruttiva parte dalla soluzione parziale vuota e aggiunge un elemento alla volta.

• A ogni passo bisogna rispondere a tre domande: quali elementi si possono aggiungere (i candidati), quale si aggiunge (il criterio di selezione) e se il risultato si può ancora completare in una soluzione ammissibile (il test di ammissibilità). Un'euristica greedy risponde alla seconda domanda nel modo più semplice: aggiunge il candidato che sembra migliore adesso, secondo un criterio che misura il beneficio immediato dell'elemento.

Definizione 30.2: Algoritmo greedy

Un algoritmo greedy è un'euristica costruttiva che costruisce una soluzione selezionando ripetutamente, fra gli elementi candidati, il migliore secondo un criterio di selezione; l'elemento si aggiunge alla soluzione parziale se il test di ammissibilità lo consente, e si scarta altrimenti.

In un algoritmo greedy ogni decisione si prende una volta per tutte: una scelta, una volta fatta, non si rivede mai.

• Lo pseudocodice qui sotto è uno schema più che un algoritmo: l'insieme dei candidati, il criterio e il test sono le tre parti che ogni euristica di queste note definisce in modo specifico.

Algoritmo: Schema greedy

Input: un'istanza \(I\), l'insieme \(C\) degli elementi delle soluzioni

Output: una soluzione ammissibile \(S\)

1Function Greedy(\(I\))

2\(S := \emptyset\) ▹ soluzione parziale vuota

3while \(C \neq \emptyset\) and \(S\) non è completa do

4\(e :=\) il migliore elemento di \(C\) secondo il criterio di selezione

5\(C \leftarrow C \setminus \{e\}\) ▹ \(e\) si esamina una sola volta

6if \(S \cup \{e\}\) supera il test di ammissibilità then

7\(S \leftarrow S \cup \{e\}\) ▹ la scelta è definitiva

8end

9end

10return \(S\)

Esegui in Colab:PythonC++

• L'ordine decide tutto. Lo schema esamina gli elementi nell'ordine indotto dal criterio di selezione, e un elemento rifiutato o accettato presto non si può riconsiderare dopo. Due euristiche greedy con gli stessi candidati e lo stesso test di ammissibilità, ma con criteri diversi, possono produrre soluzioni molto diverse: cambiare il criterio è la principale scelta di progetto.

• Criteri statici e dinamici. Un criterio è statico se il valore di un elemento non dipende dalla soluzione parziale: gli elementi si possono allora ordinare una sola volta all'inizio, e l'euristica scorre la lista ordinata (efficienza degli oggetti del KP, peso degli oggetti del BPP, tempo di esecuzione dei lavori). Un criterio è dinamico se il valore di un elemento cambia man mano che la soluzione cresce, e va ricalcolato a ogni passo (distanza dall'ultima città di un giro parziale, capacità residua dei contenitori, carico delle macchine).

• Miopia. Il criterio guarda solo all'effetto immediato di una scelta, non alle sue conseguenze sulle scelte ancora da fare. È ciò che rende veloci le euristiche greedy, ed è anche ciò che le fa fallire: una scelta buona adesso può costringere a scelte cattive dopo.

• Tempo di esecuzione. Con un criterio statico il tempo di esecuzione è di solito dominato dall'ordinamento, \(O(n\log n)\), più il costo dei test di ammissibilità; con un criterio dinamico è il numero di passi per il costo di rivalutare i candidati, di solito \(O(n^2)\) o \(O(n^3)\).

• Quando il greedy è esatto. Per alcuni problemi un algoritmo greedy trova sempre una soluzione ottima: l'algoritmo di Kruskal per il problema dell'albero ricoprente di costo minimo esamina gli archi per costo non decrescente e accetta un arco se non chiude un ciclo; il problema dello zaino frazionario si risolve all'ottimo prendendo gli oggetti per efficienza non crescente. Per i quattro problemi NP-difficili di queste note nessun algoritmo greedy è esatto, e la domanda diventa quale criterio dà buone soluzioni.

• La tabella seguente mostra come si specifica lo schema per i quattro problemi; le sezioni successive li studiano uno per uno.

problema	elemento	criterio di selezione	test di ammissibilità
KP	un oggetto	profitto, peso o efficienza (statico)	l'oggetto entra nella capacità residua
BPP	un oggetto e un contenitore	oggetto: ordine di input o peso (statico); contenitore: il primo, il più pieno, il più vuoto (dinamico)	l'oggetto entra nel contenitore
\(P\,||\,C_{\max}\)	un lavoro e una macchina	lavoro: ordine di input o tempo di esecuzione (statico); macchina: la meno carica (dinamico)	sempre ammissibile
TSP	una città e la sua posizione	la più vicina, la più lontana, la più economica (dinamico)	sempre ammissibile

---

Avanti: 30.4 Il problema dello zaino 0/1: quale ordinamento?