本節書摘來自華章計算機《人工智能：計算agent基礎》一書中的第3章，第3.7節,作者：（加）david l.poole,alan k.mackworth 更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視。
之前的政策可以進行很多優化。首先，我們給出兩種适用于圖中有環的方法：一種是對環路的明确檢查，而另一種是對到某一節點的多路徑檢查。然後，我們給出疊代深度算法和深度分支界限搜尋法，92這兩種方法是能保證找到解路徑（甚至是最優解）的一般方法，就像寬度優先搜尋算法或者a搜尋算法，但是利用了深度優先搜尋的空間優點。我們将搜尋問題分解為很多小的搜尋問題來簡化搜尋方法，這樣每一個都更容易解決。最後，我們說明利用動态規劃法如何尋找路徑和建構啟發函數。
3.7.1 環檢查
用來代表搜尋空間的圖可能包含環。例如，圖3-6中的機器人域中的機器人會在節點o103和o109之間來回移動。前面所述的搜尋方法中有些會陷入環，不斷循環，甚至在有限圖中也找不到搜尋結果。其他的方法也可能循環，但最終會找到解。
當能保證在有限圖中找到解後，修剪搜尋樹的最簡單的方法是，不考慮那些已經在從起始節點開始的路徑上的點。“環檢查”（cycle check）和“回路檢查”(loop check)就是用來檢查最後一個節點是否在從初始節點到這個點的路徑上出現過。有了循環檢查，隻有路徑〈s,…,sk,s〉，其中，s{s0,…,sk}，加入了圖3-4中第16行。另外，也可以在選擇了節點之後再進行檢查，删除有環的路徑。
環檢查的計算複雜性決定于所使用的搜尋方法。對于深度優先搜尋方法，其圖是顯式存儲的，管理費用跟常數因子一樣低。圖中每個節點增加1位，當節點擴張的時候該位應當為1，回溯的時候為0。搜尋算法可以通過不擴充該位是1的節點來避免循環。因為深度優先算法保持單一目前路徑，是以這個方法有效，路徑上的邊界有可替代的分支。即使圖是動态生成的，隻要目前路徑上的點有一個有效的索引結構，那麼很容易完成環檢查。
對于多路徑的搜尋政策（也就是說，圖3-9中所有有指數空間的那些），環檢查的時間與搜尋的路徑長度保持線性增長。在檢查以保證不會添加已經在路徑中出現過的節點上，這些算法不能比搜尋局部路徑做得更好。
3.7.2 多路徑剪枝
通常有多條路徑通向一個節點。如果隻需要一條路徑，對于已經找到一條路徑的節點，搜尋算法就需要從邊界中剪枝掉其他任何通往該節點的路徑。93
多路徑剪枝（multiple-path pruning）是通過由已擴充節點組成的closed表來實作的。如圖3-4中的13行，選擇了一個路徑，如果它的最後一個節點在closed表中，那麼這條途徑就該删除。否則，将最後的節點加到closed表中，算法會繼續進行。
這個方法不一定保證最短的路徑不被丢棄。可能要更複雜的方法才能保證找到最優解。為了保證搜尋算法可以找到至目标節點最低花費的路徑，應當遵守以下幾條之一：
保證到達任何節點的第一條路徑都是到那個點的最低花費路徑，然後像前面讨論過的那樣，剪枝掉所有随後找到的到那個點的路徑。
如果搜尋算法找到比已經找到的路徑花費更低的路徑了，那麼它就可以将所有較高花費的路徑删除（因為這些都不可能是最優解）。也就是說，如果邊界有一條路徑p在路徑〈s,…,n,…,m〉中，當發現到n的路徑p′比p中相應部分更近，那麼p就可以從邊界中删除了。
無論何時，如果搜尋中找到比之前找到的路徑花費更低的至某點的路徑，那麼就把這條新路徑吸收到已擴充路徑的初始路徑中。是以，如果有路徑p=〈s,…,n,…,m〉，一個到n的更短的路徑p′就可以代替到n的路徑p的初始部分。
這些方案中的第一條，允許在找到最優解的保證下使用closed表。其他則需要更複雜的算法。
在最低花費優先算法中，第一次找到的到某一個節點（如，從邊界中選擇的一個節點）的路徑，是到該節點的最低花費路徑。删除随後的到該節點的路徑不會移除最低花費的那條到該節點的路徑，是以，剪掉随後的路徑仍然可以保證找到最優解。
像之前描述的一樣，a算法不能保證到某點第一次選擇的路徑就是到該點的最低花費路徑。注意到，可采納性定理保證的是對于到目标節點的每一條路徑，而不是每一條路徑。看看何時删除到一個節點的随後路徑會删除最優解，假設算法選擇了到節點n的路徑p來擴充，但是存在一個到節點n的更低花費的路徑，而這條路徑還沒有找到。那麼，邊界中就應該有路徑p′，它是較低花費路徑的初始部分。猜想路徑p′在節點n′結束。則一定有f(p)≤f(p′)，因為p是在p′之前選擇的。這就是說：
如果經過p′比經過p的到n的路徑有更低花費，則
其中，d(n′,n)為從節點n′到節點n的最短路徑的實際花費。從上面兩個等式，我們可以得出：
（h(p′)-h(p) = h(n′)-h(n)可通過以上假設得出。）是以，對于任意兩個節點n和n′，如果h(n′)-h(n) ≤ d(n′,n)，那麼就能保證找到的第一條路徑就是最低花費路徑。對于任意兩個節點n和n′，對h的單調限制（monotone restriction）是h(n′)-h(n)≤d(n′,n)。也就是說，兩個節點的啟發函數值的差必須小于或等于兩點最低花費路徑的實際花費。例如，當花費函數是關于距離的函數時，它适用于兩點之間的歐幾裡得距離（在n維歐幾裡得空間的直線距離）的啟發函數。它也适用于啟發函數是有更短解的簡化問題的解。
因為單調的限制，在邊界，f值是單調非遞減函數。也就是說，随着邊界的擴充，f值不會變小。是以，因為單調的限制，a算法中随後的到任何節點的路徑都可以删除。
多路徑剪枝包含環檢查，因為環是到某個節點的另外一條路徑，是以要被删除掉。如果圖是顯式存儲的，通過在每個節點上設定一個比特位标明已被找到的路徑，多路徑剪枝可以在一個常數時間内完成。如果圖是動态生成的，通過存儲由已擴充過的所有節點組成的closed清單，它能在對數時間（隻要進行适當索引，可與已擴充的節點數量成對數級）完成。多路徑剪枝優先于寬度優先的環檢查，因為寬度優先搜尋中所有節點被認為必須存儲。然而，對于深度優先搜尋，算法并不是存儲所有的已經擴充節點。存儲它們會使這個方法的空間呈指數增長。是以，對于深度優先搜尋，環檢查優先于多路徑剪枝。
3.7.3 疊代深化
到目前為止，我們所讨論過的方法中，沒有一種方法是理想的。僅有的能保證找到路徑方法需要指數空間（見圖3-9）。結合深度優先搜尋算法的空間效率和寬度優先搜尋算法的最優性的一種方法是疊代深化（iterative deepening）。這種方法的思想是重新計算邊界中的點而不是儲存它們。每一次重新計算的過程都是深度優先搜素，是以用更少的空間。
我們考慮将寬度優先搜尋融合到疊代深化搜尋。由僅進行有限深度搜尋的搜尋器來進行。首先，通過用深度為1的方式進行深度優先搜尋，找到深度為1的深度優先方式的路徑。然後找深度為2的路徑，然後是深度為3的路勁，依次進行。每一次重新計算都可以删掉之前的計算并再次啟動。最後如果解存在就可以找到解了，95因為它是按順序列舉路徑，是以第一個找到的路徑就是弧線最少的。
當使用疊代深化搜尋時，應當注意區分：
因為達到深度界限的失敗。
還未到達深度界限的失敗。
對于第一種情況，搜尋必須進行更深界限的搜尋。對于第二種情況，重新進行一次更深界限搜尋是浪費時間，因為不管多深，路徑都不存在。我們稱這種到達了深度界限的失敗叫做非自然失敗（failing unnaturally），未到達深度界限的失敗叫做自然失敗(failing naturally)。
圖3-10中提出一種疊代深化搜尋的實作idsearch。局部程式dbsearch實作了一個深度有界的深度優先搜尋（使用遞歸來保持堆棧），可以限制正在搜尋的路徑長度。它使用深度優先搜尋來找到所有長度為k+b的路徑，其中，k是給定的從起點開始的路徑長度，b是一個非負整數。疊代深化搜尋器調用這個程式來增加深度界限。這個程式發現的到目标節點的路徑的順序和寬度優先算法相同。作為一種通用的圖搜尋算法，為找到更多路徑，在22行的return之後，搜尋能從23行繼續。
隻要寬度優先搜尋失敗，疊代深化搜尋就會失敗。當需要更多解時，即使在後續的疊代中可能被再次發現，每一個成功路徑也隻傳回一次。通過跟蹤何時增加界限可以幫助找到解能使搜尋終止：
如果深度搜尋中因為到達了深度界限而截斷了，那麼深度界限可以增加。在這種情況下，搜尋就非自然失敗了。如果因為深度界限的限制而沒有删除任何路徑，那麼搜尋就自然失敗了。這種情況下，程式終止，報告0路徑。
搜尋隻報告在之前的疊代中沒有報告過的一條路徑，是以，它隻傳回那些長度等于深度界限的路徑。
疊代深化搜尋的最明顯的問題是每一步的計算浪費。然而，這可能不像某些人想的那樣糟糕，尤其是當分支系數很高的時候。考慮下面算法的運作時間。假定一個常數分支系數b>1，考慮界限是k的搜尋。對于深度k，有bk個節點，每一個節點被生成1次。深度為k-1的節點被生成2次，那些深度為k-2的節點被生成3次，如此類推，然後深度為1的節點被産生k次。是以，節點的生成總數是：
https://yqfile.alicdn.com/87361a189fb52dbe03ad008a90c3c0b80783f5aa.png" >
在深度n生成節點有一個固定的開銷(b/(b-1))2，當b=2時，就有一個開銷系數4，當b=3時，有開銷系數2.25保證邊界。該算法是o(bk)，并且找不到一個更好的漸進的無資訊搜尋政策。注意到，如果分支系數接近1，這種分析就沒有用（因為分母趨近于0），見習題3.9。
疊代深化也可以用于a搜尋中。疊代深化a（ida）算法通過重複的有深度界限的深度優先搜尋來進行。它是一個有界的f(n)的值，而不是路徑中弧的數量有界。它的門檻值起始于是f(s)，其中s是有最小h值的初始節點。然後ida進行深度優先的深度有界搜尋，但從不擴充一個比目前的界限更高的f值的節點。如果深度有界的搜尋非自然地失敗了，那麼下一個界限就是超過之前界限的最小的f值。ida就如a一樣檢查相同的節點，但用深度優先搜尋重新計算它們，而不是存儲它們。
3.7.4 分支界限法
深度優先分支界限(branch and bound)搜尋是一種結合了深度優先搜尋算法的空間節約和啟發資訊搜尋的方法。它特别适用于存在很多條通往目标節點的路徑，我們需要的是最優的路徑。像在a搜尋中，我們假設h(n)小于或等于從n到目标節點的最低花費路徑的花費。
深度優先分支界限搜尋的思想是保持到目标最低花費的路徑和它的花費，假定這個花費是有界的。如果搜尋碰到路徑p滿足cost(p)+h(p)≥ bound，那麼p就該删除掉。如果找到沒被删除的路徑，那麼這條路徑一定優于之前最好的路徑。這個新解被記住，而且界限就設定成這個新解的花費，然後尋找更好的解。
分支界限搜尋生成持續優化解的序列。一旦找到一個解，就一直優化它。
分支界限搜尋典型地用于深度優先搜尋，這樣可以保持深度優先的節省空間的優點。它和深度有界搜尋的實作方法相似，但是這裡的界限是路徑的花費，然後減少花費發現更短的路徑。算法會記住所發現的花費最低的路徑，當搜尋完成時傳回這條路徑。
算法見圖3-11。對于花費有界搜尋，内部程式cbsearch使用全局變量來給主程式提供資訊。
最初，界限可以設定為無窮大，但是也可以設定一個高估的值，bound0，作為最優路徑的花費，這很有用。如果存在比初始花費界限bound0更低的路徑，這個算法會傳回最優解（從初始節點到目标節點的最低花費路徑）。
如果初始界限略高于最低花費路徑的花費，那麼這個算法不需擴充比a算法更多的弧就可以找到最優的路徑。上述情況發生的條件是，算法将那些花費比最低花費高的任何路徑都剪枝；一旦它發現一個通往目标節點的路徑，它就隻探索那些f值低于已擴充路徑的路徑。而這些正好就是a找到一個解後所探索的路徑。
99當bound0=∞時，如果傳回⊥，則不存在解。當bound0是有界值時，傳回⊥，表示比bound0花費少的解不存在。在找到解或者已知解不存在之前，這個算法可以結合疊代深化算法來增加界限，見習題3.13。
【例3-17】 看圖3-12中的樹形圖。目标節點被塗上陰影。假設每一段弧線的長度為1，沒有啟發資訊（即每個節點的h(n)=0）。在算法中，假設depth0=∞，深度優先搜尋總是先選擇最左邊的後繼節點。該圖說明了檢驗确定節點是否是目标節點的順序。沒有标出序号的節點是未檢驗的節點。
在節點5下面的子樹形圖中，沒有目标節點，被完全探索完（或者根據深度的有限值depth0進行擴充）。被檢驗的第9個節點是目标節點。它有一條路徑，其花費是5，是以界限值設為5。從此以後，隻有長度小于5的路徑才能作為可能的解被檢驗。第15個被檢驗的節點也是目标節點。它的路徑花費是3，是以界限減少到3。再沒有找到其他的目标節點，是以到标号15的那條路徑傳回，這個是最優路徑。有另外一條最優路徑被剪枝。算法就不再檢驗标号為18的節點的後繼節點。
如果有啟發資訊，就可以用來剪枝部分的搜尋空間，就像a算法。
3.7.5 搜尋方向
在有限無資訊圖上的通用搜尋算法的搜尋空間大小是bk，這裡b是分支系數，k是路徑長度。任何可以減少b和k的方法都可能會節省很多資源。
問題求解的圖搜尋方法的抽象定義在以下意義上是對稱的，100即這個算法可以從初始節點開始，向前搜尋目标節點；或者逆向從目标節點開始，向後搜尋初始節點。注意，目标節點的許多應用是由布爾函數隐式地确定，即當發現目标節點時傳回true，而不是顯式地傳回節點集，是以說逆向的向後搜尋也許是不可能的。
對于那些目标節點是顯式的情況，在一個方向上搜尋可能比另一個方向更有效。搜尋空間的大小與分支系數成指數增長。通常情況下，向前和向後搜尋有不同的分支系數。向前或者向後搜尋的一般原則是哪個方向有較小的分支系數。
下面讨論的幾種方法對于搜尋空間來說可以提高效率。
1.雙向搜尋
這個搜尋方法的思想是同時從起始節點向後以及從目标節點向前搜尋來減少搜尋時間。當兩個搜尋的邊界相交，這個算法就重構出一個路徑，它從起始節點到相交的邊界再到目标節點。
在雙向搜尋中産生一個新問題，即要保證兩個搜尋的邊界真正相交。舉例來說，在兩個方向上的深度優先搜尋不一定能夠很好地起作用，因為它可能會因為其較小的搜尋邊界而互相錯過相交。在兩個方向上的寬度優先搜尋可以保證相交。
一個方向深度優先搜尋結合另一個方向寬度優先搜尋可以保證所需要的搜尋邊界的相交，但是在哪個方向上選擇用哪種方法很困難。這取決于寬度優先節省的花費以及搜尋檢查深度優先搜尋何時與其元素相交的花費。
在有些情況下，雙向搜尋可以節省很多。例如，如果前向分支系數和後向分支系數都是b，目标節點的深度是k，那麼寬度優先搜尋花費的時間與bk成比例，然而一個對稱雙向搜尋花費的時間與2bk/2成比例。即使時間複雜度仍然是指數級，它以指數函數形式節省時間。注意，這種複雜性分析需要假設找到相交點是無需代價的，在很多應用中這種假設可能不成立（見習題3.10）。
2.島驅動搜尋
一種使搜尋更有效的方式是找到有限的向前和向後搜尋可以相交的地方，例如，找到不同樓層的兩間房間之間的通路，101合适的搜尋限制可能是先去其中一個樓層的電梯，然後到目标樓層的那個電梯。直覺上，這些指定的位置在搜尋圖上就像一些島（island），它們被限定在從起始節點到目标節點的解路徑上。
當島确定了，agent可以将一個搜尋問題分解為幾個子問題，例如，一個從初始房間到電梯，一個從某一層的電梯到另外一層的電梯，一個從電梯到目标房間。通過三個更簡單的問題求解就縮小了搜尋空間。這些更小問題減少了大搜尋的組合爆炸，這也是個很好的例子，說明了問題的額外資訊如何提高搜尋的效率。
為使用島來找到s和g之間的一條路徑，需要：
1) 确定一系列的島i0,…,ik；
2) 找到從s到i0，從ij-1到ij（j為1～k），從ik到g的路徑。
每一個搜尋問題應該比總的問題更簡單，是以更容易解決。
島的識别可能是我們從圖中無法獲得的額外資訊。使用不适當的島可能使問題更複雜（甚至不可解決）。通過選擇不同島集，我們可以将問題分解為另外一組子問題，并通過可能的島空間進行搜尋。在實際使用中是否适用取決于問題的細節。
3.抽象層次搜尋
島的概念可以用來定義在細節上的多個層次或者抽象的多個層次上所使用的問題求解政策。
抽象層次上的搜尋的思想首先涉及問題的抽象，盡可能去掉細節。我們可能找到問題的部分解：它的解需要進一步的細節。例如，從一個房間到另一個房間的問題，需要使用多次轉身，但是agent喜歡從一個抽象層次推理問題，其中實際轉向的細節被省略了。我們期望适當的抽象解決能從廣義角度解決問題，隻剩下一些小問題還需要解決。像傳遞機器人的路徑規劃問題，不省略細節的搜尋求解很困難，除非必須考慮它們。
這種方法的實作可以通過島驅動搜尋找到可能的島。一旦在島層次上找到一個解，子問題就可以同樣的方式通過遞歸解決了。在低層次發現的資訊可以通知高層次，其中的某些可能解不如期望的那麼好。高層次可以使用這些資訊重新規劃，這個過程通常不能保證最優解，因為它隻考慮一些高層次的分解。
在抽象層次的搜尋很大程度上取決去怎樣分解和抽象要解決的問題。一旦問題被抽象和分解出來，任何搜尋方法都能用來解決它們。然而，識别有用的抽象和問題分解并不容易。
3.7.6 動态規劃法
動态規劃法是最優化的一般方法，它可以存儲問題的部分解，是以對于已經發現的解可以檢索而不必重新計算。動态規劃算法的使用貫穿人工智能。
動态規劃算法可以用來在圖中找到路徑。直覺上，圖搜尋中的動态規劃（dynamic programming）可以被看做用來構造完美的啟發函數使得a可以保證找到解，即使它隻有邊界的一個元素。cost_to_goal函數表示每個節點到目标節點的最低花費路徑的準确花費。
政策（policy）用來指定從每個節點引出哪條弧。cost_to_goal函數可以離線計算，用來建立最優的政策。agent可以利用這個政策線上決定在這個節點做什麼。
令cost_to_goal(n)是從n到目标節點的最低花費路徑的實際花費。cost_to_goal(n)函數可以定義為：
一般的思想是從目标節點開始，建立一個表存放每一個節點的cost_to_goal(n)值。這可以通過多路徑剪枝的最低花費優先搜尋來實作，它從目标節點開始在反向圖（将圖中所有弧的方向反過來）中搜尋。對于已發現的每個節點，動态規劃算法記錄其cost_to_goal值，而不是有一個需搜尋的目标。使用反向圖計算每個節點到目标節點的花費，而不是從目标到每個節點。實質上，動态規劃從目标節點進行逆向搜尋，它通過建立從圖中每個節點到目标節點的最低花費路徑來完成。
對于一個特定的目标，一旦每個節點的cost_to_goal值記錄下來，agent就可以根據這個值來決定最優路徑的下一段弧。從節點n應該選擇這樣的鄰居m，它有cost(〈n,m〉) + cost_to_goal(m)的最小值。遵循這個政策，agent就能沿着最低花費路徑從任意節點直到目标。假設每個節點有有限鄰居，給定cost_to_goal，決定哪段弧是最優的需要常數時間，該常數與圖的大小有關。動态規劃法建立cost_to_goal表所需要的時間和空間與圖的大小呈線性關系。
動态規劃算法在下面條件下是有用的：
目标節點是顯式的（之前的方法隻假設一個函數來識别目标節點）；
需要一個最低花費路徑；
圖是有限的和足夠小的，能夠存儲每一個節點的cost_to_goal值；
目标不經常變化；
政策對于每個目标可以使用多次，産生cost_to_goal值的花費可以分攤到很多執行個體問題上。
動态規劃搜尋的主要問題是：
隻有當圖有限，而且表能小到适應于記憶體時，這個方法才有效。
對于每一個不同的目标，agent必須重新計算政策。
需要的時間空間線性于圖的大小，對于有限的圖來說，圖的大小通常是路徑長度的指數形式。
【例3-18】 對于圖3-2，從r123到目标節點的花費是0，是以
cost_to_goal (r123) = 0
繼續從r123使用最低花費優先搜尋
到這個階段向後搜尋停止了。這裡注意兩點:首先，如果一個節點沒有cost_to_goal值，那麼不存在從該節點到目标節點的路徑；其次，agent可以很快地确定任意一個節點到目标節點的最低花費值路徑的下一段弧。例如，如果agent在o103，決定到r123的最低花費路徑，需要比較4+43（通過b3的花費）和12+29（直接到o109的花費），可以很快決定去o109。
當建立cost_to_goal函數時，搜尋者會隐式地決定選擇哪個鄰居到達目标，它不是在運作時就确定哪個鄰居在最優路徑上，而是儲存該資訊。104
動态規劃搜尋可以用來為a算法和分支界限算法建構啟發資訊。建構啟發函數的一種方式是簡化問題（如去掉一些細節），直到被簡化的問題有一個足夠小的狀态空間。動态規劃算法可以用來在簡化了的問題中找到最優的路徑。這個資訊也可以用來作為原始問題的啟發資訊。a算法的最優性對于一個搜尋算法，如果不存在能使用更少的時間或空間或擴充更少的節點的其他算法，同時保證解的品質，那麼這個算法就是最優的(optimal)。最優搜尋算法每次都會選擇正确的節點。然而，因為我們不能直接實作它，是以這個算法的詳細說明并不有效。這樣一個算法是否能實作是一個開放問題（就像是否p=np）。然而，似乎有一個能被證明的陳述。
a的最優性(optimality of a)：在隻使用弧花費和從起始節點到目标節點花費的啟發式估計的搜尋算法中，沒有算法能比a算法擴充更少的節點并保證能找到最低花費路徑。
證明概述：除非算法擴充了每一個路徑p，這裡f(p)低于最優路徑的花費，否則隻給定弧線花費以及啟發資訊，我們不知道p是否是一條最低花費的路徑。更正式地，假設一個算法a′找到了問題p的解，這裡某些路徑p沒有擴充，這樣f(p)小于找到的解。假設有另一個問題p′，除了有一條花費為f(p)的通過p的路徑，其他與問題p一樣。算法a′不能分辨p′和p，因為它不擴充路徑p，是以它對問題p′會傳回和p一樣的解，但是對于p找到的解對于p′來說不是最優解，因為這個解比經過p的路徑有更高的花費。是以，算法不能保證找到最低花費的路徑，除非它找到所有的f值比最優路徑低的路徑，這樣就必須找到a所找到的所有的路徑。
反例：盡管這個證明似乎合理，但是有的算法擴充更少的節點。考慮一個算法，它使用像a算法的向前搜尋以及向後的動态規劃搜尋方法，這兩種方法在某些方面是交叉進行的（例如，向前和向後交叉進行）。向後的搜尋會建立一個表：cost_to_goal(n)，指的是從n到目标節點的實際花費，它有邊界值b，它已經擴充了所有到目标花費低于b的路徑。向前搜尋使用cost(p)+c(n)上的優先級隊列，這裡n是路徑p的最後一個節點，如果這個值已經算出c(n)是cost_to_goal(n)，否則c(n)是max(h(n),b)。直覺上，如果從路徑的最後一個節點p到目标節點存在路徑，或者它使用向後搜尋已經擴充的路徑，或者使用花費至少為b的路徑。這個算法保證能找到最低花費的路徑，擴充比a更少的節點（見習題3.11）。
總結：上面的反例似乎意味着a的最優性是錯誤的。然而，證明也有一定的吸引力，這不應被徹底忽視。a不是所有算法中最優的，但是對于所有向前搜尋的方法，這個證明似乎是正确的（見習題3.12）。