A* 啟發(fā)式搜索算法是對(duì) Dijkstra 算法的改進(jìn)版本，它和后者的主要差別在于，加入了到終點(diǎn)的距離量化，使得 A* 算法不會(huì)像 Dijkstra 算法那樣“跑偏”。

問(wèn)題分析

之前我們介紹過(guò) Dijkstra算法（下面簡(jiǎn)寫成 D算法），不知道你有沒(méi)有發(fā)現(xiàn)這樣一個(gè)問(wèn)題：當(dāng)?shù)貓D特別大的時(shí)候，D算法 的執(zhí)行時(shí)間會(huì)非常長(zhǎng)，為了確定自己找到的是最短路徑，算法執(zhí)行了大量的“跑偏”計(jì)算。

地圖.jpg

在 D算法 的實(shí)現(xiàn)過(guò)程中，最先被搜索到的頂點(diǎn)依次是 1，2，3。很明顯，這種搜索方向“跑偏了”。

在工程中，不一定要找到問(wèn)題的最優(yōu)解，我們可以一定程度地接受次優(yōu)解，尤其是這個(gè)次優(yōu)解會(huì)節(jié)省大量計(jì)算資源的時(shí)候。基于這樣的理念，A* 算法 應(yīng)運(yùn)而生。

算法解析

在 A* 算法中，除了當(dāng)前頂點(diǎn)和起始頂點(diǎn)的距離 g(i) （ i 為頂點(diǎn)編號(hào)），還要考慮當(dāng)前頂點(diǎn)到終點(diǎn)的 直線距離 （注意，是直線距離，不是路徑距離） h(i) ,這個(gè)距離的專業(yè)叫法是 啟發(fā)函數(shù) 。這個(gè)距離非常好計(jì)算，我們可以用 “勾股定理” 輕松求出，但是為了減少計(jì)算機(jī)的計(jì)算量，這里選擇 曼哈頓距離 ，其計(jì)算方式如下：

int hManhattan(Vertex v1, Vertex v2) { // Vertex表示頂點(diǎn)，后面有定義
  return Math.abs(v1.x - v2.x) + Math.abs(v1.y - v2.y);
}

有了啟發(fā)函數(shù)，我們可以使用 估值函數(shù) f(i) 代替 D算法 中的 dist數(shù)組 ，它的計(jì)算如下：

f( i ) = g( i ) + h( i )

根據(jù)這個(gè)定義，我們需要修改在 D算法 中的 vertex：

private class Vertex {
  public int id; // 頂點(diǎn)編號(hào)ID
  public int dist; // 從起始頂點(diǎn)，到這個(gè)頂點(diǎn)的距離，也就是g(i)
  public int f; // 新增：f(i)=g(i)+h(i)
  public int x, y; // 新增：頂點(diǎn)在地圖中的坐標(biāo)（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類的成員變量，在構(gòu)造函數(shù)中初始化
Vertex[] vertexes = new Vertex[this.v];
// 新增一個(gè)方法，添加頂點(diǎn)的坐標(biāo)
public void addVetex(int id, int x, int y) {
  vertexes[id] = new Vertex(id, x, y)
}

A* 算法的主要代碼實(shí)現(xiàn)在下面，這里要說(shuō)明它和 D算法 的三點(diǎn)區(qū)別：

• 優(yōu)先級(jí)隊(duì)列的構(gòu)建不同：A* 根據(jù) f 構(gòu)建優(yōu)先隊(duì)列，而 D算法根據(jù) dist（也就是 g）構(gòu)建優(yōu)先隊(duì)列；
• A* 會(huì)在更新 dist 的時(shí)候同步更新 f 值；
• 循環(huán)結(jié)束條件不同：D算法 在終點(diǎn)出隊(duì)列的時(shí)候結(jié)束，A* 在遍歷到終點(diǎn)就結(jié)束。

public void astar(int s, int t) { // 從頂點(diǎn)s到頂點(diǎn)t的路徑
  int[] predecessor = new int[this.v]; // 用來(lái)還原路徑
  // 按照vertex的f值構(gòu)建的小頂堆，而不是按照dist
  PriorityQueue queue = new PriorityQueue(this.v);
  boolean[] inqueue = new boolean[this.v]; // 標(biāo)記是否進(jìn)入過(guò)隊(duì)列
  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) { // 只要到達(dá)t就可以結(jié)束while了
        queue.clear(); // 清空queue，才能推出while循環(huán)
        break; 
      }
    }
  }
  // 輸出路徑
  System.out.print(s);
  print(s, t, predecessor); // print函數(shù)請(qǐng)參看Dijkstra算法的實(shí)現(xiàn)
}

這個(gè)算法比 D算法快速，但是A* 算法無(wú)法獲得最短路徑

如果我想獲得最短路徑，最笨的辦法是使用回溯算法：

回溯窮舉.jpg

而動(dòng)態(tài)規(guī)劃（D算法），可以通過(guò)剪枝減少計(jì)算：

Dijkstra剪枝.jpg

而 A* 算法 使用了貪婪策略，它選擇最小的 f 值 作為路徑選擇的依據(jù)，且在第一次遇到終點(diǎn)的時(shí)候就結(jié)束，這使得 A* 算法沒(méi)有考察其它路線（實(shí)際上這也是它更少耗費(fèi)資源的原因），也就不可能找出最短路徑了。

總結(jié)

• 啟發(fā)式搜索算法通過(guò)利用估價(jià)函數(shù)避免“跑偏”
• A* 使用了貪婪策略，通過(guò)節(jié)課的例子，我們有一個(gè)新的認(rèn)識(shí)：在工程中可以允許次優(yōu)解的出現(xiàn)（如果要找到最優(yōu)解會(huì)耗費(fèi)大量資源的話），而尋找次優(yōu)解的一大途徑就是使用 貪婪策略
• 所以，我們可以籠統(tǒng)地對(duì)三種算法的資源耗費(fèi)進(jìn)行排序：回溯>動(dòng)態(tài)規(guī)劃>貪婪

以上就是全部?jī)?nèi)容

注：本文章的主要內(nèi)容來(lái)自我對(duì)極客時(shí)間app的《數(shù)據(jù)結(jié)構(gòu)與算法之美》專欄的總結(jié)，我使用了大量的原文、代碼和截圖，如果想要了解具體內(nèi)容，可以前往極客時(shí)間