# Using memo method to solve the optimal binary search tree problem

2021-07-14 15:01:21

Catalog

# Problem description

Given an incrementally ordered sequence of elements $$S=\left \langle a_1,a_2,\cdots,a_n\right \rangle$$ And the associated access probability distribution $$C=\left \langle q(0), p(1), q(1), p(2), q(2), \cdots, p(n), q(n) \right \rangle$$, Store these elements on the node of a binary tree , To find $$x$$ Whether it's in these numbers . If $$x$$ be not in , determine $$x$$ In which gap . Try to construct an optimal binary search tree so that the average search times $$t$$ Minimum . The average search times of a binary search tree are defined as follows ：

$t=\sum_{i=1}^{n}{p(i)(1+d(i))}+\sum_{j=0}^{n}{q(j)d(j)}$

among ,$$d(i)$$ Represents a node $$a_i$$ The depth of the ,$$i=1,2,\cdots, n$$;$$d(j)$$ It's a gap ( leaf ) node $$(a_j, a_{j+1})$$ The depth of the ,$$j=0,1,\cdots, n$$.

# Problem modeling

## 1. Boundary parameterization of subproblems

$$S[i,j]=<x_i,x_{i+1}...x_j>$$ yes $$S$$ With $$i$$ and $$j$$ A subset as a boundary ,$$C[i,j]=<a_{i-1},b_i,a_i,...,b_j,a_j>$$ It's corresponding to $$S[i,j]$$ Access probability distribution .
Subproblem Division ： With $$x_k$$ As a root, it is divided into two subproblems

$S[i,k-1],C[i,k-1]$

$S[k+1,j],C[k+1,j]$

## 2. Recursive relations

set up m[i,j] It's relative to the input S[i,j] and C[i,j] The average comparison times of the optimal binary search tree of , Make $$w[i,j]=\sum_{p=i-1}ja_p+\sum_{q=i}jb_q$$ yes C[i,j] All the probabilities in （ Including data elements and gaps ） The sum of the , Then the recurrence equation is

$\begin{cases} m[i,j]=\min \{m[i,k-1]+m[k+1,j]+w[i,j]\} &\text{if } 1\leq i\leq j \leq n \\ m[i,i-1]=0 &\text{if } i=1,2,...n \end{cases}$

## 3. Memo table and tag function table

w: The weight of the optimal binary search tree ;

m: Calculate the cost of the optimal binary search tree ;

r: The root of the optimal binary search tree .

# Complexity analysis of the algorithm

$$i,j$$ All combinations of $$O(n^2)$$ Kind of , Each of them has to deal with different k Calculate ,$$k=O(n)$$ Each calculation is a constant time $$T(n)=O(n3),S(n)=O(n2)$$

# Iterative implementation of the algorithm pseudo code description

 function BST(p, q, n)
let m[1...n+1,0...n],w[1...n+1,0...n] and r[1...n,1...n] be new tables
for i = 1 → n + 1 do
m[i, i − 1] ← 0
w[i, i − 1] ← qi−1
for l = 1 → n do
for i = 1 → n − l + 1 do
j ← i + l − 1
m[i, j] ← ∞
w[i, j] ← w[i, j − 1] + pj + qj
for r = i → j do
t ← m[i, r − 1] + m[r + 1, j] + w[i, j]
if t < m[i, j] then
m[i, j] ← t
r[i, j] ← r
return m, r
end function


# Iterative implementation of the source code

#include<iostream>
#include<vector>
using namespace std;
int main(){
int n;
cin >> n;
vector<int> S,C;
vector<vector<int> > w,m,r;// Define the memo form
vector<int> B;
for(int i = 1;i <= n;i ++){
int a;
cin >> a;
S.push_back(a);
}// Input set S
for(int i = 0;i < 2*n+1;i ++){
double a;
cin >> a;
C.push_back(100*a);
}// Enter the access probability , multiply 100
for(int j = 0;j <= n+1;j++){
B.push_back(0);
}
for(int i = 0;i <= n+1;i++){
m.push_back(B);
w.push_back(B);
r.push_back(B);
}
for(int i = 1;i <= n+1;i ++){
m[i][i-1] = 0;
w[i][i-1] = C[2*(i-1)];
}// Initialize memo table
for(int l = 1;l <= n;l ++){
for(int i = 1;i <= n-l+1;i ++){
int j = i+l-1;
m[i][j] = 2147483647;
w[i][j] = w[i][j-1] + C[2*j-1] + C[2*j];
for(int root = i;root <= j;root ++){
int t = m[i][root-1] + m[root+1][j] + w[i][j];
if(t < m[i][j]){
m[i][j] = t;
r[i][j] = root;
}
}
}
}// Using memo method to construct the optimal binary search tree iteratively
for(int i = 1;i <= n;i ++){
for(int j = 1;j <= n;j ++){
cout << r[i][j] << " ";
}
cout << endl;
}// Output the table that records the root node
cout << " The minimum cost is " << (double)m[1][n]/100;
return 0;// Output minimum expected cost
}


# Conclusion

Love that is not expressed is an illusion

author ： Huacheng

https://chowdera.com/2021/07/20210714150041703a.html