A*算法思路

青旅半醒 2022-08-06 17:05 167阅读 0赞

最近研究了一下A\*算法，算法的思路理解了之后实现起来挺简单的，具体实现方式就不写了，因为这个没有标准，核心的逻辑都是一样的，但是根据不同的需求和情况会有不同的写法。

先说一下核心概念，A\*是启发式寻路算法，寻找出来的路径的准确性跟你选择的启发算法有关，具体的讲，这个算法会对A\*算法的判断逻辑起到引导的作用，这正是人工智能所在，模仿了人类大脑的逻辑思维。

看下边的图（1），假设你要从A点经过障碍到B点，你要走最近的路，那么，首先你会判断，下一步我要走到哪个格子,么我们的依据是什么？也就是说我们大脑是根据什么来进行判断的？

应该，有两点：

一、我要距离B点更近，也就是说我肯定是选择离B点更近的格子作为下一步的落脚点。

二、要做到最小消耗，假设我们开车的话，我们要消耗汽油，那么我们上下左右移动消耗10点汽油。而斜上斜下移动需要消耗14点汽油。那么，我们肯定先选择去走，1号格子，因为它符合上边我说的判断逻辑，最小消耗和距离B点最近，所以我选择1号格子。

那好，有不同意见的小伙伴先不要说话，我的大脑比较笨，只会一步一步思考，这时我走到了1号格子，那么我重复进行判断逻辑选择下一步，请注意，右边是墙壁了，我肯定不会判断的，而身后的格子，也不判断了（避免逻辑复杂，不考虑找不到路回退的情况），所以我只能选择上面或者下面的格子，那么我要么移动到上边一个格子，要么移动到下边一个格子没错吧，那好，那么我移动到2号格子，注意，我又进行了一次移动，我又要消耗10点的汽油了，我们穷屌丝怎么受的了，当然屌丝是没有汽车的- -！那当我移动到2号格子的时候，我一共需要移动两次，先1->2，一共消耗20点的汽油！所以我们的大脑肯定要回忆，注意是在回忆！经过回忆我发现如果从A点移动到2号格子，才只消耗14点的汽油而已！那么好，我就不走1号格子了，而直接走2号格子，然后再次执行上边的思考逻辑！这就是一次完整的A\*寻路的逻辑思维！所以说，A\*的重点是，我们要正确的判断出最好的那一步移动方式，也就是选择启发算法。

![Image 1][]

图（1）

当然了，这个地图比较简单，所以我们大脑的思维逻辑也很简单，如果地图更复杂一些，我们就要加入更多的判断逻辑在里边。下边是伪代码，我会对每一步做解释，对应上边讲的大脑思维方式。

定义两个表结构，作为大脑的记忆

listIdex //还没判断过的

listClose//已经判断过的

给每个点添加成员，G汽油消耗，H到B点的距离，F值G和H的和，表示对消耗和距离的综合评定。最后要有一个指向性的成员，这个成员指向我来时的方向， 比如，我从A移动到1方格，那么我来的方向就是A。

然后：

1、把起点A，放入我们的listIdex表，存入大脑记忆中。

2、从listIdex表中找到最优的点，通过判断F值，因为F表示的是一个综合性的评定（第一次判断的时候listIdex表中只有起点，所以最小F是起点）。

3、依据找到的最小F值的点，来判断所有下一步可以移动的点，四周八个方向都可以移动，放入我们的临时记忆中，listNext表。

4、然后把这八个点依次的都记住，在记的过程中我们做一些其他的思考和判断