a星算法视频

Ⅰ A星算法详解(个人认为最详细,最通俗易懂的一个版本)

在探索领域中，寻找最短路径的问题经常需要使用到A*算法。A*算法是一种广泛应用于路径规划和游戏开发中的启发式搜索算法。本文将通过详细的步骤，深入解读A*算法的运作原理和实现细节。首先，我们假设目标是从A点移动到B点，其中两点之间被一堵墙隔开。图1展示了这个示例，其中绿色代表A点，红色代表B点，蓝色代表墙。

图1展示了简化后的搜索区域，我们将其划分为正方形的格子。这一简化方法将搜索区域转化为二维数组，数组的每一项代表一个格子，其状态为可走或不可走。通过计算从A点到B点需要经过哪些格子，我们可以找到一条路径。当路径确定后，角色将从一个格子的中心移动到另一个格子的中心，直至到达目的地。

在A*算法中，搜索区域的简化为节点（nodes）的引入提供了基础。节点可以被放置在任意多边形内，可以位于多边形的中心，也可以位于边线上。使用这种方法最简单的原因在于其通用性，适用于不同形状的搜索区域。

算法开始于定义起点A，并将其加入到一个名为开放列表（open list）的集合中。开放列表是一个待检查的格子列表，其中的格子可能是路径的一部分，也可能是路径的候选。随后，我们检查起点A的相邻格子，并将其中可走的或可到达的格子加入开放列表中，同时将起点A作为这些格子的父节点。在追踪路径时，父节点的信息至关重要。

下一步是从开放列表中选择一个与起点A相邻的格子，重复上述过程。但选择哪一格子则基于其F值最小的原则。F值是由G值（从起点A到特定格子的移动代价）和H值（从该格子到终点B的估算成本）相加得到的。

路径排序涉及计算路径中每个格子的F、G和H值。G值代表从起点A到指定格子的移动代价，横向和纵向移动的代价为10，对角线移动的代价为14。这些数值简化了计算过程，同时提高了算法的执行效率。H值通过估计起点到终点的曼哈顿距离计算得出，即横向和纵向距离的总和，忽略对角移动。

计算出G和H值后，我们得到F值，用于后续选择操作。在选择过程开始时，我们会遍历开放列表，选择F值最小的格子。这一过程不断重复，直到将终点加入开放列表，路径被找到。在每一步中，选择的格子从开放列表移除，加入到关闭列表（closed list）中，表示不再需要关注的格子。

在搜索过程中，我们需要对选定的格子执行一系列操作。首先，将该格子从开放列表中移除并加入到关闭列表中。接着，检查与该格子相邻的格子，忽略那些已位于关闭列表中或不可走的格子。对于不在开放列表中的相邻格子，将其加入开放列表中，并将选定的格子作为其父节点。若相邻格子已在开放列表中，会检查新路径是否更优。如果新路径更优，则更新该格子的父节点，并重新计算其F、G和H值。

在搜索过程中，我们不断重复上述步骤，直到找到终点或确定无法找到路径。当终点被加入开放列表后，搜索过程完成。此时，我们可以通过追踪父节点从终点回溯到起点，找到最短路径。

在实现A*算法时，关键在于如何高效地维护开放列表和关闭列表，以及计算路径代价（G、H和F值）。为了优化性能，可以采用排序数据结构（如二叉堆）来管理开放列表，以便快速找到具有最小F值的格子。在考虑其他单位、优化速度、地形损耗、维护未探测区域、平滑路径以及处理非方形搜索区域时，A*算法的实现细节变得更为丰富和复杂。通过阅读相关的高级主题和参考资料，如Amit的A*页面、Smart Moves: Intelligent Path Finding和Terrain Analysis等文章，可以进一步深入理解A*算法的高级应用和优化策略。

Ⅱ A星寻路算法详解

A星寻路算法详解

A星算法是解决静态路网中求解最短路径的有效直接搜索方法。其核心公式为F = G + H，其中F表示当前点的总估价，G表示从起始点到指定网格的实际代价，H表示从当前网格点到终点的预计代价。启发函数的大小取决于计算H代价的函数，常用启发函数包括曼哈顿距离和欧几里得距离。

曼哈顿距离是指在坐标系中，从一个点到另一个点沿着网格线（水平或垂直）的距离。欧几里得距离是指在n维空间中，两点之间的直线距离。在二维空间中，欧几里得距离可以通过勾股定理得到。

A星算法的实现步骤包括：根据核心公式计算当前点的F值，选取F值最小的点进行探索。计算其周围相邻节点的G、H、F值，更新节点的G、F值和父节点。若节点已探索，则跳过，否则加入openList并计算其F值。重复上述步骤直至找到终点。

通过例子展示A星算法的实现过程。在网格地图中，黑色方格表示障碍物，白色方格为可通行区域，绿色方格为起点，红色方格为终点。根据算法步骤，计算每个节点的G、H、F值，选择F值最小的节点进行探索。在探索过程中，若遇到障碍物则H值不受影响。最终找到一条从起点到终点的最短路径。

A星算法是一种启发式搜索算法，通过启发式函数评估每个节点，并选择具有最低F值的节点作为下一个要探索的节点。最终，算法会找到一条最优路径。

通过一个网站演示A星算法的过程，项目源码可以在相关链接中查看。欢迎关注公众号“前端架构师笔记”了解更多精彩文章。

Ⅲ 人工智能 A*算法原理

A 算法是启发式算法重要的一种，主要是用于在两点之间选择一个最优路径，而A 的实现也是通过一个估值函数

上图中这个熊到树叶的 曼哈顿距离 就是蓝色线所表示的距离，这其中不考虑障碍物，假如上图每一个方格长度为1，那么此时的熊的曼哈顿距离就为9.
起点（X1,Y1）,终点（X2,Y2）,H=|X2-X1|+|Y2-Y1|
我们也可以通过几何坐标点来算出曼哈顿距离，还是以上图为例，左下角为（0，0）点，熊的位置为（1，4），树叶的位置为（7，1），那么H=|7-1|+|1-4|=9。

还是以上图为例，比如刚开始熊位置我们会加入到CLOSE列表中，而熊四周它可以移动到的点位我们会加入到OPEN列表中，并对熊四周的8个节点进行F=G+H这样的估值运算，然后在这8个节点中选中一个F值为最小的节点，然后把再把这个节点从OPEN列表中删除，加入到Close列表中，从接着在对这个节点的四周8个节点进行一个估值运算，再接着依次运算，这样说大家可能不是太理解，我会在下边做详细解释。

从起点到终点，我们通过A星算法来找出最优路径

我们把每一个方格的长度定义为1，那从起始点到5位置的代价就是1，到3的代价为1.41，定义好了我们接着看上图，接着运算

第一步我们会把起始点四周的点加入OPEN列表中然后进行一个估值运算，运算结果如上图，这其中大家看到一个小箭头都指向了起点，这个箭头就是指向父节点，而open列表的G值都是根据这个进行计算的，意思就是我从上一个父节点运行到此处时所需要的总代价，如果指向不一样可能G值就不一样，上图中我们经过计算发现1点F值是7.41是最小的，那我们就选中这个点，并把1点从OPEN列表中删除，加入到CLOSE列表中，但是我们在往下运算的时候发现1点的四周，2点，3点和起始点这三个要怎么处理，首先起始点已经加入到了CLOSE，他就不需要再进行这种运算，这就是CLOSE列表的作用，而2点和3点我们也可以对他进行运算，2点的运算，我们从1移动到2点的时候，他需要的代价也就是G值会变成2.41，而H值是不会变的F=2.41+7=9.41，这个值我们发现大于原来的的F值，那我们就不能对他进行改变（把父节点指向1，把F值改为9.41，因为我们一直追求的是F值最小化），3点也同理。

在对1点四周进行运算后整个OPEN列表中有两个点2点和3点的F值都是7.41，此时我们系统就可能随机选择一个点然后进行下一步运算，现在我们选中的是3点，然后对3点的四周进行运算，结果是四周的OPEN点位如果把父节点指向3点值时F值都比原来的大，所以不发生改变。我们在看整个OPEN列表中，也就2点的7.41值是最小的，那我们就选中2点接着运算。

我们在上一部运算中选中的是1点，上图没有把2点加入OPEN列表，因为有障碍物的阻挡从1点他移动不到2点，所以没有把2点加入到OPEN列表中，整个OPEN列表中3的F=8是最小的，我们就选中3，我们对3点四周进行运算是我们发现4点经过计算G=1+1=2，F=2+6=8所以此时4点要进行改变，F变为8并把箭头指向3点（就是把4点的父节点变为3），如下图

我们就按照这种方法一直进行运算，最后 的运算结果如下图

而我们通过目标点位根据箭头（父节点），一步一步向前寻找最后我们发现了一条指向起点的路径，这个就是我们所需要的最优路径。 如下图的白色选中区域

但是我们还要注意几点

最优路径有2个

这是我对A*算法的一些理解，有些地方可能有BUG，欢迎大家指出，共同学习。