论文编号:XXLW014论文字数:10175,页数:19
摘 要
启发式搜索算法A*又称为最佳图搜索算法。当在算法A的评价函数中，使用的启发函数h（n）是处在h*（n）的下界范围（h*（n）是从目标节点的实际耗散值），即满足h（n）≤h*（n）时，把这个算法称为算法A*。它实际上是分支界限和动态规划原理及使用下界范围的h函数相结合的算法。在本文中提出了求解迷宫最短路径问题的新算法，即A*算法，该算法抛弃了经典算法（深度优先搜索和广度优先搜索）中繁杂低效的递归、回溯思想。
关键词：A*算法 开启列表 父节点 二叉堆
Application of a kind of A* algorithm to solve maze puzzle
Abstract
The heuristic search algorithm names A-star also known as the best map search algorithm. When the A algorithm in the evaluation function, use the inspiration function h(n) is in h* (n) the lower bound of the (h*(n) from the target node of the actual dissipation value), is to satisfy h(n)≤h*(n), this method known as A*algorithms. It is in fact a branch of boundaries and dynamic planning and the algorithm by using lower bound of combining the functions h. In this paper, a new algorithm is presented for solving the shortest path of maze problem, which is not based on the inefficient recursive backtracking theory of classical algorithm （DFS－Depth First Search and BFS—Breadth First Search）.we will use A-star algorithm to solve the general maze of path.
Keywords：A* algorithm;Open list;Farther node;Binary heaps
目 录
中文摘要i
英文摘要ii
目录iii
第一章 前言1
第二章 常见算法2
2.1 深度优先搜索（DFS）2
2.2 广度优先搜索（BFS）3
第三章 A*算法在迷宫求解中的简单应用实例及特殊解法4
3.1 A*算法4
3.2 算例14
3.3 算例26
3.3.1 开始搜索6
3.3.2 路径评分7
3.3.3 继续搜索9
3.3.4 A*算法总结12
第四章 迷宫的一般解法及实现13
4.1 迷宫生成模块13
4.1.1 迷宫矩阵的生成13
4.1.2 转化为卡通地图13
4.2 A*算法在一般迷宫中的寻径实现14
4.3 最优路径15
4.4 结果分析以及与常规算法的对比15
第五章 A*算法的改进16
5.1 二叉堆16
5.2 二叉堆快的原因17
5.3 测试结果17
致谢18
参考文献19
附录I 常见算法框图21
附录II 程序主要代码23
A算法在迷宫求解中的应用......