武汉理工大学《算法设计与分析》课程设计
}
}
}
if (arc[i][j] + cost[i] < cost[j]) { }
cost[j] = arc[i][j] + cost[i]; path[j] = i;
cout< while (path[i] >= 0) { } cout< cout<<\i = path[i]; int main() { } int n = creatGraph( ); int pathLen = Backpath(n); cout<<\最短路径的长度是：\return 0; 8 武汉理工大学《算法设计与分析》课程设计 6.2 结果截图 7 结果分析 （1）贪心法、动态规划法和分支限界法都可以用来解决多段最短路径问题，然而在这种情况相比之下，贪心法的运算效率比较高，因为它不像另外两种方法一样，需要涉及到许多的点。可以看到，动态规划法由于需要填表，并有一个相关的迭代问题，它几乎涉及了所有的点；而分支限界法，它通过贪心法设置的上下限，并以它们为依据进行剪枝，减少了许多的运算量。而贪心法，访问了最少的点。 （2）就结果准确性来看，就本题例子来看，贪心法结果为0 2 4 7 9，路径的代价为20；动态分配法采取的路径为：0 3 5 8 9，路径的代价为16；而分支限界法，结果为0 3 5 8 9，路径的代价为16。可以看出，在这个方面，动态分配法和分支限界法都达到了预期的结果，相比直线，贪心法的误差就比较大了。 由以上的讨论，我们可以看出分支限界法的综合性能比较好，它和动态规划法在解决多段最短路径问题时都可以得到正确解，而贪心法虽然可以省时间与空间，但结果不准确 9 武汉理工大学《算法设计与分析》课程设计 是它的缺点。各方法都是有利有弊的。因此在选择方法时，还应当根据实际情况。当只需要大概的一个解时，当然是要用省时省力的贪心法；如果对结果又比较高的要求的话，就要采取动态规划法或分支限界法。dijkstra算法的明显优点就是它的多用性，它可以求任意一点到其它某一点的距离，但是它访问的数据量很大，几乎要访问所有的边（相对于贪心法而言），因此这里来说，在单纯的解决多段最短路径问题时，它们的功能都差不多，而在解决其它较复杂的图时，Dijkstra算法有明显的优越性，但当然，作为贪心法的一种，它的结果的准确性不是那么的高。Dijkstra算法在本质上为贪心算法,每一步的选择为当前步的最优,复杂度为O(n*n)。动态规划法是可以看作是对分支限界法的改进。 其实，它们各有各的优缺点，可以尝试将它们混合起来用，扬长避短，设置范围，并且过程中对肯定不会是最后结果的数据“剪枝”。这样就可以提高运行速率了。 8 课程体会 算法分析与设计是一门非常重要的课程。很多问题的解决，程序的编写都要依赖它，在软件还是面向过程的阶段，就有“程序=算法+数据结构”这个公式。算法的学习对于培养一个人的逻辑思维能力是有极大帮助的，它可以培养我们养成思考分析问题，解决问题的能力。作为IT行业学生，学习算法无疑会增强自己的竞争力，修炼自己的“内功”。 谢谢老师的指导，学习《算法分析与设计》使我对软件基础知识中算法的地位有了充分的了解，虽然课程结束了，但我依然还会继续学习算法分析与设计，以后我将充分利用所学到我实际的开发项目中。 9 参考文献 [1]王红梅，胡明.算法设计与分析（第二版）.北京：清华大学出版社.2013.4 [2]严蔚敏, 吴伟民. 数据结构(C语言版)．北京：清华大学出版社.2010 [3] 余祥宣，催国华，邹海明.计算机算法基础（第三版）[M]．武汉：华中科技大学出版社.2006 [4]卜月华.图论及其应用.南京：东南大学出版社.2000 10 武汉理工大学《算法设计与分析》课程设计 大作业成绩评定表 班级 大作业题目 学号 姓名 多种方法解决多段图的最短路径问题 评阅点 评分标准（细则） 分值 40分 30分 15分 5分 0分 20分 15分 10分 5分 10分 8分 5分 0分 20分 15分 10分 5分 10分 实得分 正确实现本程序所需全部功能，算法设计正确合理且有一定创新，结果正确 算法设计实现所需功能，算法正确，结果正确 与实现 （40分） 基本实现所需功能，结果正确 有明显重大错误 无法实现程序功能 算法分析全面、详细、正确 算法分析 （20分） 算法分析比较全面、正确 算法分析基本正确 算法分析有明显错误 程序可读性好、逻辑清晰，程序完整，可维护性好 程序可读、可维护 基本可读可维护 逻辑混乱、不可读 报告规范，符合技术用语要求，行文流畅，层次清晰 报告质量 （20分） 报告书写基本规范，符合技术用语要求，文理较通畅 结构较合理，层次较清楚，基本符合要求 结构混乱，文不对题目，或者有明显抄袭现象 设计验收 好10分；通过8分；基本合格6分 总 分 程序可读、可维护性 （10分） 教师签名： 11