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