定向搜索
在A*算法的循環中，OPEN集合用來保存所有用于尋找路徑的被搜索節點。定向搜索是在A*算法基礎上，通過對OPEN集合大小設置約束條件而得到的變體算法。當集合太大的時候，最不可能出現在最優路徑上的節點將會被剔除。這樣做會帶來一個缺點：由于必須得保持這樣的篩選，所以可選擇的數據結構類型會受到限制。
迭代深化（Iterative deepening）
迭代深化是一種很多AI算法采用的方法，開始的時候給一個估計值，然后通過迭代使它越來越精確。這個名字來源于游戲樹搜索中對接下來幾次操作的提前預判（例如，在象棋游戲中）。你可以通過向前預判更多的操作來深化游戲樹。一旦當你的結果不發生變化或提高很多，就可以認為你已經得到了一個非常好的結果，即使讓它更精確，結果也不會再改善。在迭代深化A*(IDA*)算法中，“深度”是 f 值當前的一個截斷值。當 f 值太大的時候，節點不會被考慮（也就是說，不會被加入到OPEN集中）。第一次循環時，只需要處理非常少的節點。隨后的每次循環，都會增加訪問的節點數。如果發現路徑得到優化，就繼續增加當前的截斷值，否則結束。更多細節，參見鏈接。
我個人并不看好IDA*算法在游戲地圖尋路中的應用。迭代深化的算法往往增加了計算時間，同時降低了內存需求。然而，在地圖尋路的場景中，節點僅僅包含坐標信息，所需要的內存非常小。所以減少這部分內存開銷并不會帶來什么優勢。
動態加權
在動態加權算法中，你假定在搜索開始時快速達到(任意)一個位置更為重要，在搜索結束時到達目標位置更為重要。
f(p) = g(p) + w(p) * h(p)
有一個權值(w >= 1 )和該啟發式關聯。當不斷接近目標位置的時候，權重值也不斷降低。這樣降低了啟發式函數的重要性，并增加了路徑實際代價的相對重要性。
帶寬搜索
帶寬搜索有兩個被認為非常有用的特性。這個算法變體假設 h 是一個估計過高的值，但它的估計誤差不會超過 e。那么在這樣的條件下，搜索到的路徑代價與最優路徑代價的誤差不會超過 e。這里需要再一次強調，啟發值設置得越好，那么得到的結果也將越好。
另外一個特性是用來判斷你是否可以刪掉OPEN集合中的某些節點。只要 h+d 大于路徑真實代價（對于一些 d），那么你可以丟掉任意滿足其 f 值比OPEN集合中最優節點 f 值至少大 e+d 的節點。這是一個很奇異的特性。你相當于得到了一個 f 值的帶寬；所有在這個帶寬意外的節點都可以被丟棄掉，因為他們被保證一定不會出現在最優路徑中。
有意思地是，對于這兩種特性分別使用不同的啟發值，仍然可以計算得到結果。你可以使用一個啟發值來保證路徑代價不會太大，另外一個啟發值來決定丟棄掉OPEN集中的哪些節點。
雙向搜索
與從頭到尾的搜索不同，你也可以并行地同時進行兩個搜索，一個從開始到結束，一個從結束到開始。當它們相遇的時候，你就會得到一個最優路徑。
這個想法在一些情況下非常有用。雙向搜索的主要思想是：搜索結果會形成一個在地圖上呈扇形展開的樹。而一個大的樹遠不如兩個小的樹，所以使用兩個小的搜索樹更好。
面對面的變體將兩個搜索結果鏈接到一起。該算法選擇滿足最佳 g(start,x) + h(x,y) + g(y,goal) 的一對節點，而不是選擇最佳前向搜索節點 g(start,x) + h(x,goal) 或者最佳后向搜索節點 g(y,goal) + h(start,y)。
重定向算法放棄同時前向和后向的搜索方法。該算法首先進行一個短暫的前向搜索，并選出一個最佳的前向候選節點。接著進行后向搜索。此時，后向搜索不是朝向開始節點，而是朝向剛剛得到的前向候選節點。后向搜索也會選出一個最佳后向搜索節點。然后下一步，再運行前向搜索，從當前的前向候選節點到后向候選節點。這個過程將會不斷重復，直到兩個后選節點重合。
動態A*與終身規劃A*
有一些A*的變體算法允許初始路徑計算之后地圖發生改變。動態A*可以用于在不知道全部地圖信息的情況進行尋路。如果沒有全部信息，那么A*算法的計算可能會出現錯誤，動態A*的優勢在于可以快速改正那些錯誤而不會花費很多時間。終身規劃A*算法可以用于代價發生改變的情況。當地圖發生改變的時候，A*計算得到路徑可能會失效；終身規劃A*可以重復利用以前的A*計算來產生新的路徑。
然而，動態A*與終身規劃A*都要求大量的空間——運行A*算法時需要保持它的內部信息（OPEN/CLOSED集合，路徑樹，g值）。當路徑發生改變的時候，動態A*或終身規劃A*算法會告訴你是否需要根據地圖的變化調整你的路徑。
對于一個有大量運動單元的游戲，通常不會想要保存所有的信息，所以動態D*和終身規劃A*可能不適用。這兩種算法主要為機器人而設計。當只有一個機器人的時候，你不需要為了其他機器人的路徑來重復使用內存。如果你的游戲只有一個或比較少的單元，你能會想要研究一下動態A*或者終身規劃A*算法。
D*算法概述
D*文章1
D*文章2
終身規劃算法概述
終身規劃算法論文(PDF)
終身規劃 A*算法 applet
跳躍點搜索
提高A*算法計算速度的大多數技術都是采取減少節點數量的策略。在統一代價的方格網絡中，每次單獨搜索一個獨立格空間是非常浪費的。一個解決辦法是對其中關鍵節點（例如拐角）建立一個用來進行尋路的圖。但是，沒有人愿意預先計算出一個路標圖，那就來看看可以在網格圖上向前跳躍的A*變體算法，跳躍點搜索。 考慮到當前節點的孩子節點有可能會出現在OPEN集合中，跳躍點搜索直接跳躍到從當前點可看到的遙遠的節點。隨著OPEN集合中節點的不斷減少，每一步的代價都會越來越高雖然都很高，但是步數也會越來越少。相關細節，可以參考鏈接；這篇博客中有很好的可視化解釋；還有，reddit上對優缺點的討論可點擊這個鏈接。
此外，在矩形對稱消減中，有對地圖進行分析和圖中嵌入跳躍。這兩種技術都是應用于方格網絡圖中的。
Theta*
有時網格會用來尋路是因為地圖是用網格來生成，而不是因為真的要在網格上移動。如果給定一個關鍵點的圖（例如拐角）而不是網格的話，A*算法可以運行得更快并得到更優的路徑。但是，如果你不想預先計算那些圖的拐角，你可以通過A*算法的變體Theta*在方格網絡上進行尋路而不必嚴格遵循那些方格。當構建父親指針的時候，如果有一個祖先與該節點間存在邊，那么Theta*算法會直接將該指針指向該祖先而忽略所有的中間節點。不像路徑光滑那樣將A*找到的路徑變為直線，Theta*可以把那些路徑的分析作為A*算法過程的一部分。這樣的做法可以比后處理方格路徑使之成為任意傾角的路徑的方式，可以得到更短的路徑。這篇文章的是對算法的一個比較合理的介紹，另外可參考懶惰Theta*。
Theta*的思路也可能被應用于導航網格。
更多信息請查看IT技術專欄
公眾號
事業單位
當前位置：
公考類
招聘類
各類考試
