人工智能搜索

人工智能搜索技術(shù)初探【摘要】本文簡要概述了人工智能搜索技術(shù)，分別對盲目搜索和啟發(fā)式搜索做了闡述，并且用深度優(yōu)先搜索初步分析了野人和牧師過河問題，用A*算法初步分析了九宮圖問題?！娟P(guān)鍵詞】搜索技術(shù)；盲目搜索；啟發(fā)式搜索；寬度優(yōu)先搜索；深度優(yōu)先搜索；野人與牧師；A*算法；九宮圖；搜索技術(shù)是人工智能的基本技術(shù)之一，在人工智能各應用領(lǐng)域中被廣泛地使用。早期的人工智能程序與搜索技術(shù)聯(lián)系更為密切，幾乎所有早期的人工智能程序都是以搜索技術(shù)為基礎(chǔ)的。例如，A.Newell和H.A.Simon等人編寫的LT(LogicTheorist)程序?，F(xiàn)在，搜索技術(shù)滲透在各種人工智能系統(tǒng)中，可以說沒有哪一種人工智能系統(tǒng)應用不到搜索方法。在專家系統(tǒng)、自然語言理解、自動程序設(shè)計、模式識別、機器人學、信息檢索和博弈等領(lǐng)域都廣泛使用搜索技術(shù)。人工智能問題，廣義地說都可以看作是一個問題求解過程，因此問題求解是人工智能的核心問題，通常是通過在某個可能的解答空間中尋找一個解來進行的。在問題求解過程中，人們所面臨的大多數(shù)顯示問題往往沒有確定性的算法，通常需要用搜索算法來解決。目標和達到目標的一組方法稱為問題，搜索就是探究這些方法能夠做什么的過程。問題求解一般需要考慮兩個基本問題：首先是使用合適的狀態(tài)空間表示問題，其次是測試該狀態(tài)空間中目標狀態(tài)是否出現(xiàn)。一般搜索可以根據(jù)是否使用啟發(fā)式信息分為盲目搜索和啟發(fā)式搜索。一：盲目搜索盲目搜索又叫非啟發(fā)式搜索，是一種無信息搜索，一般只使用求解比較簡單的問題。寬度優(yōu)先搜索、深度優(yōu)先搜索、分支有限搜索、迭代加深搜索都是盲目搜索。.寬度優(yōu)先搜索寬度優(yōu)先搜索算法(又稱廣度優(yōu)先搜索算法)是最簡單的圖的搜索算法之一，這一算法也是很多重要的圖的算法的原型。Dijksta單源最短路徑算法和Prim最小生成樹算法都采用了與寬度優(yōu)先搜索類似的思想。寬度優(yōu)先搜索的核心思想是：從初始結(jié)點開始，應用算符生成第一層結(jié)點，檢查目標結(jié)點是否在這些后繼結(jié)點中，若沒有，再用產(chǎn)生式規(guī)則將所有第一層的結(jié)點逐一擴展，得到第二層結(jié)點，并逐一檢查第二層結(jié)點中是否包含目標結(jié)點。若沒有，再用算符逐一擴展第二層所有結(jié)點……，如此依次擴展，直到發(fā)現(xiàn)目標結(jié)點為止。寬度優(yōu)先搜索基本算法如下：list[1]:=source;｛加入初始結(jié)點，list為待擴展結(jié)點的表｝head:=0;｛隊首指針｝foot:=1;｛隊尾指針｝REPEAThead:二head+1;FORx:=1to規(guī)則數(shù)DOBEGIN根據(jù)規(guī)則產(chǎn)生新結(jié)點nw;IFnot_appear(nw,list)THEN｛若新結(jié)點隊列中不存在，則加到隊尾｝BEGINfoot:二foot+1;list[foot]:=nw;list[foot].father:二head;IF^^。。H二目標結(jié)點THEN輸出；END；END；UNTILhead>foot;｛隊列為空表明再無結(jié)點可擴展｝.深度優(yōu)先搜索深度優(yōu)先搜索所遵循的搜索策略是盡可能“深”地搜索圖。在深度優(yōu)先搜索中，對于最新發(fā)現(xiàn)的結(jié)點，如果它還有以此為起點而未搜過的邊，就沿著邊繼續(xù)搜索下去。當結(jié)點v的所有邊都已被探尋過，搜索將回溯到發(fā)現(xiàn)結(jié)點v有那條邊的始結(jié)點。這一過程一直進行到已發(fā)現(xiàn)從源結(jié)點可達的所有結(jié)點為止。如果還存在未被發(fā)現(xiàn)的結(jié)點，則選擇其中一個作為源結(jié)點并重復以上過程，整個過程反復進行直到所有結(jié)點都被發(fā)現(xiàn)為止。深度優(yōu)先搜索基本算法如下｛遞歸算法｝:ProcedureDepth-first-searchBegin把初始結(jié)點壓入棧，并設(shè)置棧頂指針；While棧不空doBegin彈出棧頂元素；if棧頂元素=goal,成功返回并結(jié)束；Else以任何次序把棧頂元素的子女壓入棧中；EndWhileEnd例1.野人過河問題野人過河問題屬于人工智能學科中的一個經(jīng)典問題，問題描述如下：有三個牧師和三個野人過河，只有一條能裝下兩個人的船，在河的任何一方或者船上，如果野人的人數(shù)大于牧師的人數(shù)，那么牧師就會有危險.你能不能找出一種安全的渡河方法呢？算法分析先來看看問題的初始狀態(tài)和目標狀態(tài)，假設(shè)和分為甲岸和乙岸：初始狀態(tài)：甲岸，3野人，3牧師；乙岸，0野人，0牧師；船停在甲岸，船上有0個人；目標狀態(tài)：甲岸，0野人，0牧師；乙岸，3野人，3牧師；船停在乙岸，船上有0個人。整個問題就抽象成了怎樣從初始狀態(tài)經(jīng)中間的一系列狀態(tài)達到目標狀態(tài)。問題狀態(tài)的改變是通過劃船渡河來引發(fā)的，所以合理的渡河操作就成了通常所說的算符，根據(jù)題目要求，可以得出以下5個算符(按照渡船方向的不同，也可以理解為10個算符)：渡1野人、渡1牧師、渡1野人1牧師、渡2野人、渡2牧師算符知道以后，剩下的核心問題就是搜索方法了，本題采用深度優(yōu)先搜索，通過一個巾ndnext(…)函數(shù)找出下一步可以進行的渡河操作中的最優(yōu)操作，如果沒有找到則返回其父節(jié)點，看看是否有其它兄弟節(jié)點可以擴展，然后用process(…)函數(shù)遞規(guī)調(diào)用匯ndnext(…)，一級一級的向后擴展。搜索中采用的一些規(guī)則如下：1）渡船優(yōu)先規(guī)則：甲岸一次運走的人越多越好（即甲岸運多人優(yōu)先）同時野人優(yōu)先運走；乙岸一次運走的人越少越好（即乙岸運少人優(yōu)先），同時牧師優(yōu)先運走；2）不能重復上次渡船操作（通過鏈表中前一操作比較），避免進入死循環(huán)；3）任何時候河兩邊的野人和牧師數(shù)均分別大于等于0且小于等于3；4）由于只是找出最優(yōu)解，所以當找到某一算符（當前最優(yōu)先的）滿足操作條件后，不再搜索其兄弟節(jié)點，而是直接載入鏈表；5）若擴展某節(jié)點a的時候，沒有找到合適的子節(jié)點，則從鏈表中返回節(jié)點a的父節(jié)點b，從上次已經(jīng)選擇了的算符之后的算符中找最優(yōu)先的算符繼續(xù)擴展b。算法框圖如下：圖-1二、啟發(fā)式搜索所謂啟發(fā)式搜索就是利用一個評估函數(shù)對狀態(tài)空間中的搜索中的每一個搜索位置的價值進行評估，決定先嘗試哪一個方案，從而可省略大量無用的搜索路徑，極大的優(yōu)化普通的廣度優(yōu)先搜索。與普通的廣度優(yōu)先搜索不同的是，啟發(fā)式搜索會優(yōu)先順著有啟發(fā)性和具有特定信息的結(jié)點搜索下去，這些結(jié)點可能是達到目標狀態(tài)空間的最好路徑。其核心思想是通過引人一個啟發(fā)式函數(shù)(或稱為評估函數(shù))，為了有利于回溯到早期路徑的搜索，可以為評估函數(shù)增加一個深度因子，這樣，定義的評估函數(shù)就是：f(n)=g(n)+h(n);其中f(n)是節(jié)點n的估價函數(shù)，g(n)二搜索圖中結(jié)點n的深度，是從開始結(jié)點到n結(jié)點的最短路徑長度;h(n)二不正確位置的數(shù)碼個數(shù)(和目標狀態(tài)相比)，是從n到目標節(jié)點最佳路徑的估計代價。在這里主要是h(n)體現(xiàn)了搜索的啟發(fā)信息，因為g(n)是已知的，或者說g(n)代表了搜索廣度的優(yōu)先趨勢。當h(n)遠大于g(n)時，可以省略g(n)而達到提高搜索效率的目的。啟發(fā)式搜索其實有很多的算法，比如：局部擇優(yōu)搜索法、最好優(yōu)先搜索法等等。當然A*也是。這些算法都使用了啟發(fā)函數(shù)，但在具體的選取最佳搜索節(jié)點時的策略不同。象局部擇優(yōu)搜索法，就是在搜索的過程中選取'最佳節(jié)點”后舍棄其他的兄弟節(jié)點，父親節(jié)點，而一直得搜索下去。這種搜索的結(jié)果很明顯，由于舍棄了其他的節(jié)點，可能也把最好的節(jié)點都舍棄了，因為求解的最佳節(jié)點只是在該階段的最佳并不一定是全局的最佳。最好優(yōu)先就好多了，在搜索時，沒有舍棄節(jié)點(除非該節(jié)點是死節(jié)點)，在每一步的估價中都把當前的節(jié)點和以前的節(jié)點的估價值比較得到一個“最佳的節(jié)點”。這樣可以有效的防止“最佳節(jié)點”的丟失。那么A*算法又是一種什么樣的算法呢？其實A*算法也是一種最好優(yōu)先的算法。只不過要加上一些約束條件罷了。由于在一些問題求解時，我們希望能夠求解出狀態(tài)空間搜索的最短路徑，也就是用最快的方法求解問題，A*就是干這種事情的！我們先下個定義，如果一個估價函數(shù)可以找出最短的路徑，我們稱之為可采納性。A*算法是一個可采納的最好優(yōu)先算法。A*算法的估價函數(shù)可表示為：f'(n)=g'(n)+h'(n)這里，f'(n)是估價函數(shù)，g'(n)是起點到終點的最短路徑值，h'(n)是n到目標的最斷路經(jīng)的啟發(fā)值。由于這個f'(n)其實是無法預先知道的，所以我們用前面的估價函數(shù)f(n)做近似。g(n)代替g'(n)，但g(n)>=g'(n)才可(大多數(shù)情況下都是滿足的，可以不用考慮)，h(n)代替片(川，但h(n)<=h'(n)才可(這一點特別的重要)?？梢宰C明應用這樣的估價函數(shù)是可以找到最短路徑的，也就是可采納的。舉一個例子，其實廣度優(yōu)先算法就是A*算法的特例。其中g(shù)(n)是節(jié)點所在的層數(shù)，h(n)=0，這種h(n)肯定小于h'(n)，所以由前述可知廣度優(yōu)先算法是一種可采納的。實際也是。當然它是一種最臭的A*算法。再說一個問題，就是有關(guān)h(n)啟發(fā)函數(shù)的信息性。h(n)的信息性通俗點說其實就是在估計一個節(jié)點的值時的約束條件，如果信息越多或約束條件越多則排除的節(jié)點就越多，估價函數(shù)越好或說這個算法越好。這就是為什么廣度優(yōu)先算法的那么臭的原因了，誰叫它的h(n)=0，一點啟發(fā)信息都沒有。但在游戲開發(fā)中由于實時性的問題，h(n)的信息越多，它的計算量就越大，耗費的時間就越多。就應該適當?shù)臏p小h(n)的信息。A*算法：A*(A-Star)算法是一種靜態(tài)路網(wǎng)中求解最短路最有效的方法。公式表示為：f(n)=g(n)+h(n)其中f(n)是節(jié)點n從初始點到目標點的估價函數(shù)，g(n)是在狀態(tài)空間中從初始節(jié)點到n節(jié)點的實際代價，h(n)是從n到目標節(jié)點最佳路徑的估計代價。保證找到最短路徑(最優(yōu)解的)條件，關(guān)鍵在于估價函數(shù)h(n)的選?。汗纼r值h(n)<=n到目標節(jié)點的距離實際值，這種情況下，搜索的點數(shù)多，搜索范圍大，效率低。但能得到最優(yōu)解。如果估價值>實際值，搜索的點數(shù)少，搜索范圍小，效率高，但不能保證得到最優(yōu)解。估價值與實際值越接近，估價函數(shù)取得就越好。例如對于幾何路網(wǎng)來說，可以取兩節(jié)點間歐幾理德距離(直線距離)做為估價值，即』g(n)+sqrt((dx-nx)*(dx-nx)+(dy-ny)*(dy-ny))；這樣估價函數(shù)f在g值一定的情況下，會或多或少的受估價值h的制約，節(jié)點距目標點近，h值小，f值相對就小，能保證最短路的搜索向終點的方向進行。明顯優(yōu)于Dijstra算法的毫無無方向的向四周搜索。主要搜索過程：創(chuàng)建兩個表，OPEN表保存所有已生成而未考察的節(jié)點，CLOSED表中記錄已訪問過的節(jié)點。遍歷當前節(jié)點的各個節(jié)點，將n節(jié)點放入CLOSE中，取n節(jié)點的子節(jié)點X,->算X的估價值->While(OPEN!=NULL){從OPEN表中取估價值f最小的節(jié)點n;if(n節(jié)點==目標節(jié)點)break;else{if（XinOPEN）比較兩個X的估價值f//注意是同一個節(jié)點的兩個不同路徑的估價值if（X的估價值小于OPEN表的估價值）更新OPEN表中的估價值;//取最小路徑的估價值if（XinCLOSE）比較兩個X的估價值//注意是同一個節(jié)點的兩個不同路徑的估價值if（X的估價值小于CLOSE表的估價值）更新CLOSE表中的估價值；把X節(jié)點放入OPEN//取最小路徑的估價值if（Xnotinboth）求X的估價值；并將X插入OPEN表中;//還沒有排序）將n節(jié)點插入CLOSE表中；按照估價值將OPEN表中的節(jié)點排序;//實際上是比較OPEN表內(nèi)節(jié)點f的大小，從最小路徑的節(jié)點向下進行。例2.九宮圖問題九宮圖問題是指在一個3X3的方陣中有8個數(shù)碼，初始狀態(tài)是這8個數(shù)碼無序或部分無序，是否能找到一個數(shù)碼移動序列使初始的無序數(shù)碼轉(zhuǎn)變?yōu)橐恍┨厥獾呐帕校_到目標狀態(tài)。這種問題的含義是給定一種初始布局（稱初始狀態(tài)）和一個目標布局（稱目標狀態(tài)），問如何移動數(shù)碼，實現(xiàn)從初始狀態(tài)到目標狀態(tài)的轉(zhuǎn)變。問題的解答其實就是尋找一個動作序列。在這個問題中，一個明顯的目標狀態(tài)描述是一個3X3的方陣，方陣的每個單元中包含1-8之間的一個數(shù)字或一個代表空格的符號。不同狀態(tài)間的轉(zhuǎn)化就是把一個數(shù)碼移到與之相鄰的空的單元中。為了較簡便地處理，一個有效的方法是每次考查空格的移動：空格上移、空格下移、空格左移、空格右移。這個問題當然可以用窮舉的方法進行盲目搜索，但由于生成的搜索樹存儲空間大，且搜索效率不高，因此常使用啟發(fā)式搜索以控制搜索路徑的選取，從而達到減少搜索寬度、提高求解效率的目的。以下具體分析:有如圖-2所示的九宮圖問題:有如圖-2所示的九宮圖問題:圖-2現(xiàn)在采用估計函數(shù)為：f(n)=d(n)+w(n)