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