天天看點

啟發函數

這裡我們可以通過這個頂點跟終點之間的直線距離,也就是歐幾裡得距離,來近似地估計這個頂點跟終點的路徑長度(注意:路徑長度跟直線距離是兩個概念)。我們把這個距離記作 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)。