中国科学技术大学学报
中國科學技術大學學報
중국과학기술대학학보
JOURNAL OF UNIVERSITY OF SCIENCE AND TECHNOLOGY OF CHINA
2014年
10期
874-880
,共7页
张钟%吕敏%孙广中%陈国良
張鐘%呂敏%孫廣中%陳國良
장종%려민%손엄중%진국량
最短路径%下界%预处理%A*搜索%中心点%三角不等式
最短路徑%下界%預處理%A*搜索%中心點%三角不等式
최단로경%하계%예처리%A*수색%중심점%삼각불등식
shortest path%lower bounds%preprocessing%A* search%centers%triangle inequality
在许多应用中,实时计算一个源点到一个目的点的最短路径是一个非常重要的问题.学术界已经提出若干下界算法求解点到点的最短路径问题,如A*算法,ALT算法等.这些算法所使用的距离估值比较松散,仍然有很大的提升潜力.ACT算法是一种新的两阶段目标制导下界算法,它组合使用了A*搜索,中心点和三角不等式,并且不依赖于特定领域的先验知识.新算法充分利用了预处理数据,可以获得非常好的距离下界.在真实路网上的实验结果表明,新算法的性能明显优于以往的算法.在某些实例下,最优版本的ACT算法所扩展的顶点数量仅仅比最短路径上的顶点数量多25％左右.
在許多應用中,實時計算一箇源點到一箇目的點的最短路徑是一箇非常重要的問題.學術界已經提齣若榦下界算法求解點到點的最短路徑問題,如A*算法,ALT算法等.這些算法所使用的距離估值比較鬆散,仍然有很大的提升潛力.ACT算法是一種新的兩階段目標製導下界算法,它組閤使用瞭A*搜索,中心點和三角不等式,併且不依賴于特定領域的先驗知識.新算法充分利用瞭預處理數據,可以穫得非常好的距離下界.在真實路網上的實驗結果錶明,新算法的性能明顯優于以往的算法.在某些實例下,最優版本的ACT算法所擴展的頂點數量僅僅比最短路徑上的頂點數量多25％左右.
재허다응용중,실시계산일개원점도일개목적점적최단로경시일개비상중요적문제.학술계이경제출약간하계산법구해점도점적최단로경문제,여A*산법,ALT산법등.저사산법소사용적거리고치비교송산,잉연유흔대적제승잠력.ACT산법시일충신적량계단목표제도하계산법,타조합사용료A*수색,중심점화삼각불등식,병차불의뢰우특정영역적선험지식.신산법충분이용료예처리수거,가이획득비상호적거리하계.재진실로망상적실험결과표명,신산법적성능명현우우이왕적산법.재모사실례하,최우판본적ACT산법소확전적정점수량부부비최단로경상적정점수량다25％좌우.
