环游世界的计划

《环游世界的计划》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、环游世界的计划评阅专家1评阅专家2评阅专家3评阅专家4评阅专家5摘要1，对这个模型我们运用“Floyd算法”计算最短时路径。2，结果为从伦敦出发打赌会输。从上海或纽约出发打赌会赢。9正文部分一、问题重述环游世界80天在儒勒·凡尔纳的著名小说《环游世界80天》中，英国绅士福格在伦敦与人打赌能够在80天内环游世界，这在当时的1872年是一个了不起的壮举。当时最快的旅行方式是火车和轮船，然而世界上大部分地区还是靠马车、大象、驴子或者步行来旅行。下面是一个从伦敦环游世界9不同路线的交通网络图，福格选择的是往东走，每段路线所需要的

2、天数显示在图上，旅行的时间基于1872年能采用的旅行方式以及距离。1.请设计一个算法为福格选择一条最佳路径，即环游世界天数最短，你选择的路径能让他赢得赌注吗？2.如果他在别的地方与人打赌，比如纽约或者上海，结果会怎样？一、问题分析此题已经简化为了计算从图中一点出发再次回到这一点所需最短时间的问题。由题中题意易知，环游世界时是利用地球做为球体的性质一直朝东或西方向行进最后回到原位置的。观察图中所给点的标号易知由数值小的标号向数值大的标号行进的话则为由西相东行进。由于要算得最短旅行所需时间，而旅行线路为一首尾相接的折线。所以

3、从地球上方观察的话，顺逆时针的方向并不影响旅行总时间。然而由西向东行进时会经过一次国际日期变更线使得旅行时间在以出发地时间计算时会少一天，即所计算时间会比实际时间少一天。同理如果由东向西旅行的话时间9会比实际时间多一天。因此我们默认旅行者均由西向东来环游世界以算得最短时间。此题为一个求最短路径的问题，考虑到此题所涉及的数据较多，我们认为应该使用“Floyd算法”。一、模型假设1，由问题分析中知，我们假设旅行者除了回到出发地时外均为由标号小的城市向标号数值大的城市运行。2，在旅行过程中，假设不会发生任何意外影响旅行时间。3

4、，图中由点15-Minsk到点19-Moscow的距离未给出。根据历史资料，两城市间最短行进时间为5天。我们以此数据来计算题目。4，图中由点31-Calcutta到点32-Bangkok的距离未给出。根据历史资料，两城市间最短行进时间为3天。我们以此数据来计算题目。二、符号说明为避免计算时城市标号干扰计算数值，及在程序中方便调用，将城市按其标号顺序命名为V1,V2,…。三、模型建立我们运用“Floyd算法”计算最短路径，将“Floyd算法”编为一个子函数，然后设置一个TXT文件来输入环游世界图的每个路径长短，我们将每个地

5、点的位置设为v，下标他们的标号以辨别各个位置，比如伦敦标号为1，即伦敦为v1，上海为37，那上海就被表示为v37。Floyd的核心思路为通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。　　从图的带权另接矩阵A=[a(i,j)]n×n开始，递归地进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；……9；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继

6、节点矩阵path来记录两点间的最短路径。算法的过程为：1，从任意一条单边路径开始。所有两点之间的距离是边的权，或者无穷大，如果两点之间没有边相连。　　2，对于每一对顶点u和v，看看是否存在一个顶点w使得从u到w再到v比己知的路径更短。如果是更新它。我们用A[i][j]来表示他们每两点之间需要的时间，如A[1][6]=1，表示从v1到v6需要的时间为1天。因为题设中提到，福格选择了向东走，所以我们不妨把图中的距离变为有向线段，即只能从v1走到v6，不能从v6走到v1。为了能准确的表示从一点到另一点是不能走的，我设置了一个M

7、AX_INT＝10000，来表示他们间的距离是为无穷大。所以我们可以知道A[1][6]=1,但A[6][1]=MAX_INT。在程序中，我将从伦敦,上海和纽约分为3个部分，输入1，2或3就能分别计算从不同的地方出发的不同路径以及时间。因为我们是将图中的数据输入在TXT文件中的，所以在运用C语言程序的时候，我们要将“INPUT1.txt”“INPUT2.txt”“INPUT3.txt”3个文件都要放入D盘下，这样在读入TXT文件的数据时，程序的寻址才是正确的，TXT文件中的数据才能读入程序中。TXT文件的格式是每3个数一排

8、，分别表示路径的起点终点和路径走过需要的时间。在伦敦出发时，为了减少运算量，我们不妨计算一些路径长短来时程序变得简易，使数据更加简单，如假设经过v27有条路径，我将它分别计算了一次，结果表明（v1,v9,v14,v18,v27）这条路径是最短的，所以我将别的路径都归了零，如（v1,v10,v15,v19,v27）,但