資源描述：
《Engineering Highway Hierarchies工程等級分路》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、EngineeringHighwayHierarchiesPeterSandersandDominikSchultesUniversit¨atKarlsruhe(TH),76128Karlsruhe,Germany,{sanders,schultes}@ira.uka.deAbstract.Highwayhierarchiesexploithierarchicalpropertiesinherentinreal-worldroadnetworkstoallowfastandexactpoint-to-pointshortest-pathqueries.Afastpreprocessi
2、ngroutineiterativelyperformstwosteps:?rst,itremovesedgesthatonlyappearonshortestpathsclosetosourceortarget;second,itidenti?eslow-degreenodesandbypassesthembyintroducingshortcutedges.TheresultinghierarchyofhighwaynetworksisthenusedinaDijkstra-likebidirectionalqueryalgorithmtoconsiderablyreduceth
3、esearchspacesizewithoutlosingexactness.Thecrucialfactisthat`faraway'fromsourceandtargetitissuf?cienttoconsideronlyhigh-leveledges.Variousexperimentswithreal-worldroadnetworkscon?rmtheperformanceofourapproach.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.Therearealsomanyapplicationslikelogisticplanningortraf?csimulationthatneedtosolveahugenumberofshortest-pathqueries.InprinciplewecoulduseDijkstra'salgorithm[1].Butforlargeroadn
7、etworksthiswouldbefartooslow.Therefore,thereisconsiderableinterestinspeeduptechniquesforrouteplanning.Mostapproaches,includingours,assumethattheroadnetworkisstatic,i.e.,itdoesnotchangeveryoften.Then,wecanallowsomepreprocessingthat
