计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2014年
16期
54-56,71
,共4页
杨泳%户佐安%何金海
楊泳%戶佐安%何金海
양영%호좌안%하금해
最优路径规划%双向启发式A*算法%路网%二叉堆
最優路徑規劃%雙嚮啟髮式A*算法%路網%二扠堆
최우로경규화%쌍향계발식A*산법%로망%이차퇴
optimal route planning%bi-directional heuristic A*algorithm%traffic network%binary heap
针对实际城市交通路网最优路径规划中存在的计算效率问题，研究了最优路径算法的快速实现技术，提出了一种双向启发式A*诱导算法。在分析经典Dijkstra算法和A*启发式搜索算法的基础上，利用双向A*算法分解搜索空间，采用完全二叉堆结构来实现计算过程中数据的存取，从而提高了算法的执行效率。实际路网仿真结果证明了该算法的优异性能。
針對實際城市交通路網最優路徑規劃中存在的計算效率問題，研究瞭最優路徑算法的快速實現技術，提齣瞭一種雙嚮啟髮式A*誘導算法。在分析經典Dijkstra算法和A*啟髮式搜索算法的基礎上，利用雙嚮A*算法分解搜索空間，採用完全二扠堆結構來實現計算過程中數據的存取，從而提高瞭算法的執行效率。實際路網倣真結果證明瞭該算法的優異性能。
침대실제성시교통로망최우로경규화중존재적계산효솔문제，연구료최우로경산법적쾌속실현기술，제출료일충쌍향계발식A*유도산법。재분석경전Dijkstra산법화A*계발식수색산법적기출상，이용쌍향A*산법분해수색공간，채용완전이차퇴결구래실현계산과정중수거적존취，종이제고료산법적집행효솔。실제로망방진결과증명료해산법적우이성능。
Computational efficiency is widely recognized to be an essential issue in the optimal route planning against realistic urban road traffic network, the fast search technology is studied and a bidirectional heuristic A* algorithm is presented. Based on analysis of classic Dijkstra algorithm and heuristic A*algorithm, bidirectional heuristic A*is used to decompose the search space and binary heap data structure is utilized to operate data. Simulation results against real data demonstrate performance boost.
