由于非計(jì)算機(jī)專(zhuān)業(yè)畢業(yè),對(duì)于一些經(jīng)典有用的算法不是很了解,最近在網(wǎng)上看了些關(guān)于尋路算法的,雖然沒(méi)有立刻拿來(lái)所具體的項(xiàng)目,對(duì)于平時(shí)的一些思維還是很有用.高級(jí)的用法還需繼續(xù)探索.

用A*算法尋路有個(gè)比較郁悶的問(wèn)題，雖然每一步都可以選擇到最優(yōu)路徑，但是并不是起點(diǎn)到終點(diǎn)的最優(yōu)路徑，特別是在有障礙物的時(shí)候，可以饒開(kāi)障礙物，但也會(huì)走“冤枉路”。

我個(gè)人認(rèn)為的解決方法：

1、確定障礙范圍。障礙物所圍成的凸多邊形內(nèi)的可走路徑會(huì)成為“冤枉路”的陷阱。

2、障礙物所圍成的凸多邊形的眾橫向延伸范圍應(yīng)為低可走優(yōu)先級(jí)。

下圖中，橘紅色的線(xiàn)是用A*算法做的，很明顯，不是最優(yōu)路徑，綠色和紫色是兩條最優(yōu)路徑，但是黑色如果都到當(dāng)前的位置它應(yīng)該怎么選擇下一步呢？

或則通過(guò)計(jì)算，如果在某路徑下遇到不合理情況（代價(jià)+目標(biāo)距離大于了前一步的代價(jià)+目標(biāo)距離），那么退回到前一個(gè)岔口選擇另一個(gè)路徑，但是這樣的計(jì)算會(huì)比較復(fù)雜，而且在路徑長(zhǎng)并且障礙多的時(shí)候效率會(huì)很低。

以下是在網(wǎng)上找到的一篇比較簡(jiǎn)要明了的文章

如果通過(guò)圖像模擬搜索點(diǎn)，可以發(fā)現(xiàn)：非啟發(fā)式的尋路算法實(shí)際上是一種窮舉法，通過(guò)固定順序依次搜索人物周?chē)穆伏c(diǎn)，直到找到目的地，搜索點(diǎn)在圖像上的表現(xiàn)為一個(gè)不斷擴(kuò)大的矩形。如下：

???

?

很快人們發(fā)現(xiàn)如此窮舉導(dǎo)致搜索速度過(guò)慢，而且不是很符合邏輯，試想：如果要從（0，0）點(diǎn)到達(dá)（100，0）點(diǎn)，如果每次向東搜索時(shí)能夠走通，那么干嗎還要搜索其他方向呢？所以，出現(xiàn)了啟發(fā)式的A*尋路算法，一般通過(guò) 已經(jīng)走過(guò)的路程 + 到達(dá)目的地的直線(xiàn)距離 代價(jià)值作為搜索時(shí)的啟發(fā)條件，每個(gè)點(diǎn)建立一個(gè)代價(jià)值，每次搜索時(shí)就從代價(jià)低的最先搜索，如下：

???

綜上所述，以上的搜索是一種矩陣式的不斷逼近終點(diǎn)的搜索做法。優(yōu)點(diǎn)是比較直觀(guān)，缺點(diǎn)在于距離越遠(yuǎn)、搜索時(shí)間越長(zhǎng)。