最优二叉搜索树问题(二)
**m,int **s,double **w);
void Traceback(int n,int i,int j,int **s,int f,char ch);
int main()
{
double a[] = {0.15,0.1,0.05,0.05};
double b[] = {0.00,0.5,0.1,0.05};
cout<<"有序集的概率分布为："<
for(int i=0; i
{
cout<<"a"<
}
double **m = new double *[N+2];
int **s = new int *[N+2];
double **w =new double *[N+2];
for(int i=0;i
{
m[i] = new double[N+2];
s[i] = new int[N+2];
w[i] = new double[N+2];
}
OptimalBinarySearchTree(a,b,N,m,s,w);
cout<<"二叉搜索树最小平均路长为："<
cout<<"构造的最优二叉树为:"<
Traceback(N,1,N,s,0,'0');
for(int i=0;i
{
delete m[i];
delete s[i];
delete w[i];
}
delete[] m;
delete[] s;
delete[] w;
return 0;
}
void OptimalBinarySearchTree(double a[],double b[],int n,double **m,int **s,double **w)
{
//初始化构造无内部节点的情况
for(int i=0; i<=n; i++)
{
w[i+1][i] = a[i];
m[i+1][i] = 0;
}
for(int r=0; r
{
for(int i=1; i<=n-r; i++)//i为起始元素下标
{
int j = i+r;//j为终止元素下标
//构造T[i][j] 填写w[i][j],m[i][j],s[i][j]
//首选i作为根，其左子树为空，右子树为节点
w[i][j]=w[i][j-1]+a[j]+b[j];
m[i][j]=m[i+1][j];
s[i][j]=i;
//不选i作为根，设k为其根，则k=i+1，……j
//左子树为节点：i,i+1……k-1,右子树为节点：k+1,k+2,……j
for(int k=i+1; k<=j; k++)
{
double t = m[i][k-1]+m[k+1][j];
if(t
{
m[i][j]=t;
s[i][j]=k;//根节点元素
}
}
m[i][j]+=w[i][j];
}
}
}
void Traceback(int n,int i,int j,int **s,int f,char ch)
{
int k=s[i][j];
if(k>0)
{
if(f==0)
{
//根
cout<<"Root："<
}
else
{
//子树
cout<
}
int t = k-1;
if(t>=i && t<=n)
{
//回溯左子树
Traceback(n,i,t,s,k,'L');
}
t=k+1;
if(t<=j)
{
//回溯右子树
Traceback(n,t,j,s,k,'R');
}
}
}
4、构造最优解：
算法OptimalBinarySearchTree中用s[i][j]保存最优子树T(i,j)的根节点中的元素。当s[i][n]=k时，xk为所求二叉搜索树根节点元素。其左子树为T(1,k-1)。因此，i=s[1][k-1]表示T(1,k-1)的根节点元素为xi。依次类推，容易由s记录的信息在O(n)时间内构造出所求的最优二叉搜索树。
5、复杂度分析与优化：
算法中用到3个数组m,s和w，故所需空间复杂度为O(n^2)。算法的主要计算量在于计算。对于固定的r，它需要的计算时间O(j-i+1)=O(r+1)。因此算法所耗费的总时间为：。事实上，由《动态规划加速原理之四边形不等式》可以得到：而此状态转移方程的时间复杂度为O(n^2)。由此，对算法改进后的代码如下：
[cpp]
//3d11-1 最优二叉搜索树 动态规划加速原理 四边形不等式
#include "stdafx.h"
#include
using namespace std;
const int N = 3;
void OptimalBinarySearchTree(double a[],double b[],int n,double **m,int **s,double **w);
void Traceback(int n,int i,int j,int **s,int f,char ch);
int main()
{
double a[] = {0.15,0.1,0.05,0.05};
double b[] = {0.00,0.5,0.1,0.05};
cout<<"有序集的概率分布为："<
for(int i=0; i
{
cout<<"a"<
}
double **m = new double *[N+2];
int **s = new int *[N+2];
double **w =new double *[N+2];