| 一．引言 圖論是計(jì)算機(jī)科學(xué)中的一個(gè)重要研究工具，它產(chǎn)生于歐拉（Euler）對(duì)圖的連通性的研究，但直到本世紀(jì)計(jì)算機(jī)誕生以后才得最迅猛的發(fā)展。 圖論中的最短路徑問題在計(jì)算機(jī)中有著廣泛的應(yīng)用，例如網(wǎng)絡(luò)通信中最短路由的選擇，人工智能中搜索算法的研究等。 本文對(duì)幾種常見最短路徑的算法進(jìn)行介紹，尤其是在1968年發(fā)展起來的A*算法。 二． 常用算法簡(jiǎn)介 為敘述的方便，本文中假定所有圖均以鄰接矩陣表示，并將圖論中的常用符號(hào)列于下： G---------------------無(wú)向圖或有向圖 A=[aij]----------------圖G的鄰接矩陣表示 V(G)------------------圖G的頂點(diǎn)數(shù) ε(G)-----------------圖G的邊數(shù)。 1. Floyd算法 這是幾種最短路徑算法中最簡(jiǎn)單的一種，本文不詳細(xì)介紹，僅給出算法描述。 算法： For k:=1 to n do For i:=1 to n do For j:=1 to n do If A[i,j]+A[k,j]<A[i,j] then A[i,j]=a[i,k]+a[k,j]; 易知該算法的復(fù)雜度為o(n3)。 執(zhí)行該算法后矩陣A中aij即為點(diǎn)i與點(diǎn)j間的最短路徑，若要求路徑的具體行程，需在算法中以數(shù)組保存路徑的改變信息，這里不再介紹。 2. Dijkstra算法 這種算法是Dijkstra于1959年提出的，主要用于計(jì)算圖G中的某一點(diǎn)u0到其它點(diǎn)的最短距離。 算法： Step1:令l(u0)=0;l(v)=∞;v≠u0 S0={u0};v=0; Step2:"vÎ┑Si=V(G)-Si l(v)=min{l(v),l(uI)+ω(ui,v)} 設(shè)uI+1是使l(v)取到最小值的┑Si中的點(diǎn)。 令Si+1=Si∪{ui+1} Step3:If i=γ(G)-1 then Stop. If i<γ(G)-1 then i=i+1,Goto Step2. 該算法的復(fù)雜度為o(n2)。它與Floyd算法相比，優(yōu)點(diǎn)在于計(jì)算量小，缺點(diǎn)是每次只能計(jì)算出圖G中的一個(gè)點(diǎn)到其它點(diǎn)的最短路徑，但由于網(wǎng)絡(luò)通信中對(duì)路由的選擇只需計(jì)算當(dāng)前點(diǎn)與它點(diǎn)的距離，故此法得以廣泛應(yīng)用。 3. 廣度優(yōu)先搜索算法(Broad-First-Search) 廣度優(yōu)先搜索算法是一種搜索策略，與之相對(duì)應(yīng)的還有深度優(yōu)先搜索算法。廣度優(yōu)先是指從圖G中 的某點(diǎn)為始點(diǎn)出發(fā)，標(biāo)記出所有與之相鄰的點(diǎn)，并再以所有與之相鄰的點(diǎn)為始點(diǎn)，搜索所有與這些點(diǎn)相鄰的點(diǎn)，從而逐層向下擴(kuò)展，實(shí)現(xiàn)對(duì)圖的遍歷。同理，深度優(yōu) 先搜索是指從某點(diǎn)出發(fā)，逐層向下擴(kuò)展，直到無(wú)路可擴(kuò)展時(shí)向上回溯，它是優(yōu)先考慮圖的深度（指從某點(diǎn)的擴(kuò)展深度），而廣度優(yōu)先則優(yōu)先考慮圖的廣度（指從某點(diǎn) 的可擴(kuò)展量）。由于該算法僅提供出一種搜索的策略，故它不僅可用于最短路徑的搜索，事實(shí)上，圖論中有很多問題均可通過此類搜索策略而得到實(shí)現(xiàn)。本文提出它 只是因?yàn)樵?span>A*算法中，其部分地用到了該算法的思想。這里僅給出它的思想，不再對(duì)它在最短路徑中的應(yīng)用介紹。 算法： Step1: "vÎV(G),令l(v)=0,l=0 Step2:If所有標(biāo)號(hào)為l的頂點(diǎn)u的相關(guān)聯(lián)的邊皆已標(biāo)號(hào)時(shí)，Then Goto Step3。 Else 把與u相關(guān)聯(lián)的邊的未標(biāo)號(hào)的頂點(diǎn)標(biāo)以l+1，并記錄這些邊。 令l=l+1，Goto(2)。 Step3:Stop。 4. 動(dòng)態(tài)規(guī)劃算法 這 種算法利用動(dòng)態(tài)規(guī)劃理論求解最短路徑，即將始點(diǎn)到終點(diǎn)的路程分為若干狀態(tài)，從而將之轉(zhuǎn)化為多階段決策問題，這樣就可用動(dòng)態(tài)規(guī)劃理論來解決。但這也必然決定 了它的局限性，即只有求解可進(jìn)行狀態(tài)劃分的問題，而事實(shí)上有很多問題是不能進(jìn)行如是轉(zhuǎn)化的，但這種算法卻是在這種特殊條件下的最佳算法，因而也得到一些應(yīng) 用，這里不再詳述。 三． A*算法 1. 簡(jiǎn)介 A*算法是到目前為止最快的一種計(jì)算最短路徑的算法，但它一種‘較優(yōu)’算法，即它一般只能找到較優(yōu)解，而非最優(yōu)解，但由于其高效性，使其在實(shí)時(shí)系統(tǒng)、人工智能等方面應(yīng)用極其廣泛。 A*算法結(jié)合了啟發(fā)式方法（這種方法通過充分利用圖給出的信息來動(dòng)態(tài)地作出決定而使搜索次數(shù)大大降低）和形式化方法（這種方法不利用圖給出的信息，而僅通過數(shù)學(xué)的形式分析，如Dijkstra算法）。它通過一個(gè)估價(jià)函數(shù)（Heuristic Function）f(h)來估計(jì)圖中的當(dāng)前點(diǎn)p到終點(diǎn)的距離(帶權(quán)值)，并由此決定它的搜索方向，當(dāng)這條路徑失敗時(shí)，它會(huì)嘗試其它路徑。 因而我們可以發(fā)現(xiàn)，A*算法成功與否的關(guān)鍵在于估價(jià)函數(shù)的正確選擇，從理論上說，一個(gè)完全正確的估價(jià)函數(shù)是可以非常迅速地得到問題的正確解答，但一般完全正確的估價(jià)函數(shù)是得不到的，因而A*算法不能保證它每次都得到正確解答。一個(gè)不理想的估價(jià)函數(shù)可能會(huì)使它工作得很慢，甚至?xí)o出錯(cuò)誤的解答。 為了提高解答的正確性，我們可以適當(dāng)?shù)亟档凸纼r(jià)函數(shù)的值，從而使之進(jìn)行更多的搜索，但這是以降低它的速度為代價(jià)的，因而我們可以根據(jù)實(shí)際對(duì)解答的速度和正確性的要求而設(shè)計(jì)出不同的方案，使之更具彈性。 2. 實(shí)現(xiàn) 限于A*算法實(shí)現(xiàn)上的復(fù)雜，這里不能給出具體的算法流程，下面分幾個(gè)部分對(duì)A*算法實(shí)現(xiàn)中的幾個(gè)關(guān)鍵性問題加以闡述。 3. 數(shù)據(jù)結(jié)構(gòu) 眾所周知，對(duì)圖的表示可以采用數(shù)組或鏈表，而且這些表示法也各也優(yōu)缺點(diǎn)，數(shù)組可以方便地實(shí)現(xiàn)對(duì)其中某個(gè)元素的存取，但插入和刪除操作卻很困難，而鏈表則利于插入和刪除，但對(duì)某個(gè)特定元素的定位卻需借助于搜索。而A*算法則需要快速插入和刪除所求得的最優(yōu)值以及可以對(duì)當(dāng)前結(jié)點(diǎn)以下結(jié)點(diǎn)的操作，因而數(shù)組或鏈表都顯得太通用了，用來實(shí)現(xiàn)A*算法會(huì)使速度有所降低。要實(shí)現(xiàn)這些，可以通過二分樹、跳轉(zhuǎn)表等數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)，我采用的是簡(jiǎn)單而高效的帶優(yōu)先權(quán)的堆棧，經(jīng)實(shí)驗(yàn)表明，一個(gè)1000個(gè)結(jié)點(diǎn)的圖，插入而且移動(dòng)一個(gè)排序的鏈表平均需500次比較和2次移動(dòng)；未排序的鏈表平均需1000次比較和2次移動(dòng)；而堆僅需10次比較和10次移動(dòng)。需要指出的是，當(dāng)結(jié)點(diǎn)數(shù)n大于10，000時(shí)，堆將不再是正確的選擇，但這足已滿足我們一般的要求。 還有一種更好的方法是Hot Queues，而且這種方法還可應(yīng)用于Dijkstra算法以降低其復(fù)雜度。當(dāng)我們移動(dòng)估價(jià)函數(shù)值為f的結(jié)點(diǎn)時(shí)，我們插入值為f+δ(δ<=C)(若δ>=0將意味著估價(jià)函數(shù)是有效的，反之亦然)，常量C為從一個(gè)結(jié)點(diǎn)到相鄰結(jié)點(diǎn)的權(quán)的最大改變。同時(shí)我們用一些“容器”來保存估價(jià)函數(shù)值的子集（這正如o(n)的排序算法的思想）,例如，當(dāng)有10個(gè)“容器”時(shí)，堆將平均只包含1/10的估價(jià)值。因而這將比用堆更為有效。 4. 估價(jià)函數(shù)（Heuristic Function） 估價(jià)函數(shù)的正確選取將直接關(guān)系到A*算法的成功與否，而函數(shù)的確定卻與實(shí)際情形有著密切的關(guān)系。在本文中，僅對(duì)網(wǎng)格狀地圖的估價(jià)函數(shù)作部分討論，而在其它情形中，需要作不同的分析，但至少估價(jià)函數(shù)應(yīng)為連續(xù)函數(shù)。 a. Manhattan Distance 這是一種標(biāo)準(zhǔn)的估價(jià)函數(shù)， h(A) = 10 * (abs(A.x-goal.x) + abs(A.y-goal.y)) b. Diagonal Distance 如果在地圖上允許作斜線方向的運(yùn)動(dòng)，則Mahattan Distance修正為Diagonal Distance h(A) = max(abs(A.x-goal.x), abs(A.y-goal.y)) 5. 估價(jià)函數(shù)的判優(yōu) 一般情形下，我們只需對(duì)估價(jià)函數(shù)的值進(jìn)行比較而取其大者即可，但在幾個(gè)結(jié)點(diǎn)的估價(jià)函數(shù)值相同的情形下，我們需要采取一定的策略來決定這幾者誰(shuí)更優(yōu)，從而避免對(duì)多個(gè)點(diǎn)的搜索。從而如下代碼可實(shí)現(xiàn)之： double dx1 = currentX - goalX; double dy1 = currentY - goalY; double dx2 = startX - goalX; double dy2 = startY - goalY; cross = dx1*dy2 - dx2*dy1; if( cross<0 ) cross = -cross; ... add cross*0.001 to the heuristic ... 這段代碼計(jì)算始點(diǎn)、當(dāng)前點(diǎn)和終點(diǎn)的矢量積，從而可以判斷這三點(diǎn)是否共線（或近似共線），這樣不同點(diǎn)間即使有微小的差別也會(huì)被放大，從而更利于判斷。 6. 改進(jìn)的A*算法 a. Beam Search 在A*算法中需要保留所有的結(jié)點(diǎn)，這將使得時(shí)間和空間的消耗都很大，而Beam Search方法對(duì)結(jié)點(diǎn)數(shù)作出限期，當(dāng)結(jié)點(diǎn)數(shù)過多時(shí)，它會(huì)將一些不(大)可能為最優(yōu)的點(diǎn)排除，從而降低時(shí)間和空間的要求，但需要說明的是，由于在排除結(jié)點(diǎn)后需對(duì)結(jié)點(diǎn)排序，當(dāng)排序的工作量大于排除點(diǎn)后所節(jié)省的工作量，則該方法無(wú)意義。 b. Iterative deepening 這是一種在人工智能中常使用的方法，它首先產(chǎn)生一近似值，然后對(duì)它進(jìn)行修正而逐步接近最優(yōu)解。這其實(shí)在一種博奕算法的變形。 c. Dynamic weighting 這種算法是基于這樣的考慮，即在搜索初期以速度優(yōu)先，在搜索后期以準(zhǔn)確度優(yōu)先(這可通過對(duì)搜索初、后期賦予不同的權(quán)值來實(shí)現(xiàn))。即： f(p) = g(p) + w(p) * h(p) d. Bidirectional search 這種算法從起點(diǎn)和終點(diǎn)同時(shí)應(yīng)用A*算法，直到有結(jié)點(diǎn)相遇。其缺點(diǎn)在于復(fù)雜度太大，一般僅用于復(fù)雜的圖形。 e. Hierarchical A* 這種算法思想是將搜索過程化，對(duì)每個(gè)簡(jiǎn)單過程求解從而得全局較優(yōu)解。正如當(dāng)我們到另一城市時(shí)，可分解為從家里“搜索”一條路徑至車站，再?gòu)能囌?#8220;搜索”一條路徑到另一城市，當(dāng)我們從家里出發(fā)時(shí)，需要考慮的是怎樣盡快地到達(dá)車站，而不是怎樣盡快地到另一城市。 f. Dynamic A*(D*) 這種算法主要用于人工智能和機(jī)器人技術(shù)。由于A*算法一開始要求獲得全部信息，而這在實(shí)際中有時(shí)是不可能的，而D*算法就是在假定信息不完整的前提下應(yīng)用A*算法，但它會(huì)隨著得到信息的增多而不斷改進(jìn)結(jié)果，這就決定了它對(duì)空間的要求相當(dāng)高，因?yàn)樗枰Ａ粢郧暗乃蝎@得信息及運(yùn)算情形。 四． 結(jié)論 A*算法作為解決最優(yōu)路徑的一種高效算法，自從1968年誕生以來，得到了廣泛的應(yīng)用，而其的多種改進(jìn)算法也在許多領(lǐng)域發(fā)揮著作用。可以預(yù)見，在更優(yōu)的算法發(fā)現(xiàn)以前，A*算法將會(huì)得到更廣泛的應(yīng)用，并會(huì)由于圖論、人工智能、機(jī)器人技術(shù)、自動(dòng)控制等多學(xué)科的融合而得到更大的發(fā)展。 參考文獻(xiàn)： [ 1 ] 盧開澄、盧華明，圖論及其應(yīng)用（第二版），北京，清華大學(xué)出版社，1982 [ 2 ] Computer Networks(Third Edition)，Andrew S. Tanenbaum，Prentice Hall International, Inc.,1998 [ 3 ] Russell & Norvig，AI: A Modern Approach [ 4 ] Ginsberg，Essentials of Artificial Intelligence |
聯(lián)系客服
