【摘要】：針對節(jié)點約束型最短路徑問題,提出了基于回溯法的分層Dijkstra算法,通過分層結(jié)構(gòu)尋找局部最優(yōu)解來求得全局最優(yōu)解或次優(yōu)解.該算法利用分層結(jié)構(gòu)可保存搜索進度的優(yōu)勢,使其在尋找過必經(jīng)點最短路徑時可以實現(xiàn)對搜索進度的保存與回溯等操作.實驗結(jié)果表明:分層Dijkstra算法雖然增加了一定的空間復(fù)雜度,但能有效地減少Dijkstra算法的調(diào)用次數(shù);與深度優(yōu)先搜索、幾何代數(shù)算法相比,分層Dijkstra算法雖然不一定能找到理論最優(yōu)解,但出解速度較快,在數(shù)據(jù)量較大的情況下能快速找到次優(yōu)解.
[Abstract]:A hierarchical Dijkstra algorithm based on backtracking is proposed to solve the node constrained shortest path problem. The global optimal solution or suboptimal solution is obtained by searching for the local optimal solution through the hierarchical structure. This algorithm utilizes the advantage of hierarchical structure to save the search progress, so that it can save and trace the search progress when searching for the shortest path. The experimental results show that although the hierarchical Dijkstra algorithm increases the space complexity, it can effectively reduce the number of calls to the Dijkstra algorithm. Compared with depth-first search and geometric algebraic algorithm, although the hierarchical Dijkstra algorithm can not always find the theoretical optimal solution, it can quickly find the sub-optimal solution in the case of large amount of data.
【作者單位】： 華南理工大學(xué)自動化科學(xué)與工程學(xué)院;
【基金】：國家自然科學(xué)基金資助項目(61573151,61105019) 廣東省自然科學(xué)基金資助項目(2016A030313468)~~
【分類號】：O157.5

【相似文獻】

相關(guān)期刊論文 前10條

1 李國成;;Dijkstra算法在物流網(wǎng)絡(luò)設(shè)計中的應(yīng)用[J];企業(yè)導(dǎo)報;2011年18期

2 張美玉;簡t$峰;侯向輝;邊林潔;梅靖華;;Dijkstra算法在多約束農(nóng)產(chǎn)品配送最優(yōu)路徑中的研究應(yīng)用[J];浙江工業(yè)大學(xué)學(xué)報;2012年03期

3 崔小晴;關(guān)英子;;存在阻塞路段路網(wǎng)最優(yōu)路的Dijkstra優(yōu)化算法[J];旅游縱覽(下半月);2013年09期

4 陳榮軍;Dijkstra算法的應(yīng)用[J];常州工業(yè)技術(shù)學(xué)院學(xué)報;1999年02期

5 代西武;;Dijkstra矩陣算法[J];北京建筑工程學(xué)院學(xué)報;2007年02期

6 張福浩;劉紀(jì)平;;一種基于Dijkstra的海量空間數(shù)據(jù)最短路徑算法[J];遼寧工程技術(shù)大學(xué)學(xué)報(自然科學(xué)版);2009年04期

7 韓偉一,王錚;Dijkstra算法的一個改進[J];運籌與管理;2004年06期

8 劉朝霞;;基于Dijkstra的最短路徑問題的算法分析與優(yōu)化[J];佳木斯教育學(xué)院學(xué)報;2014年04期

9 熊德國;胡勇文;;用Dijkstra算法求解最短路的矩陣方法[J];河南理工大學(xué)學(xué)報(自然科學(xué)版);2011年05期

10 王華;;基于鄰接點算法的Dijkstra優(yōu)化研究[J];計算機與數(shù)字工程;2013年04期

相關(guān)會議論文 前1條

1 施培港;;Dijkstra最短路徑算法的實現(xiàn)及優(yōu)化[A];中國地理信息系統(tǒng)協(xié)會第三次代表大會暨第七屆年會論文集[C];2003年

相關(guān)碩士學(xué)位論文 前1條

1 劉國華;基于Dijkstra距離的聚類算法研究及其在物流中的應(yīng)用[D];蘭州大學(xué);2011年

，

本文編號：2405408