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