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

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

摘     要

启发式搜索算法A*又称为最佳图搜索算法。当在算法A的评价函数中，使用的启发函数h（n）是处在h*（n）的下界范围（h*（n）是从目标节点的实际耗散值），即满足h（n）≤h*（n）时，把这个算法称为算法A*。它实际上是分支界限和动态规划原理及使用下界范围的h函数相结合的算法。在本文中提出了求解迷宫最短路径问题的新算法，即A*算法，该算法抛弃了经典算法（深度优先搜索和广度优先搜索）中繁杂低效的递归、回溯思想。

关键词：A*算法 开启列表 父节点 二叉堆

目  录

中文摘要 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