计算机应用
計算機應用
계산궤응용
COMPUTER APPLICATION
2014年
4期
1192-1195
,共4页
胡欣%徐涛%丁晓璐%李建伏
鬍訢%徐濤%丁曉璐%李建伏
호흔%서도%정효로%리건복
国际航线网络%最短路径算法%K条最短路径问题%Yen算法%启发式策略
國際航線網絡%最短路徑算法%K條最短路徑問題%Yen算法%啟髮式策略
국제항선망락%최단로경산법%K조최단로경문제%Yen산법%계발식책략
international flight route network%shortest path algorithm%K-Shortest-Paths (KSP) problem%Yen algorithm%heuristic strategy
K条最短路径(KSP)问题是国际航线网络实际路径优化问题.通过对航线网络特征与K条最短路径算法的分析,研究了解决KSP问题的典型Yen算法.针对Yen算法求解候选路径占用大量运算时间的问题,提出一种改进Yen算法.改进Yen算法通过借助A*算法的启发式策略,减少了产生候选航线路径的时间,从而提高了算法的搜索效率并减小了算法搜索的规模.通过对国际航线网络实例的仿真,实验结果表明改进Yen算法能够快速求解国际航线网络中的KSP问题;同时,与Yen算法相比,运算效率提升了75.19％以上,能够为航线路径优化提供决策支持.
K條最短路徑(KSP)問題是國際航線網絡實際路徑優化問題.通過對航線網絡特徵與K條最短路徑算法的分析,研究瞭解決KSP問題的典型Yen算法.針對Yen算法求解候選路徑佔用大量運算時間的問題,提齣一種改進Yen算法.改進Yen算法通過藉助A*算法的啟髮式策略,減少瞭產生候選航線路徑的時間,從而提高瞭算法的搜索效率併減小瞭算法搜索的規模.通過對國際航線網絡實例的倣真,實驗結果錶明改進Yen算法能夠快速求解國際航線網絡中的KSP問題;同時,與Yen算法相比,運算效率提升瞭75.19％以上,能夠為航線路徑優化提供決策支持.
K조최단로경(KSP)문제시국제항선망락실제로경우화문제.통과대항선망락특정여K조최단로경산법적분석,연구료해결KSP문제적전형Yen산법.침대Yen산법구해후선로경점용대량운산시간적문제,제출일충개진Yen산법.개진Yen산법통과차조A*산법적계발식책략,감소료산생후선항선로경적시간,종이제고료산법적수색효솔병감소료산법수색적규모.통과대국제항선망락실례적방진,실험결과표명개진Yen산법능구쾌속구해국제항선망락중적KSP문제;동시,여Yen산법상비,운산효솔제승료75.19％이상,능구위항선로경우화제공결책지지.
