Esercizio - masterizzazione compatta di tracce su CD, scelta greedy e ottimalità (esercitazione greedy, es. 10.1)

Passo 1: la scelta greedy

La maniera più naturale di procedere è riempire il primo CD con più canzoni possibile: si mettono su $CD_1$ le canzoni del più lungo prefisso $C_{1..g}$ con $\sum_{j=1}^{g} d_j \le d_{max}$ (cioè $n_1 = g$), e poi si continua con il resto.

• Clean-up: nessuno. Non ci sono canzoni incompatibili da eliminare, perché le canzoni non masterizzate sono tutte ancora da sistemare. La sottoistanza residua è il suffisso $C_{g+1..n}$ delle canzoni rimaste, con lo stesso $d_{max}$.
• Se $g = n$ tutte le canzoni stanno sul primo CD ($k=1$) e la residua è la stringa vuota $\varepsilon$. Si estende lo spazio delle istanze con l'istanza vuota, associata a una sequenza vuota di CD (zero CD).

Rispetto a un'istanza a $n$ canzoni la residua ha almeno una canzone in meno ($g \ge 1$ perché $d_1 \le d_{max}$): le taglie decrescono e la ricorsione termina (Paradigma greedy - scelta golosa, sottostruttura e selezione delle attivitàIl paradigma greedy compie subito una scelta localmente migliore (scelta greedy), pulisce l'istanza (clean-up) e risolve l'unica sottoistanza residua, con ricorsione di coda eliminabile; il codice è facile, la correttezza no e richiede due proprietà, la scelta greedy (esiste un ottimo che la contiene) e la sottostruttura ottima (cut-and-paste), da cui la correttezza segue per induzione. Caso di studio: la selezione delle attività, con l'algoritmo del primo che finisce, correttezza completa, complessità Theta(n) dopo l'ordinamento e controesempi per le scelte greedy sbagliate.Paradigma greedy - scelta golosa, sottostruttura e selezione delle attività →).

Passo 2: l'algoritmo

La ricorsione è di coda, quindi si scrive iterativo: si accumula in sumd la durata del CD corrente e, quando la canzone successiva non ci sta, si chiude il CD e se ne apre uno nuovo che comincia con quella canzone. Il vettore $N$ contiene le fini $n_0, n_1, \dots$.

MIN_NUM_CD(d, dmax)              {vincolo statico: d[i] <= dmax per ogni i}
    n <- d.len
    k <- 0;  N[0] <- 0
    sumd <- d[1]                 // il primo CD comincia con la canzone c_1
    for i <- 2 to n do
        if sumd + d[i] > dmax then
            // individuata la scelta greedy: il CD corrente e' pieno
            k <- k + 1
            N[k] <- i - 1        // il CD k finisce con la canzone i-1
            sumd <- d[i]         // il prossimo CD comincia con la canzone i
        else
            sumd <- sumd + d[i]
    N[k+1] <- n                  // l'ultimo CD termina sempre con l'ultima canzone
    return N                     // i CD sono k + 1

Ammissibilità. All'inizio di ogni iterazione sumd è la durata delle canzoni $c_{N[k]+1}, \dots, c_{i-1}$, cioè del CD in costruzione, ed è $\le d_{max}$: all'inizio vale $d_1 \le d_{max}$; il ramo else somma $d_i$ solo se il totale resta $\le d_{max}$; il ramo then riparte da $d_i \le d_{max}$. Quando si fissa un valore $N[k]$, la sumd contiene la durata di $CD_k$, che quindi rispetta il limite.

Complessità. Il ciclo fa $n-1$ iterazioni, ciascuna con un confronto e una addizione (nel ramo then nessuna): $n-1$ confronti e al più $n-1$ addizioni, quindi $\Theta(n)$, con spazio ausiliario $O(1)$ oltre al vettore di uscita.

Esempio eseguito a mano

$d = (4, 3, 5, 2, 6, 1, 4, 7)$ minuti, $d_{max} = 10$, $n = 8$.

Alla fine $N[5] = 8$: $N = (0, 2, 4, 6, 7, 8)$, quindi $5$ CD: $\{4,3\}$, $\{5,2\}$, $\{6,1\}$, $\{4\}$, $\{7\}$ (durate $7, 7, 7, 4, 7$). Con la programmazione dinamica esatta e con la forza bruta su tutte le frammentazioni il minimo è $5$ (verificato con Python anche su 3000 istanze casuali).

Passo 3: proprietà di scelta greedy

Enunciato. Esiste una soluzione ottima che contiene la scelta greedy, cioè in cui $CD_1$ contiene le canzoni $c_1, \dots, c_g$ del più lungo prefisso con durata $\le d_{max}$ (in altre parole $n_1 = g$).

Dimostrazione (cut-and-paste). Sia $S^\ast$ una soluzione ottima, con successione $0 = n_0^\ast < n_1^\ast < \dots < n_k^\ast = n$.

• Se $n_1^\ast = g$, $S^\ast$ contiene già la scelta greedy.
• Altrimenti $n_1^\ast = s \ne g$. Poiché $g$ è il massimo numero di canzoni che stanno su un CD partendo dalla prima, deve essere $s < g$ (un CD non può contenere un prefisso più lungo di $g$).

Si costruisce $\hat S$ spostando le canzoni $c_{s+1}, c_{s+2}, \dots, c_g$ dal $CD_2$ al $CD_1$. Controlli:

1. Ammissibilità di $CD_1$: contiene ora $c_1, \dots, c_g$, di durata totale $\le d_{max}$ per la definizione di $g$.
2. $CD_2$ non si svuota. Deve essere $n_2^\ast > g$: se fosse $n_2^\ast \le g$, tutte le canzoni del $CD_2$ sarebbero tra $c_{s+1}$ e $c_g$ e lo spostamento lo svuoterebbe, ottenendo una soluzione con un CD in meno di $S^\ast$, contro l'ottimalità. (Per lo stesso motivo deve essere $k \ge 2$: se fosse $k = 1$ sarebbe $s = n \ge g$.)
3. Ammissibilità di $CD_2$: contiene $c_{g+1}, \dots, c_{n_2^\ast}$, un sottoinsieme di quelle che conteneva prima, quindi la durata non supera $d_{max}$.
4. Ordine: la concatenazione dei CD presenta ancora le canzoni nell'ordine originale.

La nuova successione è $0 = \hat n_0 < \hat n_1 = g < \hat n_2 < \dots < \hat n_k = n$ con $\hat n_i = n_i^\ast$ per $i > 1$, ha lo stesso numero $k$ di CD di $S^\ast$: è ottima e contiene la scelta greedy. $\square$

Passo 4: proprietà di sottostruttura ottima

Enunciato. Sia $\hat S$ una soluzione ottima che contiene la scelta greedy. Allora $CD_2, \dots, CD_k$ formano una soluzione ottima per la residua $C_{g+1..n}$.

Dimostrazione. Non c'è clean-up, quindi la sottostruttura è semplice. La disposizione delle canzoni su $CD_2, \dots, CD_k$ è una soluzione ammissibile per $C_{g+1..n}$, con la successione $g = \hat n_1 < \hat n_2 < \dots < \hat n_k = n$, e usa $k - 1$ CD. Se non fosse ottima, esisterebbe una soluzione della residua con meno di $k-1$ CD; componendola con la scelta greedy (le canzoni $c_1, \dots, c_g$ su $CD_1$, poi quella soluzione) si avrebbe una soluzione dell'istanza originale con meno di $k$ CD, contraddicendo l'ottimalità di $\hat S$. $\square$

In formula: $\mathrm{opt}(C_{1..n}) = 1 + \mathrm{opt}(C_{g+1..n})$.

Passo 5: correttezza dell'algoritmo

Per induzione sul numero di canzoni $n$, con le due proprietà (Paradigma greedy - scelta golosa, sottostruttura e selezione delle attivitàIl paradigma greedy compie subito una scelta localmente migliore (scelta greedy), pulisce l'istanza (clean-up) e risolve l'unica sottoistanza residua, con ricorsione di coda eliminabile; il codice è facile, la correttezza no e richiede due proprietà, la scelta greedy (esiste un ottimo che la contiene) e la sottostruttura ottima (cut-and-paste), da cui la correttezza segue per induzione. Caso di studio: la selezione delle attività, con l'algoritmo del primo che finisce, correttezza completa, complessità Theta(n) dopo l'ordinamento e controesempi per le scelte greedy sbagliate.Paradigma greedy - scelta golosa, sottostruttura e selezione delle attività →). Base: $n = 0$ (istanza vuota), zero CD. Passo: MIN_NUM_CD mette su $CD_1$ le canzoni $c_1, \dots, c_g$ (il ciclo si ferma esattamente quando la canzone successiva non ci sta) e poi procede, con le stesse istruzioni, sulla residua $C_{g+1..n}$, per ipotesi induttiva in modo ottimo. Il numero di CD è $1 + \mathrm{opt}(C_{g+1..n}) = \mathrm{opt}(C_{1..n})$ per la sottostruttura.

Perché qui il greedy basta. L'ordine delle canzoni è fisso: la soluzione è una frammentazione della stringa, e riempire il primo CD non può mai far perdere, perché ogni altra frammentazione chiude il primo CD prima o allo stesso punto. Se invece le canzoni si potessero riordinare, il problema sarebbe il bin packing, che è NP-difficile (osservazione fuori programma): nessun algoritmo efficiente esatto è noto.