最短路径分析

分类号密级编号2015届本科生毕业论文题目基于AHP决策分析法和Dijkstra算法的最短路径学院资源与环境工程学院姓名杜玉琪专业地理科学学号20111040205指导教师王荣提交日期2015年5月8日天水师范学院2015届毕业论文1原创性声明本人郑重声明：本人所呈交的论文是在指导教师的指导下独立进行研究所取得的成果。学位论文中凡是引用他人已经发表或未经发表的成果、数据、观点等均已明确注明出处。除文中已经注明引用的内容外，不包含任何其他个人或集体已经发表或撰写过的科研成果。本声明的法律责任由本人承担。论文（设计）作者签名：指导老师签名：签名日期:2013年5月18日目录天水师范学院2015届毕业论文20引言...................................................................................................................31研究区概况.......................................................................................................42.数据来源与研究方法........................................................................................42.1数据来源....................................................................................................42.2研究方法....................................................................................................52.2.1AHP决策分析方法..............................................................................52.2.2Dijkstra算法.........................................................................................63实例分析............................................................................................................73.1基于AHP对3A级景区决策分析........................................................73.1.1层次结构模型的构造..........................................................................73.1.2模型计算过程......................................................................................83.1.3结果分析............................................................................................103.2基于Dijkstar算法对3A级景点旅游路线的设计................................103.2.1旅游路线模型构造............................................................................103.2.2模型计算与分析................................................................................134结语..................................................................................................................13参考文献.................................................................................................14致谢...................................................................................................................15基于AHP决策分析法和Dijkstar算法的最短路径分析天水师范学院2015届毕业论文3——以天水市3A级旅游景点为例杜玉琪(天水师范学院资源与环境工程学院甘肃天水741000）摘要：随着西部旅游业的发展，旅游最佳路线的选择变得越来越重要。本文运用AHP决策分析的方法进行综合评价分析天水市众多旅游景点中的麦积石窟、伏羲庙、玉泉观、南郭寺、大象山、武山水帘洞、清水温泉，这7个3A级景点各自的旅游价值。再通过Dijkstar算法，对上述旅游景点的最短旅游路线的选择进行研究，最终为不同要求的游客提供出最佳的旅游路线。关键字：AHP决策分析；Dijkstar算法；最短路径分析；天水市BasedontheAHPdecisionanalysismethodandtheanalysisofDijkstaralgorithmoftheshortestpath——intianshui3a-classtouristattractionsasanexampleAbstract：Withthedevelopmentofthewesterntourism,tourismoptimalroutechoiceisbecomingmoreandmoreimportant.ThisarticleappliesthemethodofAHPdecisionanalysisoncomprehensiveevaluationanalysisofthenumeroustouristattractionstianshuiwheatproduct,yuquanview,nanguotemplegrottoes,fuxitemple,theelephant,wushanwaterfallcave,waterhotsprings,thesevenaaascenicspottourismvalue.AgainthroughtheDijkstraalgorithm,thechoiceofthetouristattractionsoftheshortesttravelroute,finallyfordifferentrequirementsofthebesttravelroutefortourists.Keywords:Analytichierarchyprocess;Dijkstar;Shortestpath;tianshuicity0引言随着西部旅游业如火如荼的发展，天水市自驾旅游开始被越来越多的人选择。自驾车旅游者追求以最少的花销走更远的路，看更优美的风景。因此设计出一条多景点间距离最短（或费用，时间最少）的旅游线路是自驾车游客的现实需求[1]。而对于旅游景点的评价及旅游线路的选择问题,是旅游学术界一直关注的课题。众多学者所采用的方法，大体可归纳为主观定性评价和客观定量评价。景点评价方法在我国开展的时间并不长，主要侧重定性描述，较缺乏定量天水师范学院2015届毕业论文4模型研究。定量评价方法分为单项评价和综合评价，综合评价的方法中的“多因素模糊评价法”是近些年发展起来的方法。但由于旅游景点特征具有客观不确定性，在制定评价指标时要考虑到多重因素，不能较好的体现旅游者的不同旅游要求与可得性程度。而AHP决策分析法既能体现定性评价中的旅游者可得性供给程度,也能得出的旅游资源评价指标体系中相关要素按隶属关系从而分为若干层次，再请有经验的专家对各层次各因素的相对重要性给出定量指标，最后利用数学方法综合其权值[2]。为了体现天水历史文化和民俗风情，本文在旅游地选择问题上应用AHP决策分析的方法，最终选择出天水市3A级旅游景点中的7个旅游地。以天水市7个景点旅游路线选择问题为例，通过Dijkstar算法得出天水市自驾旅游的最佳路径。1研究区概况天水作为历史文化名城，位于甘肃省东南部，地处陕、甘、川三省交界，全境介于东经104°35′～106°44′、北纬34°05′～35°10′之间，市区平均海拔高度为1100米。天水历史悠久，文化源深，人文荟萃相传华夏始祖伏羲氏诞生于此，因此又有“羲皇故里”之称[3]。境内交通方便，旅游资源丰富，目前已形成了伏羲文化、秦文化、三国文化、明清建筑文化、民俗风情文化等多元文化景观，其中麦积山石窟作为我国四大石窟之一具有“东方雕塑馆”的美称，周边的风景兼具了江南水乡的秀美和北国山川的雄奇，是国务院公布的第一批风景名胜区。天水人民自古就有祭拜伏羲的习俗，自1988年天水市恢复了公祭伏羲大典,连续多年举办的伏羲祭典，依然成为甘肃和天水重要的对外文化品牌，吸引了众多的海内外华人来天水寻根问祖，祭拜人文始祖。2006年，太昊伏羲祭典荣列国务院首批国家级非物质文化遗产名录。因此天水市旅游开发的潜力十分巨大。2.数据来源与研究方法2.1数据来源首先从天水旅游统计月报中得到相关数据，并进行研究处理分析得出AHP决策分析中的判断值；其次从goolge电子地图中得出各旅游景点间的最短距离和时间，通过比例尺转化得到旅游景点间具体路径权重值。天水师范学院2015届毕业论文52.2研究方法2.2.1AHP决策分析方法美国运筹学家T.L.Saaty于20世纪70年代提出的analytichierarchyprocess，简称AHP决策分析法，是一种决策者通过对复杂问题的决策思维过程模型化，数量化的方法[7]。应用这种方法，可以把复杂问题划分成若干层次和若干因素，在各因素之间进行简单的比较和计算，就可以得出不同方案重要性程度的权重从而为决策方案的选择提供依据[7]。（1）AHP决策分析方法的基本步骤：Step1：明确问题。即弄清问题的范围，所包含的因素以及各因素之间的关系，以便尽量掌握充分的信息。Step2：建立层次结构模型。即将问题所含的要素进行分组，把每一组作为每一层，并将其按照最高层（目标层），若干中间层（准则层）和最低层（对象层）的次序排列起来。Step3：构造判断矩阵。判断矩阵表示针对上一层的某元素而言，评定该层次中各有关元素相对重要性程度的判断。Step4：层次单排序。其目的是对于上层次中的某元素而言，确定本层次与之有联系的各元素重要性次序的权重值。Step5：层次总排序。利用同一层次中所有层次单排序的结果，就可以计算针对上一层而言，本层次所有元素的重要性权重值。层次总排序需要从上到下逐层按顺序进行，对于最高层而言，其层次单排序的结果也就是总排序的结果。（2）AHP决策分析的计算方法（和积法）Step1：将判断矩阵每一列归一化1ijnkikbbb1,2,,in(1)Step2：对按列归一化的判断矩阵，再按行求和1niijjWb1,2,,in(2)Step3：将向量12(,,,)Tin归一化：天水师范学院2015届毕业论文61iinkk1,2,,in(3)则12(,,,)Tin即为所求的特征向量。Step4：计算最大特征根：max1()niiiAWnW