A星算法

A*（A-Star)算法是一种静态路网中求解最短路最有效的方法。公式表示为：f(n)=g(n)+h(n)，其中f(n)是节点n从初始点到目标点的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。

一、算法比较

1、Dijkstra算法

Dijkstra算法从物体所在的初始点开始，访问图中的结点。它迭代检查待检查结点集中的结点，并把和该结点最靠近的尚未检查的结点加入待检查结点集。该结点集从初始结点向外扩展，直到到达目标结点。Dijkstra算法保证能找到一条从初始点到目标点的最短路径，只要所有的边都有一个非负的代价值。（我说“最短路径”是因为经常会出现许多差不多短的路径。）在下图中，粉红色的结点是初始结点，蓝色的是目标点，而类菱形的有色区域（注：原文是teal areas）则是Dijkstra算法扫描过的区域。颜色最淡的区域是那些离初始点最远的，因而形成探测过程（exploration）的边境（frontier）：

对于有障碍物的情况下，Dijkstra算法运行得较慢，但确实能保证找到一条最短路径：

2、最佳优先搜索（BFS）

最佳优先搜索（BFS算法按照类似的流程运行，不同的是它能够评估（称为启发式的）任意结点到目标点的代价。与选择离初始结点最近的结点不同的是，它选择离目标最近的结点。BFS不能保证找到一条最短路径。然而，它比Dijkstra算法快的多，因为它用了一个启发式函数（heuristic function）快速地导向目标结点。例如，如果目标位于出发点的南方，BFS将趋向于导向南方的路径。在下面的图中，越黄的结点代表越高的启发式值（移动到目标的代价高），而越黑的结点代表越低的启发式值（移动到目标的代价低）。这表明了与Dijkstra 算法相比，BFS运行得更快。

对于有障碍物的情况，BFS运行得较快，但是它找到的路径明显不是一条好的路径：

二、A star算法

1968年发明的A star算法就是把启发式方法（heuristic approaches）如BFS，和常规方法如Dijsktra算法结合在一起的算法。有点不同的是，类似BFS的启发式方法经常给出一个近似解而不是保证最佳解。然而，尽管A star基于无法保证最佳解的启发式方法，A star却能保证找到一条最短路径。

在简单的情况中，它和BFS一样快,在凹型障碍物的例子中，A*找到一条和Dijkstra算法一样好的路径.

A star把Dijkstra算法（靠近初始点的结点）和BFS算法（靠近目标点的结点）的信息块结合起来。在讨论A star的标准术语中，g(n)表示从初始结点到任意结点n的代价，h(n)表示从结点n到目标点的启发式评估代价（heuristic estimated cost）。在上图中，yellow(h)表示远离目标的结点而teal(g)表示远离初始点的结点。当从初始点向目标点移动时，A star权衡这两者。每次进行主循环时，它检查f(n)最小的结点n，其中f(n) = g(n) + h(n)。

1、启发函数

启发式函数h(n)告诉A*从任意结点n到目标结点的最小代价评估值。选择一个好的启发式函数是重要的。

• 一种极端情况，如果h(n)是0，则只有g(n)起作用，此时A演变成Dijkstra算法，这保证能找到最短路径。
• 如果h(n)经常都比从n移动到目标的实际代价小（或者相等），则A保证能找到一条最短路径。h(n)越小，A扩展的结点越多，运行就得越慢。
• 如果h(n)精确地等于从n移动到目标的代价，则A star将会仅仅寻找最佳路径而不扩展别的任何结点，这会运行得非常快。尽管这不可能在所有情况下发生，你仍可以在一些特殊情况下让它们精确地相等（译者：指让h(n)精确地等于实际值）。只要提供完美的信息，A star会运行得很完美，认识这一点很好。
• 如果h(n)有时比从n移动到目标的实际代价高，则A star不能保证找到一条最短路径，但它运行得更快。
• 另一种极端情况，如果h(n)比g(n)大很多，则只有h(n)起作用，A star演变成BFS算法。

2、算法流程

OPEN = priority queue containing START
CLOSED = empty set
while lowest rank in OPEN is not the GOAL:
  current = remove lowest rank item from OPEN
  add current to CLOSED
  for neighbors of current:
    cost = g(current) + movementcost(current, neighbor)
    if neighbor in OPEN and cost less than g(neighbor):
      remove neighbor from OPEN, because new path is better
    if neighbor in CLOSED and cost less than g(neighbor): ⁽²⁾
      remove neighbor from CLOSED
    if neighbor not in OPEN and neighbor not in CLOSED:
      set g(neighbor) to cost
      add neighbor to OPEN
      set priority queue rank to g(neighbor) + h(neighbor)
      set neighbor's parent to current

reconstruct reverse path from goal to start
by following parent pointers

3、图解算法

下面通过图解的方式解释A star 算法的工作流程。

如图所示，绿色点为start设为A，红色点为goal设为B，蓝色点为不可通过的障碍物，黑色点为自由区域。目标是规划从A到B的路径。

开始

1. 搜索的从A点开始，首先将A点加入开启列表，此时取开启列表中的最小值，初始阶段开启列表中只有A一个节点，因此将A点从开启列表中取出，将A点加入关闭列表。
2. 取出A点的相邻点，将相邻点加入开启列表。如图所示，此时A点即为相邻点的父节点。图中箭头指向父节点。将相邻点与A点加入追溯表中。

计算评分

对相邻点，一次计算每一点的g，h，最后得到f = g + h。如图，节点的右下角为g值，左下角为h值，右上角为f。

选最小值，再次搜索

1. 选出开启列表中的F值最小的节点，将此节点设为当前节点，移出开启列表，同时加入关闭列表。如图所示。
2. 取出当前点的相邻点，当相邻点为关闭点或者墙时，不操作。此外，查看相邻点是否在开启列表中，如不在开启列表中将相邻点加入开启列表。如相邻点已经在开启列表中，则需要进行G值判定

G值判定

对于相邻点在开启列表中的，计算相邻点的G值，计算按照当前路径的G值与原开启列表中的G值大小。如果当前路径G值小于原开启列表G值，则相邻点以当前点为父节点，将相邻点与当前点加入追溯表中。同时更新此相邻点的H值。如果当前路径G值大于等于原开启列表G值，则相邻点按照原开启列表中的节点关系，H值不变。因为图示中，当前点G值比原开启列表G值大，因此节点关系按照原父子关系和F值。

计算耗费评分，选最小值

此时计算开启列表中F值最小的点，将此节点设为当前节点，并列最小F值的按添加开启列表顺序，以最新添加为佳。

重复搜索判定工作

直到当goal点B加入开启列表中，则搜索完成。此时事实上生成的路径并一定是最佳路径，而是最快计算出的路径。若判定标准改为当goal点B加入关闭列表中搜索完成，则得出路径是最佳路径，但此时计算量较前者大。

当没有找到goal点，同时开启列表已空，则搜索不到路径。结束搜索。

生产路径

由goal点B向上逐级追溯父节点，追溯至起点A，此时各节点组成的路径即使A*算法生成的最优路径。

三、Java实现

需要一个Node类记录经过的每一个结点的信息，Node类的信息如下：

//结点的属性
//因为每个结点都需要存放在优先队列中，所以需要实现Comparable接口
class Node implements Comparable<Node> {
   public int x;  //x坐标
   public int y;  //y坐标
   public int F;  //F属性
   public int G;  //G属性
   public int H;  //H属性
   public Node Father;    //此结点的上一个结点
   //构造函数
   public Node(int x, int y) {
       this.x = x;
       this.y = y;
   }
   //通过结点的坐标和目标结点的坐标可以计算出F， G， H三个属性
   //需要传入这个节点的上一个节点和最终的结点
   public void init_node(Node father, Node end) {
       this.Father = father;
       if (this.Father != null) {
           //走过的步数等于父节点走过的步数加一
           this.G = father.G + 1;
       } else { //父节点为空代表它是第一个结点
           this.G = 0;
       }
       //计算通过现在的结点的位置和最终结点的位置计算H值
       this.H = Math.abs(this.x - end.x) + Math.abs(this.y - end.y);
       this.F = this.G + this.H;
   }
   // 用来进行和其他的Node类进行比较重写的方法
   @Override
   public int compareTo(Node o) {
       return Integer.compare(this.F, o.F);
   }
}

接下来是Solution方法，所有的算法和数据结构都存放在这个方法中

• 首先需要一个地图：

// -1 -> 墙壁， 1 -> 起点  2 -> 终点
public int[][] map = {
           {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
           {-1,  0,  0,  0,  0,  0,  0,  0,  0, -1},
           {-1,  0,  0,  0,  0, -1,  0,  0,  0, -1},
           {-1,  0,  0,  0, -1,  0,  0,  0,  0, -1},
           {-1,  0,  1,  0, -1,  0,  0,  2,  0, -1},
           {-1,  0,  0,  0,  0, -1,  0,  0,  0, -1},
           {-1,  0,  0,  0, -1,  0,  0,  0,  0, -1},
           {-1,  0,  0,  0,  0, -1,  0,  0,  0, -1},
           {-1,  0,  0,  0,  0,  0,  0,  0,  0, -1},
           {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}
           };

这个map就是上面的地图，由于判断地图是否越界过于麻烦，添加了辅助区域，让我们对【当前结点】进行扩展操作的时候判断扩展是否越界变得简单直观，只要不等于-1就代表没有越界，而不必判断x坐标和y坐标的范围。

• 有了地图之后我们还需要【Open表】，【Close表】

• 对结点进行扩展添加的时候除了需要判断结点是否合法，还需要判断结点是否在【Open表】和【Close表】中出现过

• 但是由于【Open表】不是可以遍历的数据结构，为了方便使用【Exist表】来记录当前结点是否出现在【Open表】中和【Close表】中

  //Open表用来存放能够到达的结点
  //Open表会自动把F值最小的结点放在队首
  public PriorityQueue<Node> Open = new PriorityQueue<Node>();
  //Close表用来存放已经到达的结点
  public ArrayList<Node> Close = new ArrayList<Node>();
  //Exist表用来存放两张表出现过的结点
  public ArrayList<Node> Exist = new ArrayList<Node>();
  
  

• 判断一个结点是否出现过（is_exist方法）

public boolean is_exist(Node node)
{
   for (Node exist_node : Exist) {
       //如果这个结点在Exist中出现过，返回true
       if (node.x == exist_node.x && node.y == exist_node.y) {
           return true;
       }
   }
   //没有出现返回false
   return false;
}

• 怎么判断一个结点是否合法（is_valid方法）

public boolean is_valid(int x, int y) {
   // 如果结点的位置在地图上是-1，则不合法
   if (map[x][y] == -1) return false;
   for (Node node : Exist) {
       //如果结点出现过，不合法
       if (is_exist(new Node(x, y))) {
               return false;
       }
   }
   //以上情况都没有则合法
   return true;
}

• 怎么扩展【当前结点】的【上】【下】【左】【右】四个方向的结点(extend_current_node方法)

public ArrayList<Node> extend_current_node(Node current_node) {
   //获取当前结点的x, y
   int x = current_node.x;
   int y = current_node.y;
   //如果当前结点的邻结点合法，就加入到neighbour_node
   ArrayList<Node> neighbour_node = new ArrayList<Node>();
   if (is_valid(x + 1, y))
   {
       Node node = new Node(x + 1, y);
       neighbour_node.add(node);
   }
   if (is_valid(x - 1, y))
   {
       Node node = new Node(x -1, y);
       neighbour_node.add(node);
   }
   if (is_valid(x, y + 1))
   {
       Node node = new Node(x, y + 1);
       neighbour_node.add(node);
   }
   if (is_valid(x, y - 1))
   {
       Node node = new Node(x, y - 1);
       neighbour_node.add(node);
   }
   //返回合法的邻结点们
   return neighbour_node;
}

• Astar寻路算法具体实现(astarSearch方法)

public Node astarSearch(Node start, Node end) {
   //把第一个开始的结点加入到Open表中
   this.Open.add(start);
   this.Exist.add(start);
   
   //主循环
   while (Open.size() > 0) {
       //取优先队列顶部元素并且把这个元素从Open表中删除
       Node current_node = Open.poll();
       
       //将这个结点加入到Close表中
       Close.add(current_node);
       //对【当前结点】进行扩展，得到一个邻居结点数组
       ArrayList<Node> neighbour_node = extend_current_node(current_node);
       //对这个邻居数组遍历，看是否有目标结点出现
       for (Node node : neighbour_node) {
           if (node.x == end.x && node.y == end.y) {//找到目标结点就返回
               //init_node操作把这个邻居结点的父节点设置为当前结点
               //并且计算出G， F， H等值
               node.init_node(current_node,end);
               return node;
           }
           if (!is_exist(node)) {  
               //没出现过的结点加入到Open表中并且设置父节点
               //进行计算对G, F, H 等值
               node.init_node(current_node, end);
               Open.add(node);
               Exist.add(node);
           }
       }
   }
   //如果遍历完所有出现的结点都没有找到最终的结点，返回null
   return null;
}