A*算法介绍_a*算法open表和close表

一、适用场景

在一张地图中，绘制从起点移动到终点的最优路径，地图中会有障碍物，必须绕开障碍物。

二、算法思路

1. 回溯法得到路径

(如果有路径)采用“结点与结点的父节点”的关系从最终结点回溯到起点，得到路径。

2. 路径代价的估算：F = G+H

A星算法的代价计算使用了被称作是启发式的代价函数。

先说明一下各符号意义：G表示的是从起点到当前结点的实际路径代价(为啥叫实际？就是已经走过了，边走边将代价计算好了)；H表示当前结点到达最终结点的估计代价(为啥叫估计？就是还没走过，不知道前面有没障碍、路通不通，所以只能用估计)；F表示当前结点所在路径从起点到最终点预估的总路径代价。

G的计算方式：计算方式有挺多种的，这里我们就用这种吧，假设每个结点代表一个正方形，横竖移动距离：斜移动距离=1：1.4（根号2），我们取个整数10和14吧，也就是说当前结点G值=父节点的G+（10或14）。

H的计算方式：估价计算也有很多种方式，我们这里使用“曼哈顿”法，H=|当前结点x值-最终结点x值|+|当前结点y值-最终结点y值|（"||"表示绝对值）。

如下图（图不是自己做的，从网上借来的，自己画的话~…惨不忍睹！）

3. 辅助表：Open、Close列表

在A星算法中，需要使用两个辅助表来记录结点。

一个用于记录可被访问的结点，成为Open表；一个是记录已访问过的结点，称为Close表。

这两个表决定了算法的结束：条件是最终结点在Close表中(找到路径)或Open表为空(找不到了路径)。

4. 移动结点、相邻结点的处理

上面的理解的话，现在就来移动当前的节点，寻找路径。

每次从Open表中取出F值最小的结点出来（这里我们使用优先队列来处理比较好），作为当前结点；然后将当前结点的所有邻结点按照邻结点规则加入到Open表中；最后将当前结点放入Close表中，这里就是每次循环的执行内容。

邻结点规则：

(1) 当邻结点不在地图中，不加入Open表；

(2) 当邻结点是障碍物，不加入Open表；

(3) 当邻结点在Close表中，不加入Open表；

(4) 当邻结点不在Open中，加入Open表，设该邻结点的父节点为当前结点；

(5) **当邻结点在Open表中，我们需要做个比较:如果邻结点的G值>当前结点的G值+当前结点到这个邻结点的代价，那么修改该邻结点的父节点为当前的结点(因为在Open表中的结点除了起点，都会有父节点)，修改G值=当前结点的G值+当前结点到这个邻结点的代价 **

蓝色框框表示在Close表中，绿色的框框表示在Open表中

最后回溯得到路径

三、代码实现(Java)

1. 输入

(1) 代表地图二值二维数组(0表示可通路，1表示路障)

int[][] maps = {

{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },

{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },

{ 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0 },

{ 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0 },

{ 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0 },

{ 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 },

{ 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 }

};

(2) 按照二维数组的特点，坐标原点在左上角，所以y是高，x是宽，y向下递增，x向右递增，我们将x和y封装成一个类，好传参，重写equals方法比较坐标(x,y)是不是同一个。

public class Coord

{

public int x;

public int y;

public Coord(int x, int y)

{

this.x = x;

this.y = y;

}

@Override

public boolean equals(Object obj)

{

if (obj == null) return false;

if (obj instanceof Coord)

{

Coord c = (Coord) obj;

return x == c.x && y == c.y;

}

return false;

}

}

(3) 封装路径结点类，字段包括：坐标、G值、F值、父结点，实现Comparable接口，方便优先队列排序。

public class Node implements Comparable<Node>

{

public Coord coord; // 坐标

public Node parent; // 父结点

public int G; // G：是个准确的值，是起点到当前结点的代价

public int H; // H：是个估值，当前结点到目的结点的估计代价

public Node(int x, int y)

{

this.coord = new Coord(x, y);

}

public Node(Coord coord, Node parent, int g, int h)

{

this.coord = coord;

this.parent = parent;

G = g;

H = h;

}

@Override

public int compareTo(Node o)

{

if (o == null) return -1;

if (G + H > o.G + o.H)

return 1;

else if (G + H < o.G + o.H) return -1;

return 0;

}

}

(4) 最后一个数据结构是A星算法输入的所有数据，封装在一起，传参方便。