摘要
针对具有大量道路节点的大型交通网络,提出了一种改进的深度优先算法.该算法在搜索过程中,首先对节点进行方向性选择,缩小了搜索的范围,同时引入启发式搜索函数,优先选择权值较低的点进行扩展,降低了深度优先的盲目性.因此,算法不仅能够在搜索早期找到最短路径,还能够提供多条备选路径.
For a large traffic network that contains a great amount of nodes, an improved algorithm based on depth- first search is figured out. In the searching process, the algorithm firstly selects nodes according to the direction, which can largely decreases the searching area. Meanwhile, a heuristic function to calculate the value of each node is introduced and the search by choosing the node with the lowest value is extended, which improves the efficiency of depth-first search. Hence, the algorithm not only can find the shortest routine in the early time, but also provides users with some more routines in support.
出处
《浙江大学学报（理学版）》
CAS
CSCD
2013年第4期469-474,共6页
Journal of Zhejiang University（Science Edition）
基金
国家自然科学基金资助项目(40901241
41101356)
国家863项目(2009AA12Z222)
浙江省攻关项目(2010C333146
2009C33011)
教育部博士点基金资助项目(200803350017)
浙江省自然科学基金资助项目(Y5080155
Y5090130
Y5090377)
关键词
深度优先
启发函数
方向选择
最短路径
deep-first
heuristic function
directional choosing
shortest path
