中国科学技术大学学报
中國科學技術大學學報
중국과학기술대학학보
JOURNAL OF UNIVERSITY OF SCIENCE AND TECHNOLOGY OF CHINA
2014年
10期
867-873
,共7页
路网%最短路径%异步并行
路網%最短路徑%異步併行
로망%최단로경%이보병행
road network%shortest path%asynchronous parallelism
图上最短路径问题是一个经典问题,应用广泛.对于路网路径的计算,要求程序能够在有限的时间内找到一条尽量短的路径,且允许运行的时间越长,找到的路径越短.由于传统的最短路径算法在设计时未考虑这一约束条件,故不能满足应用需求.为此提一种APWA* (asynchronous parallelism weighted A*)算法,该算法能够响应用户的中断信号并返回当前找到的最短的路径.在多个地图数据上的实验表明,APWA*能够很好地满足实际需求.
圖上最短路徑問題是一箇經典問題,應用廣汎.對于路網路徑的計算,要求程序能夠在有限的時間內找到一條儘量短的路徑,且允許運行的時間越長,找到的路徑越短.由于傳統的最短路徑算法在設計時未攷慮這一約束條件,故不能滿足應用需求.為此提一種APWA* (asynchronous parallelism weighted A*)算法,該算法能夠響應用戶的中斷信號併返迴噹前找到的最短的路徑.在多箇地圖數據上的實驗錶明,APWA*能夠很好地滿足實際需求.
도상최단로경문제시일개경전문제,응용엄범.대우로망로경적계산,요구정서능구재유한적시간내조도일조진량단적로경,차윤허운행적시간월장,조도적로경월단.유우전통적최단로경산법재설계시미고필저일약속조건,고불능만족응용수구.위차제일충APWA* (asynchronous parallelism weighted A*)산법,해산법능구향응용호적중단신호병반회당전조도적최단적로경.재다개지도수거상적실험표명,APWA*능구흔호지만족실제수구.
