资源描述：
《Engineering Highway Hierarchies工程等级分路》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、EngineeringHighwayHierarchiesPeterSandersandDominikSchultesUniversit¨atKarlsruhe(TH),76128Karlsruhe,Germany,{sanders,schultes}@ira.uka.deAbstract.Highwayhierarchiesexploithierarchicalpropertiesinherentinreal-worldroadnetworkstoallowfastandexactpoint-to-pointshortest-pathqueries.Afastpreprocessi
2、ngroutineiterativelyperformstwosteps:first,itremovesedgesthatonlyappearonshortestpathsclosetosourceortarget;second,itidentifieslow-degreenodesandbypassesthembyintroducingshortcutedges.TheresultinghierarchyofhighwaynetworksisthenusedinaDijkstra-likebidirectionalqueryalgorithmtoconsiderablyreduceth
3、esearchspacesizewithoutlosingexactness.Thecrucialfactisthat`faraway'fromsourceandtargetitissufficienttoconsideronlyhigh-leveledges.Variousexperimentswithreal-worldroadnetworksconfirmtheperformanceofourapproach.Ona2.0GHzmachine,preprocessingthenetworkofWesternEurope,whichconsistsofabout18millionno
4、des,takes13minutesandyields48bytesofadditionaldatapernode.Then,randomqueriestake0.61msonaverage.Ifwearewillingtoacceptslowerquerytimes(1.10ms),thememoryusagecanbedecreasedto17bytespernode.Wecanguaranteethatatmost0.014%ofallnodesarevisitedduringanyquery.ResultsforUSroadnetworksaresimilar.Highway
5、hierarchiescanbecombinedwithgoal-directedsearch,theycanbeextendedtoanswermany-to-manyqueries,andtheyareacrucialingredientforotherspeeduptechniques,namelyfortransit-noderoutingandhighway-noderouting.1IntroductionComputingfastestroutesinroadnetworksfromagivensourcetoagiventargetlocationisoneofthe
6、showpiecesofreal-worldapplicationsofalgorithmics.Manypeoplefrequentlyusethisfunctionalitywhenplanningtripswiththeircars.Therearealsomanyapplicationslikelogisticplanningortrafficsimulationthatneedtosolveahugenumberofshortest-pathqueries.InprinciplewecoulduseDijkstra'salgorithm[1].Butforlargeroadn
7、etworksthiswouldbefartooslow.Therefore,thereisconsiderableinterestinspeeduptechniquesforrouteplanning.Mostapproaches,includingours,assumethattheroadnetworkisstatic,i.e.,itdoesnotchangeveryoften.Then,wecanallowsomepreprocessingthat
