【精品硕士论文】基于路网的路径查询问题的研究

《【精品硕士论文】基于路网的路径查询问题的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、学校代码：10246学号：12210240025硕士学位论文（科学学位）基于路网的路径查询问题的研究ResearchonRoutingQueriesinRoadNetworks院系：计算机科学技术学院专业：计算机软件与理论姓名：李玉娇指导教师：杨卫东研究员完成日期：2015年4月10日基于路网的路径查询问题的研究ResearchonRoutingQueriesinRoadNetworks李玉娇导师杨卫东研究员指导小组成员谢志鹏副教授目录摘要iAbstractiii第一章　引言11.1研究背景11.2研究内容11.3本文工作21.4文章结构3第二章　支配路径查询问题52.1

2、相关工作52.1.1TPQ问题概述52.1.2OSR问题概述72.1.3KOR问题概述82.2KDR查询92.2.1引言92.2.2支配路径查询定义102.3DR算法122.3FDR算法152.4实验评估172.4.1性能评估182.4.2返回路径22第三章基于预测的最小时间路径查询问题253.1相关工作253.1.1短时交通预测算法253.2算法设计333.2.1基于改进k近邻的短时交通预测算法333.2.2基于A*的动态路径查询算法363.2.3算法框架383.3实验评估40第四章总结与展望414.1本文总结414.2将来工作41参考文献43致谢45攻读硕士学位期间发

3、表学术论文情况47摘要由于道路交通的迅猛发展，地图应用在人们生活中益发重要。不同的人在不同情况下有着不同的查询需求。本文从两个方面进行研究即基于关键字的支配路径查询问题的研究和基于短时交通预测的动态路径查询问题的研究。首先，本文提出一种基于关键字的支配路径查询，叫KDR（Keyword-awareDominateRoute）查询，形式化表示了基于关键字的支配路径的查询并证明了它的一些性质。查询关注于具有用户友好性和适应不同喜好的用户。基于关键字的支配路径查询问题是NP-hard。为解决KDR问题，本文从查询关键字入手设计了一种复杂度与路网大小无关的精确算法，DR算法和从空

4、间方位入手的启发式算法，FDR算法。在DR算法中，初始的路径为从初始结点到终点的最短路径，再不停的向路径中添加带有关键字的结点从而得到最终的支配路径。本文对DR算法的复杂度和正确性进行了证明。FDR算法的对已有的不完全路径的扩充方法是在最后一个结点后面添加一个更接近于终点的结点。在对两个算法进行验证的过程中，两个算法均取得预期成果。还有，本文提出一种基于预测的最小路径查询，并阐述了该查询的可行性和必要性。为了解决该问题，本文结合基于k近邻的短时预测技术和基于A*的动态路径规划技术，设计了基于改进k近邻和动态A*的最小路径查询方法。最后通过实验验证发现该方法能够有效解决最小

5、时间路径查询问题。关键词：路网，关键字，k近邻，支配路径中图分类号：TP3iAbstractWiththerapiddevelopmentofroadtraffic,themapapplicationismoreandmoreimportantinpeople'slife.Differentpeoplehavedifferentneedsindifferentsituations.Thispaperconcentratesontheresearchwhichisbasedonthestudyofquerykeywordsanddominantpathqueryproble

6、mofdynamicpathbasedontheresearchofshorttermtrafficprediction.Firstofall,thispaperpresentsacontrolpathbasedonkeywordquery,calledKDR(Keyword-awareDominateRoute)query,aformalrepresentationofthedominantpathkeywordbasedqueryandprovessomepropertiesofit.Queryisuser-friendlyandadaptedtodifferentu

7、serpreferences.KeywordbasedquerydominatedpathproblemisNP-hard.TosolvetheKDRproblem,thispaperstartsfromthequerykeywords.Anexactalgorithmcomplexityandindependentofthesizeofthenetworkdesign,DRalgorithmandstartingfromthespatialorientationoftheheuristicalgorithm,FDRalgor