【数据结构与算法】【算法思想】 A *搜索算法

待我称王封你为后i 2022-12-10 03:45 214阅读 0赞

### 算法解析 ###

*  这是一个非常典型的搜索问题。
 *  人物的起点就是他当下所在的位置，终点就是鼠标点击的位置。
 *  我们需要在地图中，找一条从起点到终点的路径。
 *  这条路径要绕过地图中所有障碍物，并且看起来要是一种非常聪明的走法。所谓“聪明”，笼统地解释就是，走的路不能太绕。理论上讲，最短路径显然是最聪明的走法，是这个问题的最优解。

实际上，像出行路线规划、游戏寻路，这些**真实软件开发中的问题，一般情况下都不需要非得求最优解（也就是最短路径）**。  
在权衡路线规划质量和执行效率的情况下，我们只需要寻求一个次优解就足够了。  
如何快速找出一条接近于最短路线的次优路线呢？  
*A 算法*\*：A\* 算法是对 Dijkstra 算法的优化和改造。最优出行路线规划问题中，如果图非常大，Dijkstra 最短路径算法的执行耗时会很多  
**Dijkstra 算法**有点儿类似 BFS 算法，它每次找到跟起点最近的顶点，往外扩展。这种往外扩展的思路，其实有些盲目。

#### 可以避免“跑偏”吗？ ####

当遍历到某个顶点时，从起点到这个顶点的路径长度是确定的，记作 g(i)（i 表示顶点编号）

*  虽然从这个顶点到终点的路径长度是未知的，但可以用其他估计值来代替。
 *  可以通过这个顶点跟终点之间的直线距离(欧几里得距离)，近似估算这个顶点跟终点的路径长度（注意：路径长度跟直线距离是两个概念）
 *  把这个距离记作 **h(i)**（i 表示这个顶点的编号），专业的叫法是**启发函数**（heuristic function）。
 *  因为欧几里得距离的计算公式，会涉及比较耗时的开根号计算，所以一般通过另外一个更加简单的距离计算公式，那就是**曼哈顿距离（Manhattan distance）。**
 *  曼哈顿距离是**两点之间横纵坐标的距离之和**。计算的过程只涉及加减法、符号位反转，所以比欧几里得距离更加高效。

原来只是单纯地通过顶点与起点之间的路径长度 g(i)，来判断谁先出队列，现在有了顶点到终点的路径长度估计值，通过**两者之和 f(i)=g(i)+h(i)**，来判断哪个顶点该最先出队列。  
综合两部分，就能有效避免“跑偏”**。f(i) 的专业叫法是估价函数（evaluation function）**

\*\* A *算法就是对 Dijkstra 算法的简单改造*\*  
在 A\* 算法的代码实现中，顶点 Vertex 类的定义，跟 Dijkstra 算法中的定义，稍微有点儿区别，多了 x，y 坐标，以及刚刚提到的 f(i) 值。图 Graph 类的定义跟 Dijkstra 算法中的定义一样。

private class Vertex { 
      public int id; // 顶点编号ID
      public int dist; // 从起始顶点，到这个顶点的距离，也就是g(i)
      public int f; // 新增：f(i)=g(i)+h(i)
      public int x, y; // 新增：顶点在地图中的坐标（x, y）
      public Vertex(int id, int x, int y) { 
        this.id = id;
        this.x = x;
        this.y = y;
        this.f = Integer.MAX_VALUE;//!!!
        this.dist = Integer.MAX_VALUE;
      }
    }
    // Graph类的成员变量，在构造函数中初始化
    Vertex[] vertexes = new Vertex[this.v];
    // 新增一个方法，添加顶点的坐标
    public void addVetex(int id, int x, int y) { 
      vertexes[id] = new Vertex(id, x, y)
    }

A\* 算法的代码主要有 3 点区别：

*  优先级队列构建的方式不同，  
    A\* 算法是根据 f 值（ f(i)=g(i)+h(i)）来构建优先级队列，  
    Dijkstra 算法是根据 dist 值（g(i)）来构建优先级队列；
 *  A\* 算法在更新顶点 dist 值的时候，会同步更新 f 值；
 *  循环结束的条件也不一样。Dijkstra 算法是在终点出队列的时候才结束，A\* 算法是一旦遍历到终点就结束。

public void astar(int s, int t) {  // 从顶点s到顶点t的路径
      int[] predecessor = new int[this.v]; // 用来还原路径
      // 按照vertex的f值构建的小顶堆，而不是按照dist
      PriorityQueue queue = new PriorityQueue(this.v);
      boolean[] inqueue = new boolean[this.v]; // 标记是否进入过队列
      vertexes[s].dist = 0;
      vertexes[s].f = 0;
      queue.add(vertexes[s]);
      inqueue[s] = true;
      while (!queue.isEmpty()) { 
        Vertex minVertex = queue.poll(); // 取堆顶元素并删除
        for (int i = 0; i < adj[minVertex.id].size(); ++i) { 
          Edge e = adj[minVertex.id].get(i); // 取出一条minVetex相连的边
          Vertex nextVertex = vertexes[e.tid]; // minVertex-->nextVertex
          if (minVertex.dist + e.w < nextVertex.dist) {  // 更新next的dist,f
            nextVertex.dist = minVertex.dist + e.w;
            nextVertex.f 
               = nextVertex.dist+hManhattan(nextVertex, vertexes[t]);
            predecessor[nextVertex.id] = minVertex.id;
            if (inqueue[nextVertex.id] == true) { 
              queue.update(nextVertex);
            } else { 
              queue.add(nextVertex);
              inqueue[nextVertex.id] = true;
            }
          }
          if (nextVertex.id == t) {  // 只要到达t就可以结束while了
            queue.clear(); // 清空queue，才能推出while循环
            break; 
          }
        }
      }
      // 输出路径
      System.out.print(s);
      print(s, t, predecessor); // print函数请参看Dijkstra算法的实现
    }

*A 这是为什么不能找到最短路线呢？*\*  
要找出起点 s 到终点 t 的最短路径，最简单的方法是，通过回溯穷举所有从 s 到达 t 的不同路径，然后对比找出最短的那个。但**回溯算法的执行效率非常低，是指数级的**。

Dijkstra 算法在此基础之上，利用动态规划的思想，对回溯搜索进行了剪枝，只保留起点到某个顶点的最短路径，继续往外扩展搜索。动态规划相较于回溯搜索，只是换了一个实现思路，但它实际上也考察到了所有从起点到终点的路线，所以才能得到最优解。

*  A\* 算法之所以不能像 Dijkstra 算法那样，找到最短路径，主要原因是两者的 **while 循环结束条件不一样**
 *  Dijkstra 算法是在终点出队列的时候才结束，A\* 算法是一旦遍历到终点就结束
 *  对于 Dijkstra 算法，当终点出队列时，终点的 dist 值是优先级队列中所有顶点的最小值，即便再运行下去，终点的 dist 值也不会再被更新了。
 *  对于 A\* 算法，一旦遍历到终点，我们就结束 while 循环，这个时候，终点的 dist 值未必是最小值。
 *  A\* 算法利用贪心算法的思路，每次都找 f 值最小的顶点出队列，一旦搜索到终点就不在继续考察其他顶点和路线了。

所以，它并没有考察所有的路线，也就不可能找出最短路径了。

[笔记整理来源： 王争 数据结构与算法之美][Link 1]

[Link 1]: https://s1.ax1x.com/2020/08/03/aUh2TS.png