动态规划之最优二叉查找树源代码——算法导论

此算法是根据《算法导论》里面的介绍编写的。数据也是。代码运行后，结果数据正确。

 

以《算法导论》P213中未测试数据：

p[6]={-100,0.15,0.1,0.05,0.1,0.2};

q[6]={0.05,0.1,0.05,0.05,0.05,0.1};

运行结果：

《算法导论》中的结果p216：

代码如下：

 

#include <iostream>
void main()
{
	float p[6]={-100,0.15,0.1,0.05,0.1,0.2};
	float q[6]={0.05,0.1,0.05,0.05,0.05,0.1};
	float e[7][6];
	float w[7][6];
	int root[6][6];

	for(int i=1;i<7;i++)
		e[i][i-1]=w[i][i-1]=q[i-1];//初始化d

	for(int l=0;l<6;l++)//求间隔距离为L的序列子最优二叉树
	{
		for(int i=1;i<6-l;i++)//序列从i开始
		{
			int j=i+l;//到j结束
			e[i][j]=1000;//初始化为-正无穷大
			//遍历序列中的节点作为子树的根结点，并找到最小搜索代价放入e，同时把此根结点存放入root
			w[i][j]=w[i][j-1]+q[j]+p[j];//这一个不太好理解。
			//w的物理意义是这个序列的所有k点和d点的概率和。
			//序列里面多了一个k点，同时，就要把这个Ki点和Di点加入到w里面。
			for(int k=i;k<=j;k++)//计算以k为根结点的子二叉树的搜索代价
			{
				float tmp=e[i][k-1]+e[k+1][j]+w[i][j];
				if(tmp<e[i][j])
				{
					e[i][j]=tmp;//如果搜索代价小于以前计算的，放入e（也就是说，e中一直存着目前最小的搜索代价）
					root[i][j]=k;
				}
					
			}
		}
	}
	printf("e：\n");
	for(int i=1;i<7;i++){
		for(int j=0;j<6;j++){
			if(e[i][j]>10||e[i][j]<0){
			printf("     ");
			}
			else{
			printf("%1.2f,",e[i][j]);
			}
			
		}
		printf("\n");
	}
	printf("w：\n");
	for(int i=1;i<7;i++){
		for(int j=0;j<6;j++){
			if(w[i][j]>1||w[i][j]<0){
			printf("     ");
			}
			else{
			printf("%1.2f,",w[i][j]);
			}
			
		}
		printf("\n");
	}
	printf("root：\n");
	for(int i=1;i<6;i++){
		for(int j=1;j<6;j++){
			if(root[i][j]>10||root[i][j]<0){
			printf("  ");
			}
			else{
			printf("%d,",root[i][j]);
			}
			
		}
		printf("\n");
	}

}