最短路问题在旅游线路优化中的应用_曹旭

《最短路问题在旅游线路优化中的应用_曹旭》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、最短路问最短路问题在旅游线路优化中的应用题在旅UsingShortestPathProblemtoOptimizatedtheTouristRoute游线路曹旭张吉吉马少仙优化CaoXuZhangZheMaShaoxian中（西北民族大学数学与计算机科学学院，甘肃兰州730030）的应(SchoolofMathematicsandComputer，NorthwestUniversityforNationalities，GansuLanzhou730030)用摘要：本文利用Floyd算法探究了最短路问题，经过Matlab实现后将其应用到旅游线路优化设计中。选取了甘肃及

2、周边地区13个旅游景点，求得从任意景点出发到任意目的景点的最短路，以及途中必须给定两个景点的最短路问题。关键词：最短路；旅游线路优化中图分类号：F590文献标识码：A文章编号：1671-4792-(2012)2-0115-04Abstract:ThispaperusingtheFloydalgorithmtoexploretheshortestpathproblem,throughMatlabafteritsapplicationtodesignedtouristroute.Select13attractionsinthesurroundingareaingansu

3、province,getfromanyattractionstoanypurposeofscenicspotstheshortestpathandgiventwospotsonthemostShortestpathproblem.Keywords:ShortestPath;OptimizatedtheTouristRoute给定旅游地图，游客在旅行过程中总想从出发的权重代表从一个景点到另一个景点的距离或者时地到目的地的距离最短，以节省费用和时间。例如游间或者费用。上面的问题都可以利用图论中最短路客选取甘肃省及周边地区13个旅游景点，旅游地图问题解决。如图一所示，通过

4、上网收集到各个旅游景点之间的距离如表一所示。在表一中，0表示兰州火车站，1—13分别表示甘肃省及周边旅游景点兴隆山、嘉峪关文物景区、拉卜楞寺、崆峒山、雷台、大佛寺、敦煌、黄河石林、贵清山、青海湖鸟岛景区、塔尔寺、沙坡头、麦积山。∞表示这两个旅游景点之间没有直接到达的交通线路。如何求出任意两点之间的最短距离以及最短路对旅客来说显得尤为重要，比如游客想从兰州火车站出发，前往敦煌鸣沙山月牙泉旅游，如何选择旅游线路的问题。再比如游客在旅行途中必须图一甘肃省及周边地区旅游地图去拉卜楞寺和嘉峪关观光，即选定两个旅游景点后在给定的赋权图G中，求两个互异顶点间的最到达目的地的旅行线

5、路设计。将旅游景点看成图中短路径称之为最短路问题。最短路问题是重要的最的顶点，各个景点的交通路线可看成图上的边，边上优化问题之一，也是图论研究中的一个经典算法问题。最短路问题的应用背景十分广泛，本文将最短路★基金项目:西北民族大学研究生科研创新项目,项问题应用到旅游线路设计中具有很大实用价值。归目编号：YCX10112115科技广场2012.2表一各个旅游景点间的距离表(单位：公里)步骤2：更新dij，对所有的i、j，若dij>dik+dkj，则令dij=dik+dkj。步骤3：若dij<0，则存在一条含有顶点vi的负回路，停止；或者k=n停止；否则跳转到步骤2。1

6、.2最短路的Floyd算法的Matlab实现function[Pu]=f_path(W)%W表示权值矩阵%P表示最短路%u表示最短路的权和%初始化，步骤1n=length(W);U=W;m=1;%步骤2纳起来，最短路问题一般归为两类：一类是求从某个whilem<=n顶点到其他顶点的最短路径；另一类是求图中每一fori=1:n对顶点间的最短路径。关于最短路的研究，目前已forj=1:n经有很多算法，但是基本上是以Dijkstra和Floyd两ifU(i,j)>U(i,m)+U(m,j);种算法为基础，本文利用Floyd算法研究了最短路U(i,j)=U(i,m)+U(m

7、,j);问题在旅游线路优化中的应用。end1求两个旅游景点间的最短路的Floyd算法及其endMatlab实现end1.1最短路的Floyd算法m=m+1;设图G=（V，E），顶点集记作{v1，v2，…，vn}，G的end每条边赋有一个权值，ωij表示边vivj上的权，若vi、u=U(1,n);vj不相邻，则令ωij=+∞。Floyd算法利用了动态规%输出最短路的顶点划的基本思想，即若dik是顶点vi到vk的最短距离，P1=zeros(1,n);dkj是顶点vk到顶点vj的最短距离，则dij=dik+dkj是k=1;顶点vi到顶点vj的最短距离。对于任何一个顶点