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