A*迷宫寻路
二、实验内容
以寻路问题为例实现A*算法的求解程序，设计两种不同的估价函数：
1.设置两种地图：
根据题意，用矩阵设置两个地图。
地图1：设置5行5列的迷宫，代码如下：
地图2：设置20行20列的迷宫，代码如下：
2.设置两种启发式函数
定义估价函数 式中，g(n)为起点到n 状态的最短路径代价的估计值， ℎ(n) 是 n状态到目的状态的最短路径代价的估计值。 令g(n) 为起点到 n 状态的曼哈顿距离，代码如下：
定义两种启发式函数。
启发式函数
,代码如下：
启发式函数
,代码如下:
三、实验要求
1.画出A*算法求解迷宫最短路径的流程图
2.设置不同的地图，以及不同的初始状态和目标状态，记录A*算法的求解结果，包括最短路径、扩展节点数、生成节点数和算法运行时间
设置地图1的初始状态为1,2、目标状态为5,5, 运用启发式函数1，得出求解结果如下：
设置地图2的初始状态为1,1、目标状态为20,20, 运用启发式函数1，得出求解结果如下：
3.对于相同的初始状态和目标状态，设计不同的启发式函数，比较不同启发式函数对迷宫寻路速度的提升效果，包括扩展节点数、生成节点数和算法运行时间。
设置地图2的初始状态为1,1、目标状态为20,20, 运用启发式函数1，得出求解结果如下
设置地图2的初始状态为1,1、目标状态为20,20, 运用启发式函数2，得出求解结果如下
由图可知，两种启发式函数所用时间相近，但 ℎ2 相比 ℎ1 所扩展的节点数会减少，仔细分析可以发现启发式函数 ℎ1 在路径108位置首先寻找了另一条岔路，从而相比启发式函数 ℎ2 多扩展了3个节点。
四、实验要求
1.画出A*算法求解迷宫最短路径问题的流程图如上
2.分析不同启发式函数h(n)对迷宫寻路求解的速度提升效果。
2.1常见启发式函数介绍：
2.1.1 曼哈顿距离（Manhattan Distance）
特点：计算简单快速，在迷宫寻路中能提供相对合理的估计，但在某些情况下可能会导致搜索路径不是最优（如存在斜向移动成本与水平 / 垂直移动成本相同时）。
2.1.2 欧几里得距离（Euclidean Distance）
特点：从数学上更准确地估计节点到终点的直线距离，但计算相对复杂（涉及平方根运算），在实际应用中，对于大规模迷宫可能会影响计算效率。
2.1.3 对角线距离（Diagonal Distance）
特点：更适合于可以斜向移动的场景，能更精准地估计路径代价，但计算相对复杂，且需要根据移动成本进行调整。
2.2 不同启发式函数对速度提升效果的分析
对扩展节点数的影响：
曼哈顿距离：在一般迷宫中，由于其计算简单且能提供一定的方向引导，通常能有效地限制搜索方向，使得扩展节点数相对较少。但在某些特殊迷宫布局（如存在大量斜向路径优势的情况）下，可能会导致搜索方向不够精准，从而增加一些不必要的节点扩展。
欧几里得距离：理论上能提供更准确的方向估计，可能会比曼哈顿距离更早地引导搜索朝着终点方向进行，从而减少扩展节点数。然而，其计算复杂度较高，在大规模迷宫中计算量的增加可能会抵消一部分这种优势，导致实际扩展节点数不一定比曼哈顿距离少很多，甚至在极端情况下可能因为计算耗时导致搜索效率下降而增加扩展节点数。
对角线距离：在允许斜向移动且斜向移动成本合理的迷宫中，它能更好地适应斜向路径，相比曼哈顿距离可能会减少一些不必要的绕路节点扩展。但同样，其计算复杂度较高，在复杂迷宫中计算成本可能影响整体效率，且如果斜向移动成本设置不合理，可能导致搜索方向偏差而增加扩展节点数。
3.分析A*算法求解不同规模迷宫最短路径问题的性能
3.1分析不同起点终点
采用地图2，启发式函数 ℎ1 进行分析，分别设置起点为（1，1）和（9，5），终点为（20，20）、（18，20），结果如下：
(1,1)->(20,20)
(9,5)->(18,20)
两次寻路过程的性能分析如下表1。
| 路径 | （1，1）→(20，20) | （9，5）→(18，20) |
| 扩展节点数 | 100 | 73 |
| 生成节点数 | 71 | 57 |
| 运行时间 | 2.41020155 | 3.64384174 |
由上述图表可知路径延长后运行时间会相对变长，扩展节点及生成节点也会相应增多，且两次寻找的路程有重合的部分，所以寻找到的路径为较优路径。
3.2分析不同启发式函数
采用地图2，启发式函数 ℎ1 ， ℎ2 进行分析，设置起点为（1，1），终点为（20，20），两次寻路过程的路径，扩展节点数、生成节点数和运行时间如下图
启发函数h1
启发函数h2
由图表可知，两种启发式函数所用时间相近，但 ℎ2 相比 ℎ1 所扩展的节点数会减少，仔细分析可以发现启发式函数 ℎ1 在路径108位置首先寻找了另一条岔路，从而相比启发式函数 ℎ2 多扩展了3个节点。
3.3分析不同地图
上述过程一直采用地图2进行实验，为验证程序的普适性，现采用地图1进行实验。经过分析，选择上述较优的启发式函数 ℎ2 进行分析。寻路问题初始节点为（1，1），目标节点为（5，5），寻路路径如下
汇总上述性能报告如下表2。
| 地图 | 启发式函数 | 扩展节点数 | 生成节点数 | 运行时间 |
| 地图1 | h2 | 14 | 13 | 0.36682129 |
| 地图2 | h1 | 100 | 71 | 2.41153646 |
| 地图2 | h2 | 97 | 71 | 3.05070210 |
总结
A*算法在地图寻路问题中具有很好的优势，相比宽度优先搜索，效率更高，所耗时间更少，相比深度优先搜索，可以解决其不能找到最优解的不足，具有较高的应用价值。该算法的重点及难点就是启发式函数的选择，通过上述实验，可以发现启发式函数 ℎ2 相比 ℎ1 效果更好，但仍存在一些问题，需要继续找寻更优的启发式函数。
4. 提交源程序。
5.总结实验心得体会
本次实验让我受益匪浅，对 A* 算法有了更为深刻的理解和认识。以下是我在实验过程中的一些感悟。
1）理论与实践的紧密交融
通过实际操作，我对 A* 算法的工作原理有了更透彻的理解，尤其是深刻认识到启发式函数的重要性及其对算法性能的显著影响。在实验中，我掌握了曼哈顿距离和欧几里得距离这两种启发式函数的实现方法，并对比了它们在各种情况下的成效。这使我深切体会到，挑选适宜的启发式函数对于提升算法效率具有决定性意义。
2）编程实践中的挑战与成长
在编写 A* 算法的过程中，我遭遇了不少难题，例如如何精准地管理开放列表和关闭列表，以及怎样高效地完成节点的扩展和路径的重新构建。经过持续的调试与代码优化，我的编程能力得到了显著提升，特别是在处理数据结构和算法逻辑方面取得了长足的进步。
3）性能分析的收获与领悟
实验要求我对不同启发式函数的性能进行记录和对比，包括扩展节点数、生成节点数以及算法运行时间等方面。通过这些实验，我学会了如何科学地评估算法的性能，也明白了算法效率与问题规模之间的内在联系。我发现，在规模较小的迷宫中，启发式函数的选择对性能的影响相对较小；而在较大规模的迷宫中，一个更为优秀的启发式函数能够大幅缩短搜索时间并减少节点扩展的数量。
4）问题解决能力的提升
在实验过程中，我学会了将复杂问题拆解为若干个更小、更易于掌控的部分。A* 算法的成功实现让我明白，通过逐个解决这些小问题，最终能够圆满地解决整个复杂问题。
总的来说，这次实验是一次极具价值的学习体验。它不仅进一步加深了我对 A* 算法的理解，还全方位提升了我的编程和分析能力。我渴望将所学知识运用到更为复杂的实际问题中，比如游戏开发、机器人路径规划等领域。通过这次实验，我更加坚信，理论与实践的有机结合是掌握任何技术的最优途径。