当前位置:网站首页>Using memo method to solve the optimal binary search tree problem

Using memo method to solve the optimal binary search tree problem

2021-07-14 15:01:21 Huacheng 1122

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  
}

Screenshot of operation result

 Insert picture description here

Conclusion

Love that is not expressed is an illusion

author : Huacheng

版权声明
本文为[Huacheng 1122]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/07/20210714150041703a.html