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

算法设计实验报告　 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到所有其他结点的最短路径的贪心方法就是按照路径长度的非降次序生成这些路径。 首先，生成一条到最短结点的最短路径，