创业收益的规划模型

基于Dijkstra算法的环游世界最佳路径选择数学建模协会编号：69姓名1：李明宇姓名2：杨军姓名3：艾建行指导教师：李学文评阅编号：评阅专家1评阅专家2评阅专家3评阅专家4评阅专家5摘要本文根据题中所给数据，通过建立基于Dijkstra算法的最短路径模型，为著名的《80天环游世界》中福格的壮举选取最优路径，从而判断出基于当时的交通环境不能实现该想法，同时解决了当起点发生改变时能否通过寻找最佳路径，达到在一定时间内完成环游世界的目的。在具体求解过程中，我们将从伦敦环游世界的不同路线的交通网络图划分成五个小区域，然后利用Dijkstra算法求取出各个区域的不同起点到各个终点的最短路径，然后将五个区域组合，得到简化后的环游世界的交通网络图，最后用同一算法得到从伦敦出发，环游世界的最短天数为81天，最佳路径为：1伦敦6Pairs7Barcelona12Budapest17Athens22Cairo23Aden28Bombay31Calcutta33Singapore35HongKong37Shanghai39Yokohama41SanFrancisco47Denver50Chicago53NewYork1伦敦，从而得出他不能赢得赌注的结论，同时，80天与81天相差不多，且注意到题中31-32﹑15-19之间所需天数未给出，若已知该时间且不长，则很有可能所需天数少于80天。运用类似方法计算出当环游世界的起点变为上海时，依据同一交通路线图并且在交通环境没有变化的前提下，得到环游世界的最短天数为77天，最短路径为：37Shanghai39Yokohama41SanFrancisco47Denver50Chicago53NewYork2Lisbon4Madrid7Barcelona12Budapest17Athens22Cairo23Aden28Bombay31Calcutta33Singapore35HongKong37Shanghai，从而得到此时他可以赢得赌注的结论。最后，我们对Diskstra算法进行了优化，从而提高了求最短路径时的运行速度，增加了算法的执行效率。关键字：Dijkstra算法最优路径分区简化标号法一问题重述在儒勒·凡尔纳的著名小说《环游世界80天》中，英国绅士福格在伦敦与人打赌能够在80天内环游世界，这在当时的1872年是一个了不起的壮举。当时最快的旅行方式是火车和轮船，然而世界上大部分地区还是靠马车、大象、驴子或者步行来旅行。下面是一个从伦敦环游世界不同路线的交通网络图，福格选择的是往东走，每段路线所需要的天数显示在图上，旅行的时间基于1872年能采用的旅行方式以及距离。请设计一个算法为福格选择一条最佳路径，即环游世界天数最短，你选择的路径能让他赢得赌注吗？如果他在别的地方与人打赌，比如纽约或者上海，结果会怎样？交通网络图如下：二问题分析1.对问题一的分析：问题一要求通过设计一个算法选择最佳路径，并判断福格是否能在八十天内环游世界。我们可以通过将题中所给的交通网络路线图分区域寻找最佳路径，达到简化的效果，最后得到合并后的简化的交通路线图，从而得到最短路径以及此时所需的时间。2.对问题二的分析：问题二将环游世界的起点改变为上海或纽约，在此我队对从上海出发继续向东旅行的情况利用相似的方法进行求解，从而判断出此时的最短路径及所需最少的时间。三模型假设与符号说明(一)模型假设题中所给的交通网络路线图所提供的时间准确。福格在旅行中没有发生意外情况导致旅行路线发生改变。起点改变时其他条件均不变。除出发点外，每个地点只到达一次。(二)符号说明由顶点V,弧A,和权值W组成的有向网络PD中从到的一条路P中所有弧的权之和到自身的长度四模型建立与求解1问题一的分析与求解（1）模型的引入：取最短路径问题给定有向网络，任意弧，有权，给定D中的两个顶点，。设P是D中从到的一条路，定义路P的权（长度）是P中所有弧的权之和，记为。最短路问题就是要在所有从到的路中，求一条路P0，使称是从到的最短路。路P0的权称为从到的路长,记为。Dijkstra算法思想：将中到所有其它顶点的最短路按其路长从小到大排列为：表示到自身的长度，相应最短路记为：一定只有一条弧，记取最小值的点为，。假定的值已求出，对应的最短路分别为：记则使上式达到最小值的点可取为。计算过程中可采用标号方法：中的点，值是到的最短路长度，相应的点记“永久”标号；中的点，值是到的最短路长度的上界，相应的点记“临时”标号，供进一步计算使用。前点标号:表示点到的最短路上的前一点。如，表示vs到的最短路上前一点是。Dijkstra算法步骤：第1步：令,则令，,,，第2步：(选永久标号)在中选一点，满足如果，停止，从到中各点没有路；否则，转第3步。第3步：（给点永久性标号）令如果，结束，到所有的点的最短路已经求得；否则，转第4步。第4步：(修改临时标号)对所有，如果，令否则,不变,把k换成k+1，返回第2步。（2）模型的求解：交通网络图如下：在这张地图上所涉及的共有54个点，若再加上周期延拓，该数字将达到60，将这60个点之间的关系表现在矩阵中，不仅会造成输入繁琐﹑出错可能性大、移植性差等问题，还由于矩阵所占空间与点的个数成二次曲线，点过多将大幅度提升计算机的负担，延长运算时间，降低模型的效果。因此我们将这个地图分为5个模块，每个模块中含有921个点不等，有效提高了建模的效率。这5个模块分别如下所示：模块1简化后结果：上图中，以伦敦为出发点，分别以18（St.Peterburg）、19（Moscow）、20（Kiev）、21（Istanbul）、17（Athens）为终点，得出了由起点到各终点的最短时间分别为9﹑13﹑13﹑10﹑11天。模块2简化后结果：模块2以模块1的终点：18（St.Peterburg）、19（Moscow）、20（Kiev）、21（Istanbul）、17（Athens）为起点，以27（Novosibirsk）、24（Tehran）、23（Aden）为终点，得出了各起点至终点的最短天数。图中数字含义同模块1.模块3简化后结果：模块3以模块2的终点：27（Novosibirsk）、24（Tehran）、23（Aden）为起点，以34（Beijing）、37（Shanghai）、35（HongKong）、33（Singapore）为终点，得出由各起点至终点的最短天数。模块4简化后结果：该模块原理同前模块，以34（Beijing）、37（Shanghai）、35（HongKong）、33（Singapore）为起点，以42（Seattle）、41（SanFrancisco）、43（LosAngeles）45（Panama）为终点。模块5简化后结果：以上为模块5，以42（Seattle）、41（SanFrancisco）、43（LosAngeles）45（Panama）为起点，1（伦敦）、2（Lisbon）、3（Casablanca）为终点，本模块中本不需要2（Lisbon）3（Casablanca），只需要终点伦敦即可，但考虑到模块的完整性和后面模型的需要将其加入。经过以上模块的分解，我们将一个很大的地图化解为5个较小的图，这5个模块的起点与终点之间的所有点就可以忽略不计，只考虑起点与终点之间的天数即可，将一个54点的图化为了1+5+3+4+4=17点的图，再将这个17点图带入Dijkstra算法中求解即可得出最短天数的路径为：1伦敦6Pairs7Barcelona12Budapest17Athens22Cairo23Aden28Bombay31Calcutta33Singapore35HongKong37Shanghai39Yokohama41SanFrancisco47Senver50Chicago53NewYork1伦敦所需最短天数为：81天。80天与81天相差不多，且注意到题中31-32﹑15-19之间所需天数未给出，若已知该时间且不长，则很有可能所需天数少于80天。2模型二的求解：从上海绕行与从伦敦绕行思路相同，只是模块稍有不同：模块1：本模型中上海作为起点34（Beijing）35（HongKong）33（Singapore）本不需要，但考虑到模块的完整性这里将其加入，图中数字与前相同。模块2：模块3：模块4：模块5：利用Dijkstra算法中求解即可得出最短天数的路径为：37Shanghai39Yokohma41SanFrancisco47Senver50Chicago53NewYork2Lisbon4Madrid7Barcelona12Budapest17Athens22Cario23Aden28Bombay31Calutta33Singapore35HongKong37Shanghai最短天数为77天，得出他如果在上海出发，则可以赢得赌注。五模型优化由于经典Dijkstra算法在节点个数较多时会出现运行效率低，内存占用大，出错率高，灵活性差等缺点，于是我们对经典Dijkstra算法进行了优化，对搜索网络进行了分区域处理得到“优化Dijkstra算法”从模型的求解过程可以看出，若将该地图分为几个模块，即使要换一个地点来计算最短时间也可以很快解决，直接套用原模块即可，但是若将整个地图全部输入矩阵中，一旦更换地点，将不得不重新输入图矩阵，图的规模越大，这样所浪费的时间越多，出错率越高，分块的优点就充分体现了出来。优化Dijkstra算法与原始Dijkstra算法的搜索范围比较示意图如图2．2所示。由图2．2可见，原始Dijkstra算法的搜索过程(见图2．2a)，是以源点为圆心的一系列同心圆，搜索过程没有考虑终点所在的方向或位置，在从源点出发的搜索过程中，其他结点与终点被搜索到的概率是相同的。“优化Dijkstra算法”的搜索过程(见图2．2b)是以源点和终点为焦点的一系列“同心椭圆”，永久标记点的选取原则为：当前结点距源点的最短距离与此结点到终点的直线距离之和最小者被选取为永久标记点。所以搜索过程趋向于终点，搜索过程到达终点的速度明显快于原始Di]kstm算法，搜索到的结点也少于原始Dijkstra算法。六参考文献[1]费培之图和网络及其应用四川大学出版社1996.8[2]李雷基于地图分区算法求解动态最佳路径的研究与实现江苏大学硕士学位论文2004.6[3]杨长保，王开义，马生密一种晟短路径分析优化算法的实现吉林大学学报(信息科学版)．第20卷，第2期，2002年6月[4]柬涛，范东明OlS分析中最短路径问题的圈论解决方法四川测绘，2002年04期七附录function[S,D]=minRoute(i,m,W)%图与网络论中求最短路径的Dijkstra算法M-函数%i为最短路径的起始点,m为图顶点数,W为图的带权邻接矩阵，%不构成边的两顶点之间的权用inf表示。显示结果为：S的每%一列从上到下记录了从始点到终点的最短路径所经顶点的序号；%D是一行向量，记录了S中所示路径的大小;dd=[];tt=[];ss=[];ss(1,1)=i;V=1:m;V(i)=[];dd=[0;i];%dd的第二行是每次求出的最短路径的终点，第一行是最短路径的值kk=2;[mdd,ndd]=size(dd);while~isempty(V)[tmpd,j]=min(W(i,V));tmpj=V(j);fork=2:ndd[tmp1,jj]=min(dd(1,k)+W(dd(2,k),V));tmp2=V(jj);tt(k-1,:)=[tmp1,tmp2,jj];endtmp=[tmpd,tmpj,j;tt];[tmp3,tmp4]=min(tmp(:,1));iftmp3==tmpd,ss(1:2,kk)=[i;tmp(tmp4,2)];else,tmp5=find(ss(:,tmp4)~=