摘要
图上最短路径问题是一个经典问题,应用广泛.对于路网路径的计算,要求程序能够在有限的时间内找到一条尽量短的路径,且允许运行的时间越长,找到的路径越短.由于传统的最短路径算法在设计时未考虑这一约束条件,故不能满足应用需求.为此提一种APWA*(asynchronous parallelism weighted A*)算法,该算法能够响应用户的中断信号并返回当前找到的最短的路径.在多个地图数据上的实验表明,APWA*能够很好地满足实际需求.
Finding the shortest path is a classic problem with numerous applications. For road networks, it is desirable to find a sufficient short path within a limited period of time, and find a shorter path if there is more time. Since the traditional shortest path algorithms did not consider this constraint when designed, they can not meet the application requirement. To address this issue, an algorithm called APWA^＊, asynchronous parallelism weighted A^＊ , was proposed, which can respond to users＇ interrupt signal and return to the currently shortest path. Experiments on multiple maps show APWA^＊ can meet the application requirement.
基金
国家自然科学基金(61033009
61303047)资助
关键词
路网
最短路径
异步并行
road network
shortest path
asynchronous parallelism
