30.4 Il problema dello zaino 0/1: quale ordinamento?¶
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
- Per il KP gli elementi sono gli oggetti, e il test di ammissibilità è il vincolo di capacità: un oggetto si seleziona se il suo peso non supera la capacità residua \(rc\). Poiché il test è fissato, un'euristica greedy per il KP è completamente determinata dall'ordine in cui si esaminano gli oggetti. Tre ordinamenti sono naturali:
| per profitto (\(GR_{p}\)): | \(p_j\) non crescente | prima gli oggetti di maggior valore |
|---|---|---|
| per peso (\(GR_{w}\)): | \(w_j\) non decrescente | quanti più oggetti possibile |
| per efficienza (\(GR\)): | \(\dfrac{p_j}{w_j}\) non crescente | miglior valore per unità di peso |
I pareggi si risolvono a favore dell'oggetto con l'indice minimo.
- Il greedy per efficienza si indica con \(GR\); qui lo confrontiamo con gli altri due ordinamenti.
L'algoritmo greedy con ordinamento \(\rho\) è un'euristica costruttiva per il KP. Esamina gli oggetti nell'ordine \(\rho=(\rho_1,\dots,\rho_n)\), una permutazione di \(\mathscr{I}\), partendo dallo zaino vuoto, e seleziona ogni oggetto se e solo se entra nella capacità residua.
Algoritmo: Greedy con ordinamento
- Le tre euristiche differiscono solo per l'ordinamento \(\rho\), calcolato una sola volta ordinando gli oggetti in tempo \(O(n\log n)\). Ogni criterio coglie un aspetto di una buona soluzione e ignora l'altro: il profitto ignora quanta capacità consuma un oggetto, il peso ignora quanto vale un oggetto, e l'efficienza bilancia i due, ma ignora quanto bene gli oggetti riempiono lo zaino.
Esempio 30.1: Tre ordinamenti sull'istanza di riferimento del KP
Sull'istanza di riferimento del KP (\(c=9\)) i tre ordinamenti sono
| criterio | valori | ordinamento \(\rho\) |
|---|---|---|
| profitto | \(p=(10,7,6,4)\) | \((1,2,3,4)\) |
| peso | \(w=(5,4,3,3)\) | \((3,4,2,1)\) |
| efficienza | \(\frac{p}{w}=\left(\frac{10}{5},\frac{7}{4},\frac{6}{3},\frac{4}{3}\right)=(2,\,1.75,\,2,\,1.33)\) | \((1,3,2,4)\) |
(gli oggetti \(3\) e \(4\) hanno lo stesso peso, gli oggetti \(1\) e \(3\) la stessa efficienza, e i pareggi si risolvono con l'indice). Le esecuzioni, con la capacità residua dopo ogni passo, sono:
| passo 1 | passo 2 | passo 3 | passo 4 | |
|---|---|---|---|---|
| \(GR_p\) | oggetto \(1\): dentro, \(rc=4\) | oggetto \(2\): dentro, \(rc=0\) | oggetto \(3\): fuori | oggetto \(4\): fuori |
| \(GR_w\) | oggetto \(3\): dentro, \(rc=6\) | oggetto \(4\): dentro, \(rc=3\) | oggetto \(2\): fuori | oggetto \(1\): fuori |
| \(GR\) | oggetto \(1\): dentro, \(rc=4\) | oggetto \(3\): dentro, \(rc=1\) | oggetto \(2\): fuori | oggetto \(4\): fuori |
Quindi
Il greedy per profitto trova la soluzione ottima \(\{1,2\}\), che riempie esattamente lo zaino; il greedy per efficienza, dopo gli oggetti \(1\) e \(3\), resta con \(rc=1\), troppo poco per qualunque altro oggetto; il greedy per peso prende i due oggetti leggeri, che sono anche quelli di minor valore.
-
Su questa istanza vince il criterio “ingenuo”. Non è una regola generale: nessun ordinamento è il migliore su ogni istanza, e ciascuno dei tre ordinamenti può essere arbitrariamente cattivo. Sia \(c\ge 3\):
-
profitto: un oggetto con \(p_1=2\), \(w_1=c\) e \(c\) oggetti con \(p_j=1\), \(w_j=1\). \(GR_p\) prende l'oggetto \(1\), che riempie lo zaino: \(GR_p(I)=2\), mentre i \(c\) oggetti leggeri insieme danno \(z(I)=c\);
-
peso: due oggetti con \(p_1=1\), \(w_1=1\) e \(p_2=c\), \(w_2=c\). \(GR_w\) prende l'oggetto \(1\) e l'oggetto \(2\) non entra più: \(GR_w(I)=1\), mentre \(z(I)=c\);
-
efficienza: due oggetti con \(p_1=2\), \(w_1=1\) e \(p_2=c\), \(w_2=c\): qui \(GR(I)=2\) e \(z(I)=c\).
In tutti e tre i casi il rapporto \(\frac{z(I)}{\mathscr{A}(I)}\) cresce con \(c\).
-
-
Un rimedio è combinare due soluzioni: l'algoritmo Ext-Greedy \(GR^e\) restituisce la migliore fra la soluzione di \(GR\) e il miglior oggetto singolo, e questa semplice combinazione garantisce \(\frac{z(I)}{GR^e(I)}\le 2\). Eseguire più euristiche greedy e tenere la soluzione migliore è un modo generale ed economico per proteggersi dalla debolezza di ogni singolo criterio.
Avanti: 30.5 Il problema del bin packing: prima ordinare, poi riempire