PD per il problema del taglio delle aste¶
Parte 3 · Programmazione dinamica · Capitolo 28 · Dispensa, volume 3 (PDF) · Slide · Esercizi: Taglio delle aste (RCP)
Prerequisiti
-
Da questo modulo, il capitolo «Principi della programmazione dinamica»: sottostruttura ottima, sottoproblemi sovrapposti, relazioni di ricorrenza, casi base e approcci top-down e bottom-up.
-
Da questo modulo, il capitolo «PD per il problema dello zaino 0/1»: le coppie (oggetto, capacità) e la ricostruzione di una soluzione, che ritornano qui.
-
Dal modulo Algoritmi: come leggere lo pseudocodice (Capitolo 2) e come contare i passi di un algoritmo (Capitolo 12 «Tempo di esecuzione»).
Obiettivi
Alla fine di questo capitolo saremo in grado di:
-
enunciare l'RCP, codificare una soluzione come vettore di numeri di pezzi e spiegare perché schemi di taglio e vettori sono oggetti diversi;
-
scrivere la ricorrenza \(v(\ell)\) e spiegarla, caso base compreso;
-
eseguire a mano l'algoritmo di PD con l'approccio top-down e con quello bottom-up, e con il miglior valore corrente \(m\);
-
ricostruire una soluzione ottima dal vettore \({s}\), per l'asta e per ogni asta più corta;
-
scrivere la seconda ricorrenza \(v(j,\ell)\) sulle coppie (lunghezza massima dei pezzi, lunghezza dell'asta) e contare i passi dell'algoritmo di PD.
Il problema di questo capitolo è il problema del taglio delle aste (RCP): la sua definizione è nella sua pagina.
28.1 Istanze e soluzioni ammissibili¶
Esempio 28.1: Problema del taglio delle aste
Consideriamo un'asta di lunghezza \(n = 4\) e un insieme \(\{1,2,3,4\}\) di \(4\) possibili lunghezze dei pezzi con i seguenti profitti:
Chiamiamo questa istanza dell'RCP Esempio 28.1.
Il numero di possibili soluzioni dell'RCP è \(2^{n-1}\), perché possiamo tagliare un'asta di lunghezza \(n\) in \(2^{n-1}\) modi diversi, con una scelta indipendente di tagliare (o no) in ogni possibile posizione di taglio.
-
Il numero di possibili soluzioni dell'RCP cresce esponenzialmente con la lunghezza \(n\) dell'asta:
\[ 2^{n-1} = O(2^n). \]Quindi enumerare tutte le possibili soluzioni diventa presto impraticabile al crescere di \(n\).
28.1.1 Codifica delle soluzioni ammissibili¶
Una soluzione ammissibile dell'RCP è un modo di tagliare l'asta in pezzi, tale che la lunghezza totale dei pezzi sia uguale alla lunghezza dell'asta.
-
Una soluzione ammissibile dell'RCP si può descrivere con un vettore soluzione intero
\[ (x_1,x_2,\dots,x_n) \]dove ogni componente ha il seguente significato:
\[ x_\ell = \text{numero di pezzi di lunghezza } \ell, \qquad \forall \ell \in \{1,2,\dots,n\}; \]Il numero di pezzi è
\[ \sum_{\ell=1}^{n} x_\ell. \]Poiché la soluzione è ammissibile, la lunghezza totale dei pezzi deve essere uguale alla lunghezza dell'asta:
\[ \sum_{\ell=1}^{n} \ell \, x_\ell = n. \]Il profitto totale di una soluzione ammissibile è
\[ \sum_{\ell=1}^{n} p_\ell x_\ell. \] -
Due o più schemi di taglio possono avere la stessa rappresentazione vettoriale: il vettore registra quanti pezzi di ogni lunghezza si ottengono, ma non specifica l'ordine in cui i pezzi vengono tagliati.
-
Schemi di taglio con la stessa rappresentazione vettoriale hanno lo stesso profitto totale, perché l'ordine in cui i pezzi vengono tagliati non cambia i pezzi ottenuti e quindi non cambia il profitto totale.
Esempio 28.2: Enumerazione di tutte le possibili soluzioni dell'RCP
Consideriamo l'istanza dell'RCP dell'Esempio 28.1, con un'asta di lunghezza \(n = 4\); i profitti associati alle possibili lunghezze dei pezzi sono:
Ci sono \(2^{4-1} = 8\) soluzioni ammissibili, corrispondenti ai diversi modi di tagliare l'asta.
Nel seguente albero binario ogni livello corrisponde a una possibile posizione di taglio: un arco con etichetta \(1\) indica che l'asta viene tagliata a quella lunghezza, mentre un arco con etichetta \(0\) indica che non viene tagliata a quella lunghezza. Ogni foglia rappresenta uno schema di taglio completo e riporta il vettore corrispondente.
La figura seguente mostra tutti i possibili schemi di taglio associati alle foglie dell'albero precedente, tramite le etichette \((1),(2),\dots,(8)\). Per ogni pezzo ottenuto, il numero scritto dentro il pezzo è la sua lunghezza, mentre il numero sopra è il suo profitto.
| Etichetta | Vettore soluzione | Numero di pezzi | Profitto totale |
|---|---|---|---|
| \((1)\) | \((0,0,0,1)\) | \(1\) | \(9\) |
| \((2)\) | \((1,0,1,0)\) | \(2\) | \(8+1=9\) |
| \((3)\) | \((0,2,0,0)\) | \(2\) | \(5+5=10\) |
| \((4)\) | \((2,1,0,0)\) | \(3\) | \(5+1+1=7\) |
| \((5)\) | \((1,0,1,0)\) | \(2\) | \(1+8=9\) |
| \((6)\) | \((2,1,0,0)\) | \(3\) | \(1+5+1=7\) |
| \((7)\) | \((2,1,0,0)\) | \(3\) | \(1+1+5=7\) |
| \((8)\) | \((4,0,0,0)\) | \(4\) | \(1+1+1+1=4\) |
Avanti: 28.2 Un primo algoritmo di PD
Esercizi su questo capitolo: Taglio delle aste (RCP)