基于图论的动态导航系统最短路径算法研究

《基于图论的动态导航系统最短路径算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号：Y91123l学校代号：1191lUDC．——密级：——学号：224鳗Q4192广东工业大学学位论文基于图论的动态导航系统最短路径算法研究金振伟指导教师：胡剧教援学科门类：王科专业名称：丞统王攫申请学位级别：亟±论文提交日期：三QQ盍生四旦论文答辩日期：三QQ盍生重且学位授予单位：亡盔王些去堂』查三些奎兰三兰至圭兰堡篁圣ABSTRACTInrecentyears，therehavebeenmoreandmoreVehicles，tramcdemandandtrafficnowincitieswiththedevelopmentof

2、ourcountry’seconomic．Inthiss“uation，dynamicnavigationsystemcanplananoptimalpathundertherealtimetrafncinformation，whichavoidthetrafficcongestion，andthensaVethetraVellingcostanddogoodtothewholetrafncnetwork．ThedevelopmentofthisrealtimenaVigationsystemhascomewithrealtimepath

3、planning．Thisresearchlooksattheuseofdynamictraveltimeofroadsegment，obtainedfromatrafncinformationcenter．Thison—roadtraveltimerenectstheaVerageroadwayspeedandthelevelofcongestion．ThispaperdiscussesthevectormaprepresentationintrafHcroadnetwork，shortestpathalgorithmandthes01

4、utionofoptimalpathplanning．At6rst，thisresearchintroducedtheconceptofGISinVolvedofit’sdatamodel，organizationandmanagementofGISdata，elementaryfunctionetc，analyzedVectormapr印代矾m时}0肾oflhe_city。r蹦趟t鞴mcn9tWork’thedescriptionoflimitationofrealtramcnetwork．Then，thispaperintroduce

5、dthecorrelativeconceptofgraphtheory，iⅡcludingthedatastructureofgraph，andanalysedgraphsearch，includingthegeneralgraphsearchbasedonfiinge，breadth—firstsearchbasedonFIFOqueueanddepth—firstbasedonstack．OnthesametimeanalysedtheDijkstraalgo“thmwhichisappliedincomputingsingle—so

6、urceshortestpathandEuclideanheuristicwhichisusedintrafficnetwork．Intheend，thispaperstudiedthealgo“thmandcomplexityoftimeshortestpath．analyzedA+algorithmwhichcandecreasethetimecomplexityandimproVetheefnciencyofalgorithm，ItconnrmedthemethodofgainingtheroadsegmenttraVeltimea

7、ndthestoragetraveltimeserialandconsideredthesolutionofreal“mepathplanningindynamicnavigationsystem．Keyword：ShortestPa恤Algorithm；DijkstraA190rithm；Dynamic0ptimalPathPlanningⅡ第一章绪论第一章绪论1．1研究的背景作为智能交通系统的重要组成部分，车载导航系统由于其在解决交通运输问题中的作用得到了广泛的关注和不断的发展，如缓解交通拥堵，提高交通效率，降低驾车出行成本等。许多国

8、家相继开展了在此领域的研究工作，并已产生了许多产品。车辆动态自主导航系统中的核心技术包括：数字地图技术，最优路径规划技术，地图匹配及智能导航技术，无线数据传输技术⋯等。地理信息系统(Geogr