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

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

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

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


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



本文編號：3164043