计算机应用与软件
計算機應用與軟件
계산궤응용여연건
COMPUTER APPLICATIONS AND SOFTWARE
2012年
6期
94-96,108
,共4页
梁利刚%蔡莉%刘丹枫%伏红平%李超
樑利剛%蔡莉%劉丹楓%伏紅平%李超
량리강%채리%류단풍%복홍평%리초
较优路径%交通方向%可选下一跳集%选路点
較優路徑%交通方嚮%可選下一跳集%選路點
교우로경%교통방향%가선하일도집%선로점
Dijkstra算法是计算最短路径的典型算法,它能得出最短路径的最优解,但因为遍历计算的节点很多,所以效率低下.针对此局限性,提出一种基于方向判别的较优路径选择算法.该算法利用交通网络的方向特性,能够快速收敛找到较优路径,提高选路算法的性能.引入偏差率和吻合率等概念来描述算法,对其设计与实现过程进行详细的阐述,并利用MATLAB进行仿真实验.实验结果表明该算法在性能上优于Dijkstra算法,尽管得出的路径不一定是最优路径,会存在偏差,然而这些偏差是可以容忍的,不会影响算法的价值.
Dijkstra算法是計算最短路徑的典型算法,它能得齣最短路徑的最優解,但因為遍歷計算的節點很多,所以效率低下.針對此跼限性,提齣一種基于方嚮判彆的較優路徑選擇算法.該算法利用交通網絡的方嚮特性,能夠快速收斂找到較優路徑,提高選路算法的性能.引入偏差率和吻閤率等概唸來描述算法,對其設計與實現過程進行詳細的闡述,併利用MATLAB進行倣真實驗.實驗結果錶明該算法在性能上優于Dijkstra算法,儘管得齣的路徑不一定是最優路徑,會存在偏差,然而這些偏差是可以容忍的,不會影響算法的價值.
Dijkstra산법시계산최단로경적전형산법,타능득출최단로경적최우해,단인위편력계산적절점흔다,소이효솔저하.침대차국한성,제출일충기우방향판별적교우로경선택산법.해산법이용교통망락적방향특성,능구쾌속수렴조도교우로경,제고선로산법적성능.인입편차솔화문합솔등개념래묘술산법,대기설계여실현과정진행상세적천술,병이용MATLAB진행방진실험.실험결과표명해산법재성능상우우Dijkstra산법,진관득출적로경불일정시최우로경,회존재편차,연이저사편차시가이용인적,불회영향산법적개치.
