当前位置:网站首页>使用备忘录方法求解最优二叉搜索树问题

使用备忘录方法求解最优二叉搜索树问题

2021-07-14 15:00:47 花城1122

问题描述

给定递增有序的元素序列\(S=\left \langle a_1,a_2,\cdots,a_n\right \rangle\)与相关存取概率分布\(C=\left \langle q(0), p(1), q(1), p(2), q(2), \cdots, p(n), q(n) \right \rangle\),将这些元素存储在一棵二叉树的结点上,以查找\(x\)是否在这些数中。如果\(x\)不在,确定\(x\)在哪个空隙。设法构造一棵最优二叉搜索树使得平均查找次数\(t\)最小。一棵二叉搜索树的平均查找次数定义如下:

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

其中,\(d(i)\)表示结点\(a_i\)的深度,\(i=1,2,\cdots, n\)\(d(j)\)表示空隙(叶子)结点\((a_j, a_{j+1})\)的深度,\(j=0,1,\cdots, n\)

问题建模

1.子问题的边界参数化

\(S[i,j]=<x_i,x_{i+1}...x_j>\)\(S\)\(i\)\(j\)作为边界的子数据集,\(C[i,j]=<a_{i-1},b_i,a_i,...,b_j,a_j>\)是对应\(S[i,j]\)存取概率分布。
子问题划分:以\(x_k\)作为根划分成两个子问题

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

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

2.递推关系

设m[i,j]是相对于输入S[i,j]和C[i,j]的最优二叉搜索树的平均比较次数,令$$w[i,j]=\sum_{p=i-1}ja_p+\sum_{q=i}jb_q$$是C[i,j]中所有概率(包括数据元素与空隙)之和,则递推方程为

\[\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.备忘录表与标记函数表

w:最优二叉搜索树的权;

m:计算最优二叉搜索树的成本;

r:最优二叉搜索树的根。

算法的复杂度分析

\(i,j\)的所有组合\(O(n^2)\)种,每种要对不同的k进行计算,\(k=O(n)\)每次计算为常数时间$$T(n)=O(n3),S(n)=O(n2)$$

算法的迭代实现伪代码描述

 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

迭代实现的源代码

#include<iostream>
#include<vector>
using namespace std;
int main(){
	int n;
	cin >> n;
	vector<int> S,C;
	vector<vector<int> > w,m,r;//定义备忘录表 
	vector<int> B;
	for(int i = 1;i <= n;i ++){
		int a;
		cin >> a;
		S.push_back(a);
	}//输入集合S 
	for(int i = 0;i < 2*n+1;i ++){
		double a;
		cin >> a;
		C.push_back(100*a);
    }//输入存取概率,乘以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)];
	}//初始化备忘录表
	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;
				}
			}
		}
	}//利用备忘录法迭代实现构造最优二叉搜索树 
	for(int i = 1;i <= n;i ++){
		for(int j = 1;j <= n;j ++){
			cout << r[i][j] << " ";
		}
		cout << endl;
	}//输出记录根节点的表 
	cout << "最小代价为" << (double)m[1][n]/100; 
	return 0;//输出最小期望代价 
}

运行结果截图

在这里插入图片描述

结束语

没有明确表达的爱意都是错觉

作者:花城

版权声明
本文为[花城1122]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/huacheng1122/p/15010827.html