A-star和第k短路和次小生成樹和Yen和MPS尋路算法.doc

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