Paradigma algoritmilor “greedy”

Prezentarea generala a paradigmei Studii de caz

memorarea programelorrucsac (varianta continua)arbori Huffman

Algoritmi “greedy” - ingrediente

probleme de optim proprietatea de alegere locala (“greedy”)

solutia de optim global poate fi obtinuta facind alegeri optime locale (“greedy”)

alegerea optima locala curenta poate depinde de alegerile de pina atunci dar nu si de cele viitoare

trebuie demonstrat ca alegerile optime locale conduc la obtinerea optimului global

proprietatea de substructura optimasolutia optima a problemei contine solutiile optime ale

subproblemelor

Algoritmi “greedy” – o prima formalizare

S – o multime de intrari C(S)

obiectele din C(S) sunt submultimi ale lui Soperatii: X {x}, X – {x}

ProblemaIntrare: S, f : C(S) RIesire: B obiect maximal din C(S) care optimizeaza f

B este construita incremental Alegerea locala

alege x a. i. B {x} C(S)x defineste un optim local

proprietatea de substructura optimafie x primul (sau ultimul) ales de alg. greedysolutia problemei initiale include solutia subproblemei

coresp. lui S’ = S – {x}, C(S’) = {B S’ | B {x} C(S)}, f restrictionata la C(S’)

Memorarea eficienta a programelor - formulare

instantan obiecte 0,1, ..., n-1 de marimi (lungimi) L0, L1 , ..., Ln-1

presupunem cele n obiecte asezate intr-o lista liniara in ordinea ((0), ..., (n-1))

timpul de regasire a obiectului de pe pozitia k este

t(k) = i=0,k L(i)

timpul mediu de regasire este TM() = 1/nk=0,n-1t(k)

iesireo asezare a obiectelor in lista a.i. timpul mediu de regasire sa

fie minim

Memorarea eficienta a programelor – algoritm “greedy”

exempluL = (40, 10, 60, 30)TM(id) = (40 + 50 + 110 + 140)/4 = 340/4 = 85 = (1, 3, 0, 2)TM() = (10 + 40 + 80 + 140) = 270/4 < 85

algoritm “greedy”: alege la pasul curent un obiect neales inca de lungime minimaalegerea “greedy” duce la obtinerea optimului global

o permutarea a.i. i < j si L(i) > L(j) ’ = (i,j) ( inmultit cu transpozitia (i,j))• TM(’) < TM()• rezulta ca este optima daca (i,j) i < j L(i) L(j) • permutarea calculata de alg. greedy satisface ac. prop.

proprietatea de substructura optima (?)timp: O(n log n)spatiu suplimentar: O(1)

Memorarea eficienta a programelor – algoritm “greedy”, formal

S = {(i,j) | 0 i, j < n} X C(S) daca:

((i,j), (i’,j’) X) i = i’ j = j’ alegerea locala:

(k, i) a.i. k este prima pozitie libera si L(i) minim peste obiectele nealese

B B {(k,i)} in final B descrie permutarea care ordoneaza obiectele

crescator dupa marime proprietatea de substructura optima

permutarea “include” permutarea ce ordoneaza crescator dupa marime obiectele {0,1,…,n-1} – (0) (eliminarea celui mai mic obiect)

Problema rucsacului (varianta continua): formulare

instanta: n obiecte 0, 1, ..., n-1 de dimensiuni (greutati)

w0, w1, ..., wn-1

un rucsac de capacitate M introducerea in rucsac a unei parti fractionare xi din

obiectul i aduce un profit xi pi

profitul total adus de alegerile x0, ..., xn-1 este

i=0,n-1 xipi

iesire:o alegere pentru care profitul adus este maxim

Problema rucsacului: solutie “greedy” care nu-i OK

la pasul curent alege obiectul cu profitul pi cel mai mare

contraxemplu:

• n = 3, p = (3, 4, 6), w = (6, 4, 8), M = 10

• profitul = 8 cu alegerea (0, ½, 1)

Problema rucsacului: solutie “greedy” OK

la pasul curent alege obiectul ce aduce profit maxim pe unitatea de

greutate (pi/wi)daca este loc suficient in rucsac, obiectul se introduce in

totalitate (xi = 1)altfel obiectul este introdus partial (maxim din cit se

poate, 0 xi < 1) si procesul de alegere se opreste exemplu (continuare):

p/w = (3/6, 4/4, 6/8)profitul = 17/2 cu alegerea (0, 1, 6/8)

Teorema Solutia calculata de algoritmul “greedy” este optimademonstratie

timp: O(n log n) spatiu suplimentar: O(n)

Problema rucsacului: solutie “greedy”, formalizare

S = {(i,x) | 0 i < n, x [0,1]} X C(S) daca:

((i,x), (i’,x’) X) i = i’ x = x’

(xwi | (i,x) X) M

alegerea locala:(i, xi) a.i. i aduce profit maxim pe unitatea de greutate

si xi cantit maxima ce incape in rucsac

B B {(i, xi)}

proprietatea de substructura optimasolutia x include solutia x’corespunzatoare

subproblemei P’ obtinuta din P prin eliminarea obiectului i cu profit maxim pe unitatea de greutate si M’ = M – xi

Coduri Huffman

Coduri liber (independent) de prefix optime instanta

• n mesaje M0, M1, ..., Mn-1 cu frecventele f0, f1, ..., fn-1

• cod(Mi) {0,1}*, i,j: i j cod(Mi) nu este prefix a lui cod(Mj)

• lungimea medie a codificarii = 1/n i=0,n-1 (|cod(Mi)|fi)

iesire

• o codificare cu lungimea medie minima

Coduri Huffman: reprezentarea unei codificari ca arbore HARABABURA

1

2 4 1

2

0

0

1

0

1

0 1

1

10

0

H

R A

B

U

Mi H A R B U

fi 1 4 2 2 1

cod(Mi) 0010 011 010 10 110

Coduri Huffman: algoritm “greedy”

initial: n arbori cu un singur nod etichetati cu fi

f0 f1 fn-1

pasul curent

n1n2

n1n2

n1+ n2

cu n1, n2 minime peste multimea radacinilor

T1 T2 T1 T2

Proprietati ale codurilor Huffman

Lema

Fie cod o codificare optima.

Daca fi < fj atunci |cod(Mi)| |cod(Mj)| (mesajele cu frecvente mai mari au lungimile codurilor mai mici)

demonstratie

Lema

Orice codificare optima poate fi transformata intr-o codificare Huffman cu aceeasi lungime medie.

demonstratie

Coduri Huffman: algoritm “greedy”, formalizare

S – cea mai mica multime de arbori construita astfel:fi S

T1, T2 S T1 T2 S

X C(S) daca:

(T X) T = fi sau ( T1, T2 X) T = T1 T2

X este finita

f(X) = max{suma_ponderata(T) | T S} alegere locala

B = B {T1 T2}, T1, T2 cu radacini minime in B si T1 T2 nu este in B

proprietatea de substructura optimasolutia problemei coresp. intrarii f0, f1, ..., fn-1 “include” solutia

subproblemei coresp. intrarii f0 + f1, ..., fn-1, unde f0, f1 sunt minime

Coduri Huffman: implementare

initial cele n noduri se afla in heap-ul A la pasul curent:

se extrag primele doua radacini n1 si n2 din heap-ul Ase introduce n1+n2 in heap-ul Ase adauga n1 si n2 la B A se micsoreaza cu o unitate, B se mareste cu doua unitati, C

scade cu o unitate timp: O(n log n) spatiu: O(n)

stgdrp

0 1

A = min-heap cu radacinile

B = noduri carenu-s radacini

C = zona auxiliara

. . .

inf

Paradigma algoritmilor “greedy” (continuare)

Studii de caz

• arborele partial de cost minim

• secventializarea activitatilorPrezentarea formala a paradigmei

Arborele partial de cost minim - formulare

instanta: un graf ponderat (G, w), G = (V, E), w : E Rarbore = graf conex fara ciclurisubgraf partial: G’ = (V, E’) cu E’ E arbore partial = subgraf partial + arborecostul unui arbore partial este w(G’) = {i,j}E’ w({i,j})

iesire:un arbore partial de cost minim

Arborele partial de cost minim – algoritm generic

procedure APCM(G, w)

begin

A E1 Ewhile ((V, A) nu este arbore partial) do

alege din E1 o muchie {i,j} “sigura” pentru A

E1 E1 - {{i,j}}A A {{i,j}}

endmuchia {i,j} “sigura” pentru A A {{i,j}}este

submultime a unui arbore partial de cost minim

Arborele partial de cost minim – algoritmul lui Kruskal

A este o padure pasul de alegere locala alege o muchie de cost minim ce

uneste doi arbori din A structura de date pentru A: union-find

20

10

40

30

10

3020

50 20

10

10

30

Arborele partial de cost minim – algoritmul lui Kruskal (cont)

procedure APCM_Kruskal(G, w)

begin

A for each i in V do single(i)

sorteaza E crescator dupa w

for each {i,j} in E in ordine crescatoare do

if (find(A, i) find(A, j)then union(A, i, j)

end

Complexitate: O(m log m), unde m este numarul de muchii

Algoritmul lui Kruskal - formalizare

S = multimea de muchii X C(S) daca X este padure alegere locala:

adauga la B muchia {i,j} de cost minim a.i.

• {i,j} uneste doi arbori din B (B {{i,j}} C(S) )

• {i,j} de cost minim peste muchiile care satisfac proprietatea de mai sus

proprietatea de substructura optimamuchia {i,j} adaugata prima data imparte B in doi subarbori:

B1=(V1, E1), B2 = (V2, E2) cu V = V1 V2 fie G1, G2 subgrafurile induse de V1 resp. V2B1 este APCM pentru G1 si B2 este APCM pentru G2

Arborele partial de cost minim – algoritmul lui Prim

A este arbore cu radacina r pasul de alegere locala alege o muchie de cost minim ce se poate

adauga la A mentinind proprietatea de arbore structura de date pentru A: arbore reprezentat prin legatura parinte structura de data pentru E1: un min-heap Q cu cheie[i] = ponderea

minima peste ponderile muchiilor ce unesc pe i cu un virf ales deja

20

10

40

30

10

3020

50 20

10

10

30

50

40

Arborele partial de cost minim – algoritmul lui Prim

procedure APCM_Prim(G, w, r)

begin

Q Vfor fiecare i in Q do cheie[i] cheie[r] 0; parinte[r] -1 while (Q ) do

citeste(Q,i); elimina(Q)

for (fiecare j in listaDeAdiac[i]) do

if (j Q and w({i,j}) < cheie[j])then parinte[j] = i;

cheie[j] w({i,j})end Complexitate asimptotica: O(n log n)+O(m log n) = O(m log n), unde

m este numarul de muchii si n este numarul de varfuri

Algoritmul lui Prim- formalizare

S = multimea de muchii X C(S) daca X este arbore alegere locala:

adauga la B muchia {i,j} de cost minim a.i.

• B {{i,j}} arbore ( C(S) )

• {i,j} de cost minim peste muchiile care satisfac proprietatea de mai sus

proprietatea de substructura optimafie {i,j} ultima muchie aleasa a.i. j nu e in arbore inainte de

alegerea localaB – {{i,j}} este APCM pentru graful indus de V – {j}

Secventializarea optima a activitatilor: formulare

Intrare:n activitati 0,1,2, …,n-1fiecare activitate dureaza o unitate de timprealizarea activitatii i aduce profitul p(i) > 0activitatea i trebuie terminata la termenul limita d(i)

(deadline) Iesire

o lista liniara s = (s(0),…, s(k-1)) de activitati a.i.

• orice activitate s(i) este realizata in termen, d(s(i)) i+1

• profitul este maxim

Secventializarea optima a activitatilor: exemplu

o solutie posibila: (0, 3,1) cu profitul 20 + 25 + 35 = 80d(0) = 2 1, d(3) = 2 2, d(1) = 3 3

o alta solutie posibila: (2, 3,1) cu profitul 35 + 25 + 35 = 95d(2) = 1 1, d(3) = 2 2, d(1) = 3 3

exista vreo solutie mai buna?

i 0 1 2 3

d(i) 2 3 1 2

p(i) 20 35 35 25

Secventializarea optima a activitatilor: model mat.

solutie acceptabila: s = (s(0),…, s(k-1)) a.i.

(i) d(s(i)) i+1 (orice activitate este realizata in timp) solutia optima: s* a.i. s* aduce profit maxim peste solutiile

acceptabile

i p(s*(i)) = max{i p(s(i)) | s acceptabila}

reordonarea unei solutii acceptabile in ordinea crescatoare a termenelor limita produce tot o solutie acceptabila

i 0 1 2 3

d(i) 2 3 3 2

(2, 0, 1) solutie acceptabila (0, 2, 1) solutie acceptabila

Rezulta ca putem reprezenta o solutie acceptabila ca o multime: {0, 1, 2}; secventa acceptabila se obtine ordonand multimea dupa termenii limita

Secventializarea optima a activitatilor: model mat.

criteriul de alegere locala:

B B {i}

unde i este activitatea de profit maxim a.i. B {i} este

solutie acceptabila

Teorema. Daca B este determinata de algoritmul greedy, atunci orice secventializare acceptabila a lui B este optima.

i 0 1 2 3

d(i) 2 3 1 2

p(i) 20 35 35 25

B = Ø B = {1} B = {1,2} B = {1,2,3} s = (2,3,1)

Ideea de demonstratie: Fie B’solutie optima. Daca B B’ si B are r elemente comune cu B’, se construieste o alta solutie optima B’’ din B’ a.i. B si B’’ au r+1 elemente comune.

Secventializarea optima a activitatilor: model mat.

S = multimea activitatilor C(S): X C(S) daca X este solutie acceptabila (admite o

secventializare acceptabila) proprietatea de alegere locala:

vezi slide-ul precedent proprietatea de substructura optima:

daca i este prima activitate aleasa, atunci B-{i} este solutie optima pentru subproblema obtinuta prin eliminarea lui i

Algoritmi “greedy” – formulare matematica

modelul matematic S multime de stari, C colectie de submultimi ale lui S axioma de accesibilitate (AA)

X C: X (x X: X {x} C) sistem accesibil: (S, C) X este extensibila daca exista y S – C a.i. X {y} C baza: X C maximala presupunere: B, B’ baze (B B’ B’ B)

Algoritmi “greedy” – formulare matematica (continuare I)

modelul matematic (continuare)clasa de probleme:

• intrare: S, C, f : C R (functia obiectiv)

• iesire: o baza B cu f(B) = optim{f(X) | X baza in C}alegere “greedy”: alege x dintre elementele nealese a.i.

f(B {x}) este optim peste

{f(B {y}) | y neales si (B {y}) C} (*)

Algoritmi “greedy” – formulare matematica (continuare II)

procedure algGreedy(S, C, f, B)

begin

S1 SB while (B este extensibila) do

alege x din S1 conf. crit. (*)

S1 S1 – {x}B B {x}

end

Algoritmi “greedy” – formulare matematica (continuare III)

un caz cind alegerea “greedy” produce optim global:(S, C) este matroid:

• AA este inlocuita cu proprietatea de ereditate: X C, X (x X: X {x} C)

are loc proprietatea de interschimbare (PI):

X, Y C, |X| < |Y| (y Y-X: X {y} C)(S, C) este matroid ponderat:

• f este o pondere: f : S R , f(X) = (f(x) | x X)• optim = max• alegere “greedy”: alege x a.i.

f(x) = max{f(y) | y in S B, B {y}) C}

Algoritmi “greedy” – formulare matematica (continuare IV)

Teorema: Algoritmul “greedy” determina o submultime optima daca (S, C) este matroid ponderat.

Demonstratie:x de pondere maximaFapt: exista o solutie optima B care contine pe x

• fie B’ o solutie optima; pp ca x nu e in B’

• luam B ={x}; apoi utilizam PI si adaugam la B elem. din B’ a.i. B = B’ – {y} {x}

• B este optimaS’ = { y | {x,y} C }, C’ = {X | X {x} C} daca B este solutie pentru (S, C) care contine x, atunci B – {x}

este solutie optima pentru (S’, C’)

Exemple de matroizi

S = multimea muchiilor dintr-un graf, C = mult. subgrafurilor aciclice (reprezentate ca multimi de muchii)

C = multimea submultimilor de dim cel mult k

S = multimea coloanelor unei matrici n x n, C = multimea coloanelor liniar independente