摘   要： 探討了問題空間中的啟發(fā)式搜索技術(shù)，給出了構(gòu)造啟發(fā)式函數(shù)的基本方法，指出提高啟發(fā)能力的措施和影響啟發(fā)式搜索效率的主要因素。
關(guān)鍵詞： 問題空間  搜索空間  啟發(fā)式搜索  啟發(fā)函數(shù)  搜索效率

　　搜索是人工智能研究的最基本問題。目前用于搜索的方法主要有盲目搜索和啟發(fā)式搜索。盲目搜索法不適宜解決大而復(fù)雜的問題，因?yàn)橐诿つ克阉髦姓业揭粋€(gè)解，所需擴(kuò)展的節(jié)點(diǎn)數(shù)目很大，并且當(dāng)這些節(jié)點(diǎn)的擴(kuò)展次序完全隨意時(shí)，將耗費(fèi)大量的計(jì)算時(shí)間和存儲空間，搜索效率很低。啟發(fā)式搜索法則是利用與問題有關(guān)的信息進(jìn)行搜索，將知識或經(jīng)驗(yàn)與搜索相結(jié)合，從而達(dá)到減少搜索量、提高搜索效率的目的。思維信息加工理論認(rèn)為：人腦對信息處理的一個(gè)重要特點(diǎn)就是運(yùn)用啟發(fā)式，即人在進(jìn)行認(rèn)知活動時(shí)，常常利用一些生活中常用的啟發(fā)式規(guī)則很簡單地考慮幾種可能性，而不是同時(shí)考慮解決問題的各種可能性，并對各種可能性進(jìn)行權(quán)衡比較。啟發(fā)式是憑借經(jīng)驗(yàn)的求解問題方法，不能保證問題一定得到解決，但卻常常能有效地求解問題。
　　啟發(fā)式搜索法是人工智能解決問題的主要技術(shù)，而啟發(fā)能力和搜索效率則是評價(jià)一個(gè)智能搜索系統(tǒng)的關(guān)鍵因素。本文首先研究問題空間中啟發(fā)式搜索函數(shù)的構(gòu)造，然后在此基礎(chǔ)上探討啟發(fā)能力并進(jìn)行啟發(fā)式搜索效率的評估。
1  問題空間與搜索空間
　　對許多應(yīng)用領(lǐng)域而言，問題求解是最基本的。事實(shí)上不管是對人還是對機(jī)器，解決問題的能力都是衡量其智能的一個(gè)標(biāo)準(zhǔn)。問題空間由所求解的問題構(gòu)成，而問題的求解過程又可看成是一個(gè)搜索過程。為了進(jìn)行搜索，首先必須用某種形式把問題表示出來。

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

　　(3)從增加啟發(fā)能力的角度看，可以通過使用一些非低約束的函數(shù)h(x)以可接納性為代價(jià)來換取搜索效率。也就是說，一個(gè)可能不是最優(yōu)的路徑比最優(yōu)路徑更容易找到，一個(gè)非較低約束的h(x)比一個(gè)較低約束的h(x)更容易計(jì)算。在這些情況下，效率可能會成倍地增加。另一種方法是通過對估價(jià)函數(shù)f(x)中的h(x)部分加權(quán)，即用f(x)=g(x)+w*h(x)表示估價(jià)函數(shù)，以增加其啟發(fā)能力，從而達(dá)到提高搜索效率的目的。w是一個(gè)正數(shù)，非常大的w值會過分強(qiáng)調(diào)啟發(fā)式部分，而非常小的w值會突出搜索的廣度優(yōu)先特性。實(shí)驗(yàn)結(jié)果表明，如果w值與搜索樹上的節(jié)點(diǎn)成反比，則會提高搜索效率。
　　(4)從啟發(fā)式控制策略的角度看，選擇合適的啟發(fā)式搜索算法對解決問題的效率有舉足輕重的影響。通常比較啟發(fā)式搜索算法的因素主要包括：時(shí)間T、空間S、解質(zhì)量Q和效率E。對于給定的機(jī)器平臺M和所選擇的啟發(fā)式搜索算法x而言，時(shí)間度量T(M，x)依賴于算法x在執(zhí)行過程中的各種耗時(shí)計(jì)算，如節(jié)點(diǎn)的擴(kuò)展與生成所需的時(shí)間、啟發(fā)式估值計(jì)算所需的時(shí)間、路徑深度檢測和閾值檢測所需的時(shí)間等?？臻g度量S(M，x)依賴于算法x在給定的問題領(lǐng)域產(chǎn)生的節(jié)點(diǎn)數(shù)目Tx和每個(gè)節(jié)點(diǎn)所需的存儲字?jǐn)?shù)WM，即S(M，x)=Tx*WM。解的質(zhì)量Q(x)依賴于最優(yōu)路徑長度D與由啟發(fā)式算法x獲得的解路徑長度Lx的比值，即Q(x)=D/Lx。該式表明一個(gè)好的啟發(fā)式搜索算法應(yīng)該有較高的求解質(zhì)量，它實(shí)際上也反映了啟發(fā)式搜索算法的效率。所以啟發(fā)式搜索效率度量E(x)依賴于搜索空間的平均分枝度β、生成節(jié)點(diǎn)的總數(shù)Tx和搜索路徑長度Lx，即E(x)=β*Lx/ Tx。E(x)越大，搜索效率越高。
4  結(jié)束語
　　本文對人工智能中經(jīng)典的啟發(fā)式搜索問題進(jìn)行了探討，詳細(xì)分析和研究了啟發(fā)式搜索過程中啟發(fā)函數(shù)的構(gòu)造、啟發(fā)能力和啟發(fā)式搜索效率等一些基本要素，對實(shí)際應(yīng)用具有一定的指導(dǎo)意義。目前，在啟發(fā)式搜索領(lǐng)域還有許多問題值得研究，如尋找大問題的優(yōu)化解、對確定范圍的問題給出高質(zhì)量的求解、使用不完整和不確定的信息處理動態(tài)環(huán)境和復(fù)雜情況、智能博弈評估、分析和預(yù)測啟發(fā)式搜索算法的性能等。
參考文獻(xiàn)
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*.計(jì)算機(jī)學(xué)報(bào).1996；19(2)
6   趙丹青，胡寶玉.狀態(tài)空間搜索的幾種算法討論.中南民族學(xué)院學(xué)報(bào)（自然科學(xué)版），2001；20(3)
7   許精明.狀態(tài)空間的啟發(fā)式搜索方法研究.微機(jī)發(fā)展.2002；(4)