A*算法A*（A-Star)算法是一種靜態路網中求解最短路最有效的方法。公式表示為： f(n)=g(n)+h(n), 其中f(n) 是節點n從初始點到目標點的估價函數，g(n) 是在狀態空間中從初始節點到n節點的實際代價，h(n)是從n到目標節點最佳路徑的估計代價。保證找到最短路徑（最優解的）條件，關鍵在于估價函數h(n)的選取：估價值h(n)實際值, 搜索的點數少，搜索范圍小，效率高，但不能保證得到最優解。估價值與實際值越接近，估價函數取得就越好。例如對于幾何路網來說，可以取兩節點間歐幾理德距離（直線距離）做為估價值，即f=g(n)+sqrt(dx-nx)*(dx-nx)+(dy-ny)*(dy-ny)；這樣估價函數f在g值一定的情況下，會或多或少的受估價值h的制約，節點距目標點近，h值小，f值相對就小，能保證最短路的搜索向終點的方向進行。明顯優于Dijstra算法的毫無無方向的向四周搜索。conditions of heuristicOptimistic (must be less than or equal to the real cost)As close to the real cost as possible主要搜索過程：創建兩個表，OPEN表保存所有已生成而未考察的節點，CLOSED表中記錄已訪問過的節點。遍歷當前節點的各個節點，將n節點放入CLOSE中，取n節點的子節點X,-算X的估價值-While(OPEN!=NULL)從OPEN表中取估價值f最小的節點n;if(n節點=目標節點) break;elseif(X in OPEN) 比較兩個X的估價值f /注意是同一個節點的兩個不同路徑的估價值if( X的估價值小于OPEN表的估價值 )更新OPEN表中的估價值; /取最小路徑的估價值if(X in CLOSE) 比較兩個X的估價值 /注意是同一個節點的兩個不同路徑的估價值if( X的估價值小于CLOSE表的估價值 )更新CLOSE表中的估價值; 把X節點放入OPEN /取最小路徑的估價值if(X not in both)求X的估價值;并將X插入OPEN表中; /還沒有排序將n節點插入CLOSE表中;按照估價值將OPEN表中的節點排序; /實際上是比較OPEN表內節點f的大小，從最小路徑的節點向下進行。啟發式搜索其實有很多的算法，比如：局部擇優搜索法、最好優先搜索法等等。當然A*也是。這些算法都使用了啟發函數，但在具體的選取最佳搜索節點時的策略不同。象局部擇優搜索法，就是在搜索的過程中選取“最佳節點”后舍棄其他的兄弟節點，父親節點，而一直得搜索下去。這種搜索的結果很明顯，由于舍棄了其他的節點，可能也把最好的節點都舍棄了，因為求解的最佳節點只是在該階段的最佳并不一定是全局的最佳。最好優先就聰明多了，他在搜索時，便沒有舍棄節點（除非該節點是死節點），在每一步的估價中都把當前的節點和以前的節點的估價值比較得到一個“最佳的節點”。這樣可以有效的防止“最佳節點”的丟失。那么A*算法又是一種什么樣的算法呢？其實A*算法也是一種最好優先的算法。只不過要加上一些約束條件罷了。由于在一些問題求解時，我們希望能夠求解出狀態空間搜索的最短路徑，也就是用最快的方法求解問題，A*就是干這種事情的！我們先下個定義，如果一個估價函數可以找出最短的路徑，我們稱之為可采納性。A*算法是一個可采納的最好優先算法。A*算法的估價函數可表示為：f(n) = g(n) + h(n) 這里，f(n)是估價函數，g(n)是起點到終點的最短路徑值，h(n)是n到目標的最斷路經的啟發值。由于這個f(n)其實是無法預先知道的，所以我們用前面的估價函數f(n)做近似。g(n)代替g(n)，但 g(n)=g(n)才可（大多數情況下都是滿足的，可以不用考慮），h(n)代替h(n)，但h(n)=h(n)才可（這一點特別的重要）。可以證明應用這樣的估價函數是可以找到最短路徑的，也就是可采納的。我們說應用這種估價函數的最好優先算法就是A*算法。哈。你懂了嗎？肯定沒懂。接著看。舉一個例子，其實廣度優先算法就是A*算法的特例。其中g(n)是節點所在的層數，h(n)=0，這種h(n)肯定小于h(n)，所以由前述可知廣度優先算法是一種可采納的。實際也是。當然它是一種最臭的A*算法。再說一個問題，就是有關h(n)啟發函數的信息性。h(n)的信息性通俗點說其實就是在估計一個節點的值時的約束條件，如果信息越多或約束條件越多則排除的節點就越多，估價函數越好或說這個算法越好。這就是為什么廣度優先算法的那么臭的原因了，誰叫它的h(n)=0，一點啟發信息都沒有。但在游戲開發中由于實時性的問題，h(n)的信息越多，它的計算量就越大，耗費的時間就越多。就應該適當的減小h(n)的信息，即減小約束條件。但算法的準確性就差了，這里就有一個平衡的問題。次短路徑次短路徑可以看作是k短路徑問題的一種特殊情況，求k短路徑有Yen算法等較為復雜的方法，對于次短路徑，可以有更為簡易的方法。下面介紹一種求兩個頂點之間次短路徑的解法。我們要對一個有向賦權圖(無向圖每條邊可以看作兩條相反的有向邊)的頂點S到T之間求次短路徑，首先應求出S的單源最短路徑。遍歷有向圖，標記出可以在最短路徑上的邊，加入集合K。然后枚舉刪除集合K中每條邊，求從S到T的最短路徑，記錄每次求出的路徑長度值，其最小值就是次短路徑的長度。在這里我們以為次短路徑長度可以等于最短路徑長度，如果想等，也可以看作是從S到T有不止一條最短路徑。如果我們規定求從S到T大于最短路徑長度的次短路徑，則答案就是每次刪邊后大于原最短路徑的S到T的最短路徑長度的最小值。用Dijkstra+堆求單源最短路徑，則每次求最短路徑時間復雜度為O(N*log(N+M) + M)，所以總的時間復雜度為O(N*M*log(N+M) + M2)。該估計是較為悲觀的，因為一般來說，在最短路徑上的邊的條數要遠遠小于M，所以實際效果要比預想的好。次小生成樹類比上述次短路徑求法，很容易想到一個“枚舉刪除最小生成樹上的每條邊，再求最小生成樹”的直觀解法。如果用Prim+堆，每次最小生成樹時間復雜度為O(N*log(N+M) + M)，枚舉刪除有O(N)條邊，時間復雜度就是O(N2*log(N+M) + N*M)，當圖很稠密時，接近O(N3)。這種方法簡易直觀，但我們有一個更簡單，而且效率更高的O(N2+M)的解法，下面介紹這種方法。首先求出原圖最小生成樹，記錄權值之和為MinST。枚舉添加每條不在最小生成樹上的邊(u,v)，加上以后一定會形成一個環。找到環上權值第二大的邊(即除了(u,v)以外的權值最大的邊)，把它刪掉，計算當前生成樹的權值之和。取所有枚舉修改的生成樹權值之和的最小值，就是次小生成樹。具體實現時，更簡單的方法是從每個節點i遍歷整個最小生成樹，定義Fj為從i到j的路徑上最大邊的權值。遍歷圖求出Fj的值，然后對于添加每條不在最小生成樹中的邊(i,j)，新的生成樹權值之和就是MinST + w(i,j) - Fj，記錄其最小值，則為次小生成樹。該算法的時間復雜度為O(N2 + M)。由于只用求一次最小生成樹，可以用最簡單的Prim，時間復雜度為O(N2)。算法的瓶頸不在求最小生成樹，而在O(N2+M)的枚舉加邊修改，所以用更好的最小生成樹算法是沒有必要的。次短路徑與次小生成樹的例題HAOI 2005 路由選擇問題直接求次短路徑。pku 3255 Roadblocks稍微特殊的次短路徑，允許邊重復走。Ural 1416 Confidential求次小生成樹的問題、pku 1679 The Unique MST判斷最小生成樹是否唯一。對于 前K短路徑問題 和 A*算法 的一些小小總結我很懶的 2007-12-08 10:37 首先，為了說話方便，列出一些術語： 在啟發式搜索中，對于每個狀態 x，啟發函數 f(x) 通常是這樣的形式：f(x) = g(x) + h(x) 其中 g(x) 是從初始狀態走到 x 所花的代價；h(x) 是從 x 走到目標狀態所需要的代價的估計值。 相對于 h(x)，還有一個概念叫 h*(x)，表示從 x 走到目標狀態所需要的實際最小代價（當然，這個值有時我們是事先無法知道的）。 如果在你的啟發函數里，能保證 h(x) = h*(x)，也就是說，你不能高估了從 x 走到目標狀態所需要的代價，那就可以說這個搜索是 A* 算法（這里的“*”，英文就讀作 star）。 A* 算法的特點是，如果存在從初始狀態走到目標狀態的最小代價的解，那么用 A* 算法搜索時，第一個找到的解就一定是最小代價的。這就是所謂的可采納（admissible）。1. 求前 K 短的 可以帶環的 路徑（的長度） 1.1. 典型的啟發式搜索 設起點為 s；終點為 t；對于一個點 v，dt(v) 表示從 v 走到 t 的最短路徑的長度（可以在初始化的時候全都算好）。 網友 richard 教會了我，可以用最典型的啟發式搜索來解這個問題。一個狀態 x 表示的是從 s 走到某個點的一條路徑，把這個點記作 x.v，把這條路徑的長度記作 x.len。接著，我們可以使用以下啟發函數：g(x) = x.len; h(x) = dt(x.v); f(x) = g(x) + h(x) = x.len + dt(x.v) 初始狀態中， x.v = s； x.len = 0。然后每次讓優先隊列（所謂的 Open 表）中 f(x) 值最小的狀態 x 出隊，再跟據圖中所有從 x.v 出發的邊發展下一層狀態，讓它們進隊列。優先隊列中不存在判重復的問題，因為每個狀態所代表的路徑肯定是不一樣的。 不難想通，這是一個 A* 算法，因為這里的 h(x) 本身就是 h*(x)，當然滿足 h(x) x.v 就稱作 Px 的偏離邊（deviation edge）； Px 上從 x.pre 到 t 的這一段子路徑就稱為 Px 的偏離路徑（deviation path）。為什么叫作偏離路徑，看到后面都明白了。 先求出從 s 到 t 的最短路徑，它就是初始狀態 x1 所要代表的路徑。設它的第一條邊是 s - a，則 x1.v = a； x1.len = w(s, a) （w(s, a) 表示邊 s - a 的長度）； x1.pre = s，也就是說，規定 Px1 的偏離邊是 s - a。 把 x1 放進優先隊列。接下來，每當進入最大的循環的第 i 輪，從優先隊列里出隊的狀態（啟發值最小的，也就是路徑長度目前最短的狀態，記作 xi）就代表了第 i 短的解。第一輪出隊的當然是前面定義的初始狀態 x1。下面要從它發展新的狀態，作為可能的第 2 短的解，放進優先隊列。發展的方法如下： 對于 Px1 的偏離路徑上的每一條邊（設它為 u - v），都要找出另一條邊 u - v，滿足在所有從點 u 出發的邊當中， w(u, v) + dt(v) 僅僅高于 w(u, v) + dt(v) （或與它相同）；也就是說，從 u 出發，走 u - v 這條邊到終點是最近的，走 u - v 這條邊是第 2 近的（或者一樣近）。從每一條 u - v，我們都可以發展出一個新狀態 x： x.v = v； x.len = w(Psu) + w(u, v)； x.pre = u，也就是說 Px 的偏離邊就是 u - v。圖 1 圖 1 給出了一個例子。假設圖中藍色和黑色的邊組成的路徑就是 Px1，藍色邊是它的偏離路徑；那些紅色的邊就是前面說的那些 u - v；紅色的虛線就代表了從每個 v 到 t 的最短路徑。可見，每條 Px 都是從 u - v 開始從 Px1 “身上”偏離出來的，因此把 從偏離邊到終點 的這一段路徑稱為 Px 的偏離路徑。 注意，由于本問題中求的路徑是可以帶環的，所以走到終點以后還可以回頭再走。因此，在圖 1 中可以看到在點 t 后面也發展了一條偏離路徑。這條偏離路徑顯然不再需要是第 2 短的，而是從 t 出發再回到 t 的最短的路徑。 上面講的是從 x1 發展狀態的情況。從之后的 xi 發展狀態的時候還有一點要注意：在我們尋找偏離邊 u - v 的時候，如果 u = xi.pre （也就是當 要找的偏離邊 和 xi 的偏離邊 是從同一點出發時），則要注意 u - v 不僅要和 u - xi.v 不同，而且要和 xi 的所有祖先狀態中從點 u 出發的那條邊都不同，不然新發展的狀態豈不是和 xi 的祖先狀態重復了。圖 2 圖 2 給出了一個例子。假設藍色路徑是從黑色路徑中發展出的偏離路徑；當從藍色路徑發展偏離路徑時，要找的是除了藍色和黑色的邊以外，能以最短的距離走到 t 的那條邊，假設這里我們找到的是紅色的那條邊；當從紅色路徑發展偏離路徑時，要找的是除了紅色、藍色和黑色的邊以外，能以最短的距離走到 t 的那條邊，假設這里我們找到的是綠色的那條邊。 如此一來，可能有很多偏離路徑都是從同一點偏離出來的，但是它們的偏離邊都不相同。要在程序中實現這一點，可以在每個狀態中記錄下所有祖先狀態的偏離邊。 顯然 Yen 算法也是一個 A* 算法，但是它有一個特點，前面已經說過了，就是最大的那個循環最多只要做 K 次，因為每當一個狀態出隊列時，我們就找到了一個解。因此基本上可以估計出算法的時間復雜度： 設圖中有 N 個點，那么一條偏離路徑上最多只有 N 條邊（因為它是一條邊 加上 從某一點到終點的最短路徑），也就是說，從一個狀態最多發展出 N + 1 個新狀態（偏離路徑上的每條邊發展出一個，從點 t 再發展出一個）。 尋找一條偏離路徑時，需要掃描從一個點出發的所有邊，暫且假設從一個點出發的邊最多也是 N 條，那么這一步要花 O(N) 的時間。 可以想象優先隊列（Open 表）里最多有 O(K * N) 個元素，所以每次維護優先隊列的時間差不多是 O( lg (K * N) )。 因此，總的時間復雜度，在最差情況下，差不多就是 O( K * ( N2 + lg(K * N) ) )。當然這只是我個人估計一下，不要太拿它當回事。 1.3. MPS 算法 同樣是在The K shortest paths problem這篇文章中，還介紹了作者自已發明的 MPS 算法（MPS 是該文章的三位作者的名字縮寫）。它的框架和 Yen 算法相同，但是有一個優化，可以加快尋找偏離邊的速度。方法就是把從每個點出發的所有邊，都按照從該條邊走向 t 的最短距離 升序排序（最好用鄰接鏈表描述圖）。圖 3 圖 3 給出了一個例子。圖中從點 s 出發的邊有紅、藍和綠三條，延著它們到達終點 t 的最短距離分別為 3、 2 和 4。因此把從 s 出發的邊排序為 (藍, 紅, 綠)。 這樣一來，尋找偏離邊的時間就只有 O(1) 了。因為我們從某一點第一次發展偏離邊時，只要選它的鄰接鏈表中的第一條邊；下一次再從該點發展時，只要選第二條邊再也不用一一掃描所有邊了，也不用擔心會和祖先狀態的偏離邊重復了。 假設圖中有 N 個點，從每個點出發的邊最多也是 N 條。那么排序一個點的鄰接鏈表需要 O(N * lg N) 的時間，排序整個鄰接鏈表的時間就是 O(N2 * lgN)；搜索的時間由 Yen 算法的 O(K * N2) 降至 O(K * N)。因此，整個算法在最差情況下的時間復雜度大約就是 O(N2 * lgN + K * N)。（從數字上看，好像也沒有比 Yen 算法快到哪去但是實際試下來確實是快的。）2. 求前 K 短的 無環 路徑（的長度） 2.1. 典型的啟發式搜索 網友 richard 在他的這篇文章里介紹了，把 1.1 節中的算法稍加修改，就可以用來求無環的前 K 短路徑。修改方法就是在每個狀態中保存 Psv 所經過的點；當從一個狀態發展新狀態時，下一步走的點不能出現在 Psv 中（如果點比較少的話，用位運算就可以很快地對此進行判斷。）。這樣一來，最終求出的路徑就無環了。圖 4 這個算法在大多數情況下確實很好用，但是在 2006 年橫濱賽區的最后一題中，就有一組陰險的數據可以讓這個算法超時。如圖 4 所示，從點 s 出發只有兩條邊：藍色的很短，紅色的非常長（既使把圖中所有邊的長度都加起來，也沒有它長）；能走向點 t 的只有一條邊，它的起點正是藍色邊的終點；圖的其它部分有很多點，它們兩兩之間都有邊（圖 4 中只是象征性地畫了一下，實際上有更多點）。可以想象，只要第一步走了藍色的邊，那么能到達點 t 的無環的路徑只有一條，那就是 s - 藍色的點 - t。從第 2 短的解開始，都必須走紅色的邊。 但是啟發式搜索一定會先走藍色的邊，然后嘗試其后的所有路徑。直到實在走投無路徑時，才會回過頭來走紅色的邊，因為從長度來看，紅色邊的優先級實在太低了（雖然它才是正解）。假設圖中有 N 個點，可以想象，啟發式搜索會先嘗試 O(N!) 條錯誤的路徑，那就太可怕了。 我曾經想過下面一些優化的方案，但是好像都行不通： 如果在一個我們想要發展的新狀態 x 中，從 s 到 x.v 的路徑 和 從 x.v 到 t 的最短路徑上有重復的點（前者的點集被保存在 x 中；后者的點集可以在初始化所有最短路徑時記錄下來），則不讓它進優先隊列（Open 表）？ 這樣做是不對的。因為雖然從 x.v 到 t 的最短路徑不能構成無環的解，但是這并不代表從 x.v 到 t 的稍長一點的路徑就不可能構成無環的解。因此，這樣的狀態還是必須得發展下去，否則就可能錯過了一些解。 在優先隊列（Open 表）里只保存前 K 個最優的狀態，比較差的狀態就不進隊列了？ 這樣做更加是不對的。因為圖 4 這個例子就已經明確地說明了，啟發值比較優先的狀態并不一定能通向正解，而啟發值較差的狀