Algoritmi Greedy (parte I) - unimi.itfrasca.di.unimi.it/ALGM14/slide_lez11.pdf•n = 18,5 banconote:...

Algoritmi greedy

• Gli algoritmi che risolvono problemi di ottimizzazione devono in genere operare una sequenza di scelte per arrivare alla soluzione

• Gli algoritmi greedy sono algoritmi basati sull’idea di fare sempre scelte che sembrano ottime al momento della scelta.

• IMPORTANTE: Non sempre è garanta la corret-tezza, ma sono spesso molto semplici ed efficienti.

Problema della selezione di attività

Problema: Siano date N attività in competizione tra loro per l’utilizzo di una certa risorsa. Trovare l’allocazione ottimale della risorsa, cioè il sottoinsieme di cardinalità massima delle attività che la possano condividere senza creare conflitti

• S={1,2,…,N} un insieme di attività• Ad ogni attività i S sono associati

• si = tempo di inizio (attivazione)

• fi = tempo di fine (conclusione)

• tali che si fi


Definizione: Due attività i e j si dicono compatibili se gli intervalli [si , fi] e [sj , fj] sono disgiunti, cioè non si sovrappongono. In altre parole se vale

fj si oppure fi sj

Problema (riformulato): Dato l’insieme di attività S={1,2,…,N}, trovare il massimo sottoinsieme di attività tra loro compatibili.


Problema (riformulato): Dato l’insieme di attività S={1,2,…,N}, trovare il massimo sottoinsieme di attività tra loro compatibili.❶ Partiamo con un insieme A di attività inizialmente vuoto❷ Inseriamo in A l’attività j col minimo tempo di

terminazione❸ Fra le attività rimanenti compatibili con j

selezionare l’attività i col minore tempo di terminazione

aggiungere l’attività selezionata i ad A❹ Se esistono altre attività compatibili con i, torniamo al

passo ❸, altrimenti terminamo

Problema della selezione di attività❶ Assumiamo le attività siano ordinate in modo crescente rispetto

al tempo di fine.

f1 f2 … fN

❷ Siano I=[s1,…, sN] e F=[f1,…, fN] i vettori contenenti i tempi di inizio (non ordinati) e di fine (ordinati)

❸ Greedy-Activity-Selection(S,F)

A = {1}; j = 1

for i = 2 to length[I]

do if I[i] F[j] then A = A ∪ {i}

j = i

❹ Al termine l’inseme A contiene la soluzione greedy al problema. Tempo: (n), (n log n) se dobbiamo prima ordinare le attività

1 1 4

2 3 5

3 0 6

4 5 7

5 3 8

6 5 9

7 6 10

8 8 11

9 8 12

10 12 14

i si fi

2:3-5

1:1-4

4:5-7

3:0-6

5:3-8

7:6-10

6:5-9

9:8-12

8:8-11

10:12-14

4 attività

1 4

1

74

58

118 14

1012

3 attività

0 6

3

14

10

11

9

8 12

Criterio: attività che finisce prima

11

Criterio: attività più lunga

2:3-5

1:1-4

4:5-7

3:0-61 1 4

2 3 5

3 0 6

4 5 7

5 3 8

6 5 9

7 6 10

8 8 11

9 8 12

10 12 14

i si fi

5:3-8

7:6-10

6:5-9

9:8-12

8:8-11

10:12-14

1 2 3 4 5 6 7 8 9 10 11 12 13 14

1

2

3

4

5

6

2:3-5

1:1-4

4:5-7

3:0-61 1 4

2 3 5

3 0 6

4 5 7

5 3 8

6 5 9

7 6 10

8 8 11

9 8 12

10 12 14

i si fi

5:3-8

7:6-10

6:5-9

9:8-12

8:8-11

10:12-14

1 2 3 4 5 6 7 8 9 10 11 12 13 14

1

4

7

9

8

10

2:3-5

1:1-4

4:5-7

3:0-61 1 4

2 3 5

3 0 6

4 5 7

5 3 8

6 5 9

7 6 10

8 8 11

9 8 12

10 12 14

i si fi

5:3-8

7:6-10

6:5-9

9:8-12

8:8-11

10:12-14

1 2 3 4 5 6 7 8 9 10 11 12 13 14

1

4

10

8

Selezione di attività: correttezza

Teorema: L’algoritmo Greedy-Activity-Selection produce soluzioni di dimensione massima per il problema della selezione delle attività.

Dimostrazione: Per assunzione dell’algoritmo, le N attività sono ordinate per tempo di fine, quindi la prima attività è quella che termina per prima.

Dimostriamo innanzitutto che esiste una soluzione ottima che inizia con la prima attività (proprietà della scelta greedy)– Sia A S sia una qualsiasi soluzione ottima. Ordiniamola per

tempi di fine crescenti. Supponiamo che A[1] = S[k] e k1 (cioè la prima attività di A non è quella con tempo di terminazione minore in S)

– Quindi vale f1 < fk.



Dimostrazione: – A S sia una qualsiasi soluzione ottima (ordinata per tempi di

fine) con A[1] = S[k] e k1. Quindi vale f1 < fk.

– Possiamo quindi costruire un’altra soluzione B = A - {k} + {1}; B è una soluzione perchè vale f1 < fk e quindi nessun vincolo di compatibilità è violato. B è anche ottima perchè ha lo stesso numero di attività della soluzione ottima A.

– B è quindi una sol. ottima che inizia con la scelta greedy.



Dimostrazione: Quindi esiste una soluzione ottima che inizia con la prima attività (passo base proprietà della scelta greedy).– Dopo la scelta greedy, il problema si riduce al sottoproblema

di trovare la massima sequenza di attività compatibili con la prima.

– Il sottoproblema è quindi di cercare di una sequenza massima di attività tra S’ = {i ∈ S : si f1} (if nel codice)

– Se A è una soluzione ottima, la soluzione ottima del sottoproblema S’ è allora A’ = A - {1}. Dimostriamolo!



Se A è una soluzione ottima, la soluzione ottima del sottoproblema S’ è A’ = A – {1}. Se A’ non fosse ottima, esisterebbe un B’ maggiore di A’ per

lo stesso sottoproblema S’ = {i ∈ S : si f1}. Ma aggiungendo l’attività 1 a B’, otterremo una soluzione B

per S migliore di A (contraddizione).



Abbiamo provato che esiste una soluzione ottima che inizia con la prima attività e Dopo la prima scelta greedy, rimaniamo col sottoproblema

(analogo) di cercare di una sequenza massima di attività in un insieme S’ = {i ∈ S : si f1}.

Per induzione si può allora dimostrare facilmente che data una qualsiasi soluzione ottima, essa contiene al suo interno le soluzioni ottime dei suoi sottoproblemi (proprietà della sottostruttura ottima).

Quindi la sequenza di scelte greedy determina una soluzione ottima (correttezza dell'algoritmo).

Algoritmi Greedy : problema del cambio di denaro

• Input• Un numero intero positivo n

• Output• Il più piccolo numero intero di banconote per cambiare n

dollari usando pezzi da 20, 10, 5, 1 dollaro.

• Esempi• n = 58, 7 banconote: 20+20+10+5+1+1+1• n = 18, 5 banconote: 10+5+1+1+1

• Algoritmo• Dispensa una banconota alla volta• Ad ogni passo, utilizza la banconota più grande che non

superi la cifra rimanente.

Criterio di scelta greedy

Università degli Studi di Milano

Marco Frasca

Punti per garantire l’ottimalità

● Proprietà della scelta greedy• Una soluzione globalmente ottima può esser ottenuta

effettuando, in sequenza, delle scelte localmente ottime (greedy).

• Proprietà della sottostruttura ottima• Una soluzione ottima al problema contiene le

soluzioni ottime dei sottoproblemi


Marco Frasca

Problema del cambio di denaro

Teorema: Il problema del cambio di denaro precedente soddisfa sia la proprietà della sottostruttura ottima che la proprietà della scelta greedy.

Dimostrazione (cenni): Se b1,…,bk è una soluzione ottima al problema di cambiare n dollari, b2,…,bk è una soluzione ottima per il problema di cambiare n – b1v1 dollari (la banconota b1 vale v1 dollari). Se non lo fosse ….

La seconda parte (scelta greedy) si basa sul fatto che non è possibile che in una soluzione ottima non compaia la scelta greedy.


Marco Frasca

Dimostrazione (cenni): Assumiamo b1,…,bk sia una soluzione ottima, che la banconota h sia la più grande non superiore all’importo n e che h non compaia nella soluzione.

● Analizzando i casi possibili, si nota che se h non supera n, esisterà sempre nella soluzione un insieme di almeno due biglietti di taglia inferiore ad n la cui somma sia proprio h (tutti i tagli sono infatti divisibili per qualsiasi dei tagli minori).

● Quindi sostituendo nella soluzione il biglietto di taglia maggiore si otterrebbe una soluzione migliore di b1,…,bk, il che è una contraddizione.


Marco Frasca

Problema del cambio di denaro

Scrivere una programma MATLAB che legge dal file processi.txt una lista di processi individuati da due valori: tempo di inzio e tempo di fine. Es.

0 51 45 152 7● I processi hanno bisogno della CPU per poter essere eseguiti, e la

CPU può essere assegnata ad un solo processo per volta. Il programma deve restituire la lista dei processi (es. vettore di indici) a cui può essere assegnata la CPU, massimizzando il numero di processi eseguiti.

Esercizio

Programmazione Dinamica (PD, con 'la' non 'il' !!)

Altra tecnica per risolvere problemi di ottimizzazione, più generale degli algoritmi greedy

La programmazione dinamica risolve un problema di ottimizzazione componendo le soluzioni dei sottoproblemi


Marco Frasca

Caratteristiche della programmazione dinamica

• Risolve i problemi in modo bottom-up: si parte da problemi piccoli e se ne compongono le soluzioni per trovare soluzioni di problemi di dimensioni più grandi.

• Si applica nei casi in cui un problema ha la proprietà della sottostruttura ottima.


Marco Frasca

Differenza con i metodi divide et impera

• I metodi divide et impera (esempio: ordinamento con mergesort) procedono top-down: la scomposizione produce problemi che vengono risolti in modo indipendente.

• Nei problemi a cui si applica la PD, la scomposizione produce sottoproblemi che non sono indipendenti: la soluzione di alcuni sottoproblemi richiede di risolvere i medesimi sottoproblemi.


Marco Frasca

PD versus divide et impera (segue)

• I metodi divide et impera si applicano quando la scomposizione in sottoproblemi produce problemi tutti distinti.

• La PD si applica quando la scomposizione in sottoproblemi produce piu’ volte gli stessi sottoproblemi.

• Per evitare di risolvere piu’ volte gli stessi sottoproblemi, si memorizzano le soluzioni dei sottoproblemi in una tabella.


Marco Frasca

PD versus metodi greedy

• Programmazione dinamica e metodi greedy si applicano entrambi a problemi di ottimizzazione in cui vale la proprieta’ della sottostruttura ottima.

• Nei metodi greedy, le scelte ad ogni passo dipendono da un criterio esterno (appetibilità), ogni scelta determina un sottoproblema

• Nella PD le scelte dipendono dalla soluzione dei sottoproblemi


Marco Frasca

PD versus metodi greedy (segue)

• I metodi greedy agiscono in modo top-down: riducono progressivamente un problema a sottoproblemi di dimensioni decrescenti.

• I metodi basati sulla PD procedono bottom-up risolvendo per primi i problemi più piccoli.

• I metodi greedy sono molto piu’ efficienti di quelli basati sulla programmazione dinamica che devono provare tutte le alternative per fare una scelta ottima.

• La PD ha un’applicabilità maggiore rispetto ai metodi greedy.


Marco Frasca

Sviluppo di un algoritmo di programmazione dinamica

1. Caratterizzazione della struttura di una

soluzione ottima

2. Definizione ricorsiva del valore di una

soluzione ottima.

3. Calcolo iterativo del valore di una soluzione

ottima mediante una strategia bottom-up

4. Costruzione di una soluzione ottima a partire

dal valore calcolato


Marco Frasca

Esempio: Problema dello zaino 0/1

● La programmazione dinamica permette di risolvere il problema dello zaino 0/1, che non ammette una soluzione con i metodi greedy

- o1, o

2, ...,o

n oggetti

- w1, w

2, ..., w

n pesi

- v1, v

2, ...,v

n valori

- Capacità zaino W.

Obiettivo: massimizzare il valore trasportato rispettando la capacità.


Marco Frasca

Caratterizzazione della struttura di una soluzione ottima

Definiamo:

M[i, j] = il massimo valore trasportabile

con un peso j e potendo selezionare

gli oggetti 1, …, i


Marco Frasca

Considera una soluzione ottima in cui si hanno a disposizione gli articoli 1,…, i e un carico j

• se i non è incluso nella soluzione ottima

M[i, j] = M[i-1, j]• se i è incluso nella soluzione ottima

M[i, j] = M[i-1, j - wi] + vi, e deve valere j wi


Marco Frasca

Caratterizzazione della struttura di una soluzione ottima

Condizioni limite– M[i, 0] = 0 per ogni i

– M[0, j] = 0 per ogni j

● Posso calcolare in modo iterativo (bottom-up) i valori di M[i, j] a partire da M[0, 0] per valori crescenti di i e j.

● Se ho n articoli e un peso W il valore di una selezione ottima sarà dato alla fine da

M[n, W]


Marco Frasca

Definizione ricorsiva del valore di una soluzione

M[0, j] = 0

M[i, 0] = 0

M[i, j] = M[i-1, j] se j < wi

M[i, j] = max {M[i-1, j], vi + M[i-1, j - wi ]} se j wi


Marco Frasca

Calcolo iterativo del valore di una soluzione ottima

DynamicKnapsack01(W, w, v)for j = 0 to W % inizializzazione M [0,j] 0

for i = 0 to n % inizializzazione M [i,0] 0

for i = 1 to n

for j = 1 to W

if (j wi)

then M[i, j] max {M[i-1, j], vi + M[i - 1, j - wi]}

else M[i, j] M [i-1, j];


Marco Frasca

Costruzione di una soluzione ottima a partire dal valore calcolato

● L'algoritmo ritorna la matrice M contenente i valori delle soluzioni ottime per vari sottoproblemi.● Partendo dalla cella M[n, W], risalire nella colonna M[:, W] per capire come costruire la soluzione.● Esempio: O

1 v1 = 10, w1 = 5

O2 7 3

O3 8 4

O4 5 2

W = 10


Marco Frasca

0 1 2 3 4 5 6 7 8 9 10

O0

0 0 0 0 0 0 0 0 0 0 0

O1

0 0 0 0 0 10 10 10 10 10 10

O2

0 0 0 7 7 10 10 10 17 17 17

O3

0 0 0 7 8 10 10 15 17 18 18

O4

0 0 5 7 8 12 13 15 17 20 22

Complessità dell’algoritmo

La complessità dell’algoritmo di programmazione dinamica per lo zaino 0/1 è

O(nW)

dove n è il numero degli articoli e W è il peso dello zaino.

Notare che W può essere arbitrariamente grande rispetto a n (ad esempio può essere W = 2n)

Algoritmi Greedy (parte I) - unimi.itfrasca.di.unimi.it/ALGM14/slide_lez11.pdf•n = 18,5 banconote:...

Documents

Transcript of Algoritmi Greedy (parte I) - unimi.itfrasca.di.unimi.it/ALGM14/slide_lez11.pdf•n = 18,5 banconote:...