【WHUT】*实验报告*《人工智能概论》课内实验：A*算法仿真实验

A*算法仿真实验 请下载并安装附件（虚拟实验软件-启发式搜索.rar）里的智能搜索算法教学实验系统，然后点击A*算法进行仿真实验。 实验要求如下： 1. 单击"A*算法介绍"，回顾A*算法的基本原理。 2. 在"A*算法演示程序"中，选择"自动寻路问题演示"进行仿真实验： 2.1设置起点、终点和墙：选中“起点”并单击某一方格可设置起点，选中“终点”并单击某一方格可设置终点，选中“墙”并单击若干个方格可设置墙，若单击“重置”则清除所有的设置。 2.2 运行A*算法：单击“开始”，可以看到起点的实际代价g（搜索深度，即搜索步数）、估计代价h（起点到终点的哈密尔顿距离，即起点到终点的横向和纵向的方格数之和）和估价函数值f（f=g+h），然后依次单击若干次“下一步”后，可以看到有深蓝色边框的方格为当前正扩展的状态节点，天蓝色的方格为open表中待扩展的状态节点，灰色的方格为放入closed表的已扩展的状态节点，一直到搜索到终点为止，或者单击“继续”直接搜索到终点。如果单击“重置”则重新按照2.1和2.2重新进行实验。 2.3 结果记录：请拍照或者截图搜索到终点的实验结果图，并记录A*算法 **A*算法详解** A*算法是一种启发式搜索算法，广泛应用于路径规划、游戏AI、图形处理等领域。它结合了Dijkstra算法的最优性保证和Greedy算法的搜索效率，通过一个评估函数来指导搜索方向，减少无效的探索。评估函数通常由实际代价g和估计代价h构成，公式为f(n) = g(n) + h(n)，其中g(n)是从起点到当前节点的实际路径成本，h(n)是从当前节点到目标节点的启发式估计成本。 在实验中，我们首先回顾A*算法的基本原理，它利用启发式信息来优化搜索路径，通过维护一个优先级队列（open表）来存储待扩展的节点，优先选择具有最低f值的节点进行扩展。同时，还有一个closed表用来记录已经扩展过的节点，避免重复搜索。 在仿真实验中，用户可以通过设置起点、终点和障碍物来模拟复杂环境。运行A*算法，我们可以观察到节点的扩展过程，深蓝色边框表示当前正在扩展的节点，天蓝色表示open表中的待扩展节点，灰色表示已扩展的节点。实验结果显示，A*算法扩展的节点数量相对较少，这是因为算法有效利用了启发式信息来指导搜索，避免了大量的无效探索。 实验分析了实际代价g和估计代价h的特点。起点的实际代价g通常为0，因为它就是起始位置；终点的估计代价h则是对从起点到终点最短路径的预估，通常在未达到目标前为非0。估价函数f是实际代价与估计代价的和，用于决定搜索方向。在搜索过程中，f值会随着节点的扩展而逐渐接近实际的总代价。 在8数码问题的演示中，A*算法的扩展节点数和生成节点数展示了其效率。与其他盲目搜索算法（如深度优先搜索和宽度优先搜索）相比，A*算法能更快找到最优解，因为它结合了启发式信息，减少了访问节点的数量和搜索时间。采用哈密顿距离作为启发函数优于不在位数，是因为哈密顿距离考虑了从当前状态到目标状态的实际移动代价，提供了更准确的路径估计，从而减少了无效的探索路径。 对于拓展问题，八数码问题中判断两个状态是否可以到达，可以通过计算它们的有序数列的逆序值。如果逆序值均为奇数或偶数，说明可以通过一系列合法操作（每次移动一个数字到空位）将原状态转换为目标状态；反之，如果逆序值奇偶性不同，则无法转换。这展示了状态转换的数学基础，进一步证明了A*算法在解决此类问题时的有效性和效率。