资源描述：
《K则最短路径算法效率与精度评估.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、第14卷第8期中国图象图形学报Vol.14,No.82009年8月JournalofImageandGraphicsAug.,2009K则最短路径算法效率与精度评估高松陆锋(中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室,北京100101)摘要精度和效率是决定最短路径算法实用价值的重要依据。对于K则最短路径问题,各种理论严密算法和有损算法的实用性分析是目前研究的薄弱环节。理论严密算法的实际运行效率比较及其有损算法的精度损耗与效率提高幅度的定量化一直未得到深入研究。针对这一问题,在对K则最短路径算法进行系统分类的基
2、础上,分析了各种经典的理论严密算法和精度有损算法的特征与时间复杂度,结合实际城市路网数据对各种K则最短路径算法的运行效率和精度进行了测试和比较。结果显示,与有损算法相比,理论严密的K则最短路径算法普遍缺乏实用性,只有多重标号算法适合于某些要求精度无损的应用;而一些有损K则最短路径算法以较小的精度损失换取了较大幅度的效率提高,尤以双向搜索算法最具应用推广价值。关键词K则最短路径算法交通网络效率精度中图法分类号:TP391,U491文献标识码:A文章编号:100628961(2009)0821677207TheKthShortest
3、PathAlgorithms:AccuracyandEfficiencyEvaluationGAOSong,LUFeng(StateKeyLaboratoryofResourcesandEnvironmentalInformationSystem,InstituteofGeographicalScienceandNaturalResourcesResearch,CAS,Beijing100101)AbstractEfficiencyandaccuracyareundoubtedlytwoexclusiveindicesforsh
4、ortestpathalgorithms1ThepracticalanalysisondifferentalgorithmssolvingtheKthshortestpathproblemshasnotinvokedmuchresearch1ThecomparisononrunningefficiencybetweenseveraltheoreticallyrigorousalgorithmsandtheamountofaccuracylossandefficiencyimprovementbroughtbylossyKthsh
5、ortestpathalgorithmshaveremainedquantitativelyunderinvestigated,andthetrade2offbetweenthemhasnotbeenanalyzedindetail1Inthispaper,withasystematicclassificationofthemostpopularKthshortestpathalgorithms,theauthordiscussedthecharacteristicsandtimecomplexityofthesealgorit
6、hms,andanalyzedandcomparedtheirefficiencyandaccuracywitharealroadsnetwork1TheauthorarguedthatthetheoreticallyrigorousKthshortestpathalgorithms,generallylackpracticalvalue,onlythemulti2labelsettingalgorithmcanbeappliedforsomeapplicationsrequiringlosslessaccuracy1Somel
7、ossyKthshortestpathalgorithms,greatlyimprovetheefficiencywithonlylittleaccuracylost1Thebidirectional2searchalgorithmwasarguedworthpayingmoreattentioninpracticalapplications1KeywordsKthshortestpathsalgorithms,roadsnetwork,efficiency,accuracy的多个备选优化路径,形成最短路径组,以最大程度1引言满
8、足用户对不同出行路径的选择需求。K则最短路[2]径问题最早由Hoffman和Pavley提出,多年来一K则最短路径问题是最短路径问题族中的重要直受到业界的广泛重视,提出了各种各样的K则最[1]问题之一。K则最短路径旨在寻找起点和终点间短路径算法。根据算法的理论严
