| 基于DEM格网的改进型A*路径搜索算法 |
| |
| 引用本文： | 林笃斌,李欣.基于DEM格网的改进型A*路径搜索算法[J].计算机工程与设计,2011,32(10):3414-3418. |
| |
| 作者姓名： | 林笃斌 李欣 |
| |
| 作者单位： | 华北计算技术研究所,北京,100083 |
| |
| 摘 要： | 为解决DEM格网上的路径搜索问题,分析了DEM格网和道路拓扑网络的共性与区别,并结合DEM格网的特点对比了Dijkstra算法和A*算法的优缺点,提出了基于DEM格网的改进型A*路径搜索算法。该算法充分考虑DEM格网上的路径可达条件,采用移动窗口法获取搜索网格候选集,并根据地理空间分布特征选取A*算法的估价函数,同时引入贪婪准则缩小搜索范围,降低问题复杂度。结合实例对算法进行了实验分析,验证结果表明了该算法的可行性和有效性。
|
| 关 键 词： | DEM格网 道路拓扑网络 地理信息系统 路径搜索 Dijkstra算法 A*算法 |
Improved A* path-finding algorithm based on DEM-Grid |
| |
| LIN Du-bin,LI Xin.Improved A* path-finding algorithm based on DEM-Grid[J].Computer Engineering and Design,2011,32(10):3414-3418. |
| |
| Authors: | LIN Du-bin LI Xin |
| |
| Affiliation: | LIN Du-bin,LI Xin(North China Institute of Computing Technology,Beijing 100083,China) |
| |
| Abstract: | To deal with Path-Finding problem based on DEM-Grid,the difference and sameness between DEM-Grid and road topo-network are analyzed,and the advantage and disadvantage between Dijkstra and A* algorithm on solving the problem are compared.An improved A* path-finding algorithm based on DEM-Grid is proposed.To reduce the complexity of Path-Finding algorithm,the attainable conditions on DEM-Grid are fully considered,the Moving-Window method is used to get candidate sets,an evaluation function of A* algorithm con... |
| |
| Keywords: | DEM-Grid road topo-network GIS path-finding Dijkstra algorithm A* algorithm |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
