基于Floyd算法与最短距离问题的分析.docx

基于floyd算法最短距离的问题分析武昌理工学院摘要本文主要是通过借助floyd算法来求解任意两点间的最短路问题，进而解决货物最快运送，合理设立燃料补给点以及消防站的最佳选址问题。针对问题一：问题一是有关最短运输路线问题，可以将该问题转化为求最短距离对应的路径问题，利用floyd算法通过编程可以得到最快地到达目的地的路径为。针对问题二：本问题是要设计一个简易的公路建设方案，要求燃料补给点到油库之间的公路建设花费最少，也即是燃料补给点到油库的距离最小。借助floyd算法编程求解得到所有将要设立的燃料补给点到油库的最小距离和，最后给出了7个燃料补给点的修建方案图。针对问题三：要求在已给出的10个消防重点单位中选择1个消防重点单位设立消防站。通过floyd算法编程可以求解得到10组消防重点单位到其它的消防单位的距离，再分别取10组中各自的最大距离作对比，得到其中最小值对应的消防单位，最后确定了把消防单位作为消防站的修建地。一、问题重述最短运输路线问题: 每条弧上的数字代表车辆在该路段行驶所需的时间，有向边表示单行道，无向边表示可双向行驶。若有一批货物要从1号顶点运往11号顶点，问运货车应沿哪条线路行驶，才能最快地到达目的地？简易公路建设方案: 某合同战术训练基地为保障即将进行的联合军事演习，准备在原有的1个油库的基础上，再设立7个固定的燃料补给点,为了使联合军事演习正常进行，请为即将新建的7个固定燃料补给点确定合理的修建地址。消防站选址问题: 某城市的开发区中要建一个消防站,其中表示开发区中10个消防重点单位，考虑到交通路况，部分单位之间往返的距离不完全相同，请帮助消防站做出合理的选址。二、问题分析对于问题一，若有一批货物要从1号顶点运往11号顶点，问运货车应沿哪条线路行驶，才能最快地到达目的地？将问题简化为直接求1号顶点到11顶点的最短距离的路径。对于问题二，设立燃料补给点需要考虑到，当联合军事演习的飞机或战车没油时，补充燃料用掉的时间最短。而补充燃料的用时最短，无非就是燃料补给点到油库的距离最短。现在要求设立七个固定燃料点，那么这七个燃料点必须都满足到油库的距离最短，即各燃料点到油库的距离和最短。对于问题三，在10个消防重点单位中，选择一个消防重点单位建立消防站，应该考虑到当火灾发生时，消防站可以及时赶到火灾发生区，即消防站应到最远的消防重点单位的距离也是最小的。可以将问题转化先求每个消防重点单位到其它的消防单位的距离，取它们各自的最大距离作对比，然后得到其中最小值对应的消防单位，最后确定把该消防单位作为消防站。三、符号说明:邻接矩阵:距离矩阵:路径矩阵四、模型建立与求解1. 问题1 模型最短运输路线问题(1)假设1）假设运输路线交通网络图中数据都是准确的，2）货车正常运输，不考虑意外情况的发生，3）忽略在误差范围内的计算误差。4）将运出地与运入地均理想化成点。(2)模型 已知运输路线交通网络图如下所示：运输路线交通网络图由网络图可得邻接矩阵如下通过matlab软件编程（源程序见附件1），借助floyd算法求出距离矩阵如下：求得路径矩阵如下：（3）结果解释与分析1号顶点到11号顶点的距离对应的距离矩阵d的第1行第11列即，而，因此说明1号顶点到11 顶点的最短距离为21，由路径矩阵中可知，1号顶点到11号之间插入了8号顶点，由可知1号顶点到8号顶点之间没有值插入，由可知8号顶点到11号之间插入了9号顶点，由可知8号顶点到9号顶点之间没有值插入，由可知9号顶点到11号之间插入了10号顶点，可知9号顶点到10号顶点之间没有值插入，可知10号顶点到11号顶点之间没有值插入。综上所述可以得到最短距离的路径 即：2. 问题2 模型简易公路建设方案（1）假设1）假设公路花费图给出的数据都是真实有效的，2）忽略在误差范围内的计算误差。3）仅仅只考虑已给定的花费，忽略其他的费用。4）将油库与燃料补给点均理想化成点。（2）模型记油库为，并记7个燃料补给点分别为，。修建公路花费图如下所示：修建公路花费图由公路花费图可写出邻接矩阵如下通过matlab软件编程（源程序见附件2），借助floyd算法求出距离矩阵如下：求得路径矩阵如下： 待设立的7个燃料补给点的最小造价分别对应着距离矩阵中的，将其对应的值分别从矩阵中取出得到1万元，2万元，3万元，6万元4万元，6万元，9万元。（3）结果解释与分析将可得7个燃料补给点的最小造价求和即可得总的造价为31万元。从路径矩阵可以看出将要设立的7个燃料补给点到油库的具体路径如下：它们的最短路径可以表示如下 由上述最短路径可得最佳的修建方案图如下：修建方案图3. 问题3 模型消防站选址问题（1）假设1）假设消防重点单位图给出的数据都是真实有效的，2）忽略在误差范围内的计算误差。3）消防重点单位均理想化成点。（2）模型假设10个消防重点单位分别对应消防重点单位示意图上的,，,。消防重点单位示意图由消防重点单位示意图可得邻接矩阵如下：通过matlab软件编程（源程序见附件3），借助floyd算法求出距离矩阵下： 求得路径矩阵如下：从距离矩阵可以得到任一消防重点单位到其余消防重点单位的最短距离如下：到其余消防重点单位分别为0 5 3 9 5 10 11 9 15 14，到其余消防重点单位分别为9 0 12 4 14 11 9 10 16 12 到其余消防重点单位分别为3 2 0 6 2 7 8 6 12 11，到其余消防重点单位分别为10 1 8 0 10 7 5 6 12 8，到其余消防重点单位分别为5 4 2 8 0 5 6 4 10 9，到其余消防重点单位分别为10 9 7 10 6 0 5 2 8 8 ，到其余消防重点单位分别为10 6 7 5 5 2 0 1 7 3，到其余消防重点单位分别为9 8 6 8 4 1 3 0 6 6，到其余消防重点单位分别为15 14 12 13 10 7 8 6 0 5,到其余消防重点单位分别为13 9 10 8 8 5 3 4 5 0，由以上数据可以制表如下消防重点单位相互距离表053951011915149012414119101612320627861211101801075612854280564109109710605288106755201739868413066151412131078605139108853450151612121010109913（3）结果解释与分析将消防重点单位相互距离表表中第十二行（）的最大值进行对比，可知最小值为9，而最小值9对应的是，说明了相对于其它的消防重点单位来说，它到离它最远的消防单位的距离是10个消防重点单位当中最短的，也即选择为消防站的站址可以使离其最远的消防重点单位在发生火灾时可以尽可能的得到消防站的支援，故应选择消防重点单位作为消防站建设地。五、模型的评价1.模型的优点（1）模型中利用的floyd算法，可以求解任意两点间的距离，这为模型的通用性奠定了一定的基础。（2）采用较为成熟的数学理论建立数学距离最短模型,可信度比较高。 （3）模型的计算采用专业数学软件，可信度较高,便于推广。2模型的缺点 （1）floyd算法用于该模型，会使得模型只适用于理想化状态下的两点之间的情况。（2）模型受限于时间复杂度和数据数量。一旦时间复杂度较高、数据过多，那么就难以借用floyd算法模型进行求解。六、模型的推广（1）模型经过较为严谨的方法得以建立,适用于求解任意两点间的距离以及路径,给出的floyd算法模型对于相关部门有较大的参考价值。（2）本问题的建模思路还可以用于解决移动机器人最短路径规划研究，电力系统应急服务点的选址以及电网故障行波定位等方面的合理规划问题。七、参考文献1 叶其孝 姜启源,数学建模（第四版）,北京,机械工业出版社,2009.42 薛定宇 陈阳泉,高等应用数学问题的matlab求解（第二版）,北京,清华大学出版社,2008.7附录附件一a=0 8 inf inf inf inf 7 8 inf inf inf; inf 0 3 inf inf inf inf inf inf inf inf; inf inf 0 5 6 inf 5 inf inf inf inf; inf inf inf 0 1 inf inf inf inf inf 12 inf inf 6 inf 0 2 inf inf inf inf 10; inf inf inf inf 2 0 9 inf 3 inf inf; inf inf inf inf inf 9 0 inf inf inf inf; 8 inf inf inf inf inf inf 0 9 inf inf; inf inf inf inf 7 inf inf 9 0 2 inf; inf inf inf inf inf inf inf inf 2 0 2; inf inf inf inf 10 inf inf inf inf inf 0;n=size(a,1);d=afor i=1:n for j=1:n r(i,j)=j; endendr for k=1:n for i=1:n for j=1:n if d(i,k)+d(k,j)d(i,j) d(i,j)=d(i,k)+d(k,j); r(i,j)=r(i,k); end end end k d rend附件二a=0 1 2 inf 7 4 8 inf; 1 0 2 3 inf inf 7 inf; 2 2 0 1 5 inf inf inf; inf 3 1 0 3 inf inf 6; 7 inf 5 3 0 3 inf 4; 4 inf inf inf 3 0 2 6; 8 7 inf inf inf 2 0 4; inf inf inf 6 4 6 4 0;n=size(a,1);d=afor i=1:n for j=1:n r(i,j)=j; endendr for k=1:n for i=1:n for j=1:n if d(i,k)+d(k,j)d(i,j) d(i,j)=d(i,k)+d(k,j); r(i,j)=r(i,k); end endendkdrend附件三a=0 9 3 inf inf inf inf inf inf inf; 9 0 inf 4 inf inf inf inf inf inf; 3 2 0 8 2 7 inf inf inf inf; inf 1 8 0 inf inf 5 inf inf 9; inf inf 2 inf 0 8 6 4 inf inf; inf inf 7 inf 9 0 inf 2 inf inf; inf inf inf 5 6 inf 0 1 inf 3; inf inf inf inf 4 1 3 0 6