算法设计与分析实验报告.docx

算法设计实验报告课 程 设 计 报 告题目： 计算机算法基础实验报告 课程名称： 专业班级： 学 号： 姓 名： 指导教师： 报告日期： 计算机科学与技术学院目录一、实验目的3二、实验题目3三、设计分析31生成最短路径问题设计分析32最优二分检索树问题设计分析4四、算法描述51生成最短路径问题算法描述（用流程图表示）52最优二分检索树问题算法描述（用流程图表示）6五、程序71. 生成最短路径问题算法代码72最优二叉检索树源代码10六、测试与分析131.生成最短路径问题算法132.最优二叉检索树源测试及分析15七、实验总结及体会16八、参考书目16一、 实验目的1. 掌握贪心方法、动态规划的基本思想2. 了解适用贪心方法、动态规划的问题类型，并能设计相应的贪心法算法3. 掌握贪心算法、动态规划算法时间空间复杂度分析，以及问题复杂性分析方法二、 实验题目1. 实现单源点生成最短路径的贪心方法，完善算法，求出长度，并推导路径上的结点序列2. 实现最优二分检索树算法，计算各C(i,j)、R(i,j)、W(i,j)的值，并推导树的形态三、 设计分析1生成最短路径问题设计分析为了制定产生最短路径贪心算法，对于这个问题需要想出一个多级解决方案和最优的量度标准。方法之一是逐条构造这些最短路径，可以用迄今已经生成的所有路径长度之和作为一种量度，为了使这一量度达到最小，其单独的每一个路径都必须具有最小长度。使用这一个量度标准时，假定已经构造了i条最短路径，则下面要构造的路径应该是下一个最小的长度路径。生成从源点v0到所有其他结点的最短路径的贪心方法就是按照路径长度的非降次序生成这些路径。首先，生成一条到最短结点的最短路径，然后生成一条到第二近结点的最短路径，依次往下进行。为了按照这样的路径生成这些最短路径，需要确定与其生成最短路径的下一个结点，以及到这一结点的最短路径。实验中用S表示对其已经生成了最短路径的那些结点（包括v0）的集合，对于来写不在S中的w，设Dist（w）是从v0开始只经过S中结点而在w结束的那条最短路径的长度。则可以很容易的得到以下结论:a) 如果下一条最短路径是到结点u，则这条路径是从v0处开始而在u处结束，并且只 那些在S中的结点。b) 所生成的下一个路径的终点u必定是所有不在S内的结点中具有最小距离Dist（u）的结点。c) 如二中那样选出了结点u并生成从v0到u的最短路径后，结点u就成为S中的一个成员。由上述分析所知，单源点最短路径存在一个简单算法，这个算法实际上只求出从v0到G中所有其他结点的最短路径长度。2最优二分检索树问题设计分析已知一个固定的标识符集合，希望产生一个构造二分检索树的方法。可以预料，同一个标识符集合有不同的二分检索树，而不同的二分检索树有不用的性能特征。由于一般的检索树具有不同的概率，另外，也要做一些不成功的检索，即对不在这棵树中标识符的检索。假定给出的标识符集合为a1,a2,a3an，其中a1a2,a3an，设P(i)是对ai 的检索概率，Q(i)是正被检索的标识符X的概率，而标识符X满足 aiXai+1,1=i=n,那么0nQ（i）就是不成功的概率。明显的有0nQ（i）+1nP（i）=1.为了得到二分检索树的成本函数，在这棵检索树的每一个空子树的位置上加上一个虚构的结点，即外部结点，如果一个二分检索树表示n个标识符，那么正好有n个内部结点和n+1个外部结点（虚构的）。每个内部结点表示一次成功检索可能终止的位置。每个外部结点编号依次不成功检索可能终止的位置。为了把动态规划应用于得到一棵最优二分检索树的问题，需要把构造恶言的一棵树看成一系列决策的结果，而且要能列出求取最优决策序列的递推式。解决上述问题的一种可能方法是，对于这些ai，1=i=n,要决策出将其中的哪一个作为T的根结点。如果选择ak，那么，a1a2ak-1这些内部结点和E0，E1，E2 Ek-1这些类的外部结点显然都将位于这个根的左子树L中，而其余的结点将在右子树R中。定义如下标识符：Cost（L）=1k-1P（i）*level（ai）+0k-1Q（i）*(levelEi-1) Cost（R）=k+1nP（i）*level（ai）+knQ（i）*(levelEi-1) 如果用W（i，j)表示Q(i)+ 1+1j(Ql+P(l)的和，于是可以得到检索树T的预期成本是：P（k）+Cost（L）+Cost（R）+W（0.k-1）+W（k，n）， 如果T是最优的，则上式必定为最小值。则必须有Cost(L)=C(0,k-1)和Cost(R)=C(k，n),而且k应该选择使得P（k）+ C(0,k-1)+ C(k，n)+W（0，k-1）+W（k，n）最下的k值。 因此，关于C（0，n），C（i，j）=C（0，k-1）+C（k，n）+P(k)+ W（0.k-1）+W（k，n）,C（i，j）=C（0，k-1）+C（k，n）W（i，j）。如果在这期间，记下每棵树Tij的根R（i，j）=K，用上面方法即可得C（0，n）。四、 算法描述1 生成最短路径问题算法描述（用流程图表示）开始将G中n个结点被记上0-n，集合S作为一个位数组存放，如果结点i不在S中，则S(i)=0，否则S（i）=1。在本算法中，图使用邻接矩阵表示。Cost（i，j）是每个边的权，则在边不在E（G）中的情况下，Cost=0，且Cost（i，i）=0（1=i=n）。最短路径算法及求路径上结点序列FindWays流程图如下：1 主函数main定义变量SN,CostNN,DistNNn输出源点到各点路径长度Disti,调用各结点查找路径结点函数Findways();输入当前结点个数n及Costij, 令i=1结束S(i) 0 , Dist(i) Cost(0,i) FindWays（）函数流程图开始i=i+1 Ni=n实参数：各点路径长度，当前结点m，当前路径长度length. Y 返回S0=1，Dist0=1Length=0,找到最小的Distw,Sw=1,m=0 Y N找到使Dist（m）成立的前一个结点i，递归调用FindWays（），调用前使length=length-Cost(i,m),输出i+1m=m+1Sm=1找到所有Sw=0的结点wDist(w)=MinDistw),Dist+Costuw 12 最优二分检索树问题算法描述（用流程图表示）在计算时，首先计算所有使得j-i=1的Cij，其中Cii=0，且Wii=Qi(0=i=n)，接着计算使得j-i=2的Cij，在计算期间，记下每根树的根结点Tij，即可得到最终二叉检索树的形态。下图表示最优二叉检索树的生成算法及最终求出树形态表示函数Root（）如下所示：开始主函数main 求出树形态函数Root（）开始定义：内部结点概率值数组PN; 外部结点概率值QN+1; 成本CN+1N+1， WN+1N+1;根 RN+1N+1（全局变量） 实参 m，n 表示树Tmn 输入结点数目n，以及内部结点概率值Pn;外部结点概率值Qn+1; i=0; Nm=n Y左右子树为空，输出* Wii Qi, Rii Cii 0Wii+1 Qi+Qi+1+Pi+1 i i+1 printf(%d,Rmn);输出当前结点Root(m,Rmn-1); 递归调用左子树Root(Rmn,n);递归调用右子树 i=i+1 N i = nWii=Qi,Rii=Cii Y 格式化输出，调用函数Root（）输出树的形态m=m+1m=1 Y i=0 j=i+m Y m=n+1 N Wij=Wij-1+Pj+Qj 寻找k满足Cik-1+Ckj取最小Rij=k,Cij=Wij+Cik-1+Ckj i=n Ni=i+1五、 程序1. 生成最短路径问题算法代码 #include#include #define MAX 100#define MAX_NUMBER 65536#define MIN(a,b) (a)(b)?(b):(a)void FindWays(float Dist,int m,float length); int n; /全局变量float CostMAXMAX; void main (void) float DistMAX; int SMAX; /状态 int i; int j; /结点个数 int m; float min=MAX; printf(请输入结点个数:); scanf(%d,&n); if( n100 ) printf(n输入结点个数过多，错误!n);exit(0); printf(请输入邻接矩阵，以空格隔开，其中，若两结点之间无连线，则输入为0n); for(i =0 ; i n ;i+) for(j =0 ;j n ; j+) scanf(%f,&Costij); for(i=1;in;i+) Disti=Cost0i; /给路径长度赋初值Si=0; /各点状态值 S0=1; /给初始点赋值 Dist0=0; printf(n以下格式按照书上输出n); printf(置初值 - 1 ); for(i = 0; i n ; i+) printf( %.2f , Disti); for(j=0;jn-1;j+) printf(n %d ,j); for(i=1;in;i+) if(0 = Si & 0 != Disti & Disti min) /找到符合条件的结点 min=Disti; /记录最小Cost节点位置 m=i; min = MAX; Sm=1; /将找到的结点计入S printf( | %d |,m); for(i=0;in;i+) if(1 = Si) printf( %d ,i+1); for(i=1;in;i+) if(0 = Si & Costmi != 0) if(0 = Dist i)Disti= Distm+Costmi;else Disti=MIN(Disti,Distm+Costmi); for(i = 0; i n ; i+) printf( %.2f , Disti); for(i = 1;i = 0; i-) /查找使Distm最小的前一个结点 if( Disti+Costim = length & 0 != Costim) /找到，则先递归，后输出，这样就可以保持输出时从源结点至当前结点 FindWays(Dist, i,length-Costim); printf( %d ,i+1); /输出，找到的中间结点 return; 2最优二叉检索树源代码 #include#define N 100#define MAX 65535void Root( int m,int n); /求出树的形态int RN+1N+1;void main (void) float PN; /内部结点概率值 float QN+1; /外部结点概率值float CN+1N+1; /成本float WN+1N+1; int i=0;int j=0;int m=0;int k=0;int k1=0;float min=0;int n; /结点数目printf(请输入内结点数目（n100）:);scanf(%d,&n);for(i=0;in;i+) printf(请输入第%d个内部部结点的概率值：,i+1); scanf(%f,&Pi); for(i=0;i=n;i+) printf(请输入第%d个外部部结点的概率值：,i+1); scanf(%f,&Qi); printf(n结果显示是：n); for(i=0;i=n;i+) for(j=0;j=n;j+) Cij=MAX; Wij=MAX; for(i=0;i=n-1;i+) /置初值 Wii=Qi; Rii=0; Cii=0; Wii+1=Qi+Qi+1+Pi; /含有一个结点的最优树 Cii+1= Wii+1; /由计算规则简化 Rii+1=i+1; /选取根结点 Wnn=Qn; /继续赋初值 Rnn=0; Cnn=0; for(m=2;m=n;m+) /找出m个结点的最优树 for(i=0;i=n-m;i+) j=i+m; Wij=Wij-1+Pj-1+Qj; k=i+1; min=Wij+Cik-1+Ckj; /给min赋初值 k1=k; k+; for(;k (Wij+Cik-1+Ckj) /替换min=Wij+Cik-1+Ckj; k1=k; Cij=min;Rij=k1; /记录K k=0; for(i=0;i=n;i+) /依次输出W C R for(j=0;j=n;j+) if(Wj-kj0 & Cj-kj 0) printf( %2.2f ,Wj-kj); printf( %2.2f ,Cj-kj); printf( %d ,Rj-kj); k+; printf(n); printf(最小检索成本是：%2fn,C0n); /最小检索成本最终结果 printf(最小检索检索树的先序遍历如下,其中*表示外部结点，数字表示第i个结点在树中位置n); /树形态最终结果 Root(0,n); printf(n谢谢使用!n);void Root( int m,int n) /求出树的形态 if (m = n | n=0 ) printf( * ); else printf( %d ,Rmn); Root(m,Rmn-1); Root(Rmn,n); return;六、 测试与分析1. 生成最短路径问题算法a) 解决如图的最短路径问题 2 31 2 0.533 4 1 输出结果是如下图： b) 解决书上图5-10的最短路径问题，如下所示c) 算法时间及空间复杂度分析在此算法中，由于采用邻接矩阵，邻接矩阵采用数组存放，n结点图的空间复杂度为O(MAX*MAX)，由于在输入n个结点的邻接矩阵时，必须采用两重循环，因此，n结点计算产生的时间复杂度也为O(n*n)。2. 最优二叉检索树源测试及分析a) 首先解决书上例6.10的的问题。按照如图输入得到的结果如下（其中最后树形态输出采用的是先序遍历，且外部结点用*表示）：b) 解决书上习题6.3的问题。按照如图输入得到的结果如下（其中最后树形态方法输出和a一致，且为了便于计算，将P、Q均乘以20）：c) 时间及空间复杂度分析由于采用二维定大小数组存储W及C，因此所需要的空间复杂度为O(N*N)； 在计算时，找有m个节点的最优树的时间复杂度为O(n*n)（n表示输入结点的个数，与N不一定相同）。此外，在构造树的形态函数Root（）中，时间复杂度为O（n*log2n）。七、 实验总结及体会本次算法实验题目比较简单，而且书上都有很清晰的伪代码，我们要做的更多的是对于算法进行具体的代码实现以及老师要求的一些辅助功能的添加，但是，尽管如此，算法实验中也会或多或少有些知识性的错误或者由于粗心产生的错误。下面对我实验中产生的错误原因及更正方法一一进行说明。 第一个问题是在实验求最短路径中如何判断两个结点之间无连接。一种方案是直接将此结点与对应结点的邻接值置为某个大数，但是在实验输入时又不是很方便，第二种方案是将上述值置为0，但在确定由源结点出发的路径长度时，又不得不考虑两点之间值为0产生的影响。因此实验中部分地方采用是判断Disti！= 0，Costmi !=