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:
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.
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:
Trimiteți un comentariu