proiectarea algoritmilor 4. scheme de...

Platformă de e-learning și curriculă e-content pentru învățământul superior tehnic

Proiectarea Algoritmilor

4. Scheme de algoritmi – Programare dinamica

Bibliografie

Cormen – Introducere în Algoritmi cap. 17

Giumale – Introducere in Analiza Algoritmilor cap 4.4 ,4.5

http://www.cs.umass.edu/~barring/cs611/lecture/4.pdf

http://thor.info.uaic.ro/~dlucanu/cursuri/tpaa/resurse/Curs6.pps

http://www.math.fau.edu/locke/Greedy.htm

http://en.wikipedia.org/wiki/Greedoid

http://activities.tjhsst.edu/sct/lectures/greedy0607.pdf

http://www.cse.ust.hk/~dekai/271/notes/L12/L12.pdf









http://activities.tjhsst.edu/sct/lectures/greedy0607.pdf

http://www.cse.ust.hk/~dekai/271/notes/L12/L12.pdf

Proiectarea Algoritmilor 2010

Programare dinamică


Descriere generală

Algoritm generic

Caracteristici

Exemplificare: Înmulțirea matricilor

Exemplificare: Arbori optimi la căutare (AOC)

Definiții

Construcția AOC


Programare dinamica

Descriere generală

Soluții optime construite iterativ asamblând soluții optime ale

unor probleme similare de dimensiuni mai mici.

Algoritmi “clasici”

Algoritmul Floyd-Warshall care determină drumurile de cost

minim dintre toate perechile de noduri ale unui graf.

AOC

Înmulţirea unui şir de matrici

Numere catalane

Viterbi


Algoritm generic

Programare dinamică (crit_optim, problema) // fie problema0 problema1 … probleman astfel încât

// probleman= problema; problemai mai simpla decât problemai+1

1. Sol = soluții_inițiale(crit_optim, problema0);

2. Pentru i = 1 n Repetă // construcție soluții pentru problemai

// folosind soluțiile problemelor precedente

3. Soli = calcul_soluții(Sol, Crit_optim, Problemai);

// determin soluția problemeii 4. Sol = Sol U Soli;

// noua soluție se adaugă pentru a fi refolosită pe viitor

5. s = soluție_pentru_probleman(Sol); // selecție / construcție soluție finala

6. Întoarce s;


Caracteristici

O soluție optimă a unei probleme conține soluții optime ale

subproblemelor.

Decompozabilitatea recursivă a problemei P in subprobleme

similare P = Pn, Pn-1, … P0 care acceptă soluții din ce in ce mai

simple.

Suprapunerea problemelor (soluția unei probleme Pi participă in

procesul de construcție a soluțiilor mai multor probleme Pk de talie

mai mare k > i) – memoizare (se foloseşte un tablou pentru

salvarea soluţiilor subproblemelor pentru a nu le recalcula)

In general se folosește o abordare bottom-up, de la subprobleme

la probleme.


Diferențe Greedy – programare

dinamică

Programare lacomă

Sunt menținute doar

soluțiile parțiale curente

din care evoluează

soluțiile parțiale următoare

Soluțiile parțiale anterioare

sunt eliminate

Se poate obține o soluție

neoptimă. (trebuie

demonstrat că se poate

aplica)


Se păstrează toate

soluțiile parțiale

La construcția unei soluții

noi poate contribui orice

altă soluție parțială

generată anterior

Se obține soluția optimă.


Diferenţe divide et impera –

programare dinamică

Divide et impera

abordare top-down – problema este descompusă în subprobleme care sunt rezolvate independent

putem rezolva aceeaşi problemă de mai multe ori (dezavantaj potenţial foarte mare)


abordare bottom-up - se porneşte de la sub-soluţii elementare şi se combină sub-soluţiile mai simple în sub-soluţii mai complicate, pe baza criteriului de optim

se evită calculul repetat al aceleiaşi subprobleme prin memorarea rezultatelor intermediare

Se dă o şir de matrice: A1, A2, ..., An.

Care este numărul minim de înmulţiri de scalari pentru a calcula produsul:

A1 x A2 x ... x An ?

Să se determine una dintre parantezările care minimizează numărul de înmulţiri de scalari.


Exemplu: Parantezarea matricilor

(Chain Matrix Multiplication)

Înmulţirea matricilor

A(p, q) x B (q, r) => pqr înmulţiri de scalari.

Dar înmulţirea matricilor este asociativă (deşi nu este comutativă).

A(p, q) x B (q, r) x C(r, s)

(AB)C => pqr + prs înmulţiri

A(BC) => qrs + pqs înmulţiri

Ex: p = 5, q = 4, r = 6, s = 2

(AB)C => 180 înmulţiri

A(BC) => 88 înmulţiri

Concluzie: Parantezarea este foarte importantă!


Soluţia banală

Matrici: A1, A2, ..., An.

Vector de dimensiuni: p0, p1, p2, ... , pn.

Ai(pi-1, pi) A1(p0, p1), A2(p1, p2), …

Dacă folosim căutare exhaustivă şi vrem să

construim toate parantezările posibile pentru a

determina minimul: Ω(4n / n3/2).

Vrem o soluţie polinomială folosind P.D.


Descompunere în subprobleme

Încercăm să definim subprobleme identice cu problema

originală, dar de dimensiune mai mică.

1 ≤ i ≤ j ≤ n:

Notăm Ai, j = Ai x … x Aj. Ai,j are pi-1 linii si pj coloane: Ai,j(pi-1, pj)

m[i, j] = numărul optim de înmulţiri pentru a rezolva

subproblema Ai,j

s[i, j] = poziţia primei paranteze pentru subproblema Ai,j

Care e parantezarea optimă pentru Ai, j?

Problema iniţială: A1,n


Combinarea subproblemelor

Pentru a rezolva Ai,j

trebuie găsit acel indice i ≤ k < j care

asigură parantezarea optimă:

Ai, j = (Ai x…x Ak) x (Ak+1 x…x Aj)

Ai, j = Ai, k x Ak+1, j


Alegerea optimală

Căutăm optimul dintre toate variantele

posibile de alegere (i ≤ k < j)

Pentru aceasta, trebuie însă ca şi

subproblemele folosite să aibă soluţie

optimală (adică Ai, k şi Ak+1, j)


Substructura optimală

Dacă ştim că alegerea optimală a soluţiei pentru problema A i, j implică

folosirea subproblemelor (Ai, k şi Ak+1, j) şi soluţia pentru Ai, j este optimală,

atunci şi soluţiile subproblemelor Ai, k şi Ak+1, j trebuie să fie optimale!

Demonstraţie: Folosind metoda cut-and-paste (metodă standard de

demonstrare a substructurii optimale pentru problemele de programare

dinamică).

Observație: Nu toate problemele de optim posedă această proprietate!

Ex: drumul maxim dintr-un graf orientat.


Definirea recursivă

Folosind descompunerea in subprobleme,

combinarea subproblemelor, alegerea optimală şi

substructura optimală putem să rezolvăm problema

prin programare dinamică.

Următorul pas este să definim recursiv soluţia unei

subprobleme.

Vrem să găsim o formulă recursivă pentru m[i, j] şi

s[i, j].


Definirea recursivă (II)

Cazurile de bază sunt m[i, i]

Noi vrem să calculăm m[1, n]

Cum alegem s[i, j] ?

Bottom-up de la cele mai mici subprobleme la cea iniţială


Rezolvare bottom-up


Rezolvare - iniţializare


Rezolvare – pas intermediar


Rezolvare – final


Pseudocod


Complexitate

Spaţială: Θ(n2)

Pentru memorarea soluţiilor subproblemelor

Temporală: O(n3)

Ns: Număr total de subprobleme: O(n2)

Na: Număr total de alegeri la fiecare pas: O(n)

Complexitatea este de obicei egala cu Ns x Na



Arbori optimi la căutare

Def 2.1: Fie K o mulțime de chei. Un arbore binar cu

cheile K este un graf orientat si aciclic A = (V,E) a.i.:

Fiecare nod u V conține o singură cheie k(u) K iar cheile din

noduri sunt distincte.

Există un nod unic r V a.i. i-grad(r) = 0 si u ≠ r, i-grad(u) = 1.

u V, e-grad(u) ≤ 2; S(u) / D(u) = succesorul stânga / dreapta.

Def 2.2: Fie K o mulțime de chei peste care exista o

relație de ordine . Un arbore binar de căutare

satisface:

u,v,w V avem (v S(u) => cheie(v) cheie(u)) (w D(u)

=> cheie(u) cheie(w))


Căutare

Caută(elem, Arb)

Dacă Arb = null Întoarce null

Dacă elem = Arb.val // valoarea din nodul crt. Întoarce Arb

Dacă elem Arb.val Întoarce Caută(elem, Arb.st)

Întoarce Caută(elem, Arb.dr)

Complexitate: Θ(logn)


Inserţie în arbore de căutare

Inserare(elem, Arb)

Dacă Arb = vid // adaug cheia in arbore nod_nou(elem, null, null)

Dacă elem = Arb.val // valoarea există deja Întoarce Arb

Dacă elem Arb.val Întoarce Inserare(elem, Arb.st) // adaugă in stânga

Întoarce Inserare(elem, Arb.dr) // sau in dreapta

Complexitate: Θ(logn)

nod Stânga

nod Dreapta


Exemplu de arbori de căutare

Cu aceleaşi chei se pot construi arbori

distincţi

28

23

32 8

19

15

41

A2

23

15 32

8 19 28 41

A1 23

15 32

8

19

28 41

A


Exemplu (I)

presupunem că elementele din A1 şi A2 au probabilităţi de căutare egale: numărul mediu de comparaţii pentru A1 va fi:

(1 + 2 + 2 + 3 + 3 + 3 + 3) / 7 = 2.42

numărul mediu de comparaţii pentru A2 va fi: (1 + 2 + 2 + 3 + 3 + 4 + 5) / 7 = 2.85

28

23

32 8

19

15

41

A2

23

15 32

8 19 28 41

A1


Exemplu (II)

presupunem că elementele au următoarele probabilităţi: 8: 0.2; 15: 0.01; 19: 0.1; 23: 0.02; 28: 0.25; 32: 0.2; 41:

0.22;

numărul mediu de comparaţii pentru A1: 0.02*1+0.01*2+0.2*2+0.2*3+0.1*4+0.25*3+0.22*3=2.85

numărul mediu de comparaţii pentru A2: 0.25*1+0.02*2+0.22*2+0.2*3+0.2*3+0.01*4+0.1*5=2.47

28

23

32 8

19

15

41

A2

23

15 32

8 19 28 41

A1


Probleme

Costul căutării depinde de frecvenţa cu care

este căutat fiecare termen.

Ne dorim ca termenii cei mai des căutaţi să

fie cât mai aproape de vârful arborelui pentru a

micşora numărul de apeluri recursive.

Dacă arborele este construit prin sosirea

aleatorie a cheilor putem ajunge la o simplă listă

cu n elemente


Definiţie AOC

Definiție: Fie A un arbore binar de căutare cu chei intr-

o mulțime K, fie {x1, x2, … xn} cheile conținute in A, iar

{y0, y1, … yn} chei reprezentante ale cheilor din K ce

nu sunt in A astfel încât: . Fie pi, i = 1,n

probabilitatea de a căuta cheia xi si qj, j = 0,n

probabilitatea de a căuta o cheie reprezentata de yj.

Vom avea relația: . Se numește arbore

de căutare probabilistică, un arbore cu costul:

Definiție: Un arbore de căutare probabilistică având

cost minim este un arbore optim la căutare (AOC).

niyxy iii ,1,1

101

n

jj

n

ii qp

n

jjj

n

iii qAynivelpAxnivelACost

01

*),(*)1),(()(


Algoritm AOC naiv

Generarea permutărilor x1, ... xn.

Construcţia arborilor de căutare corespunzători.

Calcularea costului pentru fiecare arbore.

Alegerea arborelui de cost minim.

Complexitate: Θ(n!) (deoarece sunt n! permutări).

căutăm altă variantă!!!


Construcţia AOC – Notaţii

Ai,j desemnează un AOC cu cheile {xi+1, xi+2, … xj} in noduri

si cu cheile {yi, yi+1, … yj} in frunzele fictive.

Ci,j = Cost (Ai,j).

Ri,j este indicele α al cheii xα din rădăcina arborelui Ai,j.

Observație: A0,n este chiar arborele A, C0,n = Cost (A) iar

w0,n = 1.

j

ik

k

j

ik

kji qpw1

,

j

ik

kijk

j

ik

kijkij qAynivelpAxnivelACost *),(*)1),(()(1


Construcţia AOC - Demonstraţie

Lemă: Pentru orice 0 ≤ i ≤ j ≤ n există relaţiile:

Ci,j = 0 , daca i = j; (arbore vid)

Demonstrație:

Ci,j depinde de indicele α al nodului rădăcină.

dacă Ci,α-1 şi Cα,j sunt minime (costurile unor AOC) Ci,j este minim.

jijiji

ji wCCC ,,1,, }{min

jijiji wCCC ,,1,,

j

ik

kijk

j

ik

kijkij qAynivelpAxnivelACost *),(*)1),(()(1

xi+1,...xα-1

yi,...yα-1

x α+1,...xj

y α+1,...yj

x α

Ai, j

Aα, j = D(Ai, j)

Ai, α-1 = S(Ai, j)


Construcţia AOC

1. In etapa d, d = 1, 2, … n se calculează costurile si indicele

cheilor din rădăcina arborilor AOC Ai, i+d, i = 0, n-d cu d noduri si d

+ 1 frunze fictive.

Arborele Ai, i+d conține in noduri cheile {xi+1, xi+2, … xi+d}, iar in

frunzele fictive sunt cheile {yi, yi+1, … yi+d}. Calculul este efectuat pe

baza rezultatelor obținute in etapele anterioare.

Conform lemei avem

Rădăcina Ai, i+d are indicele Ri, j = α care minimizează Ci, i+d.

2. Pentru d = n, C0, n corespunde arborelui AOC A0, n cu cheile {x1,

x2, … xn} in noduri si cheile {y0, y1, … yn} in frunzele fictive.

diidiidii

dii wCCC

,,1,, }{min


Algoritm AOC

AOC(x, p, q, n)

Pentru i = 0 n

{Ci, i = 0, Ri, i = 0, wi,i = qi} // inițializare costuri AOC vid Ai, i

Pentru d = 1 n

Pentru i = 0 n-d // calcul indice rădăcina si cost pentru Ai, i+d

j = i + d, Ci, j = ∞, wi, j = wi, j-1 + pj + qj

Pentru α = i + 1 j // ciclul critic – operații intensive

Dacă (Ci, α-1 + Cα, j < Ci, j) // cost mai mic?

{ Ci, j = Ci, α-1 + Cα, j ; Ri, j = α} // update

Ci, j = Ci, j + wi, j // update

Întoarce gen_AOC(C, R, x, 0, n) // construcție efectiva arbore A0, n

// cunoscând indicii

Complexitate???


Exemplu constructie AOC (I)

8: 0.2; 15: 0.01; 19: 0.1; 23: 0.02; 28: 0.25; (58%)

[0:8): 0.02; (8:15): 0.07; (15:19): 0.08; (19:23): 0.05; (23:28):

0.05; (28,∞): 0.15 (42%)

C01=p1+q0+q1=0.29

C12=p2+q1+q2=0.16

C23=p3+q2+q3=0.25

C34=p4+q3+q4=0.02+0.05+0.05=0.12

C45=p5+q4+q5=0.25+0.05+0.15=0.45

j

ik

k

j

ik

kji qpw1

, diidiidii

dii wCCC

,,1,, }{min


Exemplu constructie AOC (II)

C02= min {(C00+C12),(C01+C22)} + w02 = min(0.16,0.29) + 0.38 = 0.54 R02= 1 (α=1)

C13 = min{C23,C12} + w13 = min(0.25,0.16) + 0.31 = 0.47 R13= 3

C24 = min{C34,C23} + w24 = min(0.12,0.25) + 0.3 = 0.42 R24= 3

C35 = min{C45,C34} + w35 = min(0.45,0.12) + 0.52 = 0.64 R35= 5

8

<8 8-15

A01:0.29 15

8-15 15-19

A12:0.16 19

15-19 19-23

A23:0.25 23

19-23 23-28

A34:0.12 28

23-28 >28

A45:0.45

8

<8 15

8-15 15-19

A02:0.54 19

19-23 15

8-15 15-19

A13:0.47 19

15-19 23

19-23 23-28

A24:0.42

23

19-23 23-28

28

23-28

A35:0.64

j

ikk

j

ikkji qpw

1, diidii

diidii wCCC

,,1,, }{min


Exemplu constructie AOC (III)

C03 = min(C00+C13, C01+C23, C02+C33) + w03 = min (0.47,0.54, 0.54) + w03 =>

R03 =1

C14= min(C11+C24,C12+C34,C13+C44) + w14 = min(0.42,0.28, 0.47) + w14 =>

R14= 3

C25 = min(C22+C35,C23+C34, C24+C55) + w25 = min(0.64, 0.37, 0.42) + w25 =>

R25 = 4

j

ikk

j

ikkji qpw

1, diidii

diidii wCCC

,,1,, }{min

8

<8 19

19-23 15

8-15 15-19

19

15

8-15 15-19

23

19-23 23-28

19

15-19 19-23

23

28

23-28 >28


AOC – Corectitudine (I)

Teoremă: Algoritmul AOC construiește un arbore AOC A cu cheile x

= {x1, x2, … xn} conform probabilităților de căutare pi, i = 1,n si qj, j =

0,n.

Demonstrație: prin inducție după etapa de calcul al costurilor arborilor cu

d noduri.

Caz de baza: d = 0. Costurile Ci, i ale arborilor vizi Ai, i, i = 0, n sunt 0,

așa cum sunt inițializate de algoritm.

Pas de inducție: d ≥ 1. Ip. ind.: pentru orice d’ < d, algoritmul AOC

calculează costurile Ci, i+d’ si indicii Ri, i+d’, ai rădăcinilor unor AOC Ai, i+d’,

i = 0, n-d’ cu cheile {xi+1, xi+2, … xi+d’}. Trebuie sa arătam ca valorile Ci, i+d

si Ri, i+d corespund unor AOC Ai, i+d, i = 0, n-d cu cheile {xi+1, xi+2, … xi+d}.


AOC – Corectitudine (II)

Pentru d si i fixate, algoritmul calculează:

unde costurile Ci, α-1 si Cα, i+d corespund unor arbori cu un număr de noduri d’

= α – 1 – i in cazul Ci, α-1 si d’ = i + d – α in cazul Cα, i+d.

0 ≤ d’ ≤ d – 1 aceste valori au fost deja calculate in etapele d’ < d si

conform ipotezei inductive sunt costuri si indici ai rădăcinilor unor AOC.

Conform Lemei anterioare, Ci, j este costul unui AOC. Conform algoritmului

rădăcina acestui arbore are indicele r = Ri, j, iar cheile sunt {xi+1, xi+2, … xr-1}

{xr} {xr+1, xr+2, … xj} = {xi+1, xi+2, … xj}

Pentru d = n, costul C0, n corespunde unui AOC A0, n cu cheile x si cu rădăcina

de indice R0, n.

diidiidii

dii wCCC

,,1,, }{min

AOC – Concluzii

Câte subprobleme sunt folosite în soluţia optimală intr-un anumit

pas?

AOC: 2 subprobleme

Câte variante de ales avem de făcut pentru determinarea alegerii

optimale intr-un anumit pas?

AOC: j – i + 1 candidaţi pentru rădăcină

Informal, complexitatea = Ns * Na (Ns = număr subprobleme; Na

= număr alegeri)

Complexitate AOC: O(n2) * O(n) = O(n3)

Optimizare – Knuth: O(n2)


proiectarea algoritmilor 4. scheme de...

Documents