交通運輸網(wǎng)絡的最短路徑分析是地理信息系統(tǒng)網(wǎng)絡分析最常見的應用之一.該文在二叉堆索引結構的基礎上改進了計算最短路徑的Dijkstra算法和A*算法,采用了多種優(yōu)化策略提高算法的運行效率.首先,應用二叉堆索引提高了交通運輸網(wǎng)絡存儲結構的讀取效率;其次,通過數(shù)據(jù)類型的低精度損耗簡化和運算類型的簡化,提高了算法的計算效率.另外,優(yōu)化了A*算法中估計函數(shù)的計算方式,有效降低了搜索空間,提高了Dijkstra算法和A*算法的整體計算效率.實驗結果表明Dijkstra算法的改進方法可使計算速度提高7倍以上,對A*算法的改進可使計算速度提高200倍以上. 

【文章來源】：應用科學學報. 2020,38(06)北大核心CSCD

【文章頁數(shù)】：11 頁

【文章目錄】：
1 交通運輸網(wǎng)絡的二叉堆數(shù)據(jù)結構表示和算法改進
    1.1 交通運輸網(wǎng)絡的最短路徑算法分析
        1.1.1 Dijkstra算法
        1.1.2 A*算法
    1.2 交通運輸網(wǎng)絡的二叉堆索引結構
    1.3 基于二叉堆的Dijkstra改進算法
    1.4 基于二叉堆的A*改進算法
2 實驗與分析
    2.1 實驗環(huán)境及數(shù)據(jù)
    2.2 實驗結果與分析
3 結語


【參考文獻】：
期刊論文
[1]基于不同交通工具多約束條件的最短路徑算法研究[J]. 范林林,李翔,張晶,張江水,趙婷.  測繪工程. 2016(12)
[2]一種并行模糊神經(jīng)網(wǎng)絡最短路徑算法[J]. 閆春望,黃瑋,王勁松.  計算機應用研究. 2016(11)
[3]大數(shù)據(jù)環(huán)境下的動態(tài)最短路徑算法[J]. 徐建閩,王鈺,林培群.  華南理工大學學報(自然科學版). 2015(10)
[4]道路網(wǎng)上最短路徑算法綜述[J]. 張波良,張瑞昌,關佶紅.  計算機應用與軟件. 2014(10)
[5]基于Dijkstra算法和Floyd算法的物流運輸最短路徑研究[J]. 李晶,閆軍.  科技信息. 2012(34)
[6]改進的Dijkstra最短路徑算法及其應用研究[J]. 王樹西,吳政學.  計算機科學. 2012(05)
[7]基于Bellman-Ford算法的動態(tài)最優(yōu)路徑算法設計[J]. 宮恩超,李魯群.  測繪通報. 2011(08)
[8]改進的最短路徑搜索A*算法的高效實現(xiàn)[J]. 段莉瓊,朱建軍,王慶社,馬玲.  海洋測繪. 2004(05)
[9]最短路徑算法:分類體系與研究進展[J]. 陸鋒.  測繪學報. 2001(03)
[10]Dijkstra最短路徑算法的一種高效率實現(xiàn)[J]. 樂陽,龔健雅.  武漢測繪科技大學學報. 1999(03)



本文編號：3164043