|
|||||
|
|
| 一种基于Dijkstra算法的启发式最优路径搜索算法 | |
| 引用本文： | 王景存,张晓彤,陈彬,陈和平.一种基于Dijkstra算法的启发式最优路径搜索算法[J].北京科技大学学报,2007,29(3):346-350. |
| 作者姓名： | 王景存 张晓彤 陈彬 陈和平 |
| 作者单位： | 1. 北京科技大学信息工程学院,北京,100083;武汉科技大学信息科学与工程学院,武汉,430081 2. 北京科技大学信息工程学院,北京,100083 3. 武汉科技大学信息科学与工程学院,武汉,430081 |
| 基金项目： | 中国科学院计算所知识创新工程研究项目 |
| 摘 要： | 为了建立一个高效的路径搜索引擎,针对大型应用系统中寻径算法的平衡最优性、时间复杂度以及空间复杂度问题,从经典Dijkstra算法出发,将AI领域的决策机制引入到路径搜索中来,提出了一个启发式最优路径搜索算法.该算法在寻径过程中引入代价函数,由代价函数来决定寻径策略(即优先搜索哪些中间节点),以期望减少搜索节点数.给出了该算法得到最佳解的条件及其证明过程,并且以实例数据对两种算法进行了对比测试. |
| 关 键 词： | 路径搜索 导航 启发式 最优 Dijkstra algorithm 路径搜索算法 启发式 最优性 based optimization 对比测试 实例数据 证明过程 条件 最佳 节点数 期望 优先搜索 寻径策略 代价函数 决策机制 问题 空间复杂度 时间 |
| 修稿时间： | 2006-04-05 |
A heuristic optimization path-finding algorithm based on Dijkstra algorithm |
|
| WANG Jingcun,ZHANG Xiaotong,CHEN Bin,CHEN Heping.A heuristic optimization path-finding algorithm based on Dijkstra algorithm[J].Journal of University of Science and Technology Beijing,2007,29(3):346-350. | |
| Authors: | WANG Jingcun ZHANG Xiaotong CHEN Bin CHEN Heping |
| Institution: | 1 Information Engineering School, University of Science and Technology Beijing, Beijing 100083, China ;2 Information Engineering School, Wuhan University of Science and Technology, Wuhan 430081, China |
| Abstract: | To make an efficient path-finding engine, a heuristic optimization path-finding algorithm was proposed for resolving the time and space complexity problems of a searching algorithm in a large application system. The algorithm was based on the classical Dijkstra algorithm and introduced the decision mechanism in AI into path-finding. To decrease the number of nodes to search, cost-function was incorporated into this algorithm and used to decide the path-finding policy, that was, which nodes were searched firstly. The condition of getting the optimal solution from this algorithm was put forward and proved. These two algorithms were tested comparatively. |
| Keywords: | path-finding navigation heuristic optimization |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ | |