A*算法在寻路问题中的应用-19S103256文荟俨实验报告

"本次实验是关于搜索算法的学习和实践，特别是A*算法的应用。实验的主要目的是让学生理解并掌握搜索算法的基本原理，特别是A*算法的设计思路，同时要求学生能够使用高级编程语言实现这一算法，并通过具体寻路问题的实例来验证算法的正确性。实验中设置了具体的寻路规则，如地图由方格组成，障碍物为灰色格子，不同地形的移动代价不同，路径代价由移动代价和地形代价两部分组成。实验步骤包括使用单向A*算法进行路径规划，涉及openlist和closelist的操作，并定义了一个包含坐标、F、G、H值以及父节点指针的结构体用于路径的计算和回溯。" 实验中，A*算法是一个重要的知识点，它是启发式搜索算法的一种，结合了Dijkstra算法的最优化路径寻找和贪婪最佳优先搜索的特性。A*算法的核心在于使用了F值（F = G + H）来评估节点的优劣，其中G值表示从起点到当前节点的实际代价，H值是当前节点到目标节点的启发式估计代价。算法的目标是找到F值最小的节点，以逐步接近目标。 在实验步骤中，首先将起始点S加入openlist，然后在while循环中不断找出openlist中F值最低的节点，将其移入closelist。如果找到的节点是目标节点T，则结束搜索，否则更新其F、G、H值，并检查其邻接节点。邻接节点如果未被探索过，就将其加入openlist并设置当前节点为父节点；如果已在openlist中但F值更低，也会更新其F值和父节点信息。最后，通过回溯每个节点的父节点，从目标节点T反向构建出最优路径。 在实验的具体实现中，定义了一个名为my_point的结构体，包含了节点的坐标信息（x和y），以及F、G、H值。F值用于比较节点的优先级，G值记录实际移动代价，H值是启发式估计代价，而parent属性则用于回溯路径。这个结构体对于A*算法的实现至关重要，因为它提供了存储和更新节点状态的载体。 通过这个实验，学生不仅可以深入理解A*算法的工作机制，还能提高编程能力，尤其是处理复杂数据结构和优化问题的能力。同时，实验中设定的寻路问题使得理论知识与实际应用相结合，有助于巩固和扩展学生的算法思维。