Paradigma greedy - scelta golosa, sottostruttura e selezione delle attività

In questa pagina 4

Terzo paradigma del corso dopo il divide and conquer (Divide and conquer - proprietà di sottostruttura e albero delle chiamate) e la programmazione dinamica (Programmazione dinamica - Fibonacci, memoizzazione e schema del paradigma). Vale per i problemi di ottimizzazione (Problemi computazionali - istanze, soluzioni, correttezza e complessità): tra le soluzioni ammissibili di un'istanza se ne cerca una di costo minimo o massimo.

Dalla programmazione dinamica al greedy

In un algoritmo di DP la soluzione ottima si ottiene componendo una sequenza di scelte, e le informazioni salvate per ricostruirla (l'indice $k^\star$ in $s[1,n]$ per la catena di matrici, la freccia scelta nella tabella della LCS) sono proprio le scelte. Ma ogni scelta è meditata: si può fare solo dopo aver risolto molte sottoistanze (tutti i $k$ possibili, tutte e tre le sottoistanze della LCS). È la cautela che rende la DP applicabile a tanti problemi, ma ha un costo (una tabella di sottoistanze e un lavoro per cella).

Per alcuni problemi si può rovesciare l'approccio:

Scelta greedy (golosa, "incauta"): si fa subito la prima scelta, quella che localmente sembra la migliore, senza risolvere nessuna sottoistanza.
Clean-up: si ripulisce l'istanza, togliendo gli elementi incompatibili con la scelta fatta. Quello che resta è un'unica sottoistanza, la sottoistanza residua, che si risolve con lo stesso procedimento.

È il modo "umano" di risolvere un problema: si costruisce la soluzione a passi, scegliendo ogni volta ciò che conviene sul momento.

Conseguenze.

Ogni istanza ha una sola sottoistanza, quindi lo spazio delle sottoistanze ha taglia al più lineare e non esistono sottoistanze ripetute: la memoizzazione è inutile.
L'unica chiamata ricorsiva è l'ultima istruzione dopo il clean-up: è una ricorsione di coda, che si elimina con un ciclo in cui si alternano scelta greedy e clean-up (Algoritmi ricorsivi). Gli algoritmi risultanti sono iterativi, semplici e veloci, spesso lineari o quasi lineari, basati su una scansione dell'istanza.
Lo svantaggio è che non sempre funziona: costruire la soluzione per scelte locali non converge, in generale, all'ottimo. La classe dei problemi risolubili così è piccola, ma contiene casi importanti: l'albero di copertura minimo (Minimum spanning tree), i cammini minimi (Cammini minimi e algoritmo di Dijkstra) e la compressione ottima (Codifica di Huffman - codici prefissi, algoritmo e ottimalità).

Il codice viene prima dell'analisi. In D&C e DP si studia la sottostruttura e poi si scrive l'algoritmo; qui il codice discende direttamente dalla definizione di scelta greedy e di clean-up, ed è facile. Il lavoro difficile è dimostrare che è corretto, e ci sono scelte greedy altrettanto naturali che producono soluzioni sbagliate.

Le due proprietà da dimostrare

Proprietà di scelta greedy. Esiste sempre una soluzione ottima che contiene la scelta greedy. Garantisce che la scelta incauta non compromette l'ottimalità.

Proprietà di sottostruttura ottima. Esiste una soluzione ottima che, oltre alla scelta greedy, contiene una soluzione ottima della sottoistanza residua.

Le tecniche tipiche:

Scelta greedy: si parte da una soluzione ottima qualunque $\hat A$ ; se non contiene la scelta greedy la si modifica (scambio, o cut-and-paste: si toglie un pezzo e se ne incolla un altro) in $A^\star$ che la contiene, senza peggiorare il costo. Allora $A^\star$ è ancora ottima.
Sottostruttura: per assurdo. Se la parte di $A^\star$ che resta dopo la scelta greedy non fosse ottima per la residua, si sostituirebbe con una ottima (cut-and-paste) ottenendo una soluzione migliore di $A^\star$ per l'istanza di partenza: contraddizione.

Teorema (schema di correttezza). Se un algoritmo greedy compie ogni volta la scelta greedy, fa il clean-up e risolve ricorsivamente la residua, e valgono le due proprietà, allora ritorna una soluzione ottima.

Dimostrazione. Per induzione sulla taglia dell'istanza. Base: istanza vuota, la soluzione vuota è ottima. Passo: si assume l'algoritmo corretto sulle istanze più piccole, in particolare sulla residua, che è strettamente più piccola. Per le due proprietà esiste un ottimo $A^\star$ composto dalla scelta greedy e da una soluzione ottima della residua. L'algoritmo ritorna la scelta greedy più la soluzione che l'ipotesi induttiva garantisce ottima per la residua: ha lo stesso costo di $A^\star$ , quindi è ottima. $\square$

Il ragionamento induttivo è sempre lo stesso: di problema in problema cambiano solo le due proprietà. Per questo negli esercizi (Esercitazione greedy - tracce su CD, scheduling shortest-first e (2,1)-boxing) ci si limita a provare quelle.

Il controesempio. Per mostrare che una strategia greedy è sbagliata basta un'istanza in cui la scelta greedy esclude ogni ottimo: è molto più facile che dimostrare la correttezza.

Il problema della selezione delle attività

Una risorsa condivisa (un'aula) e un insieme di attività $S = \{a_1, \dots, a_n\}$ che la vogliono usare. L'attività $a_j$ occupa l'intervallo $[s_j, f_j)$ con $s_j < f_j$ (inizio incluso, fine esclusa).

Definizione. Due attività $a_i$ e $a_j$ sono compatibili se gli intervalli sono disgiunti, $[s_i, f_i) \cap [s_j, f_j) = \emptyset$ , cioè se $s_j \ge f_i \quad\text{oppure}\quad s_i \ge f_j .$ Un sottoinsieme è mutuamente compatibile se lo sono tutte le coppie. Il problema (activity selection) chiede un sottoinsieme mutuamente compatibile di cardinalità massima.

Poiché gli intervalli sono aperti a destra, un'attività che finisce e una che inizia nello stesso istante sono compatibili.

Esempio. $s = (2,1,2,3,5,7)$ , $f = (3,5,6,6,7,8)$ , cioè $a_1 = [2,3)$ , $a_2 = [1,5)$ , $a_3 = [2,6)$ , $a_4 = [3,6)$ , $a_5 = [5,7)$ , $a_6 = [7,8)$ . In rosso le attività scelte dall'algoritmo che segue (si trovano più sotto).

Grafico interattivo: Le sei attività: in rosso quelle scelte dal greedy del primo che finisce, a1, a4 e a6

L'algoritmo greedy

Si suppone $a_1, \dots, a_n$ ordinate per fine non decrescente, $f_1 \le f_2 \le \dots \le f_n$ ; se non lo sono si riordinano in $O(n \log n)$ (Algoritmi di ordinamento). L'ordine è cruciale per la correttezza.

Scelta greedy: la prima attività dell'ordine, $a_1$ , cioè quella che finisce per prima. Intuizione: lascia libera la risorsa per l'intervallo contiguo più lungo possibile.
Clean-up: si eliminano le attività che seguono nell'ordine e sono incompatibili con $a_1$ , cioè quelle con $s_j < f_1$ , fino alla prima compatibile $a_g$ , con $g = \min\{j : s_j \ge f_1\}$ . La residua è il suffisso $a_g, \dots, a_n$ (vuoto se nessuna è compatibile). Le istanze residue sono sempre suffissi, individuati da un indice $i$ : l'istanza principale è $i = 1$ e quella vuota è $i = n+1$ .

Il codice segue subito:

REC_GREEDY_SEL(s, f, i)                  {attivita' ordinate per fine}
    n <- s.len
    if i > n then return {}
    G <- {i}
    j <- i + 1
    while j <= n and s[j] < f[i] do      // clean-up: scarta le incompatibili
        j <- j + 1
    return G U REC_GREEDY_SEL(s, f, j)

Nella condizione del while si controlla prima j <= n: con l'ordine opposto si leggerebbe s[n+1] fuori dal vettore. Si chiama con $i = 1$ . La ricorsione è di coda, quindi si elimina. Ora basta ricordare l'ultima attività scelta, $g$ , e confrontare ogni attività con lei:

IT_GREEDY_SEL(s, f)
    n <- s.len
    A <- {1}
    g <- 1                               // ultima scelta greedy
    for i <- 2 to n do
        if s[i] >= f[g] then             // compatibile con l'ultima scelta
            A <- A U {i}
            g <- i
    return A

python

def it_greedy_sel(s, f):          # indici da 1 come nel testo; s, f gia' ordinati per fine
    A, g = [1], 1
    for i in range(2, len(s) + 1):
        if s[i - 1] >= f[g - 1]:
            A.append(i); g = i
    return A

Complessità. La scansione fa esattamente $n-1$ confronti ( $s_i \ge f_g$ , uno per ciascun $i = 2, \dots, n$ ) e al più $n-1$ inserimenti: $\Theta(n)$ . L'ordinamento per fine costa $O(n \log n)$ e domina se i dati non sono già ordinati.

Esempio eseguito a mano

Stessa istanza di prima, con $s = (2,1,2,3,5,7)$ e $f = (3,5,6,6,7,8)$ .

$i$	$a_i$	confronto $s_i \ge f_g$	esito	$A$	$g$
1	$[2,3)$	scelta iniziale	scelta	$\{1\}$	1 ( $f_g = 3$ )
2	$[1,5)$	$1 \ge 3$ no	scartata	$\{1\}$	1
3	$[2,6)$	$2 \ge 3$ no	scartata	$\{1\}$	1
4	$[3,6)$	$3 \ge 3$ sì	scelta	$\{1,4\}$	4 ( $f_g = 6$ )
5	$[5,7)$	$5 \ge 6$ no	scartata	$\{1,4\}$	4
6	$[7,8)$	$7 \ge 6$ sì	scelta	$\{1,4,6\}$	6

Il clean-up dopo la scelta di $a_1$ elimina $a_2$ e $a_3$ (che iniziano prima di $f_1 = 3$ ): la prima attività della sottoistanza residua è $a_4$ , perché $s_4 = 3 \ge f_1 = 3$ (la fine di $a_1$ e l'inizio di $a_4$ coincidono e questo è permesso). Il risultato ha 3 attività, e 3 è il massimo (anche $\{a_1, a_5, a_6\}$ è ottima: si verifica con la forza bruta sui sottoinsiemi).

Perché il clean-up può essere limitato. Il clean-up elimina solo le incompatibili che seguono immediatamente $a_1$ , non tutte quelle incompatibili con $a_1$ . Questo non compromette la correttezza: un'attività incompatibile non eliminata lo sarà con qualche scelta greedy successiva (per transitività sull'ordine per fine) e verrà scartata dopo. Esempio con $(3,5), (4,6), (5,7), (4,8), (7,9)$ : dopo la scelta di $a_1 = [3,5)$ il clean-up toglie $a_2$ ( $4 < 5$ ) e si ferma ad $a_3 = [5,7)$ ; la residua $\{a_3, a_4, a_5\}$ contiene ancora $a_4 = [4,8)$ , incompatibile con $a_1$ . Ma $a_3$ viene scelta e scarta $a_4$ ( $4 < 7$ ), e l'algoritmo termina con $\{a_1, a_3, a_5\}$ , ottima. L'effetto è un algoritmo con una sola scansione lineare.

Correttezza

Notazione: $S_i = \{a_i, \dots, a_n\}$ (suffisso), $g(i) = \min\{j > i : s_j \ge f_i\}$ (con $S_{g(i)} = \emptyset$ se non esiste), $\mathrm{opt}(i)$ la cardinalità massima di un sottoinsieme mutuamente compatibile di $S_i$ , con $\mathrm{opt}(n+1) = 0$ .

Proprietà di scelta greedy. In $S_i$ esiste una soluzione ottima che contiene $a_i$ .

Dimostrazione (scambio). Sia $\hat A$ una soluzione ottima di $S_i$ . Se $a_i \in \hat A$ basta porre $A^\star = \hat A$ . Altrimenti sia $a_h$ l'attività di $\hat A$ di indice minimo; poiché $a_i \notin \hat A$ è $h > i$ . Si pone $A^\star = (\hat A \setminus \{a_h\}) \cup \{a_i\}, \qquad |A^\star| = |\hat A| .$ Resta da mostrare che $A^\star$ è ammissibile, cioè che $a_i$ è compatibile con ogni $a_j \in \hat A \setminus \{a_h\}$ . Poiché $a_j$ e $a_h$ stanno insieme in $\hat A$ sono compatibili: $s_j \ge f_h$ oppure $s_h \ge f_j$ . La seconda è impossibile: darebbe $f_j \le s_h < f_h \le f_j$ (l'ultima disuguaglianza perché $j > h$ e l'ordine è per fine). Dunque $s_j \ge f_h$ , e per l'ordine $f_i \le f_h \le s_j ,$ cioè $a_j$ inizia dopo la fine di $a_i$ : compatibile. $\square$

Proprietà di sottostruttura ottima. Vale $\mathrm{opt}(i) = 1 + \mathrm{opt}(g(i))$ .

Dimostrazione. ( $\le$ ) Per la scelta greedy esiste un ottimo $A$ di $S_i$ con $a_i \in A$ . Ogni $a_j \in A \setminus \{a_i\}$ è compatibile con $a_i$ e ha $f_j \ge f_i$ , quindi $s_j \ge f_i$ (come sopra: l'altra alternativa $s_i \ge f_j$ darebbe $f_j \le s_i < f_i$ ). Un'attività con $s_j \ge f_i$ ha $j > i$ e perciò $j \ge g(i)$ per definizione di minimo: $A \setminus \{a_i\} \subseteq S_{g(i)}$ , ed è compatibile, quindi $|A| - 1 \le \mathrm{opt}(g(i))$ .

( $\ge$ ) Sia $B$ un ottimo di $S_{g}$ , con $g = g(i)$ (se è vuota non c'è nulla da dimostrare). Non ogni soluzione di $S_g$ va bene: può contenere attività incompatibili con $a_i$ (come $a_4$ nell'esempio sopra). Si sceglie allora, per la scelta greedy applicata a $S_g$ , un ottimo $B$ che contiene $a_g$ . Ogni altro $a_j \in B$ è compatibile con $a_g$ e ha $j > g$ , quindi $s_j \ge f_g > s_g \ge f_i$ ; anche $a_g$ ha $s_g \ge f_i$ per definizione di $g$ . Allora $\{a_i\} \cup B$ è ammissibile e $\mathrm{opt}(i) \ge 1 + |B| = 1 + \mathrm{opt}(g)$ . $\square$

Teorema. $\mathrm{REC\_GREEDY\_SEL}(s, f, i)$ ritorna una soluzione ammissibile di $S_i$ di cardinalità $\mathrm{opt}(i)$ .

Dimostrazione. Induzione su $n - i + 1$ , la taglia di $S_i$ . Base: $i > n$ , ritorna $\emptyset$ , con $\mathrm{opt} = 0$ . Passo: l'algoritmo ritorna $\{a_i\} \cup R$ con $R = \mathrm{REC\_GREEDY\_SEL}(s, f, g(i))$ (il ciclo del clean-up calcola esattamente $g(i)$ ). Per ipotesi induttiva $R$ è ammissibile in $S_{g(i)}$ e ha $\mathrm{opt}(g(i))$ elementi; poiché $a_g$ è il suo primo elemento e le altre iniziano dopo $f_g$ (come costruito), tutte iniziano dopo $f_i$ e $\{a_i\} \cup R$ è ammissibile. La sua cardinalità è $1 + \mathrm{opt}(g(i)) = \mathrm{opt}(i)$ per la sottostruttura. $\square$

Con $i = 1$ si ottiene l'ottimo dell'istanza principale. L'algoritmo iterativo calcola gli stessi indici (confronta ogni attività con l'ultima scelta, e per transitività con tutte le precedenti, perché le fini sono crescenti).

Scelte greedy che non funzionano

Altre scelte sembrano ragionevoli ma sono sbagliate; per ciascuna basta un controesempio (verificati con la forza bruta).

Strategia	Istanza	Cosa succede
minima durata	$[0,5), [4,6), [5,10)$	sceglie $[4,6)$ (durata 2) che è incompatibile con entrambe le altre: 1 attività, mentre $\{[0,5),[5,10)\}$ ne ha 2
inizio più presto	$[0,10), [1,2), [3,4)$	sceglie $[0,10)$ e blocca tutto: 1 contro 2
minimo numero di incompatibilità	11 attività: $A\,[0,4)$ , $B\,[5,9)$ , $C\,[10,14)$ , $D\,[15,19)$ , $S\,[8,11)$ , $L_1\,[2,6)$ , $L_2\,[3,7)$ , $L_3\,[3,6)$ , $R_1\,[12,16)$ , $R_2\,[13,17)$ , $R_3\,[12,17)$	$S$ ha 2 incompatibilità (con $B$ e $C$ ), tutte le altre almeno 3: la scelta cade su $S$ e si ottengono 3 attività al massimo; l'ottimo è $\{A, B, C, D\}$ , con 4

La simmetrica funziona: se le attività sono ordinate per inizio non crescente e la scelta greedy è quella che inizia per ultima, con lo stesso tipo di clean-up (si scartano quelle con $f > s$ dell'ultima scelta), la dimostrazione è lo specchio di quella sopra (tempo che scorre al contrario). Anche questa è verificata con la forza bruta.

Attenzione al peso. Se ogni attività ha un peso e si vuole massimizzare la somma dei pesi, il greedy per fine non basta (le istanze $[0,10)$ con peso 100 e $[0,5), [5,10)$ con peso 1 lo mostrano): serve la programmazione dinamica.

Domande d'esame

Nel problema della selezione delle attività con $s = (2,1,2,3,5,7)$ e $f = (3,5,6,6,7,8)$ , qual è l'indice della prima attività della sottoistanza residua dopo la prima scelta greedy e il relativo clean-up? Risposta: scelta greedy $a_1 = [2,3)$ ; $a_2$ ( $1 < 3$ ) e $a_3$ ( $2 < 3$ ) vengono eliminate, $a_4$ ha $s_4 = 3 \ge f_1 = 3$ : l'indice è 4.
Quali due proprietà garantiscono la correttezza di un algoritmo greedy e con quali tecniche si dimostrano? Traccia: scelta greedy (esiste un ottimo che la contiene: partendo da un ottimo si fa lo scambio senza peggiorare il costo) e sottostruttura ottima (l'ottimo contiene un ottimo della residua: per assurdo con il cut-and-paste); la correttezza segue per induzione sulla taglia.
Perché nell'algoritmo delle attività l'ordinamento per fine è cruciale? Dare un controesempio per la scelta "minima durata". Traccia: lo scambio usa $f_i \le f_h \le s_j$ , che richiede l'ordine per fine; controesempio $[0,5), [4,6), [5,10)$ .

Versione ripasso

Dalla DP al greedy (confronto con Programmazione dinamica - Fibonacci, memoizzazione e schema del paradigma): in DP ogni scelta è meditata (si risolvono prima molte sottoistanze); nel greedy si fa subito la scelta localmente migliore, poi si ripulisce l'istanza (clean-up) e resta una sola sottoistanza residua, risolta allo stesso modo.
Conseguenze: spazio delle sottoistanze lineare, nessuna sottoistanza ripetuta (la memoizzazione non serve); la ricorsione è di coda e diventa un ciclo (Algoritmi ricorsivi); algoritmi semplici e veloci, spesso lineari. Ma non sempre funziona: casi buoni sono Minimum spanning tree, Cammini minimi e algoritmo di Dijkstra, Codifica di Huffman - codici prefissi, algoritmo e ottimalità.
Il codice viene prima della prova. Per la correttezza servono due proprietà: (1) scelta greedy, esiste un ottimo che contiene la scelta greedy (si parte da un ottimo $\hat A$ , lo si modifica per scambio in $A^\star$ senza peggiorare il costo); (2) sottostruttura ottima, esiste un ottimo che oltre alla scelta greedy contiene un ottimo della residua (assurdo + cut-and-paste).
Schema di correttezza: induzione sulla taglia; base istanza vuota; passo: per (1) e (2) esiste un ottimo fatto da scelta greedy più ottimo della residua, e l'algoritmo ritorna scelta greedy più la soluzione della residua, ottima per ipotesi induttiva, quindi di pari costo. Il ragionamento è sempre lo stesso: si provano solo (1) e (2). Per escludere una strategia basta un controesempio.
Selezione delle attività: $a_j = [s_j, f_j)$ , $s_j < f_j$ ; compatibili se $s_j \ge f_i$ o $s_i \ge f_j$ (fine e inizio coincidenti vanno bene). Si cerca un sottoinsieme mutuamente compatibile di cardinalità massima. Si ordina per fine non decrescente ( $O(n \log n)$ , Algoritmi di ordinamento).
Scelta e clean-up: scelta greedy $a_1$ (finisce per prima); clean-up elimina i successivi con $s_j < f_1$ fino a $g = \min\{j : s_j \ge f_1\}$ ; la residua è il suffisso $a_g..a_n$ . Il clean-up è limitato: un'incompatibile non eliminata (es. $a_4 = [4,8)$ in $(3,5),(4,6),(5,7),(4,8),(7,9)$ ) viene scartata da una scelta successiva.
Codice iterativo: A <- {1}; g <- 1; for i <- 2 to n: if s[i] >= f[g] then A <- A U {i}; g <- i. Esattamente $n-1$ confronti, $\Theta(n)$ . In REC_GREEDY_SEL il while controlla prima j <= n.
Esempio: $s = (2,1,2,3,5,7)$ , $f = (3,5,6,6,7,8)$ : $a_2, a_3$ scartate ( $1, 2 < 3$ ), $a_4$ scelta ( $3 \ge 3$ ), $a_5$ scartata ( $5 < 6$ ), $a_6$ scelta ( $7 \ge 6$ ): $\{a_1, a_4, a_6\}$ , ottimo. La residua dopo $a_1$ parte da $a_4$ .
Scelta greedy (prova): $\hat A$ ottima, $a_h$ di indice minimo, $A^\star = \hat A \setminus \{a_h\} \cup \{a_i\}$ . Per ogni altra $a_j \in \hat A$ : l'alternativa $s_h \ge f_j$ darebbe $f_j \le s_h < f_h \le f_j$ , impossibile, quindi $s_j \ge f_h$ e $f_i \le f_h \le s_j$ : $A^\star$ è ammissibile e ha la stessa cardinalità.
Sottostruttura (prova): $\mathrm{opt}(i) = 1 + \mathrm{opt}(g(i))$ . $\le$ : un ottimo $A \ni a_i$ ha $A \setminus \{a_i\} \subseteq S_{g(i)}$ , perché $s_j \ge f_i$ implica $j > i$ e quindi $j \ge g(i)$ . $\ge$ : si prende un ottimo di $S_g$ che contiene $a_g$ (non uno qualunque, potrebbe avere attività incompatibili con $a_i$ ); le altre iniziano dopo $f_g > s_g \ge f_i$ , quindi $\{a_i\} \cup B$ è ammissibile.
Strategie sbagliate (controesempi): minima durata ( $[0,5), [4,6), [5,10)$ : 1 contro 2), inizio più presto ( $[0,10), [1,2), [3,4)$ ), minimo numero di incompatibilità (11 attività: ottimo 4, il greedy ne ottiene 3). La versione simmetrica (ordine per inizio non crescente) è corretta. Con pesi il greedy non basta: serve la DP.
Errori tipici: non ordinare per fine; usare $s_j \le f_i$ (escludendo la compatibilità in un punto); prendere come ottimo della residua una soluzione qualunque senza imporre la scelta greedy della residua; dimenticare la verifica di ammissibilità dello scambio; contare male i confronti ( $n-1$ , non $n$ ).