环游世界最优线路分析.doc

 PAGE \* MERGEFORMAT 18 环游世界最优线路分析 3213 环游世界最优线路 分析 评阅编号： 评阅专家1评阅专家2评阅专家3评阅专家4评阅专家5 摘 要 本文运用离散数学的知识针对最短路问题进行求解，采用Dijkstra标号法对所给线路进行分析。由于福格环游世界的方向是向东开始行进的，所以问题确定为有向图问题。并针对图中一些确实的数据作出相应的合理假设和处理，最终得出较为合理的结果。 首先，明确题目中要求的问题： 通过合理假设和实际地理位置等因素来最终确定15—19,31—32两条线路所需时间。 分别找到从伦敦、纽约或上海出发环游世界的最佳路线。 然后，针对第一个问题，分为水路和陆路两种情况考虑。充分查找网上资源，利用谷歌地图对相应城市之间的距离进行估测，对于水路，通过城市之间的线路和相应时间关系得出时间和距离的比例关系。从而得出要求的时间。对于陆路，查资料的当时该地区还没有铁路这一最快捷的交通工具，最终以马车为例进行估算，得出结果。 最后采用Dijkstra标号法对相应的城市进行编号，利用lingo软件编程得出路线，并考虑时差问题得出最终的结果如下： 出发地所需时间线路考虑时差不考虑时差伦敦79801—6—7—12—17—22—23—28—31—32—35—37—39—41—47—50—53—1纽约757653—2—4—7—12—17—22—23—28—31—32—35—37—39—41—47—50—53上海757637—39—41—47—50—53—2—4—7—12—17—22—23—28—31—32—35—37由表中可知，从纽约出发和从上海出发环游世界的路线除出发地点不同外，是完全相同的。 关键字：离散数学 Dijkstra标号法 有向图 lingo 时差 正文部分 问题重述 本题主要是探讨在已知环游世界不同路线的交通网络图和每段路线所需要的天数的情况下，如何选择旅游线路，使环游世界所需要的时间最少。 在儒勒·凡尔纳的著名小说《环游世界80天》中，英国绅士福格在伦敦与人打赌能够在80天内环游世界，这在当时的1872年??一个了不起的壮举。当时最快的旅行方式是火车和轮船，然而世界上大部分地区还是靠马车、大象、驴子或者步行来旅行。下面是一个从伦敦环游世界不同路线的交通网络图，福格选择的是往东走，每段路线所需要的天数显示在图上，旅行的时间基于1872年能采用的旅行方式以及距离。 （1）请设计一个算法为福格选择一条最佳路径，即环游世界天数最短，你选择的路径能让他赢得赌注吗？ （2）如果他在别的地方与人打赌，比如纽约或者上海，结果会怎样？ 问题分析 选择一条最佳的路径即找到一条所用时间总和最小的路线。最小路径问题为离散数学研究的领域，本题主要考虑采用Dijkstra标号法求解。仔细观察发现问题给出的路线中有两条线路的时间是未知的，分别为15—19,31—32。需要通过合理的假设和实际地理位置等因素来最终确定两条线路所需时间。 综上需要解决的问题有两个： 1、通过合理假设和实际地理位置等因素来最终确定15—19,31—32两条线路所需时间。 2、分别找到从伦敦、纽约或上海出发环游世界的最佳路线。 模型假设 为了建立数学模型求解，进行以下假设： 本题主人公一直向东航行，途中没有返航； 图中所给的每一条线路都是安全可行的； 不考虑主人公在城市中逗留的时间； 不考虑主人公换乘交通工具所需要的时间； 主人公在旅行途中没有患病。 符号说明 A 表示主人公的出发地 Bi 表示途径的城市（i取1—54） C 表示返回地点（实际与出发地为同一城市，不同的表示为便于程序设计） 模型建立 1、算法说明 （1）最短路问题： 设图G=V,E,给定W：E→R，对G的每一条边e，称W(e)为边e的权。把这样的图称为带权图，记作G=v,E,W。当e=（u，v）（u,v）,把W(e)记作W(u,v). 设P是G的一条通路，P中所有边的权之和称为P的长度，记作W(P),即W(P)=e∈E(p)W(e) 。类似地，可定义回路C的长度W(C)。 最短路问题：给定带权图G=V,E,W及顶点u和v，其中每条边e的权W(e)为非负实数，求从u到v的最短路径。 （2）Dijkstra标号法 输入：带权图G=V,E,W和s∈V，其中｜Ｖ｜＝ｎ，?ｅ∈Ｅ，Ｗｅ≥０ 　输出：ｓ到Ｇ中的每一点的最短路径及距离 令ｌ（ｓ）←ｓ，０，ｌｖ←ｓ，＋∞　ｖ∈Ｖ-ｓ，ｉ←１， ｌ（ｓ）是永久标号，其余标号均为临时标号，ｕ←ｓ ｆｏｒ与ｕ关联的临时标号的顶点ｖ if　 ｌ２ｕ＋Ｗｕ，ｖ＜ｌ２ｖｔｈｅｎ　令ｌｖ←ｕ，