创业收益的规划模型

《创业收益的规划模型》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、基于Dijkstra算法的环游世界最佳路径选择数学建模协会编号：69姓名1：李明宇姓名2：杨军姓名3：艾建行指导教师：李学文评阅编号：评阅专家1评阅专家2评阅专家3评阅专家4评阅专家518摘要本文根据题中所给数据，通过建立基于Dijkstra算法的最短路径模型，为著名的《80天环游世界》中福格的壮举选取最优路径，从而判断出基于当时的交通环境不能实现该想法，同时解决了当起点发生改变时能否通过寻找最佳路径，达到在一定时间内完成环游世界的目的。在具体求解过程中，我们将从伦敦环游世界的不同路线的交通网络图划分成五个小区域

2、，然后利用Dijkstra算法求取出各个区域的不同起点到各个终点的最短路径，然后将五个区域组合，得到简化后的环游世界的交通网络图，最后用同一算法得到从伦敦出发，环游世界的最短天数为81天，最佳路径为：1伦敦6Pairs7Barcelona12Budapest17Athens22Cairo23Aden28Bombay31Calcutta33Singapore35HongKong37Shanghai39Yokohama41SanFrancisco47Denver50Chicago53NewYork1伦敦，从而得出他不

3、能赢得赌注的结论，同时，80天与81天相差不多，且注意到题中31-32﹑15-19之间所需天数未给出，若已知该时间且不长，则很有可能所需天数少于80天。运用类似方法计算出当环游世界的起点变为上海时，依据同一交通路线图并且在交通环境没有变化的前提下，得到环游世界的最短天数为77天，最短路径为：37Shanghai39Yokohama41SanFrancisco47Denver50Chicago53NewYork2Lisbon4Madrid7Barcelona12Budapest17Athens22Cairo23Ad

4、en28Bombay31Calcutta33Singapore35HongKong37Shanghai，从而得到此时他可以赢得赌注的结论。最后，我们对Diskstra算法进行了优化，从而提高了求最短路径时的运行速度，增加了算法的执行效率。关键字：Dijkstra算法最优路径分区简化标号法18一问题重述在儒勒·凡尔纳的著名小说《环游世界80天》中，英国绅士福格在伦敦与人打赌能够在80天内环游世界，这在当时的1872年是一个了不起的壮举。当时最快的旅行方式是火车和轮船，然而世界上大部分地区还是靠马车、大象、驴子或者步

5、行来旅行。下面是一个从伦敦环游世界不同路线的交通网络图，福格选择的是往东走，每段路线所需要的天数显示在图上，旅行的时间基于1872年能采用的旅行方式以及距离。1．请设计一个算法为福格选择一条最佳路径，即环游世界天数最短，你选择的路径能让他赢得赌注吗？2．如果他在别的地方与人打赌，比如纽约或者上海，结果会怎样？交通网络图如下：18二问题分析1.对问题一的分析：问题一要求通过设计一个算法选择最佳路径，并判断福格是否能在八十天内环游世界。我们可以通过将题中所给的交通网络路线图分区域寻找最佳路径，达到简化的效果，最后得到

6、合并后的简化的交通路线图，从而得到最短路径以及此时所需的时间。2.对问题二的分析：问题二将环游世界的起点改变为上海或纽约，在此我队对从上海出发继续向东旅行的情况利用相似的方法进行求解，从而判断出此时的最短路径及所需最少的时间。三模型假设与符号说明(一)模型假设1.题中所给的交通网络路线图所提供的时间准确。2.福格在旅行中没有发生意外情况导致旅行路线发生改变。3.起点改变时其他条件均不变。4.除出发点外，每个地点只到达一次。(二)符号说明由顶点V,弧A,和权值W组成的有向网络PD中从到的一条路P中所有弧的权之和到自

7、身的长度四模型建立与求解1问题一的分析与求解（1）模型的引入：取最短路径问题给定有向网络，任意弧，有权，给定D中的两个顶点，。设P是D中从到的一条路，定义路P18的权（长度）是P中所有弧的权之和，记为。最短路问题就是要在所有从到的路中，求一条路P0，使称是从到的最短路。路P0的权称为从到的路长,记为。Dijkstra算法思想：将中到所有其它顶点的最短路按其路长从小到大排列为：表示到自身的长度，相应最短路记为：一定只有一条弧，记取最小值的点为，。假定的值已求出，对应的最短路分别为：记则使上式达到最小值的点可取为。计

8、算过程中可采用标号方法：中的点，值是到的最短路长度，相应的点记“永久”标号；中的点，值是到的最短路长度的上界，相应的点记“临时”标号，供进一步计算使用。前点标号:表示点到的最短路上的前一点。如，表示vs到的最短路上前一点是。Dijkstra算法步骤：18第1步：令,则令，,,，第2步：(选永久标号)在中选一点，满足如果，停止，从到中各点没有路；否则，转第3步。第3步：（给