【文章內(nèi)容簡介】 FS） BFS 算法試圖找出一點與最初始的點最接近在一 層內(nèi)，但是他不會連續(xù)兩次訪問同一個節(jié)點。他的最好的情況為 o(bd)，最差的情況為 o(bd)此處 b樹的廣度， d樹的深度 。這個算法的好處是他一定可以找出一個解，并且解出步數(shù)將會小于 DFS 的步數(shù)，因為對于樹來說，深度往往要比樹的廣度要打，但是這一算法將會大量的耗費內(nèi)存，他會將他所有的可能的節(jié)點全部保存下來，因此他在算法效率上十分的笨重。 BFS 算法傾向于使用隊列作為他的數(shù)據(jù)處理方式 。 深度優(yōu)先搜尋 （ DFS） DFS 算法與 BFS 的區(qū)別就是他將會對每個節(jié)點子節(jié)點優(yōu)先進行搜索，這將會對具有很大廣度的樹來說更加 有效率，它最好的情況為 o(b*d)最壞的情況為 o(bd)。此處 b樹的廣度， d樹的深度 。 DFS 對于某些特殊的情況更加使用，因此它的使用范圍相對 BFS小點，但是它的優(yōu)勢就是 BFS 就會使用 bd個空間用于存儲節(jié)點，而 DFS 不會，它將大大節(jié)省空間。 DFS 更加傾向于使用堆債作為他的數(shù)據(jù)的處理方式。 A*算法 以上兩種算法 BFS 肯定能找出答案，但是他會耗費大量的資源， DFS 雖然效率更好但是他只是用某些特殊的情況，而且他有可能會在一個局部內(nèi)死循環(huán)，從而得出一個局部的最優(yōu)解，而不是全局的最優(yōu)解。 這里引入 A*算 法， A*算法更加的智能它引入了一個估價函數(shù)的機制，從而避免了局部最優(yōu)解的局面。 *的意思是他比起普通的算法更加的優(yōu)化。對于 A 算法來說，他不會比較估價函數(shù)的值，而 A*算法則會比較他們之間的值，從而得出最好接，這就會將局部以外的可能更優(yōu)的節(jié)點加入到搜索的過程中。 這個函數(shù)式為 f*(n)=g*(n)+h*(n)，最重要的是找出 h*(n)的值如果無法計算出一個好的值，那么他的效率將會和上面說到算法一樣低下，因此它最好的情況是 O(b*d)最差的情況是 O(bd)。此處 g*(n)不是重點的原因是因為在其他的位置可能存在更好 的解，這就會防止局部最優(yōu)解的產(chǎn)生。 基于 A*算法的路徑尋找 8 A*搜尋算法， 他可以應(yīng)用在具有多個不同節(jié)點的路徑的圖上，同時求出一個最短路徑的算法 。 它的最常見的應(yīng)用是在游戲中 NPC 的移動方面，或者是在網(wǎng)絡(luò)游戲中 BOT 的移動計算方面 。 上文中提到 該算法像 與 Dijkstra 算法 的原理基本一致 ， 目的是為找出一條最短的路徑 ； 同時他 也像 BFS 一樣，進行啟發(fā)式的搜索。 在這個算法中引入了一個叫做估價值的概念 ， 它的大致的原理如下： g(n)表示從起點到任意 節(jié)點 n 的 路徑的 距離長度 ， h(n)表示 圖中 任意 一個存在的節(jié)點 n到目標 節(jié)點 的 股價值的大小 。 因此， A*算法的 關(guān)于估價值的 公式 可以表示為下式 ： f(n)=g(n)+h(n)。 這個公式 具有以下幾個特殊的地方 ： 如果 h(n)為 0， 那么 f(n)=g(n)， 這種情況出現(xiàn)在 求出起點到任意 節(jié)點 n的最短路徑， 這種情況下問題就類似于 單源最短路徑 的 問題， 此時就可以應(yīng)用 Dijkstra算法。 如果 h(n)=“n 到目標的實際距離 ” ， 那么不停比較這些值就可以最終產(chǎn)生出最優(yōu)解 。 不過當 h(n)的值越來 越小 的時候 ， 他所涉及到的 需要計算的節(jié)點 數(shù)目將會 越多，此時的 算法效率 將會低下 。 比如當應(yīng)用到幾何型的網(wǎng)絡(luò)中時， 可以取兩節(jié)點間 直線距離（即是歐幾 理德距離 ）做為 節(jié)點的 估價值，即 f=g(n)+sqrt((dxnx)*(dxnx)+(dyny)*(dyny))； 這樣的話受到估價值 h的影響個，在 g值一定的情況下估價函數(shù) f 會受到 h 的約束 ， f的值越小 就意味著 h的值也小，同時表示這個節(jié)點距離目標點就越近 ， 這樣話就是表示搜索到的每一個點就會產(chǎn)生一條最短路徑 。 而這點 明顯 和 Dijstra 算法 在點四周漫無目的的以枚舉的方式進行尋找就好很多，因為他對每個點進行了預判剔除了不必要的點，極大地提高了效率 。 這里需要提到 h（ n）的一個屬性他被稱為信息性，他的意思是在估算 一個節(jié)點的估價值的時候的約束條件， 當一個節(jié)點的約束條件越多或者說他的信息性越多的話，他被剔除的可能性就越大，這樣大量不需要計算的節(jié)點就會被排除，所以我們就可以說這個估價函數(shù)很好或者是這個算法更加優(yōu)秀。這個特性使得它比廣度優(yōu)先算法優(yōu)秀很多，因為他的 h(n)為 0，換句話就是它不具有信息性即啟發(fā)性信息。但是在路徑搜索的過程中，他往往要求了很高的實時性， h(n)的信息性越強，他的要求的計算量就會相對上升，使得他耗費的時間也就會越大。此時為了滿足他的實時性，我們必須在一定程度上減少的h(n)的信息性 ，即減少節(jié)點的約束 性的條件。但是他付出的代價就是準確性會降低，這就是一個我們需要權(quán)衡的問題。 簡化的 A*算法流程： 搜索區(qū)域被劃分成了方形網(wǎng)格。簡化搜索區(qū)域，是尋路的第一步。這一方法把搜索區(qū)域簡化成了一個二維數(shù)組。數(shù)組的每一個元素是網(wǎng)格的一個方塊，方塊被標記為可通過的和不可通過的。路徑被描述為從 A到 B我們經(jīng)過的方塊的集合。一旦路徑被找到，我們的人就從一個方格的中心走向另一個，直到到達目的地。 基于 A*算法的路徑尋找 9 ，他會將其周圍待處理的節(jié)點放入一個列表中。一開始只有一個，即是起點，但是之后就會多起來。表格內(nèi)包含待檢查的方格。 找起點周圍可到達的一切可通過的方格，放棄不可通過的方格。把這些可行的方格加入到列表中。為這些方格保存點 A 為這些方格的父方格。父方格很重要類，類似于樹中的父節(jié)點。 A，將其加入另一個表（稱為關(guān)閉列表），這個列表中保存所有不需要再次檢查的方格。接著重復以上步驟，找出每個可行的方格的表和關(guān)閉列表。類似于一棵樹，尋找他的最小的路徑。 選擇路徑中經(jīng)過哪個方格的關(guān)鍵是下面這個等式： F=G+H *G=從起點 A，沿著產(chǎn)生的路徑，移動到網(wǎng)格上指定方格的移動耗費。 *H=從網(wǎng)格上那個方格移動到終點 B 的預估移 動耗費。這經(jīng)常被稱為啟發(fā)式的 ， H的值將會是不定的。此為最簡單的方式。既然我們在計算沿特定路徑通往某個方格的 G值，求值的方法就是取它父節(jié)點的 G 值，然后依照它相對父節(jié)點是對角線方向或者直角方向 (非對角線 )，分別增加和。例子中這個方法的需求會變得更多，因為我們從起點方格以外獲取了不止一個方格。 H值可以用不同的方法估算。我們這里使用的方法被稱為曼哈頓方法，它計算從當前格到目的格之間水平和垂直的方格的數(shù)量總和，忽略對角線方向，然后把結(jié)果乘以 10。這被稱為曼哈頓方法是因為它看起來像計算城市中從一個地方到另外一個地方的 街區(qū)數(shù)，在那里你不能沿對角線方向穿過街區(qū)。很重要的一點，我們忽略了一切障礙物。這是對剩余距離的一個估算，而非實際值，這也是這一方法被稱為啟發(fā)式的原因。想知道更多？你可以在這里找到方程和額外的注解。 F的值是 G和 H的和。第一步搜索的結(jié)果可以在下面的圖表中看到。 F,G 和 H 的評分被寫在每個方格里。正如在緊挨起始格右側(cè)的方格所表示的， F被打印在左上角， G在左下角， H 則在右下角。 為了繼續(xù)搜索，我們簡單的從開啟列表中選擇 F值最低的方格。然后，對選中的方格做如下處理： 4，把它從開啟列表中刪除，然后添加到關(guān)閉列表中。 5，檢查所有相鄰格子。跳過那些已經(jīng)在關(guān)閉列表中的或者不可通過的 (有墻，水的地形，或者其他無法通過的地形 )，把他們添加進開啟列表，如果他們還不在里面的話。把選中的方格作為新的方格的父節(jié)點。 6，如果某個相鄰格已經(jīng)在開啟列表里了，檢查現(xiàn)在的這條路徑是否更好。換句話說，檢查如果我們用新的路徑到達它的話， G 值是否會更低一些。如果不是，那就什么都不做。 基于 A*算法的路徑尋找 10 以上就是 A*算法的主要的過程，但是無法體現(xiàn)估價函數(shù)重要的價值。 為了更加明了的解釋這格的重要性，我將用華容道作為例子來解釋他的重要性。 有一個 3*3的方格 8 1 3 4 5 2 7 6 他最終的目的是變成 1 2 3 8 4 7 6 5 他將會使用兩種不動估價函數(shù)，在附錄中將會有這兩種情況的圖片 使用了兩種不同的估價函數(shù) f(n)good 和 f(n)weak 都最終得到了結(jié)果但是 f(n)good的估價函數(shù)效率更加高。我們通過更加深入的觀察這些過程可以了解到為何 f(n)weak 用了更多的步數(shù)才得到了結(jié)果，從一開始，搜索的步驟直接導向了有最終結(jié)果的那個分支。但是在 f(n)weak 達到這個路徑之前他多使用了 4 步才搜索到了這個具有最終解的分支。并且 f(n)good 三個子節(jié)點的估價值遠遠高于 f(n)weak的估價值是的結(jié)果更加具有了區(qū)分度，更加容易得出具有答案的分支。 再設(shè)計 f(n)函數(shù)的時候， h(n)必須謹慎的設(shè)計，如果隨意設(shè)置就會導致算法效率及其的低下。 h(n)的值可以根據(jù)不同的應(yīng)用的場景特殊設(shè)計。 基于 A*算法的路徑尋找 11 4 A*算法 仿真系統(tǒng)設(shè)計 路徑尋址系統(tǒng)概述 建立一個可以自由畫障礙物的程序，在起點到終點的過程中可以繞過障礙物。尋找一個最優(yōu)的路徑。并且可以保存及加載路徑，一邊可以用相互之間的比較。 對用戶界面進行模塊設(shè)計 主窗口界面 使用 JAVA 的 SWING 技術(shù)搭建一個 UI 界面 主要的程序入口為 AStarDemo 文件，他會負責加載各個窗體的組建 AstarPanelastarPanel = newAstarPanel(15,15,60,40)。 StatusPanelstatusPanel = newStatusPanel()。 (statusPanel)。 (newAStarMenuBar(astarPanel))。 ().add(new ControlPanel(astarPanel), )。 (true)。 ()。 以上代碼將 astarPanel， statusPanel， AStarMenuBar， ControlPanel 等相關(guān)的組建加入到 UI 中 。 繪畫過程代碼 astarPanel 作用是最主要他負責在界面上畫出障礙物 和畫出計算出的路徑 ，使得A*算法畫出他算出的路徑。并且可以顯示出每個節(jié)點的相應(yīng)的坐標。 (x, y , width, height, arc, arc)。 (TIPS_COMPOSITE2)。 (TIPS_FG)。 (Current grid num : ( + ().x + , + ().y + ), x + 15, y + 15)。 ()。 其上為顯示坐標的代碼 基于 A*算法的路徑尋找 12 在 60*40的表格而每個節(jié)點的大小為 15pix*15pix的背景。 publicvoidpaintComponent(Graphics g) { (g)。 fillBarrier(g)。 fillTargetAndSourceGrid(g)。 fillOpenList(g)。 fillAStarPath(g)。 fillDrawData(g)。 drawGridLine(g)。 drawTips(g)。 } 以上代碼的繪畫邏輯是 ： 圖 繪畫代碼邏輯 工具欄代碼 AStarMenuBar 的作用是顯示菜單欄，它的基本顯示的代碼： enumMainMenu{ File(File, 39。F39。), View(View, 39。V39。), Help(Help, 39。H39。) 。 基于 A*算法的路徑尋找 13 publicSubMenu[] getSubMenus() { if(subMenus==null){ ListSubMenutmp = newLinkedListSubMenu()。 for(SubMenusubMenu : ()){ if(()==this){ (subMenu)。 } } subMenus = newSubMenu[()]。 subMenus = (subMenus)。 } returnsubMenus。 } } 他有三個主菜單組成使用， getSubMenus()方法得到下層的菜單。 ControlPanel 的作用是實現(xiàn)界面上的三個按鈕通過調(diào)用不同的函數(shù)實現(xiàn)功能，三個函數(shù)是 : startFind()這是算法開始的入口，是最重要的函數(shù)他將調(diào)用他的一個 find()方法實現(xiàn)他的路徑搜索。 clearPath()清理路徑 clearMap(