如何解析Heuristics函數

如何解析Heuristics函數，很多新手對此不是很清楚，為了幫助大家解決這個難題，下面小編將為大家詳細講解，有這方面需求的人可以來學習下，希望你能有所收獲。

啟發式函數h(n)告訴A*從任何結點n到目標結點的最小代價評估值。因此選擇一個好的啟發式函數很重要。

啟發式函數在A* 中的作用

啟發式函數可以用來控制A*的行為。

• 一種極端情況，如果h(n)是0，則只有g(n)起作用，此時A* 算法演變成Dijkstra算法，就能保證找到最短路徑。

• 如果h(n)總是比從n移動到目標的代價小（或相等），那么A* 保證能找到一條最短路徑。h(n)越小，A* 需要擴展的點越多，運行速度越慢。

• 如果h(n)正好等于從n移動到目標的代價，那么A* 將只遵循最佳路徑而不會擴展到其他任何結點，能夠運行地很快。盡管這不可能在所有情況下發生，但你仍可以在某些特殊情況下讓h(n)正好等于實際代價值。只要所給的信息完善，A* 將運行得很完美。

• 如果h(n)比從n移動到目標的代價高，則A* 不能保證找到一條最短路徑，但它可以運行得更快。

• 另一種極端情況，如果h(n)比g(n)大很多，則只有h(n)起作用，同時A* 算法演變成貪婪最佳優先搜索算法（Greedy Best-First-Search）。

所以h(n)的選擇成了一個有趣的情況，它取決于我們想要A* 算法中獲得什么結果。h(n)合適的時候，我們會非常快速地得到最短路徑。如果h(n)估計的代價太低，我們仍會得到最短路徑，但運行速度會減慢。如果估計的代價太高，我們就放棄最短路徑，但A* 將運行得更快。

在游戲開發中，A* 的這個特性非常有用。例如，你可能會發現在某些情況下，你寧愿有一個“好”的路徑而不是一個“完美”的路徑。為了平衡g(n)和h(n)之間的關系，你可以修改其中的任何一個。

注釋： 從技術上來看，如果啟發式函數值低估了實際代價，A* 算法應該被稱為簡單的A算法(simply A)。不過，我將繼續稱之為A* 算法，因為它們的實現是相同的，而且游戲編程社區對A算法和A* 算法并不區分對待。

速度和準確性？

A* 基于啟發式函數和代價函數來改變其行為的能力在游戲中非常有用。速度和準確性之間的折衷可以提高游戲速度。對于大多數游戲而言，你并不需要兩個點之間的最佳路徑。你只需要知道近似的路徑就足夠了。你所需要的路徑往往取決于游戲中接下來要發生什么，或是運行游戲的計算機有多快。

假設你的游戲中有兩種地形，平原和山地，它們的移動代價分別是1和3，A* 算法沿著平原搜索的路徑長度是沿著山區的三倍。這是因為可能有一條繞著山地的平原路徑。你可以把兩個地圖單位之間的啟發式距離設為1.5可以加快A* 的搜索速度。于是A* 會將山區的移動成本3改為1.5，這個變化不像3到1那么大。這種方法在山區的移動成本不像之前那樣高，因此不用花太多的時間去尋找繞著山地的路徑。或者，你可以通過告訴A* 在山區的移動成本為2而不是3，以減少山區周圍路徑的搜索量，來加快A* 的搜索速度。現在，沿著平原搜索路徑的速度只是沿著山區的兩倍。這兩種方法都放棄了理想路徑來獲得更快的搜索速度。

速度和準確性之間的權衡不需要是固定的。你可以根據CPU速率、用于尋路的時間片數、地圖上物體的數量、物體的重要性、組(group)的大小、難度級別，或其他任何因素來進行動態地選擇。一種動態的折衷啟發式函數方法是，假設通過一個網格空間的最小代價為1，然后建立一個在下式中范圍內的代價函數(cost function)：

g'(n) = 1 + alpha * (g(n) - 1)

如果alpha值為0，則修改后后的代價函數的值將總是為1。在這種情況下，地形代價被完全忽略，A* 的工作變成了簡單判斷一個網格能否通過。如果alpha的值為1，則初始代價函數將被使用，你會得到A* 算法的所有優點。你可以將alpha設為0到1之間的任意值。

你也應該考慮在啟發式函數返回的絕對最小代價和期望最小代價中做選擇。例如，如果你的地圖上大部分地形是移動代價為2的草地而一些地形是移動代價為1的道路，那么你可以考慮讓啟發式函數假設沒有道路，而只返回兩倍的距離。

速度和準確性之間的選擇并不必是全局的。在地圖上的某些區域，你可以基于其準確性的重要性來進行動態選擇。舉個例子，假設我們在任意點都可能停止并重新計算路徑或改變方向，那么為什么要困擾于后續路徑的準確性呢？在這種情況下快速選擇一條的路徑更加重要。或者，對于地圖上的某個安全區域，準確的最短路徑并不那么重要；但在渡過危險區域時，安全和準確是必需的。

度量

A* 計算f(n) = g(n) + h(n)。為了將兩個值相加，這兩個值必須使用相同的單位去度量。如果度量g(n)的單位是小時，衡量h(n)的單位是米，則A* 將認為g或h太大或太小，因此，要么你無法得到好的路徑，要么A* 的運行速度會更慢。

精確啟發式函數

如果你的啟發式函數值正好等于最佳路徑的距離，正如下一部分的圖中所示，你會看到A* 擴展的結點非常少。A* 算法所做的是在每個結點處計算f(n) = g(n) + h(n)。當h(n)和g(n)完全匹配時，f(n)的值不會沿著路徑改變。不在正確路徑上的所有結點的f值均大于正確路徑上結點的f值。由于A* 在考慮f值較低的點前，不會考慮f值較高的點，因此它肯定不會偏離最短路徑。

預先計算的精確啟發式函數

構造精確的啟發式函數的一種方法是預先計算每對結點之間的最短路徑的長度。這種做法對于大多數游戲的地圖而言并不可行。但是，有幾種方法可以近似模擬啟發式函數：

• 在細網格(fine grid)擬合合適密度的粗網格(coarse grid)。 預先計算粗網格中任何一對結點之間的最短路徑。

• 預先計算任何一對路徑點(waypoints)之間的最短路徑。這是粗網格方法的一般化。

然后添加一個啟發式函數h’來估計從任何位置到其鄰近路徑點的代價。(如果需要，后者也可以通過預計算得到。)最終的啟發式函數將是：

h(n) = h'(n, w1) + distance(w1, w2) + h'(w2, goal)

或者，如果你想要一個更好但代價更大的啟發式函數，則分別用靠近結點和靠近目標的所有w1, w2對上式進行計算。

線性的精確啟發式函數

在特殊情況下，不需要預先計算也能使啟發式函數很精確。如果你的地圖沒有障礙物或者移動緩慢的區域，那么從初始點到目標點的最短路徑應該是一條直線。

如果你使用的是簡單的啟發式函數（不知道地圖上障礙物的情況），那么它應該匹配精確的啟發式函數。如果沒有，那么你選擇的啟發式函數的類型和衡量單位可能有問題。

網格地圖中的啟發式函數

在網格地圖中，有一些眾所周知的啟發式函數可供使用。

啟發式函數的距離與所允許的移動方式相匹配：

• 在正方形網格中，允許向4鄰域的移動，使用曼哈頓距離(L1)。

• 在正方形網格中，允許向8鄰域的移動，使用對角線距離(L∞)。

• 在正方形網格中，允許任何方向的移動，歐幾里得距離(L2)可能適合，但也可能不適合。如果用A* 在網格上尋找路徑，但你又不允許在網格上移動，你可能要考慮用其它形式表現該地圖。

• 在六邊形網格中，允許6個方向的移動，使用適合于六邊形網格的曼哈頓距離。

曼哈頓距離(Manhattan distance)

對于方形網格，標準的啟發式函數就是曼哈頓距離。考慮一下你的代價函數并確定從一個位置移動到相鄰位置的最小代價D。在簡單的情況下，你可以將D設為1。在一個可以向4個方向移動的方向網格中，啟發式函數是曼哈頓距離的D倍：

function heuristic(node) =

    dx = abs(node.x - goal.x)

    dy = abs(node.y - goal.y)

    return D * (dx + dy)

如何確定D？你使用的衡量單位應該與你的代價函數相匹配。對于最佳路徑，和“可采納的”的啟發式函數，應該將D設為鄰近方格間移動的最低代價值。在一個沒有障礙物、最小移動代價為D的地形上，每向目標靠近移動一步，g就增加D的移動代價同時h減少D的代價。此時將g和h相加時，f保持不變；這是啟發式函數與代價函數的衡量單位相匹配的一個標識。你也可以通過放棄最優路徑增加代價D或是降低最低和最高邊際代價之間比率的手段，來讓A* 的運行速度更快。

對角線距離

如果你允許在地圖中沿著對角線移動，那么你需要一個不同的啟發式函數（有時被稱為契比雪夫距離(Chebyshev distance)）。偏東4個單位偏北4各單位(4 east, 4 north)的曼哈頓距離是8*D。然而，對對角線距離而言，你可以簡單地移動4個對角線長度，因此啟發式函數將為4*D。下面這個函數用于處理對角線，假設直線和對角線的移動代價都是D:

function heuristic(node) =

    dx = abs(node.x - goal.x)

    dy = abs(node.y - goal.y)

    return D * max(dx, dy)

如果你沿對角線移動的代價并不是D，而是類似于D2 = sqrt(2)*D，那么上面的啟發式函數并不適合你。你會想要一個更復雜而準確的函數：

function heuristic(node) =

    dx = abs(node.x - goal.x)

    dy = abs(node.y - goal.y)

    return D * (dx + dy) + (D2 - 2 * D) * min(dx, dy)

在這里，我們計算不走對角線所需要的步數，然后減去走對角線節約的步數。在對角線上的步數有min(dx, dy)個，其每步的代價為D2，可以節約2*D的非對角線步數的代價。

Patrick Lester用一種不同的方式來寫這個啟發式函數，他使用dx > dy及dx < dy顯式的表達。上面的代碼有相同的測試方法，但它隱藏了內部對min函數的調用。

歐幾里得距離

如果你允許沿著任何角度移動（而不是網格方向），那么你或許應該使用直線距離：

function heuristic(node) =

    dx = abs(node.x - goal.x)

    dy = abs(node.y - goal.y)

    return D * sqrt(dx * dx + dy * dy)

然而，在這種情況下，你直接使用A* 將可能有麻煩，因為代價函數g不會匹配啟發式函數h。由于歐幾里得距離比曼哈頓距離或對角線距離更短，你仍然會得到最短路徑，但A* 將需要更長的運行時間：

平方后的歐幾里得距離

我曾看到一些有關A* 的網頁推薦你使用距離的平方來避免歐幾里得距離中耗時的平方根計算。

function heuristic(node) =

    dx = abs(node.x - goal.x)

    dy = abs(node.y - goal.y)

    return D * (dx * dx + dy * dy)

千萬不要這樣做！這無疑會導致衡量單位的問題。因為你要將函數g和h的值相加，它們的衡量單位需要相匹配。當A* 計算f(n) = g(n) + h(n)時，距離的平方將比函數g的代價大很多，并且你會因為啟發式函數的評估值過高而停止。對于較長的距離，這樣做會接近g(n)的極端情況而對計算f(n)沒有任何幫助，A* 算法將退化成貪婪最佳優先搜索算法(Greedy Best-First-Search)。

你也可以縮小啟發式函數的度量單位。然而，此時你會面臨相反的問題：對于較短的距離，相比于g(n)，啟發式函數的代價將小得多，A* 算法將退化成Dijkstra算法。

如果你經過分析發現平方根的代價很顯著，要么使用快速平方根逼近歐幾里得距離，要么使用對角線距離作為歐幾里得距離的近似值。

多個目標

如果你想要搜索幾個目標中的一個，構建一個啟發式函數h'(x)，它是h2(x), h3(x), h4(x), …中最小的，其中h2, h3, h4是每個目標點附近的啟發式函數。

如果你想要搜索一個目標附近的點，要求A* 算法找到一條路徑通往目標區域的中心。當處理的節點來自開放集(OPEN set)時，在得到一個足夠近的節點時退出。

值相等時的決勝法(Breaking ties)

在一些網格地圖上，有許多具有相同的長度的路徑。例如，在沒有變化的地形平坦的區域中，使用網格會產生許多等長的路徑。A* 可能會搜索具有相同f值的所有路徑，而不是其中一條。

f值的相等情況

為了解決這個問題，我們需要調整g或h的值；調整h的值通常會更容易。決勝值(tie breaker)必須根據頂點來確定（即，它不應該僅是一個隨機數），而且它必須使f值不同。因為A* 對f值排序，讓f值不同意味著所有“等價”的f值中只有一個將被搜索到。

在相等的值中進行抉擇的一種方式是稍微改變(nudge)h值的衡量單位。如果減小衡量單位，那么當我們朝著目標點移動時，f值將逐漸增加。不幸的是，這意味著A* 將更傾向于擴展靠近初始點的結點，而不是靠近目標點的結點。我們可以稍微增大衡量單位(甚至是0.1%)。A* 將更傾向于擴展靠近目標點的結點。

heuristic *= (1.0 + p)

因子p的選擇應該使得p<(移動一步的最小代價)/(期望的最長路徑長度)。假設你不希望路徑超過1000步，你可以使p = 1/1000。（注意，這稍微打破了“可受理”啟發式函數，但在游戲中幾乎從來不重要。）改變這個關鍵值(tie-breaking)的結果使A* 在地圖上搜索的結點比以前更少。

加入比例決勝值后的啟發式函數。

當有障礙物時，仍然要在其周圍尋找路徑，但要注意在繞過障礙物之后，A* 搜索的區域非常少：

加入比例型決勝值的啟發式函數在在有障礙物時也能得到較好的效果。

Steven van Dijk建議，一個更直截了當的方法是把h作為比較函數的依據。當f值相等時，比較函數將通過檢查h來解決f值相等的情況。

另一種方法是添加一個確定的隨機數到啟發式函數或邊的代價（選擇確定的隨機數的一種方法是計算坐標的哈希值。）這比上面提到的調整h值能更好的解決f值相等的問題。感謝Cris Fuhrman的這個建議。

另一種的方法更傾向于沿著從起始點到目標點的直線路徑：

dx1 = current.x - goal.x

dy1 = current.y - goal.y

dx2 = start.x - goal.x

dy2 = start.y - goal.y

cross = abs(dx1*dy2 - dx2*dy1)

heuristic += cross*0.001

這段代碼計算初始-目標向量和當前-目標向量之間的向量叉積。當這些向量不平行時，叉積將很大。其結果是，這段代碼選擇的路徑稍微傾向于沿著初始點到目標點的直線路徑。當沒有障礙物時，A* 不僅搜索很少的區域，而且它找到的路徑看起來非常好。

啟發式函數中加入叉積作為決勝值，產生更好的路徑。

但是，因為這個決勝值更傾向于從初始點到目標點的直線路徑，當出現障礙物時會出現奇怪的結果（請注意，這條路徑仍然是最佳的；它只是看起來很奇怪）

啟發式函數中加入叉積作為決勝值，在有障礙物時效果不夠好。

為了交互式地探索這種關鍵值方法的改進，請參考James Macgill的A* 應用?[或使用這個鏡像或這個鏡像]。使用”Clear”來清除地圖，并選擇地圖上對角的兩個點。當你使用“Classic A*”方法時，你會看到關鍵值的效果。當你使用“Fudge”方法時，你會看到上面提到給啟發式函數添加叉積后的效果。

另一種方法是小心地構造你的A* 優先隊列，使新插入的特定f值的結點總是比那些具有相同f值的舊結點有更高的優先級。

同時，另一種在網格上打破平局的方法是盡量減少轉向。從上一結點到當前結點x,y的變化將告訴你你的移動方向。對于所有當前點到下一相鄰點構成的邊而言，如果x,y的移動方向與從上一結點到當前結點的移動方向不同，那么在移動代價中增加一個小的懲罰值。

如果多個相等的f值出現次數很多，上述對啟發式函數的修改可能僅僅是一個“創口貼”般的低效方法。當有大量一樣好的路徑時，多個相等f值的出現會導致大量結點被搜索。考慮“更聰明而不是更辛苦”的方法：

• 替換地圖表征可以通過減少圖形上結點的數量來解決這個問題。將多個結點歸于一個，或刪除重要結點外的所有結點。長方形對稱縮減(Rectangular Symmetry Reduction)是在方形網格上實現這個的一個辦法；同時還可以考慮“framed quad trees”方法。分層尋路(Hierarchical pathfinding)使用具有少量結點的高層級圖形來找到最佳路徑，然后使用具有大量結點的低層級圖形完善該路徑。

• 某些方法讓大量結點獨立但減少了被訪問結點的數量。?Jump Point 搜索跳過大面積含有大量關系的結點；該方法被設計用于方形網格。跳過鏈接添加“捷徑”的邊來跳過地圖上的區域。AlphA* 算法添加了一些深度優先搜索到A* 通常的廣度優先的行為中，以便它可以探索單條路徑而不是同時處理所有這些路徑。

• Fringe 搜索(PDF)?通過結點快速處理來解決這個問題。它分批處理結點，只擴展具有低f值的結點，而不是保存一個排序的開放集，并一次訪問一個結點。這涉及到HOT 隊列方法。

看完上述內容是否對您有幫助呢？如果還想對相關知識有進一步的了解或閱讀更多相關文章，請關注億速云行業資訊頻道，感謝您對億速云的支持。