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