A算法在迷宫求解中的应用

论文编号: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  算例1 4
      3.3  算例2 6
           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