Esercizio - (2,1)-boxing di oggetti, scelta greedy e ottimalità (esercitazione greedy, es. 10.3)

Passo 1: la scelta greedy

Si guarda l'oggetto più pesante, $o_n$, perché è quello più difficile da sistemare. Casi:

1. $n = 1$: $o_n$ è l'unico oggetto, scatola $B_1 = \{o_n\}$.
2. $n > 1$ e $p_1 + p_n > 1$: anche accoppiato con l'oggetto più leggero $o_1$ si supera $1$, quindi con qualsiasi altro oggetto (di peso almeno $p_1$) si supererebbe: $o_n$ sta da solo, $B_1 = \{o_n\}$.
3. $n > 1$ e $p_1 + p_n \le 1$: si fa la scatola $B_1 = \{o_1, o_n\}$, accoppiando il più pesante con il più leggero.

Nel caso 3 la scelta è "azzardata": si accontenta di accoppiare $o_n$ con $o_1$, anche se potrebbe esistere un oggetto più pesante di $o_1$ che ci sta ancora con $o_n$, sprecando parte della portata. La proprietà di scelta greedy proverà che non si perde nulla.

Clean-up: nessuno. Dopo la scelta la sottoistanza residua $O_R$ è formata dagli oggetti ancora da sistemare:

• casi 1 e 2: $O_R = \{o_1, \dots, o_{n-1}\}$ (nel caso 1 è vuoto);
• caso 3: $O_R = \{o_2, \dots, o_{n-1}\}$.

La residua è ancora ordinata per peso e soddisfa le stesse ipotesi, e ha almeno un oggetto in meno (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

Gli indici first e last delimitano la residua: $\{o_{first}, \dots, o_{last}\}$.

BOXING_2_1(O, p)                         {p ordinato non decrescente}
    n <- |O|
    B <- {}
    first <- 1;  last <- n
    while first <= last do
        if first = last or p[first] + p[last] > 1 then      // casi 1 e 2
            B <- B U { {o_last} }
        else                                                  // caso 3
            B <- B U { {o_first, o_last} }
            first <- first + 1
        last <- last - 1
    return B

(last diminuisce sempre, first aumenta solo nel caso 3, quando $o_{first}$ è stato inscatolato.)

Ritorna un (2,1)-boxing. Ogni iterazione inscatola $o_{last}$ e, nel caso 3, anche $o_{first}$, poi li esclude dalla residua; il ciclo termina con $first > last$, cioè dopo aver inscatolato ogni oggetto in una e una sola scatola. Le scatole hanno uno o due oggetti e peso totale $\le 1$: nel caso 3 per la condizione dell'if, altrimenti c'è un solo oggetto con $p \le 1$.

Complessità. last decresce di $1$ a ogni iterazione, quindi le iterazioni sono al più $n$; sono almeno $\lceil n/2 \rceil$ (ogni iterazione sistema al più due oggetti). Ogni iterazione fa una somma e un confronto: $\Theta(n)$ confronti tra pesi (più $O(n \log n)$ se i pesi non sono già ordinati).

Esempio eseguito a mano

Pesi $(0{,}10;\ 0{,}20;\ 0{,}30;\ 0{,}45;\ 0{,}60;\ 0{,}70;\ 0{,}85;\ 0{,}95)$, $n = 8$.

Risultato: $5$ scatole, che è l'ottimo (verificato con una ricerca esaustiva). Con l'esempio del testo ($0{,}2; 0{,}6; 0{,}7$): $n = 3$, $p_1 + p_3 = 0{,}9 \le 1$ dà $\{o_1, o_3\}$; resta $\{o_2\}$ con $first = last$: $\{o_2\}$. Due scatole.

Passo 3: proprietà di scelta greedy

Enunciato. Esiste un (2,1)-boxing ottimo che contiene la scelta greedy.

Dimostrazione. Casi 1 e 2. In ogni (2,1)-boxing $o_n$ sta da solo (non può stare con nessun altro oggetto), quindi ogni boxing, in particolare uno ottimo, contiene $\{o_n\}$.

Caso 3 (scelta greedy $\{o_1, o_n\}$ con $p_1 + p_n \le 1$). Sia $B^\ast$ un (2,1)-boxing ottimo.

• Se $o_1$ e $o_n$ sono nella stessa scatola, questa è proprio $\{o_1, o_n\}$ (al più due oggetti): $B^\ast$ contiene la scelta greedy.
• Altrimenti sono in due scatole distinte $B_1 \ni o_1$ e $B_2 \ni o_n$. Si costruisce $$\hat B = \big(B^\ast \setminus \{B_1, B_2\}\big) \cup \big\{\{o_1, o_n\},\ (B_1 \cup B_2) \setminus \{o_1, o_n\}\big\},$$ sostituendo le due scatole con la scatola greedy e una scatola con gli oggetti rimasti.

Verifiche:

1. Numero di scatole. $|\hat B| \le |B^\ast|$ (la seconda nuova scatola, se fosse vuota, si toglie: ci sarebbe una scatola in meno, assurdo per l'ottimalità; quindi non è vuota e $|\hat B| = |B^\ast|$).
2. La scatola greedy $\{o_1, o_n\}$ è ammissibile per ipotesi ($p_1 + p_n \le 1$).
3. La seconda scatola contiene al più due oggetti, perché $B_1$ porta al più un oggetto oltre a $o_1$ e $B_2$ al più uno oltre a $o_n$. Se ne ha uno solo, rispetta il vincolo di peso. Se ne ha due, siano $o_s \in B_1$ e $o_t \in B_2$. Allora $p_s \le p_n$ ($o_n$ è il più pesante) e $p_t + p_n \le 1$ (vincolo su $B_2$, che contiene $o_t$ e $o_n$), cioè $p_t \le 1 - p_n$. Sommando, $$p_s + p_t \le p_n + (1 - p_n) = 1 .$$
4. Gli altri oggetti restano nelle scatole di prima.

Dunque $\hat B$ è un (2,1)-boxing con la stessa cardinalità di $B^\ast$, quindi ottimo, e contiene la scelta greedy. $\square$

Passo 4: proprietà di sottostruttura ottima

Enunciato. Se $\hat B$ è un (2,1)-boxing ottimo che contiene la scelta greedy, allora le altre scatole $\hat B_R$ formano un (2,1)-boxing ottimo della residua $O_R$.

Dimostrazione. Non c'è clean-up, quindi è semplice. Le scatole di $\hat B$ diverse dalla scatola greedy contengono tutti e soli gli oggetti di $O_R$, nel rispetto dei vincoli: sono un (2,1)-boxing ammissibile $\hat B_R$ di $O_R$. Se non fosse ottimo, aggiungendo la scatola greedy a un (2,1)-boxing ottimo di $O_R$ si otterrebbe un (2,1)-boxing di $O$ con meno scatole di $\hat B$ (cut-and-paste), contro la sua ottimalità. $\square$

In formula $\mathrm{opt}(O) = 1 + \mathrm{opt}(O_R)$, con $\mathrm{opt}(\emptyset) = 0$.

Passo 5: correttezza dell'algoritmo

Per induzione sul numero di oggetti $n$. Base: $n = 0$, nessuna scatola. Passo: l'algoritmo compie la scelta greedy dei casi 1, 2 o 3 e prosegue, con le stesse istruzioni, sulla residua (la parte rimasta tra first e last), che per ipotesi induttiva è risolta in modo ottimo. Per la sottostruttura il numero di scatole è $1 + \mathrm{opt}(O_R) = \mathrm{opt}(O)$.

Verifica numerica: confronto con la ricerca esaustiva del minimo numero di scatole su 3000 istanze casuali ($n \le 10$, pesi interi in $(0, 100]$ con limite $100$) e controllo che ogni uscita sia un (2,1)-boxing con $\lceil n/2 \rceil \le$ iterazioni $\le n$.