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

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

# 问题描述

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

# 问题建模

## 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]$$存取概率分布。

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

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

## 2.递推关系

$\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}$

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;//输出最小期望代价
}


# 结束语

https://www.cnblogs.com/huacheng1122/p/15010827.html