啟發函數

這裡我們可以通過這個頂點跟終點之間的直線距離，也就是歐幾裡得距離，來近似地估計這個頂點跟終點的路徑長度（注意：路徑長度跟直線距離是兩個概念）。我們把這個距離記作 h(i)（i 表示這個頂點的編号），專業的叫法是啟發函數（heuristic function）。因為歐幾裡得距離的計算公式，會涉及比較耗時的開根号計算，是以，我們一般通過另外一個更加簡單的距離計算公式，那就是曼哈頓距離（Manhattan distance）。曼哈頓距離是兩點之間橫縱坐标的距離之和。計算的過程隻涉及加減法、符号位反轉，是以比歐幾裡得距離更加高效。

int hManhattan(Vertex v1, Vertex v2) { // Vertex 表示頂點，後面有定義

  return Math.abs(v1.x - v2.x) + Math.abs(v1.y - v2.y);

}

原來隻是單純地通過頂點與起點之間的路徑長度 g(i)，來判斷誰先出隊列，現在有了頂點到終點的路徑長度估計值，我們通過兩者之和 f(i)=g(i)+h(i)，來判斷哪個頂點該最先出隊列。綜合兩部分，我們就能有效避免剛剛講的“跑偏”。這裡 f(i) 的專業叫法是估價函數（evaluation function）。