由于非計算機專業(yè)畢業(yè),對于一些經(jīng)典有用的算法不是很了解,最近在網(wǎng)上看了些關(guān)于尋路算法的,雖然沒有立刻拿來所具體的項目,對于平時的一些思維還是很有用.高級的用法還需繼續(xù)探索.
用A*算法尋路有個比較郁悶的問題，雖然每一步都可以選擇到最優(yōu)路徑，但是并不是起點到終點的最優(yōu)路徑，特別是在有障礙物的時候，可以饒開障礙物，但也會走“冤枉路”。
我個人認為的解決方法：
1、確定障礙范圍。障礙物所圍成的凸多邊形內(nèi)的可走路徑會成為“冤枉路”的陷阱。
2、障礙物所圍成的凸多邊形的眾橫向延伸范圍應(yīng)為低可走優(yōu)先級。
下圖中，橘紅色的線是用A*算法做的，很明顯，不是最優(yōu)路徑，綠色和紫色是兩條最優(yōu)路徑，但是黑色如果都到當前的位置它應(yīng)該怎么選擇下一步呢？
或則通過計算，如果在某路徑下遇到不合理情況（代價+目標距離大于了前一步的代價+目標距離），那么退回到前一個岔口選擇另一個路徑，但是這樣的計算會比較復雜，而且在路徑長并且障礙多的時候效率會很低。
以下是在網(wǎng)上找到的一篇比較簡要明了的文章
如果通過圖像模擬搜索點，可以發(fā)現(xiàn)：非啟發(fā)式的尋路算法實際上是一種窮舉法，通過固定順序依次搜索人物周圍的路點，直到找到目的地，搜索點在圖像上的表現(xiàn)為一個不斷擴大的矩形。如下：
?
??
?
很快人們發(fā)現(xiàn)如此窮舉導致搜索速度過慢，而且不是很符合邏輯，試想：如果要從（0，0）點到達（100，0）點，如果每次向東搜索時能夠走通，那么干嗎還要搜索其他方向呢？所以，出現(xiàn)了啟發(fā)式的A*尋路算法，一般通過 已經(jīng)走過的路程 + 到達目的地的直線距離 代價值作為搜索時的啟發(fā)條件，每個點建立一個代價值，每次搜索時就從代價低的最先搜索，如下：
???
綜上所述，以上的搜索是一種矩陣式的不斷逼近終點的搜索做法。優(yōu)點是比較直觀，缺點在于距離越遠、搜索時間越長。