应用于城市道路网的启发式深度优先有向搜索算法  

Heuristic depth-first directional algorithm for shortest path searching in traffic networks

作　　者：房佳[1,2] 杜震洪[1,2] 张丰[1,2] 曾志[1,2] 刘仁义[2] 

机构地区：[1]浙江大学浙江省资源与环境信息系统重点实验室,浙江杭州310028 [2]浙江大学地理信息科学研究所,浙江杭州310027

出　　处：《浙江大学学报（理学版）》2013年第4期469-474,共6页Journal of Zhejiang University（Science Edition）

基　　金：国家自然科学基金资助项目(40901241;41101356);国家863项目(2009AA12Z222);浙江省攻关项目(2010C333146;2009C33011);教育部博士点基金资助项目(200803350017);浙江省自然科学基金资助项目(Y5080155;Y5090130;Y5090377)

摘　　要：针对具有大量道路节点的大型交通网络,提出了一种改进的深度优先算法.该算法在搜索过程中,首先对节点进行方向性选择,缩小了搜索的范围,同时引入启发式搜索函数,优先选择权值较低的点进行扩展,降低了深度优先的盲目性.因此,算法不仅能够在搜索早期找到最短路径,还能够提供多条备选路径.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.

关 键 词：深度优先 启发函数 方向选择 最短路径 

分 类 号：P208[天文地球—地图制图学与地理信息工程]