改进A*算法及其在GIS路径搜索中的应用

被引:15
作者
李志建
郑新奇
王淑晴
杨鑫
机构
[1] 中国地质大学(北京)土地科学技术学院
关键词
A*算法; dijkstra算法; 最短路径; 时间复杂度;
D O I
10.16182/j.cnki.joss.2009.10.054
中图分类号
P208 [测绘数据库与信息系统]; U116.2 [运输线路优选];
学科分类号
070503 ; 081603 ; 0818 ; 081802 ;
摘要
路径选择在实际运用中主要追求的是最优而不是最短。为此通常采用精度换效率的策略。这种策略虽然在一定程度上达到了路径搜索的任务要求,但如果能在精度和效率之间综合取值的话,效果往往会更令人满意。采用了一种改进的A*算法来实现这一目的。主要是通过变权值的方式来控制算法的搜索精度和搜索效率。实验证明,改进的A*算法可以实现最优路径的选择,且效率有很大的提高。
引用
收藏
页码:3116 / 3119
页数:4
相关论文
共 9 条
[1]   基于启发式策略的最短路径算法 [J].
陈曦 ;
费奇 ;
李炜 .
华中科技大学学报(自然科学版), 2006, (12) :4-6
[2]   改进的最短路径搜索A*算法的高效实现 [J].
段莉琼 ;
朱建军 ;
王庆社 ;
马玲 .
海洋测绘, 2004, (05) :20-22
[3]   变权值加快收敛的路径寻优实时算法 [J].
谭德荣 ;
严新平 .
交通运输工程学报, 2004, (01) :118-120
[4]   GIS中最短路径搜索算法 [J].
李春葆 .
计算机工程与应用 , 2002, (20) :70-71
[5]   最短路径算法:分类体系与研究进展 [J].
陆锋 .
测绘学报, 2001, (03) :269-275
[6]   图的节点-弧段联合结构表示法及其在GIS最优路径选取中的应用 [J].
王杰臣 ;
毛海城 ;
杨得志 ;
不详 .
测绘学报 , 2000, (01) :49-53
[7]   基于四叉堆优先级队列及逆邻接表的改进型Dijkstra 算法 [J].
陆锋 ;
卢冬梅 ;
崔伟宏 .
中国图象图形学报, 1999, (12) :32-38
[8]   交通网络限制搜索区域时间最短路径算法 [J].
陆锋 ;
卢冬梅 ;
崔伟宏 .
中国图象图形学报, 1999, (10) :47-51
[9]  
GIS与空间分析[M]. 科学出版社 , 黎夏, 2006