基于GIS的路径规划算法的研究与实现.pdf

《基于GIS的路径规划算法的研究与实现.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于GIS的路径规划算法的研究与实现朱磊2015年1月中图分类号：TQ028.1UDC分类号：540基于GIS的路径规划算法的研究与实现作者姓名朱磊学院名称计算机学院指导教师刘琼昕副教授答辩委员会主席刘玉树教授申请学位工学硕士学科专业计算机科学与技术学位授予单位北京理工大学论文答辩日期2015年1月ResearchandRealizationofPathPlanningAlgorithmbasedonGISCandidateName：ZhuLeiSchoolorDepartment:ComputerSciencea

2、ndTechnologyFacultyMentor:AssociateProf.LiuQiongxinChair,ThesisCommittee：Prof.LiuYushuDegreeApplied:MasterofEngineeringMajor：ComputerScienceandTechnologyDegreeby:BeijingInstituteofTechnologyTheDateofDefence：January，2015研究成果声明本人郑重声明：所提交的学位论文是我本人在指导教师的指导下进行的研究工作

3、获得的研究成果。尽我所知，文中除特别标注和致谢的地方外，学位论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得北京理工大学或其它教育机构的学位或证书所使用过的材料。与我一同工作的合作者对此研究工作所做的任何贡献均已在学位论文中作了明确的说明并表示了谢意。特此申明。签名：日期：北京理工大学硕士学位论文摘要路径规划问题是地理信息系统（GIS）研究领域中的关键内容之一，最短路径的寻找更是热点问题。在数据量较大时，传统前K条最短路径算法效率较低，且不能解决某些实际需求下规划K条差异较大的路径问题。在Dijkstr

4、a算法的基础上，引入有利度与重复度的概念，通过对路径结果重复度的检测以及由有利度的改变所引起的图的变化，循环寻找当前图中的最短路径，从而实现了多条差异路径的规划。与同类算法相比，速度较快，得到的多条路径结果在满足一定重复度要求的同时长度也较为合理。同时，在上述算法的基础上，对野外区域中带状区域的有利度及重复度进行控制，解决了传统前K条最短路径算法所难以满足的野外区域多条差异路径规划问题。关键词：Kth路径；算法；重复度；大规模数据；野外区域I北京理工大学硕士学位论文AbstractPathplanningprobl

5、emisoneofthekeycontentsintheresearchfieldofGeographicInformationSystem(GIS),amongwhichthefindingoftheshortestpathisalwaysahottopic.Whenthereislargequantityofdata,theefficiencyoftraditionalalgorithmsofKthshortestpathsisrelativelylow,andsomepathproblemsconcernin

6、gbigdifferencebetweentheplannedKthpathsunderactualrequirementscannotbesolved.OnthebasisofDijkstraalgorithm,theconceptsoffavorabilityandrepeatabilityareintroducedtofindKthpathsincludingtheshortestinthecurrentgraphcyclicallybydeterminationofrepeatabilityofpathre

7、sultsandthechangeofgraphcausedbythechangeoffavorability,therebyrealizingtheplanningofmultipledifferentpaths.Comparedwithsimilaralgorithms,thisalgorithmisfaster,andthemultiplepathresultsobtainedmeettherequirementforcertainrepeatabilitywhilethelengthsofpathsarea

8、lsoquitereasonable.Inadditional,favorabilityandrepeatabilityofbelt-shapedregionswithinthewildareaarecontrolledbasedontheabovealgorithm,therebyresolvingtheproblemofmultipledifferent