动态规划之最优二叉查找树源代码——算法导论
此算法是根据《算法导论》里面的介绍编写的。数据也是。代码运行后,结果数据正确。
以《算法导论》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"); } }