Metodo greedy

26 novembre 2014

19-esima lezione

Calendario 19. Mercoledì 26 novembre (oggi): Greedy 2

20. Martedì 2 dicembre 9-11: Greedy 3:Huffman

21. Mercoledì 3 dicembre: Grafi 1

22. Martedì 9 dicembre: Grafi 2

23. Mercoledì 10 dicembre: Grafi 3

24. Martedì 16 dicembre 9-11-12: Reti di flusso

Proposte: Martedì 2 dicembre ore 11-13, aula F8: Esercitazione sulla programmazione din amica Martedì 9 dicembre ore 11-13, aula F8: Esercitazione su greedy e grafi Mercoledì 17 dicembre ore 13-15 aula P3: Terzo test (di 20 minuti) su programmazione din amica, greedy e grafi, e correzione.

Punto della situazione

Tecniche di progettazione di algoritmi:

• divide et impera;

• programmazione dinamica;

• tecnica greedy

Esempi:

1. Selezione di intervalli (versione non pesata) ([KT] par. 4.1) (VISTO la scorsa lezione)

2. Partizionamento di intervalli ([KT] par. 4.1)

3. Scheduling che minimizza il ritardo ([KT] par. 4.2)

4. Codici di Huffman

E altri sui grafi: MST, cammini minimi, …

Tecnica greedy

• Serve per risolvere problemi di ottimizzazione = ricerca di una soluzione ammissibile che ottimizzi (max/min) un valore associato.

• Non sempre è possibile utilizzarla per ottenere una soluzione ottimale (devo usare programmazione dinamica)

• Schema molto semplice

• Prova della correttezza… di meno

Schema algoritmo greedy

• Ordino secondo un criterio di convenienza

• Inizializzo SOL = insieme vuoto

• Considero ogni oggetto in ordine di convenienza

– Se è compatibile con SOL lo aggiungo a SOL

• Restituisco SOL

6

7

Correttezza “Greedy algorithm stays ahead”

Confronto soluzione dell’algoritmo greedy con una ottimale.

Supponiamo Greedy abbia k intervalli, e OPT m≥k. Tesi: k=m.

Poichè Greedy sceglie la prima compatibile: f(i1) f(j1).

Poi anche: f(i2) f(j2), e “così via” (formalmente per induzione) f(ik) f(jk).

Se esistesse jk+1 compatibile con jk, a maggior ragione sarebbe compatibile con ik e l’algoritmo greedy l’avrebbe scelto, anziché terminare,

j1 j2 jk-1

i1 i2 ik-1 ik

jk+1

Greedy:

OPT: jk …

…

4.1 Interval Partitioning

Interval Partitioning

Interval partitioning Lecture j starts at sj and finishes at fj.

Goal: find minimum number of classrooms to schedule all lectures so that no two occur at the same time in the same room.

Ex: This schedule uses 4 classrooms to schedule 10 lectures.

10 Time

9 9:30 10 10:30 11 11:30 12 12:30 1 1:30 2 2:30

h

c

b

a

e

d g

f i

j

3 3:30 4 4:30

adesso abbiamo più risorse e vogliamo accontentare tutti (col minimo delle risorse….). Applicazioni…..

Interval Partitioning Interval partitioning.

Lecture j starts at sj and finishes at fj.

Goal: find minimum number of classrooms to schedule all lectures so that no two occur at the same time in the same room.

Ex: This schedule uses only 3.

11 Time

9 9:30 10 10:30 11 11:30 12 12:30 1 1:30 2 2:30

h

c

a e

f

g i

j

3 3:30 4 4:30

d

b

Interval Partitioning: Lower Bound on Optimal Solution

•Def. The depth of a set of open intervals is the maximum number that contain any given time.

•Key observation. Number of classrooms needed depth.

•Ex: Depth of schedule below = 3 schedule below is optimal.

•Q. Does there always exist a schedule equal to depth of intervals?

12 Time

9 9:30 10 10:30 11 11:30 12 12:30 1 1:30 2 2:30

h

c

a e

f

g i

j

3 3:30 4 4:30

d

b

a, b, c all contain 9:30

Osservazione chiave: se d lezioni si accavallano all’istante t qualsiasi schedule usa almeno d aule

Interval Partitioning: Greedy Algorithm

Greedy algorithm. Consider lectures in increasing order of start time: assign lecture to any compatible classroom. Implementation. O(n log n).

For each classroom k, maintain the finish time of the last job added. Keep the classrooms in a priority queue.

13

Sort intervals by starting time so that s1 s2 ... sn.

d 0

for j = 1 to n {

if (lecture j is compatible with some classroom k)

schedule lecture j in classroom k

else

allocate a new classroom d + 1

schedule lecture j in classroom d + 1

d d + 1

}

number of allocated classrooms

Esempio di esecuzione • Ordina per start time: a, b, c, …, j.

• a in Aula 1: Aula 1: a

• b è incompatibile con Aula 1: apro Aula 2: Aula 2: b

• c è incompatibile con Aula 1 e Aula 2: apro Aula 3: Aula 3: c

• d è compatibile con Aula 1: Aula 1: a, d

• e è incompatibile con Aula 1 e Aula 2, ma compatibile con Aula 3: Aula 3: c, e

• f è compatibile con Aula 1: Aula 1: a, d, f

• g è incompatibile con Aula 1, ma compatibile con Aula 2: Aula 2: b, g

• h è incompatibile con Aula 1 e Aula 2, ma compatibile con Aula 3: Aula 3: c, e, h

• i è compatibile con Aula 1: Aula 1: a, d, f, i

• j è incompatibile con Aula 1, ma compatibile con Aula 2. Aula 2: b, g, j

14 Time 9 9:30 10 10:30 11 11:30 12 12:30 1 1:30 2 2:30

h

c

b

a

e

d g

f i

j

3 3:30 4 4:30

Esempio (continua)

• a in Aula 1: Aula 1: a

• b è incompatibile con Aula 1: apro Aula 2: Aula 2: b

• c è incompatibile con Aula 1 e Aula 2: apro Aula 3: Aula 3: c

• d è compatibile con Aula 1: Aula 1: a, d

• e è incompatibile con Aula 1 e Aula 2, ma compatibile con Aula 3: Aula 3: c, e

• f è compatibile con Aula 1: Aula 1: a, d, f

• g è incompatibile con Aula 1, ma compatibile con Aula 2: Aula 2: b, g

• h è incompatibile con Aula 1 e Aula 2, ma compatibile con Aula 3: Aula 3: c, e, h

• i è compatibile con Aula 1: Aula 1: a, d, f, i

• j è incompatibile con Aula 1, ma compatibile con Aula 2. Aula 2: b, g, j

15 Time

9 9:30 10 10:30 11 11:30 12 12:30 1 1:30 2 2:30

h

a

c e

f

g j

i

3 3:30 4 4:30

d

b

Aula 1

Aula 2

Aula 3

Interval Partitioning: Greedy Analysis Observation. Greedy algorithm never schedules two incompatible lectures in the same classroom.

Theorem. Greedy algorithm is optimal.

Pf.

Let d = number of classrooms that the greedy algorithm allocates.

Classroom d is opened because we needed to schedule a job, say x, that is incompatible with all d-1 other classrooms.

Since we sorted by start time, all these incompatibilities are caused by lectures that start no later than sx.

Thus, we have d lectures overlapping at time sx + .

Key observation all schedules use d classrooms. ▪

16

Nell’esempio: d = 3 è il numero di aule aperte dall’algoritmo. L’ Aula 3 è aperta perché la lezione x=c è incompatibile con le Aule 1 e 2, in cui ho già inserito a e b; a e b sono state considerate prima perché sa= sb = 9 ≤ sc= 9. Quindi abbiamo d=3 lezioni che si accavallano al tempo sc=9 (o anche 9:30). Osservazione chiave: se d lezioni si accavallano al tempo t qualsiasi schedule usa almeno d aule

Osserva… • Dove interviene nella prova la scelta di un ordinamento

basato sui tempi di inizio si crescenti?

«Since we sorted by start time, all these incompatibilities are caused by

lectures that start no later than sx , thus, we have d lectures overlapping at time sx + »

Nota: se le lezioni non fossero selezionati secondo i tempi di inizio crescenti, si sarebbe potuto avere che, pur essendo che c si accavalla sia con a che con b, i compiti a, b e c non si accavallano in uno stesso istante sc + :

17

a

c

b

4.2 Scheduling to Minimize Lateness

Scheduling to Minimizing Lateness

Minimizing lateness problem. Single resource processes one job at a time.

Job j requires tj units of processing time and is due at time dj (deadline).

If j starts at time sj, it finishes at time fj = sj + tj.

Lateness of j: j = max { 0, fj - dj }. (Se fj ≤ dj allora il ritardo=0)

Goal: schedule all jobs to minimize maximum lateness L = max j.

Ex:

19

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

d5 = 14 d2 = 8 d6 = 15 d1 = 6 d4 = 9 d3 = 9

lateness = 0 lateness = 2

dj 6

tj 3

1

8

2

2

9

1

3

9

4

4

14

3

5

15

2

6

max lateness = 6

Esempio

• Il ritardo di questo primo scheduling è max{0, 0, 0, 2, 0, 6} = 6

• Il ritardo di questo secondo scheduling è max{0, 0, 0, 1, 0, 0} = 1

20

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

d5 = 14 d2 = 8 d6 = 15 d1 = 6 d4 = 9 d3 = 9

lateness = 0 lateness = 2

dj 6

tj 3

1

8

2

2

9

1

3

9

4

4

14

3

5

15

2

6

max lateness = 6

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

d5 = 14 d2 = 8 d6 = 15 d1 = 6 d4 = 9 d3 = 9

max lateness = 1

Minimizing Lateness: Greedy Algorithms

Greedy template. Consider jobs in some order.

[Shortest processing time first] Consider jobs in ascending order of processing time tj.

[Earliest deadline first] Consider jobs in ascending order of deadline dj.

[Smallest slack] Consider jobs in ascending order of slack dj - tj.

Quale porta ad una soluzione ottima?

21

Minimizing Lateness: Greedy Algorithms

Greedy template. Consider jobs in some order. [Shortest processing time first] Consider jobs in ascending order of processing time tj.

[Smallest slack] Consider jobs in ascending order of slack dj - tj.

22

counterexample

counterexample

dj

tj

100

1

1

10

10

2

dj

tj

2

1

1

10

10

2

Minimizing Lateness: Greedy Algorithm

Greedy algorithm. Earliest deadline first.

23

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

d5 = 14 d2 = 8 d6 = 15 d1 = 6 d4 = 9 d3 = 9

max lateness = 1

Sort n jobs by deadline so that d1 d2 … dn

t 0

for j = 1 to n

Assign job j to interval [t, t + tj]

sj t, fj t + tj t t + tj

output intervals [sj, fj]

dj 6

tj 3

1

8

2

2

9

1

3

9

4

4

14

3

5

15

2

6 Esempio

Minimizing Lateness: No Idle Time

Il nostro scopo è adesso dimostrare che:

fra tutte le possibili soluzioni ottimali c’è anche la soluzione fornita dall’algoritmo greedy (cioè lo scheduling che inserisce le attività una dopo l’altra in ordine crescente di deadline)

Observation. The greedy schedule has no idle time (tempo di inattività).

Observation. There exists an optimal schedule with no idle time.

24

0 1 2 3 4 5 6

d = 4 d = 6

7 8 9 10 11

d = 12

0 1 2 3 4 5 6

d = 4 d = 6

7 8 9 10 11

d = 12

Minimizing Lateness: Inversions Recall: jobs sorted in ascending order of due dates di.

Def. An inversion in schedule S is a pair of jobs i and j such that: i < j but j scheduled before i.

Esempio:

3 -2, 3-1, 2-1, 6-1, 6-5, 6-4, 5-4

Observation. Greedy schedule has no inversions.

Observation. If a schedule (with no idle time) has an inversion, it has one with a pair of inverted jobs scheduled consecutively (in rosso nell’esempio sopra).

Altrimenti: la deadline del primo ≤ deadline del secondo ≤ deadline del terzo, etc: nessuna inversione! (confronta con esercizio sul gap!)

25

i j

inversion

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

d5 = 14 d2 = 8 d6 = 15 d1 = 6 d4 = 9 d3 = 9

Riprendiamo l‘esempio

• Il ritardo di questo scheduling è max{0, 0, 0, 2, 0, 6} = 6

• Scambiamo 5 con 4:

Adesso le inversioni sono: 3 -2, 3-1, 2-1, 6-1, 6-5, 6-4: una in meno!

• Il ritardo dopo lo scambio è max{0, 0, 0, 2, 3, 1} = 3 < 6

26

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

d5 = 14 d2 = 8 d6 = 15 d1 = 6 d4 = 9 d3 = 9

lateness = 0 lateness = 2

dj 6

tj 3

1

8

2

2

9

1

3

9

4

4

14

3

5

15

2

6

max lateness = 6

Inversioni: 3 -2, 3-1, 2-1, 6-1, 6-5, 6-4, 5-4

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

d5 = 14 d2 = 8 d6 = 15 d1 = 6 d4 = 9 d3 = 9

Minimizing Lateness: Inversions Def. An inversion in schedule S is a pair of jobs i and j such that: i < j but j scheduled before i.

Claim. Swapping two adjacent, inverted jobs reduces the number of inversions by one and does not increase the max lateness.

Pf. Let be the lateness before the swap, and let ' be it afterwards.

'k = k for all k i, j

'i i

If job j is late:

27

i j

i j

before swap

after swap

n)(definitio

)(

) time at finishes (

n)(definitio

i

ii

iji

jjj

jidf

fjdf

df

f'j

fi inversion

Quindi: nel calcolo del massimo fra i ritardi non troviamo valori maggiori

Minimizing Lateness: Analysis of Greedy Algorithm

Theorem. Greedy schedule S is optimal. Pf. Define S* to be an optimal schedule that has the fewest number of inversions, and let's see what happens.

Can assume S* has no idle time.

If S* has no inversions, then S = S*.

If S* has an inversion, let i-j be an adjacent inversion.

swapping i and j does not increase the maximum lateness and strictly decreases the number of inversions

this contradicts definition of S* ▪

28

Greedy Analysis Strategies

(Strategie per provare la correttezza di algoritmi greedy)

• Greedy algorithm stays ahead. Show that after each step of the greedy algorithm, its solution is at least as good as any other algorithm's. (esempio: scheduling di intervalli)

• Structural. Discover a simple "structural" bound asserting that every possible solution must have a certain value. Then show that your algorithm always achieves this bound. (esempio: partitioning di intervalli)

• Exchange argument. Gradually transform any solution to the one found by the greedy algorithm without hurting its quality. (esempio: scheduling to minimize lateness)

29

30

Coin Changing Goal. Given currency denominations: 1, 5, 10, 25, 100, devise a method to pay amount to customer using fewest number of coins. Ex: 34¢.

Cashier's algorithm. At each iteration, add coin of the largest value that does not take us past the amount to be paid. Ex: $2.89.

31

Coin-Changing: Greedy Algorithm Cashier's algorithm. At each iteration, add coin of the largest value that does not take us past the amount to be paid.

Q. Is cashier's algorithm optimal?

Sort coins denominations by value: c1 < c2 < … < cn.

S

while (x 0) {

let k be largest integer such that ck x

if (k = 0)

return "no solution found"

x x - ck S S {k}

}

return S

coins selected

32

Coin-Changing: Analysis of Greedy Algorithm

Observation. Greedy algorithm is sub-optimal for US

postal denominations: 1, 10, 21, 34, 70, 100, 350, 1225, 1500.

Counterexample. 140¢.

Greedy: 100, 34, 1, 1, 1, 1, 1, 1.

Optimal: 70, 70.