AStar

AStar——既脚踏实地，又仰望星空

简介

AStar算法，又称为A*算法，它作为一个启发式的寻路算法，在大部分情况下的性能要优于非启发式算法（如Dijkstra算法和Prim算法），特别是时间复杂度方面，只要选取的估值函数足够好。

AStar算法可以用来搜寻所有非负图中的最短路径，并且能够找到最优解，是一种在人工智能和游戏引擎中被广泛使用的寻路算法。

原理

“既脚踏实地，又仰望星空”。A*算法的设计很巧妙地贯彻了这句鸡汤。假设一个旅行者需要找到起点和目的地之间的最短路径，那么他不仅会根据自己走过的中转站计算出到达这个中转站的最短路径，也会根据手中的地图来估计一下距离目的地还有多远的距离，在把两者权衡一下之后，选择接下来的旅行策略。这样既能够充分地利用已经走过的中转站，又不会出现南辕北辙的情况（明明这个中转站的方向是相反的还要去尝试）。或者说，借助非启发式算法的前提下，又一直在朝着目的地的方向迈进。

A*算法的核心函数如下：
$$
f(n)= g(n) + h(n)
$$

• f(n): 从起点到终点并且经过点n的一个路径长度估计值。在实际处理新的中间点的过程中，当这个点对应的f(n)越小，证明这个点具有更好地成为最短路径的潜质，因此会优先去考虑这个点的相邻点作为下一个可能的路径点。
• g(n): 从起点到点n并且经过其父节点的最短距离。
• h(n): 从点n到终点的估值距离。这个距离越大则算法性能越好，但是不能超过两点之间实际距离的最小值，否则不能保证得到最优解。可以使用极限法考虑，如果h(n) 趋向于无穷大，则永远不可能找到最短路径。实际上，当f(n)小于实际的最优解时，那么在后续的遍历中，最优解下的路径一定会将之前的那个路径给覆盖掉，当f(n)始终等于最优解时，该算法就一直在遍历最短路径了。

算法实现

图的基本结构

因为AStar算法是基于非负图的，因此数据结构的选取非常重要。如果把一张2D网格映射成一张图的话，其基本类和变量如下：

//图的结点
public class Node{
    String nodeId;  //为每个结点生成一个字符串Id，主要便于查找到这个结点和作为Key
    Point position; //用来存放该结点存储的坐标
    List<Node> neghbors; //存储相邻结点
    Map<String, Integer> distances; //通过Id来获得该点与相邻点之间的距离
}

//图类
public class Graph{
    Map<String, Node> graph;  //存储图中的所有结点
}

A*算法

为了便于理解，可以直接根据算法需要实现的功能来设计对应的数据结构。

• g(n): 该函数需要得到当前结点在经过父节点的情况下到达起点的最短路径，可以直接利用Dijkstra算法的思想来实现，假设点n-1是点n的父节点并且g(n-1)已知，那么g(n) = min(g(n), g(n-1) + d(n-1, n)), 其中d是两点之间的距离。为了记录当前结点的父节点，可以设计数据结构Map<String, Node> cameFrom，这样，可以通过当前结点的Id找到其父节点。g(n)也可以通过Map来实现。
• h(n): 估算点n到终点的距离，保证h(n)小于实际最短距离的前提下让估算值越接近真实值越好，因此对于不同的实际问题可以采取不同的计算方式。一般来说，对于一个2D平面，采取两点之间的线段距离，而对于一个2D的网格，因为不能斜着走，所以两点直接长宽差的和就是最短的情况了。
• f(n): 用来指导算法的行进方向，也可以通过Map来存储每个结点对应的函数值，同时，为了使得每次取出f(n)值最小的结点，可以采用堆结构或者优先队列的结构来存储结点，即PriorityQueue<Node> openSet。

这样，已知的变量如下：

Map<String, Node> cameFrom;
Map<String, Integer> gScore;
Map<String, Integer> fScore;
PriorityQueue<Node> openSet = new PriorityQueue<>(new Comparator<Node>(){
   //f(n)越小则对应结点放置地越靠前
   @override
   public int compare(Node o1, Node o2){
       return fScore.get(o1.getNodeId()).compareTo(fScore.get(o2.getNodeId));
   }
});

h(n)需要根据场景不同进行不同的设计：

   /**
    * heuristic function that caculate approximately the distance between 
    * current point and the end point.
    * <p><strong>About distance : </strong>in AStar algorithm, the bigger is distance,
    * the better its performance can be. However, this appro. distance shouldn't beyond the 
    * actual distance between the two points. Otherwise, it may can't get the best
    * solution.
    * <p>in 2D grid, the distance can set as width add length
    * <p>in 2D map, the distance should set as the segment's length between the
    * two points
    * 
    * @param cur the current point
    * @param end the end point
    * @return the approximately distance between two points
    */
int heuristic(Point cur, Point end, int mode){
       switch (mode) {
           //不进行估值，NONE是定义的常变量
           case AStar.NONE:
               return 0;
           //网格图    
           case AStar.GRID:
               return Math.abs(end.getRow() - cur.getRow()) + Math.abs(end.getCol() - cur.getCol());
           //一般的2D平面
           case AStar.EUCLID:
               double dx = cur.getRow() - end.getRow();
               double dy = cur.getCol() - end.getCol();
               return (int)Math.sqrt(dx * dx + dy * dy);
           default:
               return -1;
       }      
   }

先为所有变量设置初值：

      //@param startNode, endNode
openSet.add(startNode);                        //最初只访问了起点
      cameFrom.put(startNode.getNodeId(), null);     //起点没有父节点
//为结点的g和f设置INF，但除了起点
      while (iterator.hasNext()) {
          Node current = iterator.next().getValue();
          gScore.put(current.getNodeId(), Integer.MAX_VALUE);
          fScore.put(current.getNodeId(), Integer.MAX_VALUE);
      }
      gScore.replace(startNode.getNodeId(), 0);
      fScore.replace(startNode.getNodeId(), heuristic(start, end, mode));

寻路过程：

      //优先队列不为空或者没有找到终点时循环
while(!openSet.isEmpty()){
          //从队列中取出f(n)值最小的点，在保证得到最优解的情况下，这个点的期望也是当前最大的，因此把它的邻接点作为下一个考虑点
          Node currentNode = openSet.poll();
          //找到终点，根据父节点输出路径
          if(currentNode.getNodeId().compareTo(endNode.getNodeId()) == 0){
              return reconstructPath(cameFrom, currentNode);
          }
          //遍历所有邻接点
          for (int i = 0; i < currentNode.getNeighborsSize(); i++) {
              Node neighbor = currentNode.getNeighbor(i);
              //获得临界点的Id
              String nbrId = neighbor.getNodeId();
              //计算邻接点经过当前点(currentNode)的最小g(n)
              Integer tmpGScore = gScore.get(neighbor.getNodeId()) 
                                  + currentNode.getDistance(neighbor.getNodeId());
              //如果比之前的路径更优，则修改其父节点
              if(tmpGScore.compareTo(gScore.get(neighbor.getNodeId())) < 0){
                  cameFrom.put(nbrId, currentNode);
                  //依次修改g(n) 和 h(n)
                  gScore.put(nbrId, tmpGScore);
                  fScore.put(nbrId, gScore.get(nbrId) + heuristic(neighbor.getPosition(), end, mode));
                  //把当前点放入待处理的队列中
                  if(!openSet.contains(neighbor)){
                      openSet.add(neighbor);
                  }
              }
          }
      }

总结

可以看出，A*算法可以说是BFS和DFS的结合。

当g(n)为0时，A*算法退化为DFS, 尽管能够很快找到终点，但只有遍历完所有点才能确定最短的那条，有点好高骛远的感觉。

当h(n)为0时，A*算法退化为BFS, 即使大方向错了，还是得闷头去走，是一种非启发式的傻瓜算法。