楚孟慧，吳姝瑤

（山東科技大學(xué)電氣信息系，山東濟南，250031）

0 引言

人工智能這個詞已經(jīng)成為現(xiàn)代科技前沿的的代表了。人工智能在最近幾年逐漸成為互聯(lián)網(wǎng)方向的主流，作為一種新興的現(xiàn)代技術(shù)在互聯(lián)網(wǎng)領(lǐng)域的多種服務(wù)上已經(jīng)有所體現(xiàn)。其中搜索過程是人工智能技術(shù)實現(xiàn)的一個重要環(huán)節(jié)，是推理不可或缺的一部分。求解一個問題實質(zhì)上就是對現(xiàn)有知識進行搜索，搜索也是求解問題的方法和過程。掌握搜索算法對人工智能的開發(fā)至關(guān)重要。

1 搜索的概括與八數(shù)碼問題

搜索是如何利用知識找到問題的解并記錄下求解路線或者求解過程的算法。搜索分為兩種，一種是盲目搜索一種是啟發(fā)式搜索。盲目搜索即在沒有任何提示，或者知識的指導(dǎo)下，按照系統(tǒng)規(guī)定的規(guī)則對知識庫進行搜索，無論什么問題都采用相同的搜索方式。這種搜索方式雖然適用于所有問題但當(dāng)碰到復(fù)雜的問題時就需要耗費相當(dāng)長的時間，效率較低，因此盲目搜索只適用于解決較為簡單的搜索問題。啟發(fā)式搜索是在盲目搜索的基礎(chǔ)上不斷的增加搜索信息改變搜索方向使問題得到更快的解決，提高搜索解決問題的效率的一種新的搜索方式。

八數(shù)碼問題：在3＊3的棋盤上擺放著八個數(shù)碼1、2、3、4、5、6、7、8有一個地方是空格，我們可以對空格進行上下左右的移動使得八數(shù)碼盤從初始狀態(tài)如圖1轉(zhuǎn)變?yōu)槟繕?biāo)狀態(tài)如圖2所示。

圖1 初始狀態(tài)

圖2 目標(biāo)狀態(tài)

2 盲目搜索

■2.1 寬度優(yōu)先搜索

寬度優(yōu)先搜索策略的核心思想為從初始結(jié)點開始首先判斷初始結(jié)點是否為目標(biāo)結(jié)點如果為目標(biāo)結(jié)點則搜索結(jié)束，若不為目標(biāo)結(jié)點則遍歷該結(jié)點的所有子結(jié)點并同時判斷遍歷的每一個子結(jié)點是否為目標(biāo)結(jié)點。然后依次將每一個子結(jié)點作為初始結(jié)點完成上面的操作，直到找到目標(biāo)結(jié)點。針對八數(shù)碼問題給出寬度優(yōu)先搜索的算法步驟如下：

a.把初始結(jié)點S0放入鏈表1中。

b.如果鏈表1是空表，則沒有解，失敗退出；否則繼續(xù)。

c.把鏈表1中的第一個結(jié)點（記為結(jié)點n）移出，并放入 鏈表2中。

d.判斷結(jié)點n是否為目標(biāo)結(jié)點，如果是，則求解結(jié)束，并用回溯法找出解的路徑，退出；否則繼續(xù)執(zhí)行e。

e.若結(jié)點n 不可擴展，轉(zhuǎn)b；否則繼續(xù)執(zhí)行e。

f.對結(jié)點n進行擴展，將它的所有子結(jié)點放入鏈表1的末端，并為這些子結(jié)點設(shè)置指向父結(jié)點n的指針，然后轉(zhuǎn)b。

以下是寬度優(yōu)先搜索策略解決八數(shù)碼問題的搜索樹如圖3所示。

圖3中每個方塊代表一個狀態(tài)，每個狀態(tài)左邊的數(shù)字為此狀態(tài)的編碼，開始結(jié)點為S0首先對判斷S0是否為目標(biāo)結(jié)點，若S0為目標(biāo)結(jié)點則該搜索過程結(jié)束，若不是則拓展S0，對于此問題來說S0并不是目標(biāo)狀態(tài)，于是我們拓展S0并且判斷S0的子結(jié)點是否為目標(biāo)結(jié)點以此作為循環(huán)直到每一層的結(jié)點擴展結(jié)束再進行下一層的判斷，直到找到目標(biāo)結(jié)點。目標(biāo)結(jié)點為Sg經(jīng)過27個結(jié)點最終到達目標(biāo)結(jié)點可以看出其路徑為：S0，3 , 8 , 16 , Sg。

圖3 寬度優(yōu)先搜索樹

由圖3可以看出寬度優(yōu)先搜索解決八數(shù)碼問題時會產(chǎn)生大量的無用結(jié)點。但寬度優(yōu)先搜索總能找到最后的解。

■2.2 深度優(yōu)先搜索

深度優(yōu)先搜索的核心思想是從初始結(jié)點出發(fā)，擴展順序總是先擴展最新產(chǎn)生的結(jié)點，這樣搜索順序就會順著一條路徑一直延伸下去，直到最后的結(jié)點不能產(chǎn)生新的結(jié)點或找到目標(biāo)結(jié)點為止。當(dāng)搜索到不能產(chǎn)生新的結(jié)點且還是無法找到目標(biāo)結(jié)點時，就會沿著最終結(jié)點的反方向?qū)ふ夷軌虍a(chǎn)生新的結(jié)點的結(jié)點并且搜索新產(chǎn)生的結(jié)點，就這樣執(zhí)行以上步驟，直到找到目標(biāo)結(jié)點或者再無可擴展結(jié)點為止。針對八數(shù)碼問題給出深度優(yōu)先搜索的算法步驟：

a.將初始結(jié)點S0放入鏈表1。

b.如果鏈表1為空，則問題無解并退出程序。

c.在鏈表1中將第一個結(jié)點（結(jié)點n）移出，放入已經(jīng)擴展結(jié)點鏈表2中。

d.考察結(jié)點n是否為目標(biāo)結(jié)點，如果是，即找到問題的解，并回溯法求解的路徑然后退出。

e.若結(jié)點n不可再擴展，則轉(zhuǎn)b。

f.擴展結(jié)點n，將其子結(jié)點放到鏈表1的前端，并為其設(shè)置指向結(jié)點n的指針，之后轉(zhuǎn)b。由于過程詳細(xì)此處不再展示搜索樹。

深度優(yōu)先搜索容易陷入某個錯誤的方向，在錯誤的分支上一去不返，造成大量的結(jié)點浪費，而且深度優(yōu)先搜索并不能保證找到目標(biāo)狀態(tài)，容易陷入一個死循環(huán)。

3 啟發(fā)式搜索

根據(jù)以上盲目搜索中它們進行的搜索路線是事先確定好的，沒有根據(jù)被求解問題的任何有利信息。沒有考慮現(xiàn)在正在搜索的路徑是否更有利于接近目標(biāo)結(jié)點。所以啟發(fā)式搜索正是彌補了盲目搜索的這一劣勢，啟發(fā)式搜索在搜索過程中關(guān)鍵是如何確定哪一個是下一個要被判斷的結(jié)點，在確定下一個需要被判斷的結(jié)點時要利用有關(guān)結(jié)點能夠做出判斷的信息，計算出結(jié)點的重要性，并且要選擇重要性高的結(jié)點來拓展。因此啟發(fā)式優(yōu)先搜索應(yīng)定義一個估價函數(shù)f(x)，我們以八數(shù)碼問題為例f(x)由兩部分組成一部分是該結(jié)點所在層數(shù)計為m(x)，另一部分是該結(jié)點與目標(biāo)結(jié)點中數(shù)字所處不同位置的個數(shù)計為n(x)。所以估價函數(shù)可寫作：f(x)=m(x)+n(x)。例如當(dāng)S0結(jié)點位于第0層時它的m(x)=0,與目標(biāo)結(jié)點數(shù)字不相符的地方有3處所以n(x)=3那么f(x)=3。由f(x)的定義可知，f(x)越小說明距離目標(biāo)結(jié)點越近，所以我們應(yīng)首先考察和拓展f(x)值最小的點。針對八數(shù)碼問題給出啟發(fā)式搜索算法步驟：

a.將初始結(jié)點S0放入鏈表1，并計算f(S0)的值。

b.如果鏈表1為空鏈表，則問題無解并退出。

c.將鏈表1中第一個結(jié)點記為結(jié)點n移入鏈表2中。

d.考察結(jié)點n是否為目標(biāo)結(jié)點，如果是，則求得問題的解并退出；否則轉(zhuǎn)e。

e.若結(jié)點n可擴展，轉(zhuǎn)f；否則轉(zhuǎn)b。

f.對結(jié)點n進行擴展之后，并計算所有子結(jié)點的估價函數(shù)f(x)的值，并為每個子結(jié)點設(shè)置指向n的指針。

g.把這些子結(jié)點都送入鏈表1，然后對鏈表1中的全部結(jié)點按照估價值從小到大的順序進行排序。

h.轉(zhuǎn)b。

根據(jù)這些規(guī)則可以得到算法流程圖如圖4所示。

圖4 啟發(fā)式搜索算法流程圖

根據(jù)此算法得出搜索樹如圖5所示。

圖5中每一個方塊代表一個狀態(tài)，每個狀態(tài)左邊的數(shù)字代表估價函數(shù)的值。首先判斷S0是否為目標(biāo)結(jié)點，若S0為目標(biāo)結(jié)點則搜索過程結(jié)束，若S0不為目標(biāo)結(jié)點，則拓展S0并計算所有子結(jié)點的代價函數(shù)，取其中代價函數(shù)最小的結(jié)點進行判斷，若不是目標(biāo)結(jié)點則擴展此結(jié)點，并計算其子結(jié)點的代價函數(shù)，這時再次尋找沒有判斷過的代價函數(shù)最小的結(jié)點直到找到目標(biāo)結(jié)點。由圖5可知搜索的結(jié)點數(shù)目與盲目搜索相比減少了很多，經(jīng)過搜索13個結(jié)點找到了目標(biāo)結(jié)點并且面對更加復(fù)雜的問題時啟發(fā)式搜索的效率會明顯增加。

圖5 啟發(fā)式搜索

4 總結(jié)

現(xiàn)實中的問題都是通過一步一步求解得到答案的，所以人工智能也是仿造人類一步一步搜索出最終答案。盲目搜索在不加入任何特征信息時進行搜索，這種搜索類似于沒有方法但知道答案的范圍將答案帶入問題去匹配，只有少數(shù)問題能夠比較幸運的快速算出，大多數(shù)較為復(fù)雜的問題在進行搜索時就會耗費大量內(nèi)存。啟發(fā)式搜索就像得到了解決問題的方案，每走一步都是距離目標(biāo)更近的一步，對于復(fù)雜的問題往往能快速找到解決方案。因此掌握啟發(fā)式搜索技術(shù)對于研究人工智能領(lǐng)域有著重要意義。