基于DEM格网的改进型A*路径搜索算法

作者：林笃斌; 李欣

来源：计算机工程与设计, 2011, (10): 3414-3418.

DOI：10.16208/j.issn1000-7024.2011.10.045

• DEM格网
• 道路拓扑网络
• 地理信息系统
• 路径搜索
• Dijkstra算法
• A*算法 DEM-Grid
• road topo-network
• GIS
• path-finding
• Dijkstra algorithm
• A* algorithm

为解决DEM格网上的路径搜索问题,分析了DEM格网和道路拓扑网络的共性与区别,并结合DEM格网的特点对比了Dijkstra算法和A*算法的优缺点,提出了基于DEM格网的改进型A*路径搜索算法。该算法充分考虑DEM格网上的路径可达条件,采用移动窗口法获取搜索网格候选集,并根据地理空间分布特征选取A*算法的估价函数,同时引入贪婪准则缩小搜索范围,降低问题复杂度。结合实例对算法进行了实验分析,验证结果表明了该算法的可行性和有效性。

• 单位
  中国电子科技集团公司第十五研究所