28钟嘉鸣虞程凯郑明晔a环游世界路程规划问题的分析

《28钟嘉鸣虞程凯郑明晔a环游世界路程规划问题的分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、环游世界路程规划问题的分析数学建模协会编号：28钟嘉鸣虞程凯郑明晔指导教师：房永飞评阅编号：评阅专家1评阅专家2评阅专家3评阅专家4评阅专家519环游世界路程规划问题的分析摘要本文综合运用了Dijkstra算法、Floyd算法和最短路径问题的0—1规划模型等多种算法和Matlab、Lingo等多种编程软件，在确定以伦敦为起（终）点的环游世界的最佳（最短）路径、以其他地点为起（终）点的环游世界的最佳（最短）路径等两个问题上做出了严密的解答。解答过程层层递进，结果相互印证。首先对题目中所给的地图进行了预处理。将地图中左右两侧相同的地点进行了拼接，使之只出现一次，并将起点左侧与之相连的

2、直线进行了切割，并填入序号为55的终点。并且根据单向（即向东）的路径网络(详见附录)将网络交通图抽象成为有（无）向图模型，得到带权邻接矩阵以便求解。然后通过Dijkstra算法、Floyd算法和最短路径问题的0—1规划三种算法对以伦敦为始、终点的环游世界的最佳（最短）路径问题进行了求解，用三种方法所得的最短路径和相应的天数完全相同，增加了所得结论的可靠性。对于第二问，通过Matlab的程序优化，本文建立通用的有向图模型，得到了通用的带权邻接矩阵，通过改进算法和程序，求得了以54个城市为起点环游世界的最短路径和相应的天数。从而得到可以在80天内环游世界并作为起点的城市，很好地解决了

3、第二问。之后我们对模型进行了评价与检验，讨论了题中两段不确定路径对结果的影响，并对模型进行了推广应用。本文主要有三个亮点：第一、在第一个问中同时利用三种方法进行平行求解，并得到了完全相同的结论，说明了模型的可靠性；第二、基于第一问中的Floyd算法，建立通用的有向图模型和带权邻接矩阵，方便而快速地求得了以任何一点为起点环游世界的最短路径及相应天数；第三、在第二个问的基础上，我们又对模型进行了推广，并对模型提出了严谨的评价与检验，深入地分析了问题。关键字：最短路径Dijkstra算法Floyd算法0—1整数规划有向图模型19环游世界路程规划问题的分析正文部分问题重述本题以儒勒·凡尔

4、纳的著名小说《环游世界80天》中，英国绅士福格在伦敦与人打赌环游世界的故事为背景，提出了路程规划的相关问题。在小说《环游世界80天》中，英国绅士福格在伦敦与人打赌能够在80天内环游世界，这在当时的1872年是一个了不起的壮举。当时最快的旅行方式是火车和轮船，然而世界上大部分地区还是靠马车、大象、驴子或者步行来旅行。下面是一个从伦敦环游世界不同路线的交通网络图，福格选择的是往东走，每段路线所需要的天数显示在图上，旅行的时间基于1872年能采用的旅行方式以及距离。要求解答以下两个问题：（1）请设计一个算法为福格选择一条最佳路径，即环游世界天数最短，你选择的路径能让他赢得赌注吗？（2）

5、如果他在别的地方与人打赌，比如纽约或者上海，结果会怎样？图表1题图：从伦敦环游世界不同路线的交通网络图以下是题中所给地图：问题分析本题为典型的离散规划问题。对于问题一，是寻找路径最短的规划问题，可以由离散数学中Dijkstra算法、Floyd算法和0-1整数规划算法求解，得到的结果应该是一条具体的路径和相应的路程。对于问题二，根据解决第一问的方法，利用matlab编程找到以任何一个点为起点环绕地球一周所用的最短天数，从而找出在80天内可以环绕地球一周起点（与终点），即说明在这些点所代表的地方与别人打赌可以赢。本题涉及的点较多，并且数据以图片形式给出，需要对数据进行预处理。1.数据

6、的预处理19环游世界路程规划问题的分析观察题图可以发现，图中有两段路径没有给出相应的路程，我们通过查找地图上两点之间的距离，类比于相似旅行方式的路径，按比例求出相应的路程。我们将利用Dijkstra算法、Floyd算法和0-1整数规划算法求解本题，因此要将地图转化为有向图或者无向图模型，所以首先要将地图上的数据整理为有（无）向图矩阵。我们可以利用matlab编程对数据进行整理。1.问题一的分析对于问题一，我们将问题抽象成一个有向图，每一个城市由一个标有数字的点代表（正如题中所示）。其中1代表起点伦敦，2～54代表沿途的城市，以55代表终点。将每段路径所需花费的时间记为该段路径的权

7、值。由于题目规定只能向东移动，我们就将每条路径设为单向，并对地图进行整理以便整理相应的矩阵。由此，将问题抽象为最短路径问题模型。考虑到模型中每段路径的权值非负，可以用Dijkstra算法、Floyd算法和0-1整数规划算法，用matlab和lingo软件编程求解出最短环绕地球路径及对应的天数。2.问题二的分析对于问题二，我们首先以上海和纽约为起点（和终点），求出环绕地球的最短路径。再将问题推广：在哪些城市打赌自己能在80天内环游世界能赢？这样就可以很好地解答第二问。为此，我们根据