相比于传统的深度搜索和广度搜索的递归回溯算法，A*算法启发式的提供代价估算能力来评估到达目标结点的最短路径所需的代价，即到达终点最省体力的方式。这在我们日常地图导航需求中得到了广泛的应用。本小节我们将以图解的方式向大伙儿揭示A星（这里姑且用星来代指*）算法的奥秘。
引出问题
现在我们看两个简单的例子，通过简单明了的问题直接给出答案的形式，让大家先思考下实现该问题的算法是怎样的。这或许很难，但是带着探索的乐趣积极的思考来叩响知识的大门这是第一步。
算法示意图
迷宫一图解：
迷宫二图解：
伪代码
这里以一个二位数组代表我们的迷宫地图，元素为1代表障碍物，0（这里省略）代表可通行，S代表起点，E代表终点。天蓝色代表一个优先级队列（也叫Open队列）中保存的被辐射出来的结点，绿色代表已经评估过路径代价的结点，位于一个Close集合中。黄色的箭头代表结点的父子关系（连接方向）。每个加入Open队列的结点都会计算一个G值（由起点经过多少步到达当前结点）和一个H值（由当前结点经过多少步到达终端，只考虑最短的步数，不考虑障碍物）。以下是算法的核心步骤：
默认将起点作为被辐射的起点，加入Open队列
只要Open队列不为空，从中poll代价值（G + H）最小的结点，记为currNode，如果它已经是终点，则按照父节点引用回溯到起点输出最短路径，否则如果Open队列已为空，结束程序，提示无通路，否则把currNode放到Close列表中，执行后续操作
为currNode进行四周（左、上、右、下四个方向）辐射，也就是处理邻结点，具体的处理方式：
3.1. 获取邻结点要在数组边界内，跳过值为1的障碍物，并且忽略已在Close列表中的结点
3.2. 获取到邻结点后，根据(x, y)索引信息判断是否已在Open队列中：
3.2.1. 已经在队列中，则判断G值如果比现在计算的大，则调整结点的G值，并设置其父节点为currNode，将其对象重新添加到队列
3.2.2. 在队列，则根据坐标索引计算G值、H值，绑定currNode为当前结点，新创建一个对象，将其添加到Open队列
继续执行第2步
算法思想
算法的主要思想就是从起点开始不断的向四周（左、上、右、下四个结点）辐射，当然辐射会被障碍物阻挡，但是辐射整体会朝着离目标结点更近的趋势进行，关键就是在挑选新的结点辐射时，会做一个代价评估，也就是从起点经过该结点到目标结点所要花费的代价。这里我们设定迷宫的走法只能每次横向或者纵向移动一步，那么相邻（非斜向）两个结点的代价就是1。
这里淡蓝色的格子表示被当前选中的结点（也是从已被辐射的结点中选，按照总代价F来选，关于总代价F后面有介绍）所辐射的结点，我们会将其记录在一个能按照权重的优先级进行获取的一个集合中，这里我们可以考虑用Java中的优先级队列PriorityQueue进行存储。这些被当前结点辐射的结点我们称之为Open状态，因为它们还未被挑选。
一旦某个结点从优先级队列中“出列”，这里我们假设总代价F值越小的优先级越高（排在前列），被选中的结点会作为当前结点，这里我们以红框显示，将它放入一个Close集合。该Close集合存放的是每次从Open队列中获取的评估代价值最小（如果有多个结点代价值一样，任取其一）的结点，因为只用于存储目的，用ArrayList即可。在上述图示中以绿框代表已经进行代价评估的结点。
我们在来看A星算法中最核心的代价评估，它有一个公式：
F=G+HF = G+H F=G+H
首先聊下什么是代价值，可以认为它指的是两个点之间的距离，假定迷宫的轨迹指定横向或者纵向绘制，它指的是两个结点之间连接所经过的步数，这里每一步我们记录其代价值为1。计算代价值有一个公式，叫做曼哈顿距离计算公式，这里我们记录两个结点在代表迷宫的二维数组中的索引位置分别为(x1, y1)和(x2, y2)。则它们之间的距离d（代价值）的计算公式为：
d=∣x1−x2∣+∣y1−y2∣d = |x1-x2|+|y1-y2| d=∣x1−x2∣+∣y1−y2∣
|a - b|代表求取横向或纵向索引之间的绝对值。
G代表当前结点与起点的代价值，从起点开始每个被辐射的结点都会记录它与起点的代价值为G（作为自己的属性），计算方式为当前结点的G值加1（相邻代价值）。H代表当前结点与终点的代价值。需要注意的这只是排除障碍物的理想的代价，实际可能与终点并不连通。
通过引入和考量结点的代价值，可以确保每次从Open队列中获取的都是总代价最小的结点，对它再做四周辐射。这种辐射可以理解为我们在玩一个RPG游戏时开拓未知区域的地图，而对于辐射出来的Open结点，如何知道哪个或哪些距离终点最近，看总代价F即可。如果存在多个相同总代价值的Open结点，这里的选择是随机的，会最终将辐射趋势引入死胡同，这是该算法存在的一个弊端，比如这里的迷宫二的情况。但不管怎样，它都可能会跳过一些代价值太大而永远无法被选中的结点。在辐射到之前已被辐射的Open结点时，会重新评估其G值，也就是与起点的代价值，如果更小，则更新辐射路径，最终当辐射蔓延到终点时，则可以回溯得到起点与终点的连通路径；或者当Open队列为空，无法再进行辐射，而终点不包含在Close集合中时，则说明无法从起点到终点找到一条连通路径。
具体的代码实现将会在笔者的另一个技术专栏Java设计模式活学活用即将更新的《A*算法提升敌方坦克智能》小节呈现，大家加油！
