24 martie 2014

Optimal binary search tree (OBST)

Titlul problemei: Se dă un set de chei cu o probabilitate de accesare, să se creeze arborele binar optim de căutare astfel încât costul total / timpul mediu de accesare să fie minim.

Formule importante:
OBST(i,j) = min {OBST(i, r-1) + OBST(r+1,j) + p[k]}, unde i r j and i k j
OBST(i,i) = p[i] și OBST(i,i-1) = 0 pentru oricare 1 i N

Costul final este OBST(1,N)
Reconstituirea se face în functie de r-ul ales pentru fiecare iterație a lui OBST, care reprezintă rădăcina arborelui sau sub-arborelui curent.

Și un program pentru rezolvarea în Python are următorul output:



Programul se poate descărca aici.

Niciun comentariu: