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

PAGE \* MERGE?FORMA?T 12 环游世界路?程规划问题?的分析 环游世界路?程规划 问题的分析? 数学建模协?会编号：28 钟嘉鸣 虞程凯 郑明晔 指导教师：房永飞 评阅编号： 评阅专家1? 评阅专家2? 评阅专家3? 评阅专家4? 评阅专家5? 摘 要 本文综合运?用了Dij?kstra?算法、Floyd?算法和最短?路径问题的?0—1规划模型?等多种算法?和Matl?ab、Lingo?等多种编程?软件，在确定以伦?敦为起（终）点的环游世?界的最佳（最短）路径、以其他地点?为起（终）点的环游世?界的最佳（最短）路径等两个?问题上做出?了严密的解?答。解答过程层?层递进，结果相互印?证。 首先对题目?中所给的地?图进行了预?处理。将地图中左?右两侧相同?的地点进行?了拼接，使之只出现?一次，并将起点左?侧与之相连?的直线进行?了切割，并填入序号?为55的终?点。并且根据单?向（即向东）的路径网络?(详见附录) 将网络交通?图抽象成为?有（无）向图模型，得到带权邻?接矩阵以便?求解。 然后通过D?ijkst?ra算法、Floyd?算法和最短?路径问题的?0—1规划三种?算法对以伦?敦为始、终点的环游?世界的最佳?（最短）路径问题进?行了求解，用三种方法?所得的最短?路径和相应?的天数完全?相同，增加了所得?结论的可靠?性。 对于第二问?，通过Mat?lab的程?序优化，本文建立通?用的有向图?模型，得到了通用?的带权邻接?矩阵，通过改进算?法和程序，求得了以5?4个城市为?起点环游世?界的最短路?径和相应的?天数。从而得到可?以在80天?内环游世界?并作为起点?的城市，很好地解决?了第二问。 之后我们对?模型进行了?评价与检验?，讨论了题中?两段不确定?路径对结果?的影响，并对模型进?行了推广应?用。 本文主要有?三个亮点：第一、在第一个问?中同时利用?三种方法进?行平行求解?，并得到了完?全相同的结?论，说明了模型?的可靠性；第二、基于第一问?中的Flo?yd算法，建立通用的?有向图模型?和带权邻接?矩阵，方便而快速?地求得了以?任何一点为?起点环游世?界的最短路?径及相应天?数；第三、在第二个问?的基础上，我们又对模?型进行了推?广，并对模型提?出了严谨的?评价与检验?，深入地分析?了问题。 关键字：最短路径 Dijks?tra算法?Floyd?算法 0—1整数规划? 有向图模型? 正文部分 问题重述 本题以儒勒?·凡尔纳的著?名小说《环游世界8?0天》中，英国绅士福?格在伦敦与?人打赌环游?世界的故事?为背景，提出了路程?规划的相关?问题。 在小说《环游世界8?0天》中，英国绅士福?格在伦敦与?人打赌能够?在80天内?环游世界，这在当时的?1872年?是一个了不?起的壮举。当时最快的?旅行方式是?火车和轮船?，然而世界上?大部分地区?还是靠马车?、大象、驴子或者步?行来旅行。下面是一个?从伦敦环游?世界不同路?线的交通网?络图，福格选择的?是往东走，每段路线所?需要的天数?显示在图上?，旅行的时间?基于187?2年能采用?的旅行方式?以及距离。要求解答以?下两个问题?： 请设计一个?算法为福格?选择一条最?佳路径，即环游世界?天数最短，你选择的路?径能让他赢?得赌注吗？ 如果他在别?的地方与人?打赌，比如纽约或?者上海，结果会怎样?？ 图表 SEQ 图表 \* ARABI?C 图表 SEQ 图表 \* ARABI?C 1 题图：从伦敦环游?世界不同路?线的交通网?络图 问题分析 本题为典型?的离散规划?问题。对于问题一?，是寻找路径?最短的规划?问题，可以由离散?数学中Di?jkstr?a算法、Floyd?算法和0-1整数规划?算法求解，得到的结果?应该是一条?具体的路径?和相应的路?程。对于问题二?，根据解决第?一问的方法?，利用mat?lab编程?找到以任何?一个点为起?点环绕地球?一周所用的?最短天数，从而找出在?80天内可?以环绕地球?一周起点（与终点），即说明在这?些点所代表?的地方与别?人打赌可以?赢。本题涉及的?点较多，并且数据以?图片形式给?出，需要对数据?进行预处理?。 数据的预处?理 观察题图可?以发现，图中有两段?路径没有给?出相应的路?程，我们通过查?找地图上两?点之间的距?离，类比于相似?旅行方式的?路径，按比例求出?相应的路程?。 我们将利用?Dijks?tra算法?、Floyd?算法和0-1整数规划?算法求解本?题，因此要将地?图转化为有?向图或者无?向图模型，所以首先要?将地图上的?数据整理为?有（无）向图矩阵。我们可以利?用matl?ab编程对?数据进行整?理。 问题一的分?析 对于问题一?，我们将问题?抽象成一个?有向图，每一个城市?由一个标有?数字的点代