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

算法设计实验报告 PAGE2 / NUMPAGES16 课 程 设 计 报 告 题目： 计算机算法基础实验报告 课程名称： 专业班级： 学 号： 姓 名： 指导教师： 报告日期： 计算机科学与技术学院 目录 TOC \o 1-3 \h \z \u HYPERLINK \l _Toc329695726 一、实验目的 PAGEREF _Toc329695726 \h 3 HYPERLINK \l _Toc329695727 二、实验题目 PAGEREF _Toc329695727 \h 3 HYPERLINK \l _Toc329695728 三、设计分析 PAGEREF _Toc329695728 \h 3 HYPERLINK \l _Toc329695729 1．生成最短路径问题设计分析 PAGEREF _Toc329695729 \h 3 HYPERLINK \l _Toc329695730 2．最优二分检索树问题设计分析 PAGEREF _Toc329695730 \h 4 HYPERLINK \l _Toc329695731 四、算法描述 PAGEREF _Toc329695731 \h 5 HYPERLINK \l _Toc329695732 1．生成最短路径问题算法描述（用流程图表示） PAGEREF _Toc329695732 \h 5 HYPERLINK \l _Toc329695733 2．最优二分检索树问题算法描述（用流程图表示） PAGEREF _Toc329695733 \h 6 HYPERLINK \l _Toc329695734 五、程序 PAGEREF _Toc329695734 \h 7 HYPERLINK \l _Toc329695735 1. 生成最短路径问题算法代码 PAGEREF _Toc329695735 \h 7 HYPERLINK \l _Toc329695736 2．最优二叉检索树源代码 PAGEREF _Toc329695736 \h 10 HYPERLINK \l _Toc329695737 六、测试与分析 PAGEREF _Toc329695737 \h 13 HYPERLINK \l _Toc329695738 1. 生成最短路径问题算法 PAGEREF _Toc329695738 \h 13 HYPERLINK \l _Toc329695739 2. 最优二叉检索树源测试及分析 PAGEREF _Toc329695739 \h 15 HYPERLINK \l _Toc329695740 七、实验总结及体会 PAGEREF _Toc329695740 \h 16 HYPERLINK \l _Toc329695741 八、参考书目 PAGEREF _Toc329695741 \h 16 实验目的 掌握贪心方法、动态规划的基本思想 了解适用贪心方法、动态规划的问题类型，并能设计相应的贪心法算法 掌握贪心算法、动态规划算法时间空间复杂度分析，以及问题复杂性分析方法 实验题目 实现单源点生成最短路径的贪心方法，完善算法，求出长度，并推导路径上的结点序列 实现最优二分检索树算法，计算各C(i,j)、R(i,j)、W(i,j)的值，并推导树的形态 设计分析 1．生成最短路径问题设计分析 为了制定产生最短路径贪心算法，对于这个问题需要想出一个多级解决方案和最优的量度标准。方法之一是逐条构造这些最短路径，可以用迄今已经生成的所有路径长度之和作为一种量度，为了使这一量度达到最小，其单独的每一个路径都必须具有最小长度。 使用这一个量度标准时，假定已经构造了i条最短路径，则下面要构造的路径应该是下一个最小的长度路径。生成从源点v0 首先，生成一条到最短结点的最短路径，然后生成一条到第二近结点的最短路径，依次往下进行…。为了按照这样的路径生成这些最短路径，需要确定与其生成最短路径的下一个结点，以及到这一结点的最短路径。实验中用S表示对其已经生成了最短路径的那些结点（包括v0）的集合，对于来写不在S中的w，设Dist（w）是从v 如果下一条最短路径是到结点u，则这条路径是从v0 处结束，并且只 那些在S中的结点。 所生成的下一个路径的终点u必定是所有不在S内的结点中具有最小距离Dist（u）的结点。 如二中那样选出了结点u并生成从v0 由上述分