摘 要： 探討了問題空間中的啟發式搜索技術，給出了構造啟發式函數的基本方法，指出提高啟發能力的措施和影響啟發式搜索效率的主要因素。
關鍵詞： 問題空間 搜索空間 啟發式搜索 啟發函數 搜索效率
搜索是人工智能研究的最基本問題。目前用于搜索的方法主要有盲目搜索和啟發式搜索。盲目搜索法不適宜解決大而復雜的問題，因為要在盲目搜索中找到一個解，所需擴展的節點數目很大，并且當這些節點的擴展次序完全隨意時，將耗費大量的計算時間和存儲空間，搜索效率很低。啟發式搜索法則是利用與問題有關的信息進行搜索，將知識或經驗與搜索相結合，從而達到減少搜索量、提高搜索效率的目的。思維信息加工理論認為：人腦對信息處理的一個重要特點就是運用啟發式，即人在進行認知活動時，常常利用一些生活中常用的啟發式規則很簡單地考慮幾種可能性，而不是同時考慮解決問題的各種可能性，并對各種可能性進行權衡比較。啟發式是憑借經驗的求解問題方法，不能保證問題一定得到解決，但卻常常能有效地求解問題。
啟發式搜索法是人工智能解決問題的主要技術，而啟發能力和搜索效率則是評價一個智能搜索系統的關鍵因素。本文首先研究問題空間中啟發式搜索函數的構造，然后在此基礎上探討啟發能力并進行啟發式搜索效率的評估。
1 問題空間與搜索空間
對許多應用領域而言，問題求解是最基本的。事實上不管是對人還是對機器，解決問題的能力都是衡量其智能的一個標準。問題空間由所求解的問題構成，而問題的求解過程又可看成是一個搜索過程。為了進行搜索，首先必須用某種形式把問題表示出來。
定義4 問題空間的狀態模型M可用一個4元組表示，即M=（I，F，G，C）。其中I是問題的所有初始狀態集合，F是算符的集合，G是目標狀態的集合，C為費用的集合。
這樣，問題空間的搜索問題就由狀態集合、引起狀態轉移的操作算符集合和用于指出狀態轉移成本的費用函數組成。搜索的目的就是尋找從初始狀態到目標狀態的最小成本路徑。若把每個狀態看成一個節點，則問題空間的狀態模型可用一個有向圖表示。這個圖不一定全連通，即從某些狀態不一定到達另一些狀態，但在每個連通的部分，每條弧代表一個算符，它把一個狀態引向另一個狀態。如果從某個初始狀態（節點）出發，有一條路徑通向目標狀態（節點），則稱此目標狀態所代表的問題在當前的初始狀態下是可解的。
定義5 在問題的狀態圖中，解題路徑所經過的所有狀態的集合，稱為搜索空間。
通常搜索空間與問題空間的關系為：搜索空間
問題空間。假定問題的初始狀態、算符和目標狀態的定義都是完全確定的，則要解決的問題就是如何有效地確定一個搜索空間，以及如何有效地搜索這個給定的空間。通常，若要有效地確定一個搜索空間，則需要某些與具體問題領域有關的特性信息，即啟發式信息。而對給定的搜索空間進行有效的搜索，則需要有好的搜索策略。二者結合就構成了所謂的啟發式搜索策略。這種策略可以大大提高解題效率，它也是人工智能領域使用最普遍的搜索策略。對啟發式搜索策略可從四個方面進行評價：(1)完整性。當問題有解時，該策略能否保證找到一個解；(2)時間復雜性。多長時間找到一個解；(3)空間復雜性。進行搜索時需要多少存儲量；(4)最優性。當有若干個不同的解時，該策略能否找到最高質量的解。
2 啟發函數和啟發能力
在搜索過程中，關鍵的一步是如何確定要擴展的節點，不同的確定方法就形成不同的搜索策略。如果在確定節點時能充分利用與問題求解有關的特性信息，估計出節點的重要性，就能在搜索時選擇重要性較高的節點進行擴展，從而求得最優解。而啟發式搜索正是這種利用問題自身的某些特性信息，指導搜索朝著最有希望的方向前進的一種方法。在啟發式搜索中，用于評價節點重要性的函數稱為估價函數，該函數表示從初始節點S0經過節點x到達目標節點Sg的最優路徑的代價估計值，其一般形式為：f(x)=g(x)+h(x)。其中g(x)為從初始節點S0到節點x已經實際付出的代價，它指出了搜索的橫向趨勢，有利于搜索的完備性，但影響搜索效率。當希望有較高的搜索效率，且只關心到達目標節點的路徑時，g(x)可以忽略，但此時會影響搜索的完備性。h(x)為節點x到目標節點Sg的最優路徑的估計代價，它體現了問題的啟發性信息，又稱為啟發函數，其形式要根據問題的特性確定。啟發函數h(x)所攜帶的啟發性信息越多，搜索時擴展的節點數就越少，搜索的效率就越高。因此在確定f(x)時，要權衡利弊，使g(x)與h(x)各占適當的比重。
由f(x)=g(x)+h(x)看出，啟發式搜索實際上涉及二種計算：
(1)確定下一個擴展節點的元級計算。首先要構造一個啟發式估價函數f(x)，該函數基于指定問題領域的信息，通常是狀態描述的一個實數值函數。一般約定，下一個要擴展的節點x是f(x)值最小的節點，并且當下一個要擴展的節點是目標節點時，搜索過程中止。
(2)擴展指定的節點和產生相應搜索路徑的目標級計算。對f(x)值最小的節點進行擴展，根據約定產生節點的一個后繼節點或所有后繼節點，然后在后繼節點上再次進行元級計算。如此往復，從而生成整個搜索空間，并在此空間中根據節點的擴展路徑，找到一條從初始節點S0到目標節點Sg的通路，即求得問題的一個解。
由于f(x)基于指定問題領域的信息，因此構造和選擇合適的啟發函數h(x)就成為啟發式搜索策略的一個關鍵問題。就構造h(x)而言，通常必須對求解的問題有比較深入的理解。目前構造啟發函數h(x)的方法主要有三種：(1)根據處在最優路徑上的節點的概率構造h(x)；(2)根據任意節點x與目標集G（Sg∈G）之間的距離量度或差別量度構造h(x)；(3)在棋類博弈中，根據棋局的某些特點，決定棋步的得分數來構造h(x)等。
總之，構造啟發函數應滿足二方面的要求：一是函數要簡單易算，二是函數要有較高的精確度。對很多問題，這二方面的要求是相互矛盾的。簡單易算的啟發函數往往精確度較低，估計某條路徑好壞程度的誤差較大；而精度高的啟發函數，雖然能有效地估計搜索路徑的好壞程度，但函數往往比較復雜，計算函數值要花較多的時間，總計算量很大。因為在各種搜索算法中，被估值的葉子節點的數目與搜索的時間有著接近線性的關系，隨著搜索層數的加深，葉子節點的數目迅速上升，啟發函數被數以百萬次的調用，將花費大量的運算時間。所以構造一個好的啟發函數，必須要權衡這二種因素。
確定一種啟發式搜索方法是否比另一種啟發式搜索方法具有更強的啟發能力，往往與啟發函數h(x)的選擇有關。啟發函數是將問題狀態的描述詳細計劃成一種對此問題狀態滿意程度的量度，其目的在于當搜索過程中有一條以上的路徑可以使用時，引導搜索走最有利的路徑。啟發函數對搜索空間中的每個節點的重要性估計得越準，解決問題的過程就會越直接和越快。因此，對同一個問題，選用不同的h(x)，將得到不同的搜索過程，當然搜索效率也不同。一般而言，對于不太復雜的求解問題，通常選用0≤h(x)≤h*(x)，以求問題的最優解，而且在滿足h(x)≤h*(x)的前題下，h(x)的值越大越好。h(x)值越大，表明它攜帶的啟發性信息就越多。h*(x)為節點x到目標節點Sg的最優路徑的代價。對于比較復雜的求解問題，為了加大啟發能力，可適當選用h(x)＞h*(x)。這樣雖然犧牲了算法的可采納性，不能保證得到最優解，但卻有益于使搜索集中指向目標，且在初始節點附近盡量有限的范圍內進行，從而減少了擴展節點的數量，并能得到一個滿意解。
3 啟發式搜索效率
啟發式搜索在解決困難問題上是一種非常有效的工具，其搜索效率不僅取決于過程自身的啟發能力，而且還與被求解問題的有關屬性等多種因素有關。下面將討論啟發式搜索效率問題。
(1)從問題求解所需知識的角度看，運用知識的目的就是為了減少搜索量。如果解決一類智能問題涉及的知識越多，則搜索量就越少。因此，提高搜索效率的途徑之一就是逐步積累知識并恰當使用有助于減少搜索的信息與知識。指導搜索的啟發知識實際上是一種控制元知識，即是關于如何用問題領域知識的知識和關于問題求解方法的知識。搜索效率在很大程度上決定于問題的表示方法，而問題的表示方法又與知識的表達方式有關。啟發式搜索實際上是在二個空間中進行的，一個是狀態空間，一個是知識空間。利用算符作用于舊狀態而得到新狀態，這是在狀態空間中移動，查看新狀態是否即是目標狀態，其為搜索過程。然而，當確定采用哪一個算符或確定選擇哪一個狀態進行擴展時，則需要參考事先準備好的、且與問題領域有關的知識，這就需要到知識空間去搜索。因此在選擇和使用知識方面，合理地構造知識庫并建立高效的知識推理機制，也是提高搜索效率的關鍵因素之一。
(2)從搜索過程的角度看，通常用二個參數來度量搜索效率。一個參數是滲透率P，定義為P=L/T。其中L為初始節點到目標節點的路徑長度，T為整個搜索過程中所生成的節點總數。滲透率反映了搜索過程中從初始節點向目標節點前進時搜索區域的寬度，它度量出搜索過程所產生的搜索樹是“單枝延伸”還是“多枝密葉”。當L=T時，P=1表示搜索過程每次只生成一個節點，且該節點恰好是解路徑上的節點，搜索效率最高。P越小，表示搜索時產生的無用節點越多，搜索效率越低。另一個參數是有效分枝因子B，它描述了一個搜索過程朝著目標前進的激烈程度。設L為搜索路徑長度，T為搜索過程中生成的節點總數，則有：
(3)從增加啟發能力的角度看，可以通過使用一些非低約束的函數h(x)以可接納性為代價來換取搜索效率。也就是說，一個可能不是最優的路徑比最優路徑更容易找到，一個非較低約束的h(x)比一個較低約束的h(x)更容易計算。在這些情況下，效率可能會成倍地增加。另一種方法是通過對估價函數f(x)中的h(x)部分加權，即用f(x)=g(x)+w*h(x)表示估價函數，以增加其啟發能力，從而達到提高搜索效率的目的。w是一個正數，非常大的w值會過分強調啟發式部分，而非常小的w值會突出搜索的廣度優先特性。實驗結果表明，如果w值與搜索樹上的節點成反比，則會提高搜索效率。
(4)從啟發式控制策略的角度看，選擇合適的啟發式搜索算法對解決問題的效率有舉足輕重的影響。通常比較啟發式搜索算法的因素主要包括：時間T、空間S、解質量Q和效率E。對于給定的機器平臺M和所選擇的啟發式搜索算法x而言，時間度量T(M，x)依賴于算法x在執行過程中的各種耗時計算，如節點的擴展與生成所需的時間、啟發式估值計算所需的時間、路徑深度檢測和閾值檢測所需的時間等。空間度量S(M，x)依賴于算法x在給定的問題領域產生的節點數目Tx和每個節點所需的存儲字數WM，即S(M，x)=Tx*WM。解的質量Q(x)依賴于最優路徑長度D與由啟發式算法x獲得的解路徑長度Lx的比值，即Q(x)=D/Lx。該式表明一個好的啟發式搜索算法應該有較高的求解質量，它實際上也反映了啟發式搜索算法的效率。所以啟發式搜索效率度量E(x)依賴于搜索空間的平均分枝度β、生成節點的總數Tx和搜索路徑長度Lx，即E(x)=β*Lx/ Tx。E(x)越大，搜索效率越高。
4 結束語
本文對人工智能中經典的啟發式搜索問題進行了探討，詳細分析和研究了啟發式搜索過程中啟發函數的構造、啟發能力和啟發式搜索效率等一些基本要素，對實際應用具有一定的指導意義。目前，在啟發式搜索領域還有許多問題值得研究，如尋找大問題的優化解、對確定范圍的問題給出高質量的求解、使用不完整和不確定的信息處理動態環境和復雜情況、智能博弈評估、分析和預測啟發式搜索算法的性能等。
參考文獻
1 Buro M.Improving heuristic mini-max search by supervised learning. Artificial Intelligence，2002；(134)
2 Al-Ayyoub A E，Masoud F A.Heuristic search revisited. The Journal of Systems and Software，2000；(55)
3 Muller M.Partial order bounding：A new approach to evaluation in game tree search.Artificial Intelligence，2001；(129)
4 王永慶.人工智能原理與方法.西安：西安交通大學出版社，1998
5 王士同.多因素問題的啟發式搜索算法MFRA*.計算機學報.1996；19(2)
6 趙丹青，胡寶玉.狀態空間搜索的幾種算法討論.中南民族學院學報（自然科學版），2001；20(3)
7 許精明.狀態空間的啟發式搜索方法研究.微機發展.2002；(4)