Paradigma algoritmilor greedy
Prezentarea generala a paradigmei
Studii de caz
rucsac (varianta continua)
arbori Huffman
arbori partiali de cost minim
Algoritmi greedy modelul matematic
domeniul problemei
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 C este extensibila daca exista y S X a.i. X {y}
C
baza: X C maximala (nu mai poate fi extinsa)
B, B baze diferite (B B B B)
Algoritmi greedy modelul matematic
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(locala): alege x dintre elementele
nealese a.i.
f(B {x}) este optim peste
{f(B {y}) | y neales si (B {y}) C} (*)
trebuie demonstrat ca alegerile greedy (locale) conduc la
determinarea optimului global
Algoritmi greedy modelul matematic
schema de algorithm
greedy(S, C, f)
{
S1 = S;
B = ;
while (B este extensibila) {
alege x din S1 conf. crit. (*);
S1 = S1 {x};
B = B {x};
}
return B;
}
Algoritmi greedy modelul matematic
un caz cind alegerea greedy produce optim global:
(S, C) este matroid daca:
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 pentru matroizi
greedyMatroid(S, C, f)
{
S1 = S;
B = ;
while (B este extensibila) {
alege x din S1 conf. crit. (**);
S1 = S1 {x};
B = B {x};
}
return B;
}
Algoritmi greedy modelul matematic
Teorema:
Algoritmul greedyMatroid determina o submultime
optima daca (S, C) este matroid ponderat.
Demonstratie:
fie x de pondere maxima
Fapt: 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 optima (pe tabla)
S = { y | y != x, {x,y} C }, C = {X | X {x} C}
(S, C) matroid
daca B este solutie pentru (S, C) care contine x, atunci B {x} este
solutie optima pentru (S, C)
Studii de caz
rucsac (varianta continua)
arbori Huffman
arbori partiali de cost minim
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
partile fractionare alese trebuie sa incapa in rucsac
i=0,n-1 xiwi M
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: domeniul problemei
S = {(i,xi) | 0 i < n, xi [0,1]}
X C daca:
((i,xi), (i,xi) X) i = i xi = xi
(xiwi | (i,xi) X) M
are loc proprietatea de ereditate
X C , (i, xi) X implica X {(i, xi)} C
nu are proprietatea de interschimbare (deci nu se poate aplica
teorema de la matroizi)
w = (7, 4, 5), M = 10, X = {(0, 1), Y = {(1, 1), (2, 1)}
|X| = 1, |Y| = 2, dar nu exista (i, y) Y a.i. X {(i, y)} C
f(i, xi) = xipi
f(X) = (f(i, xi) | (i, xi) X)
Problema rucsacului: alegeri greedy
alegere 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)
alegerea greedy OK:
(i, xi) a.i. i aduce profit maxim pe unitatea de greutate si xi
cantit maxima ce incape in rucsac
B B {(i, xi)}
exemplu (continuare):
p/w = (3/6, 4/4, 6/8)
profitul = 17/2 cu alegerea (0, 1, 6/8)
Problema rucsacului: algoritmul greedy
greedyRucsac(n, w, p, M)
{
S1 = {0,1,, n-1};
B = ; wB = 0;
while (wB < M) {
alege i din S1 cu pi/wi maxim;
S1 = S1 {i};
xi = min((M wB)/wi, 1);
B = B {(i,xi)};
wB += xi;
}
return B;
}
Problema rucsacului: analiza algoritmului greedy OK
Teorema Solutia calculata de algoritmul greedyRucsac este
optima
demonstratie (pe tabla)
timpul de executie in cazul cel mai nefavorabil: O(n log n)
spatiu suplimentar: O(n)
Studii de caz
rucsac (varianta continua)
arbori Huffman
arbori partiali de cost minim
Coduri Huffman
Coduri liber (independent) de prefix optime
instanta
n mesaje M0, M1, ..., Mn-1 cu frecventele w0, w1, ..., wn-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)|wi)
iesire
o codificare cu lungimea medie minima
Coduri Huffman: istoric
Din wikipedia:
In 1951, David A. Huffman and his MIT information theory
classmates were given the choice of a term paper or a final
exam. The professor, Robert M. Fano, assigned a term paper on
the problem of finding the most efficient binary code. Huffman,
unable to prove any codes were the most efficient, was about to
give up and start studying for the final when he hit upon the idea
of using a frequency-sorted binary tree and quickly proved this
method the most efficient.
In doing so, the student outdid his professor, who had worked with
information theory inventor Claude Shannon to develop a
similar code. By building the tree from the bottom up instead of
the top down, Huffman avoided the major flaw of the
suboptimal Shannon-Fano coding.
Coduri Huffman: reprezentarea unei codificari ca arbore
HARABABURA
Mi
wi
cod(Mi)
0010
011
010
10
110
0
1
0
1
0
2 R
0
H
1
0
2 B 0
1
4 A
1 U
Coduri Huffman: reprezentarea unei codificari ca arbore
deoarece ne intereseaza numai codificarile optime, ne putem
restrange numai la arbori in care nodurile interne au exact doi
copii (se face o compactare a drumurilor)
0
1
0
1
0
2 R
0
2 B
1
4 A
1
1 U
Echivalenta cu arbori ponderati pe frontiera minimali
Consideram arbori binari cu proprietatea ca orice varf v are
0 sau 2 succesori si care au ca informatii (etichete,
ponderi) in varfurile de pe frontiera numere wv. Convenim
sa numim acesti arbori ca fiind ponderati pe frontiera.
Pentru un varf v din arborele T notam cu dv lungimea
drumului de la radacina lui T la varful v. Lungimea externa
ponderata a arborelui t este
LEP(T)= v pe frontiera lui t dv wv
problema determinarii unei codificari de lungime medie
minima este echivalenta cu cea a determinarii unui arbore
cu lungimea externa ponderata minima pentru ponderile w
date de frecvente.
Arbori ponderati pe frontiera: domeniul problemei
S cea mai mica multime de arbori construita astfel:
wi S pentru orice i
T1, T2 S T1 T2 S
n1+ n2
n1
T1
n2
n2
n1
T2
T1 T2
S include toti arborii ponderati pe frontiera cu valori wi
S include toti arborii optimi (care au lungimea externa ponderata
minima pentru o secventa w data)
Arbori ponderati pe frontiera: domeniul problemei
X C daca:
( T1, T2 X) ( T1 T2 T2 T1), unde T1 T2 ddaca
exista T a. i. T2 = T1 T
X este finita
X C include numai elemente -maximale
f(T) = LEP(T)
f(X) = T Xf(T)
Arbori ponderati pe frontiera: domeniul problemei
are loc axioma de accesibilitate (de ce?) (S, C) sistem
accesibil
nu are loc proprietatea de ereditate (contraexemplu) nu se
poate aplica teorema de la matroizi
ce se poate spune despre proprietatea de interschimbare?
Coduri Huffman: alegere greedy
initial: B = { w0 , , wn-1 }
alegere locala
alege T1, T2 cu radacini minime in B si T1 T2 nu este in B
B = B {T1, T2} {T1 T2}
(nu mai e nevoie de S1, ea poate fi calculata)
arborii construiti cu algoritmul greedy se numesc si arbori
Huffman (ei definesc codurile Huffman)
Proprietati ale codurilor Huffman
Lema
Fie T un arbore optim, v si v doua noduri pe frontiera lui T.
Daca wv < wv atunci dv dv.
Interpretarea pentru coduri optimale: mesajele cu frecvente mai
mari au lungimile codurilor optime mai mici
demonstratie (pe tabla)
Lema
Orice arbore optim poate fi transformat intr-un arbore
Huffman.
demonstratie (pe tabla)
Coduri Huffman: algoritm greedy
greedyArbPondFr(w)
{
B = ;
for (i=0; i<n; ++i)
B = B {single(wi)};
while (|B| > 1) {
alege T1, T2 din B cu root(T1)si root(T2)
minime;
B = B {T1, T2} } {T1 T2};
}
return B;
}
Coduri Huffman: implementare
A = min-heap B = noduri care
cu radacinile nu-s radacini
C = zona
auxiliara
w
stg
drp
0 1
...
initial cele n noduri se afla in heap-ul A
la pasul curent:
se extrag primele doua radacini n1 si n2 din heap-ul A
se introduce n1+n2 in heap-ul A
se adauga n1 si n2 la B
A se micsoreaza cu o unitate, B se mareste cu doua unitati, C
scade cu o unitate
timpul de executie in cazul cel mai nefavorabil: O(n log n)
spatiu: O(n)
Studii de caz
rucsac (varianta continua)
arbori Huffman
arbori partiali de cost minim
Arborele partial de cost minim - formulare
instanta:
un graf ponderat (G, w), G = (V, E), w : E R
arbore = graf conex fara cicluri
subgraf partial: G = (V, E) cu E E
arbore partial = subgraf partial + arbore
costul unui arbore partial este w(G) = {i,j}E w({i,j})
iesire:
un arbore partial de cost minim
Domeniul problemei generic
S = multimea de muchii E
X C daca X e submultime de muchii a unui arbore partial
f(X) = suma ponderilor muchiilor din X (este functie de pondere)
Alegere greedy generica
muchia {i,j} este sigura pentru B B {{i,j}}este
submultime a unui arbore partial de cost minim
deocamdata pare magic cum putem alege o muchie sigura fara
sa cunoastem un arbore partial de cost minim (daca am sti un
astfel de arbore, problema ar fi rezolvata!)
Arborele partial de cost minim algoritm generic
procedure APCM(G, w)
begin
B = ;
S1 = E;
while ((V, B) nu este arbore partial) do
alege din S1 o muchie {i,j} sigura pentru B;
S1 = S1 - {{i,j}};
B = B {{i,j}};
end
Arborele partial de cost minim algoritmul lui Kruskal
X C daca X este padure
(S, C) este matroid, deci se poate aplica teorema de la matroizi
rezulta ca {i,j} e sigura pentru B ddaca w({i,j}) este minim
peste muchiile care unesc doi arbori din B
10
10
20
50
20
30
20
30
30
40
10
10
Arborele partial de cost minim algoritmul lui Kruskal (cont)
structura de date pentru B: union-find, S1 nu mai e necesara
kruskal(G, w)
{
B = ;
for each (i in V) B = B {single(i)};
sorteaza E crescator dupa w;
for each {i,j} in E in ordine crescatoare
if (find(B, i) find(B, j)
union(B, i, j);
return B
}
Complexitate: O(m log m), unde m este numarul de muchii
Arborele partial de cost minim algoritmul lui Prim
X C daca X este arbore
{i,j} e sigura pentru B ddaca w({i,j}) este minim peste muchiile
care se pot adauga la B mentinind proprietatea de arbore
10
10
20
50
20
30
20
50
30
40
30
10
40
10
Arborele partial de cost minim algoritmul lui Prim
procedure APCM_Prim(G, w, r) {
Q = V;
for each i in Q key[i] = ;
cheie[r] = 0; parent[r] = -1;
while (Q ) {
i = [Link](); [Link]();
for each j in G.a[i])
if (j Q && w({i,j}) < key[j]) {
parent[j] = i;
key[j] = w({i,j});
}
}
return parent;
}
Algoritmul lui Prim - analiza
structura de data pentru S1: un min-heap Q cu key[i] = ponderea
minima peste ponderile muchiilor ce unesc pe i cu un virf ales
deja
structura de date pentru B: arbore reprezentat prin legatura parinte
graful reprezentat prin liste de adiacenta G.a[i]
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