多种方法求多段图的最短路径问题-算法设计与分析课程设计(共14页).doc

精选优质文档-倾情为你奉上学 号： 算法设计与分析B大 作 业题 目多种方法解决多段图的最短路径问题学 院计算机科学与技术学院专 业软件工程班 级姓 名指导教师2014年12月26日多种方法解决多段图的最短路径问题摘 要多段图的最短路径问题是求从源点到终点的最小代价路径。本文主要描述的是分别用动态规划法、贪心法和分支限界法来解决多段图最短路径问题时的情况。文章首先阐述了各个方法的原理，主要的思路是通过输入一组数据，比较三者的输出结果的准确性以及运行时间，以之为基础来分析、讨论三者的性能区别。文章最后讲述了若这几种方法运行到有向图中的情况，几种方法的对比和它们比较适应的使用情况的讨论，并给出了自己的建议。关键字：多段图最短路径问题；动态规划法；分支限界法；贪心法专心-专注-专业目 录摘 要II1 引 言12 问题描述13 贪心法求解23.1 贪心法介绍23