定向搜索

在A*算法的循環(huán)中，OPEN集合用來(lái)保存所有用于尋找路徑的被搜索節(jié)點(diǎn)。定向搜索是在A*算法基礎(chǔ)上，通過(guò)對(duì)OPEN集合大小設(shè)置約束條件而得到的變體算法。當(dāng)集合太大的時(shí)候，最不可能出現(xiàn)在最優(yōu)路徑上的節(jié)點(diǎn)將會(huì)被剔除。這樣做會(huì)帶來(lái)一個(gè)缺點(diǎn)：由于必須得保持這樣的篩選，所以可選擇的數(shù)據(jù)結(jié)構(gòu)類型會(huì)受到限制。

迭代深化（Iterative deepening）

迭代深化是一種很多AI算法采用的方法，開(kāi)始的時(shí)候給一個(gè)估計(jì)值，然后通過(guò)迭代使它越來(lái)越精確。這個(gè)名字來(lái)源于游戲樹(shù)搜索中對(duì)接下來(lái)幾次操作的提前預(yù)判（例如，在象棋游戲中）。你可以通過(guò)向前預(yù)判更多的操作來(lái)深化游戲樹(shù)。一旦當(dāng)你的結(jié)果不發(fā)生變化或提高很多，就可以認(rèn)為你已經(jīng)得到了一個(gè)非常好的結(jié)果，即使讓它更精確，結(jié)果也不會(huì)再改善。在迭代深化A*(IDA*)算法中，“深度”是 f 值當(dāng)前的一個(gè)截?cái)嘀?。?dāng) f 值太大的時(shí)候，節(jié)點(diǎn)不會(huì)被考慮（也就是說(shuō)，不會(huì)被加入到OPEN集中）。第一次循環(huán)時(shí)，只需要處理非常少的節(jié)點(diǎn)。隨后的每次循環(huán)，都會(huì)增加訪問(wèn)的節(jié)點(diǎn)數(shù)。如果發(fā)現(xiàn)路徑得到優(yōu)化，就繼續(xù)增加當(dāng)前的截?cái)嘀担駝t結(jié)束。更多細(xì)節(jié)，參見(jiàn)鏈接。

我個(gè)人并不看好IDA*算法在游戲地圖尋路中的應(yīng)用。迭代深化的算法往往增加了計(jì)算時(shí)間，同時(shí)降低了內(nèi)存需求。然而，在地圖尋路的場(chǎng)景中，節(jié)點(diǎn)僅僅包含坐標(biāo)信息，所需要的內(nèi)存非常小。所以減少這部分內(nèi)存開(kāi)銷并不會(huì)帶來(lái)什么優(yōu)勢(shì)。

動(dòng)態(tài)加權(quán)

在動(dòng)態(tài)加權(quán)算法中，你假定在搜索開(kāi)始時(shí)快速達(dá)到(任意)一個(gè)位置更為重要，在搜索結(jié)束時(shí)到達(dá)目標(biāo)位置更為重要。

f(p) = g(p) + w(p) * h(p)

有一個(gè)權(quán)值(w >=  1 )和該啟發(fā)式關(guān)聯(lián)。當(dāng)不斷接近目標(biāo)位置的時(shí)候，權(quán)重值也不斷降低。這樣降低了啟發(fā)式函數(shù)的重要性，并增加了路徑實(shí)際代價(jià)的相對(duì)重要性。

帶寬搜索

帶寬搜索有兩個(gè)被認(rèn)為非常有用的特性。這個(gè)算法變體假設(shè) h 是一個(gè)估計(jì)過(guò)高的值，但它的估計(jì)誤差不會(huì)超過(guò) e。那么在這樣的條件下，搜索到的路徑代價(jià)與最優(yōu)路徑代價(jià)的誤差不會(huì)超過(guò) e。這里需要再一次強(qiáng)調(diào)，啟發(fā)值設(shè)置得越好，那么得到的結(jié)果也將越好。

另外一個(gè)特性是用來(lái)判斷你是否可以刪掉OPEN集合中的某些節(jié)點(diǎn)。只要 h+d 大于路徑真實(shí)代價(jià)（對(duì)于一些 d），那么你可以丟掉任意滿足其 f 值比OPEN集合中最優(yōu)節(jié)點(diǎn) f 值至少大 e+d 的節(jié)點(diǎn)。這是一個(gè)很奇異的特性。你相當(dāng)于得到了一個(gè) f 值的帶寬；所有在這個(gè)帶寬意外的節(jié)點(diǎn)都可以被丟棄掉，因?yàn)樗麄儽槐ＷC一定不會(huì)出現(xiàn)在最優(yōu)路徑中。

有意思地是，對(duì)于這兩種特性分別使用不同的啟發(fā)值，仍然可以計(jì)算得到結(jié)果。你可以使用一個(gè)啟發(fā)值來(lái)保證路徑代價(jià)不會(huì)太大，另外一個(gè)啟發(fā)值來(lái)決定丟棄掉OPEN集中的哪些節(jié)點(diǎn)。

雙向搜索

與從頭到尾的搜索不同，你也可以并行地同時(shí)進(jìn)行兩個(gè)搜索，一個(gè)從開(kāi)始到結(jié)束，一個(gè)從結(jié)束到開(kāi)始。當(dāng)它們相遇的時(shí)候，你就會(huì)得到一個(gè)最優(yōu)路徑。

這個(gè)想法在一些情況下非常有用。雙向搜索的主要思想是：搜索結(jié)果會(huì)形成一個(gè)在地圖上呈扇形展開(kāi)的樹(shù)。而一個(gè)大的樹(shù)遠(yuǎn)不如兩個(gè)小的樹(shù)，所以使用兩個(gè)小的搜索樹(shù)更好。

面對(duì)面的變體將兩個(gè)搜索結(jié)果鏈接到一起。該算法選擇滿足最佳 g(start,x) + h(x,y) + g(y,goal) 的一對(duì)節(jié)點(diǎn)，而不是選擇最佳前向搜索節(jié)點(diǎn) g(start,x) + h(x,goal) 或者最佳后向搜索節(jié)點(diǎn) g(y,goal) + h(start,y)。

重定向算法放棄同時(shí)前向和后向的搜索方法。該算法首先進(jìn)行一個(gè)短暫的前向搜索，并選出一個(gè)最佳的前向候選節(jié)點(diǎn)。接著進(jìn)行后向搜索。此時(shí)，后向搜索不是朝向開(kāi)始節(jié)點(diǎn)，而是朝向剛剛得到的前向候選節(jié)點(diǎn)。后向搜索也會(huì)選出一個(gè)最佳后向搜索節(jié)點(diǎn)。然后下一步，再運(yùn)行前向搜索，從當(dāng)前的前向候選節(jié)點(diǎn)到后向候選節(jié)點(diǎn)。這個(gè)過(guò)程將會(huì)不斷重復(fù)，直到兩個(gè)后選節(jié)點(diǎn)重合。

動(dòng)態(tài)A*與終身規(guī)劃A*

有一些A*的變體算法允許初始路徑計(jì)算之后地圖發(fā)生改變。動(dòng)態(tài)A*可以用于在不知道全部地圖信息的情況進(jìn)行尋路。如果沒(méi)有全部信息，那么A*算法的計(jì)算可能會(huì)出現(xiàn)錯(cuò)誤，動(dòng)態(tài)A*的優(yōu)勢(shì)在于可以快速改正那些錯(cuò)誤而不會(huì)花費(fèi)很多時(shí)間。終身規(guī)劃A*算法可以用于代價(jià)發(fā)生改變的情況。當(dāng)?shù)貓D發(fā)生改變的時(shí)候，A*計(jì)算得到路徑可能會(huì)失效；終身規(guī)劃A*可以重復(fù)利用以前的A*計(jì)算來(lái)產(chǎn)生新的路徑。

然而，動(dòng)態(tài)A*與終身規(guī)劃A*都要求大量的空間——運(yùn)行A*算法時(shí)需要保持它的內(nèi)部信息（OPEN/CLOSED集合，路徑樹(shù)，g值）。當(dāng)路徑發(fā)生改變的時(shí)候，動(dòng)態(tài)A*或終身規(guī)劃A*算法會(huì)告訴你是否需要根據(jù)地圖的變化調(diào)整你的路徑。

對(duì)于一個(gè)有大量運(yùn)動(dòng)單元的游戲，通常不會(huì)想要保存所有的信息，所以動(dòng)態(tài)D*和終身規(guī)劃A*可能不適用。這兩種算法主要為機(jī)器人而設(shè)計(jì)。當(dāng)只有一個(gè)機(jī)器人的時(shí)候，你不需要為了其他機(jī)器人的路徑來(lái)重復(fù)使用內(nèi)存。如果你的游戲只有一個(gè)或比較少的單元，你能會(huì)想要研究一下動(dòng)態(tài)A*或者終身規(guī)劃A*算法。

D*算法概述

D*文章1

D*文章2

終身規(guī)劃算法概述

終身規(guī)劃算法論文(PDF)

終身規(guī)劃 A*算法 applet

跳躍點(diǎn)搜索

提高A*算法計(jì)算速度的大多數(shù)技術(shù)都是采取減少節(jié)點(diǎn)數(shù)量的策略。在統(tǒng)一代價(jià)的方格網(wǎng)絡(luò)中，每次單獨(dú)搜索一個(gè)獨(dú)立格空間是非常浪費(fèi)的。一個(gè)解決辦法是對(duì)其中關(guān)鍵節(jié)點(diǎn)（例如拐角）建立一個(gè)用來(lái)進(jìn)行尋路的圖。但是，沒(méi)有人愿意預(yù)先計(jì)算出一個(gè)路標(biāo)圖，那就來(lái)看看可以在網(wǎng)格圖上向前跳躍的A*變體算法，跳躍點(diǎn)搜索。 考慮到當(dāng)前節(jié)點(diǎn)的孩子節(jié)點(diǎn)有可能會(huì)出現(xiàn)在OPEN集合中，跳躍點(diǎn)搜索直接跳躍到從當(dāng)前點(diǎn)可看到的遙遠(yuǎn)的節(jié)點(diǎn)。隨著OPEN集合中節(jié)點(diǎn)的不斷減少，每一步的代價(jià)都會(huì)越來(lái)越高雖然都很高，但是步數(shù)也會(huì)越來(lái)越少。相關(guān)細(xì)節(jié)，可以參考鏈接；這篇博客中有很好的可視化解釋；還有，reddit上對(duì)優(yōu)缺點(diǎn)的討論可點(diǎn)擊這個(gè)鏈接。

此外，在矩形對(duì)稱消減中，有對(duì)地圖進(jìn)行分析和圖中嵌入跳躍。這兩種技術(shù)都是應(yīng)用于方格網(wǎng)絡(luò)圖中的。

Theta*

有時(shí)網(wǎng)格會(huì)用來(lái)尋路是因?yàn)榈貓D是用網(wǎng)格來(lái)生成，而不是因?yàn)檎娴囊诰W(wǎng)格上移動(dòng)。如果給定一個(gè)關(guān)鍵點(diǎn)的圖（例如拐角）而不是網(wǎng)格的話，A*算法可以運(yùn)行得更快并得到更優(yōu)的路徑。但是，如果你不想預(yù)先計(jì)算那些圖的拐角，你可以通過(guò)A*算法的變體Theta*在方格網(wǎng)絡(luò)上進(jìn)行尋路而不必嚴(yán)格遵循那些方格。當(dāng)構(gòu)建父親指針的時(shí)候，如果有一個(gè)祖先與該節(jié)點(diǎn)間存在邊，那么Theta*算法會(huì)直接將該指針指向該祖先而忽略所有的中間節(jié)點(diǎn)。不像路徑光滑那樣將A*找到的路徑變?yōu)橹本€，Theta*可以把那些路徑的分析作為A*算法過(guò)程的一部分。這樣的做法可以比后處理方格路徑使之成為任意傾角的路徑的方式，可以得到更短的路徑。這篇文章的是對(duì)算法的一個(gè)比較合理的介紹，另外可參考懶惰Theta*。

Theta*的思路也可能被應(yīng)用于導(dǎo)航網(wǎng)格。

更多信息請(qǐng)查看IT技術(shù)專欄