A*算法求解迷宫寻路问题（启发式算法）

A*算法求解迷宫寻路问题资源链接如右：A*算法求解迷宫寻路问题

如果觉得这篇文章对你有帮助请点赞收藏加关注啊，真的很谢谢大家！大家可以进入我的CSDN主页查看其它文章，都是我在进行课后题目与课程设计时遇到的一些问题，如果你正在学习人工智能，一定会有所收获，并且可以在我的GitHub仓库主页下载相关代码，如无法进入GitHub仓库主页也可以进入Gitee进行查看，后续我也会根据需求不断完善。

lazyn的CSDN_blog_code(GitHub) lazyn的CSDN_blog_code(Gitee)

同时如果想要系统化的学习人工智能，可以进入下面的网站进行学习

通俗易懂，风趣幽默的人工智能学习网站-床长人工智能教程

作为人工智能专业的学生，我认为该网站的课程设置足够专业与完整，由浅入深，基本涵盖了当前人工智能的热门领域并且在不断完善，目录简洁明了，大家可以对照目录进行查漏补缺，作为读者，我发现课程内容通俗易懂，风趣幽默，可以激发大家的学习兴趣。

修改后代码可以实现评论区迷宫的寻路，结果如下图所示。

感谢评论区 weeknight, m0_57493007, 子夜ザ“, 格”式化 等人的指正。

在一个n×m的迷宫里，入口坐标和出口坐标分别为(startx,starty)和(endx,eny)，每一个坐标点有两种可能：0或1，其中0表示该位置允许通过，1表示该位置不允许通过。以寻路问题为例实现A*算法的求解程序，设计两种不同的估价函数。

根据题意，用矩阵设置两个地图。 地图1：设置5行5列的迷宫，代码如下：

地图2：设置20行20列的迷宫，代码如下

定义估价函数 f ( n ) = g ( n ) + h ( n ) f(n)=g(n)+h(n) f(n)=g(n)+h(n) 式中， g ( n ) g(n) g(n)为起点到 n n n状态的最短路径代价的估计值， h ( n ) h(n) h(n)是 n n n状态到目的状态的最短路径代价的估计值。 令 g ( n ) g(n) g(n)为起点到 n n n状态的曼哈顿距离，代码如下：

定义两种启发式函数。 启发式函数 h 1 ( n ) h_1 (n) h1​(n)： h 1 ( n ) = 10 × ( ∣ n x − e n d x ∣ + ∣ n y − e n d y ∣ ) h_1 (n)=10×(|n_x-endx|+|n_y-endy|) h1​(n)=10×(∣nx​−endx∣+∣ny​−endy∣)，代码如下：

启发式函数 h 2 ( n ) h_2 (n) h2​(n)： h 2 ( n ) = ( n x − e n d x ) 2 + ( n y − e n d y ) 2 h_2 (n)=(n_x-endx)^2+(n_y-endy)^2 h2​(n)=(nx​−endx)2+(ny​−endy)2，代码如下：

采用地图2，具体如下图1，启发式函数 h 1 h_1 h1​进行分析，分别设置起点为（1，1）和（9，5），终点为（20，20）、（18，20）。

（1，1）→(20,20)的路径如图2，（9，5）→(18,20)的路径如图3。 两次寻路过程的性能分析如下表1。

由上述图表可知路径延长后运行时间会相对变长，扩展节点及生成节点也会相应增多，且两次寻找的路程有重合的部分，所以寻找到的路径为较优路径。

采用地图2，启发式函数 h 1 h_1 h1​， h 2 h_2 h2​进行分析，设置起点为（1，1），终点为（20，20），两次寻路过程的路径，扩展节点数、生成节点数和运行时间分别如下图4，图5。

由图表可知，两种启发式函数所用时间相近，但 h 2 h_2 h2​相比 h 1 h_1 h1​所扩展的节点数会减少，仔细分析可以发现启发式函数 h 1 h_1 h1​在路径108位置首先寻找了另一条岔路，从而相比启发式函数 h 2 h_2 h2​多扩展了3个节点。

上述过程一直采用地图2进行实验，为验证程序的普适性，现采用地图1进行实验。经过分析，选择上述较优的启发式函数 h 2 h_2 h2​进行分析。寻路问题初始节点为（1，1），目标节点为（5，5），寻路路径如图6。

汇总上述性能报告如下表2。

A*算法在地图寻路问题中具有很好的优势，相比宽度优先搜索，效率更高，所耗时间更少，相比深度优先搜索，可以解决其不能找到最优解的不足，具有较高的应用价值。该算法的重点及难点就是启发式函数的选择，通过上述实验，可以发现启发式函数 h 2 h_2 h2​相比 h 1 h_1 h1​效果更好，但仍存在一些问题，需要继续找寻更优的启发式函数。

主程序代码如下，其中用到的方法和地图在上述代码中已定义，故不再给出。设置不同的起点与终点需相应的更改startx, starty和endx, endy的值。