第七章搜索策略

搜索是人工智能中的一個基本問題，是推理不可分割的一部分，它直接關系到智能系統(tǒng)的性能與運行效率，因而尼爾遜把它列入人工智能研究的四個核心問題之一。第一頁，共一百五十二頁。1第七章搜索策略

7.1基本概念

7.2狀態(tài)空間的搜索技術7.3與/或圖的搜索策略7.4博弈樹搜索第二頁，共一百五十二頁。2第七章搜索策略7.1基本概念7.2狀態(tài)空間的搜索技術7.3與/或圖的搜索策略7.4博弈樹搜索7.1.1什么是搜索7.1.2狀態(tài)空間表示法

7.1.3與/或圖表示法第三頁，共一百五十二頁。3第七章搜索策略根據問題的實際情況不斷尋找可利用的知識，從而構造一條代價較少的推理路線，從而使問題圓滿得到解決的過程稱為搜索。

基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略

7.1.1什么是搜索博弈樹搜索第四頁，共一百五十二頁。4第七章搜索策略搜索分為盲目搜索和啟發(fā)式搜索。

盲目搜索（或稱非啟發(fā)式搜索）是按預定的控制策略進行搜索，在搜索過程中獲得的中間信息不用來改進搜索策略。

啟發(fā)式搜索（或稱非盲目搜索）是在搜索中加入了與問題有關的啟發(fā)性信息，用以指導搜索朝著最有希望的方向前進，加速問題的求解過程并且找到最優(yōu)解。基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第五頁，共一百五十二頁。5第七章搜索策略1、什么是狀態(tài)圖例題7.1設有三個錢幣，其初始狀態(tài)為(反、正、反),欲得的目標狀態(tài)為(正、正、正)或(反、反、反)。

7.1.2狀態(tài)圖表示法反正反反正正正反反初始狀態(tài)目標狀態(tài)基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索問題是允許每次只能且必須翻轉一個錢幣，連翻三次，問能否達到目標狀態(tài)？第六頁，共一百五十二頁。6第七章搜索策略【解】要求解這個問題，可通過引入一個３維變量將問題表示出來。

設３維變量為：

Q=[q1,q2.q3]

其中：qi=0表示正，qi=1表示反（i=1,2,3）基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第七頁，共一百五十二頁。7第七章搜索策略共有八種組合：

Q0=(0,0,0)Q1=(0,0,1)Q2=(0,1,0)Q3=(0,1,1)Q4=(1,0,0)Q5=(1,0,1)

Q6=(1,1,0)Q7=(1,1,1)每個組合就視為一個節(jié)點。初始狀態(tài)為Q5，目表狀態(tài)為Q0和Q7

基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第八頁，共一百五十二頁。8第七章搜索策略由圖可得解有7個：

aab,aba,baa,bbb,bcc,cbc,ccb其中：a表示q1的變化，b表示q2的變化，c表示q3的變化。Q0(0,0,0)Q4(1,0,0)(1,1,0)Q6Q1(0,0,1)Q3(0,1,1)(0,1,0)Q2

Q7(1,1,1)Q5(1,0,1)cbaacbbacabc基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第九頁，共一百五十二頁。9第七章搜索策略把這種描述得到的有向圖稱為狀態(tài)（空間）圖。

其中的節(jié)點代表一種格局（或稱為狀態(tài)），而兩節(jié)點之間的連線表示兩節(jié)點之間的聯系，它可視為某種操作、規(guī)則、變換等。在狀態(tài)圖中，從初始節(jié)點到目標節(jié)點的一條路徑是一個解。

7.1.2狀態(tài)圖表示法基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第十頁，共一百五十二頁。10第七章搜索策略2、問題的狀態(tài)空間表示法1)狀態(tài)：描述問題求解過程中任一時刻狀況的數據結構，一般用一組變量的有序組合表示：Sk=(Sk0，Sk1，

…),當給每一個分量以確定的值時，就得到了一個具體的狀態(tài)。2)操作：亦稱算符/算子/運算符。引起狀態(tài)中某些分量發(fā)生變化，從而使問題由一個狀態(tài)變?yōu)榱硪粋€狀態(tài)。基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第十一頁，共一百五十二頁。11第七章搜索策略

3)狀態(tài)空間：由問題的全部狀態(tài)及一切可用算符所構成的集合稱為問題的狀態(tài)空間，一般用一個三元組表示：

(S,F,G)其中S是問題的所有初始狀態(tài)構成的集合；F是算符的集合；G是目標狀態(tài)的集合?；靖拍顮顟B(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第十二頁，共一百五十二頁。12第七章搜索策略例7.2

二階梵塔問題。

設有3個鋼針，在1號鋼針上穿有A、B兩個金片，A小于B，A位于B的上面。要求把這兩個金片全部移到另一根鋼針上，而且規(guī)定每次只能移動一片，任何時刻都不能使B位于A的上面?；靖拍顮顟B(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索123ＢＡ第十三頁，共一百五十二頁。13第七章搜索策略解：設用Sk=(Sk0,Sk1)表示問題的狀態(tài)。其中Sk0表示金片A所在的鋼針號，Sk1表示金片B所在的鋼針號。

全部可能的狀態(tài)有九種：

基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第十四頁，共一百五十二頁。14第七章搜索策略

基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索問題的初始狀態(tài)集合為S={S0}，目標狀態(tài)集合為G={S4，S8}。第十五頁，共一百五十二頁。15第七章搜索策略算符分別用A(i,j)及B(i,j)表示。A(i,j)表示把金片A從第i號針移到第j號針上；B(i,j)表示把金片B從第i號針移到第j號針上。共有12個算符，它們分別是：A(1,2)，A(1,3)，A(2,1)，A(2,3)，A(3,1)，A(3,2)B(1,2)，B(1,3)，B(2,1)，B(2,3)，B(3,1)，B(3,2)

根據9種可能的狀態(tài)和12種算符，可構成二階梵塔問題的狀態(tài)空間圖。另：每個算符都含有“條件”和“動作”（如表7-1）?；靖拍顮顟B(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第十六頁，共一百五十二頁。16第七章搜索策略基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索操作符條件操作A（1，2）A（1，3）A（2，1）A（2，3）A（3，1）A（3，2）B（1，2）B（1，3）B（2，1）B（2，3）B（3，1）B（3，2）sk0=1sk0=1sk0=2sk0=2sk0=3sk0=3sk0=3且sk1=1sk0=2且sk1=1sk0=3且sk1=2sk0=1且sk1=2sk0=2且sk1=3sk0=1且sk1=3sk0=2sk0=3sk0=1sk0=3sk0=1sk0=2sk1=2sk1=3sk1=1sk1=3sk1=1sk1=2表7-1二階梵塔問題的12種操作

第十七頁，共一百五十二頁。17第七章搜索策略

7.1.2狀態(tài)圖表示法3,11,12,33,22,21,31,23,32,1基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索Ａ（２，１）Ａ（１，３）Ａ（３，２）Ｂ（１，２）B（3，１）Ａ（3，2）第十八頁，共一百五十二頁。18第七章搜索策略狀態(tài)空間圖中，從初始節(jié)點(1,1)到目標節(jié)點(2,2)及(3,3)的任何一條通路都是問題的一個解，其中最短的路徑長度是3，它由3個算符組成，例如A(1,3)，B(1,2)，A(3,2)。

基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第十九頁，共一百五十二頁。19第七章搜索策略由此例可以看出：1)用狀態(tài)空間方法表示問題時，首先必須定義狀態(tài)的描述形式，可把問題的一切狀態(tài)都表示出來。

其次，還要定義一組算符，通過使用算符可把問題的一種狀態(tài)轉變?yōu)榱硪环N狀態(tài)?；靖拍顮顟B(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第二十頁，共一百五十二頁。20第七章搜索策略2)問題的求解過程是一個不斷把算符作用于狀態(tài)的過程。如果在使用某個算符后得到的新狀態(tài)是目標狀態(tài)，就得到了問題的一個解。這個解是從初始狀態(tài)到目標狀態(tài)所用算符構成一個的序列?；靖拍顮顟B(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第二十一頁，共一百五十二頁。21第七章搜索策略3)問題從初始狀態(tài)到目標狀態(tài)可能得到多個解，我們把使用算符最少的解稱為最優(yōu)解。評價解的優(yōu)劣不僅要看使用算符的數量，還要看使用算符所付出的代價。4)對任何一個狀態(tài)，可使用的算符可能不止一個，這樣由一個狀態(tài)所生成的后繼狀態(tài)就可能有多個?；靖拍顮顟B(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第二十二頁，共一百五十二頁。22第七章搜索策略

當對這些后繼狀態(tài)使用算符生成更進一步的狀態(tài)時，首先應對哪一個狀態(tài)進行操作呢？這取決于搜索策略，不同搜索策略的操作順序是不相同的，這正是本章要討論的問題?；靖拍顮顟B(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第二十三頁，共一百五十二頁。23第七章搜索策略與/或圖示用于表示問題及其求解過程的又一種形式化方法，通常用于表示比較復雜問題的求解。1、什么是與/或圖例如要證明兩個四角形相等，可先分別將其分成兩個三角形，在證三角形相等的基礎上再證四角形相等。2、對于一個復雜問題，直接求解往往比較困難。此時，可通過下面方法進行簡化：

7.1.3與/或圖表示法基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第二十四頁，共一百五十二頁。24第七章搜索策略1)分解把一個復雜問題分解為若干個較為簡單的子問題，每個子問題又可繼續(xù)分解為若干更為簡單的子問題，重復此過程，直到不需要再分解或者不能再分解為之。然后對每個子問題分別進行求解，最后把各子問題的解復合起來就得到了原問題的解。例如：

P1

，P2

，P3

是問題P的三個子問題，只有當這三個子問題有解時，問題P才有解，稱P1

，P2

，P3之間存在“與”關系；稱節(jié)點P為“與”節(jié)點；基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第二十五頁，共一百五十二頁。25由P，P1

，P2

，P3所構成的圖稱為“與”樹。在圖中，為了標明某個節(jié)點是“與”節(jié)點，通常用一條弧把各條邊連接起來。

7.1.3與/或圖表示法PP2P3P1第七章搜索策略基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第二十六頁，共一百五十二頁。262）等價變換

對于一個復雜問題，除了可用“分解”方法進行分解外，還可利用同構或同態(tài)的等價變換，把它變換為若干個較容易求解的新問題。若新問題中有一個可求解，則就得到了原問題的解。問題的等價變換過程，也可用一個圖表示出來，稱為“或”樹。PP2P3P1第七章搜索策略基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第二十七頁，共一百五十二頁。273)“與/或”樹：

上述兩種方法也可結合起來使用，此時的圖稱為“與/或”樹。其中既有“與”節(jié)點，又有“或”節(jié)點。注意：狀態(tài)圖是與/或圖的特殊形式，即與/或圖中既有與關系又有或關系，而狀態(tài)圖只有或關系。把一個問題經“分解”得到的子問題以及經“變換”得到的新問題統(tǒng)稱為子問題；把“與”樹及“或”樹統(tǒng)稱為“與/或”樹；把子問題所對應的節(jié)點稱為子節(jié)點。第七章搜索策略基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第二十八頁，共一百五十二頁。283、基本概念：1)根節(jié)點：無父節(jié)點的節(jié)點，為初始節(jié)點，對應初始問題下的描述；2)葉節(jié)點：無子節(jié)點的節(jié)點，亦稱端節(jié)點；3)終止節(jié)點：有解的葉節(jié)點，對應本原問題。即終止節(jié)點一定是端節(jié)點，但端節(jié)點不一定是終止節(jié)點。第七章搜索策略基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第二十九頁，共一百五十二頁。294)可解節(jié)點：滿足下列條件之一者：它是一個終止節(jié)點。它是一個“或”節(jié)點，且其子節(jié)點中至少有一個是可解節(jié)點。③它是一個“與”節(jié)點，且其子節(jié)點全部是可解節(jié)點。5)不可解節(jié)點：關于可解節(jié)點的三個條件全部不滿足的節(jié)點。6)解樹：由可解節(jié)點所構成，并且由這些可解節(jié)點可推出初始節(jié)點（它對于原始問題）為可解節(jié)點的子樹稱為解樹。第七章搜索策略基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第三十頁，共一百五十二頁。30例7.3利用與/或圖的方法二階梵塔問題如下:根據例7.2的討論，初始狀態(tài)為:

P：({S0}，F，{S4，

S8})而P可等價變換為兩個彼此獨立的子問題：

P1：({S0}，F，{S4})P2：({S0}，F，{

S8})

任何一個子問題得解，P問題就有解，即：

P=P1

∨P2而P1

和P2又可進一步分解為若干個相關的子問題，第七章搜索策略基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第三十一頁，共一百五十二頁。31例如在P1問題中引入關鍵狀態(tài)S7后，P1被分解為兩個子問題的與：

P11：({S0}，F，{S7}) P12：({S7}，{A(3，2)}，{S4})

P12是本原問題，無須再分解；

P11中再引入關鍵狀態(tài)S6后，又可以分解為兩個子問題的與：

P111：({S0}，{A(1，3)}，{S6})本原問題 P112：({S6}，{B(1，2)}，{S7})本原問題第七章搜索策略基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第三十二頁，共一百五十二頁。32至此P1已得解：P1=P111∧P112∧P12類似P2可解得：P2=P211∧P212∧P22，其中：

P211：（{S0}，{A（1，2）}，{S3}）（本原問題） P212：（{S3}，{B（1，3）}，{S5}）（本原問題） P22：（{S5}，{A（2，3）}，{S8}）（本原問題）

這個轉化過程可以用一個與/或圖來表示。由于該與/或圖的每一個葉節(jié)點都是一個合法操作可以實現的本原問題，故P問題有解，且有兩個解。第七章搜索策略基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第三十三頁，共一百五十二頁。33與/或圖的方法二階梵塔問題：第七章搜索策略PP111P2P1P11P12P212P22P211P21P112第三十四頁，共一百五十二頁。34課堂練習以與/或圖的方法表示例7-1的錢幣翻轉問題。第三十五頁，共一百五十二頁。35課堂練習參考答案

以與/或圖的方法表示例7-1的錢幣翻轉問題。解:原始問題為： P: (Q5，F，{Q0，Q7})對P等價變換（即“或”）后為: P1: (Q5，F，Q0) P2: (Q5，F，Q7)因為，對P1無解，而P2有7個解，即aab，aba，baa，bbb，bcc，cbc，ccb.第三十六頁，共一百五十二頁。36對解1(aab)可得(分解,即“與”) P21: (Q5,F,Q5) P22: (Q5,b,Q7)而對P21又可分解（即“與”)得 P211: (Q5,a,Q1) P212: (Q1,a,Q5)同理對解2(aba)可得 P23: (Q5,F,Q3) P24: (Q3,a,Q7)而對P23又可分解（即“與”)得 P231: (Q5,a,Q1) P232: (Q1,b,Q3)第三十七頁，共一百五十二頁。37對解3(baa)可得 P25: (Q5,F,Q3) P26: (Q3,a,Q7)而對P25又可分解（即“與”)得 P251: (Q5,a,Q7) P252: (Q1,a,Q3)對解4(bbb)可得 P27: (Q5,F,Q5) P28: (Q5,b,Q7)而對P27又可分解（即“與”)得 P271: (Q5,b,Q7) P272: (Q7,b,Q5)第三十八頁，共一百五十二頁。38對解5(bcc)可得 P29: (Q5,F,Q6) P30: (Q6,c,Q7)而對P29又可分解（即“與”)得 P291: (Q5,b,Q7) P292: (Q7,c,Q6)對解6(cbc)可得 P31: (Q5,F,Q6) P32: (Q6,c,Q7)而對P31又可分解（即“與”)得 P311: (Q5,c,Q4) P312: (Q4,b,Q6)第三十九頁，共一百五十二頁。39對解7(ccb)可得 P33: (Q5,F,Q5) P34: (Q5,b,Q7)而對P33又可分解（即“與”)得 P331: (Q5,c,Q4) P332: (Q4,c,Q5)第四十頁，共一百五十二頁。40

PP2P1P26P21P24P22P25P23……P211P212P231P232……第四十一頁，共一百五十二頁。41第七章搜索策略7.1基本概念7.2狀態(tài)空間的搜索技術7.3與/或圖的搜索策略7.4博弈樹搜索7.2.1圖搜索的基本概念7.2.2寬度優(yōu)先搜索7.2.3深度優(yōu)先搜索7.2.4有限深度優(yōu)先搜索7.2.5啟發(fā)式搜索第四十二頁，共一百五十二頁。42第七章搜索策略1、顯式圖與隱式圖為了求解問題，需要把有關的知識存儲在計算機的知識庫中，有以下兩種存儲方式。1)顯式存儲把與問題有關的全部狀態(tài)空間圖，即相應的全部有關知識（敘述性知識、過程性知識和控制性知識），都直接存入知識庫，這種存儲方式稱為顯式存儲或顯式圖。

7.2.1圖搜索的基本概念基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第四十三頁，共一百五十二頁。43第七章搜索策略2)隱式存儲只存儲與問題求解有關的部分知識(即部分狀態(tài)空間)，這種存儲方式稱為隱式存儲。在求解過程中，由初始狀態(tài)出發(fā)，運用相應的知識，逐步生成所需的部分狀態(tài)空間圖，通過搜索推理，逐步轉移到要求的目標狀態(tài)，只需在知識庫中存儲局部狀態(tài)空間圖，這種圖稱為隱式圖。

為了節(jié)約計算機的存儲容量，提高搜索推理效率，通常采用隱式存儲方式，進行隱式圖搜索推理?；靖拍顮顟B(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第四十四頁，共一百五十二頁。44第七章搜索策略2、圖搜索的基本思想

圖搜索就是一種在圖中尋找路徑的方法。這種尋找過程從圖中的初始節(jié)點開始，至目標節(jié)點為止。其中，初始節(jié)點和目標節(jié)點分別代表產生式系統(tǒng)的初始數據庫和滿足終止條件的數據庫。

基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第四十五頁，共一百五十二頁。45第七章搜索策略

方法是先把問題的初始狀態(tài)作為當前狀態(tài)，選擇適用的算符對其進行操作，生成一組子狀態(tài)，檢查目標狀態(tài)是否在其中出現。

若出現，則搜索成功，找到了問題的解；

若不出現，則按某種搜索策略從已生成的狀態(tài)中再選一個狀態(tài)作為當前狀態(tài)。

重復上述過程，直到目標狀態(tài)出現或者不再有可供操作的狀態(tài)及算符時為止?；靖拍顮顟B(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第四十六頁，共一百五十二頁。46第七章搜索策略3、圖搜索的一般過程圖搜索的一般搜索過程。它是由尼爾遜（N.J.Nilsson）提出的一個圖搜索過程GRAPHSEARCH，它是表達能力很強的一個搜索策略框架。在此過程中要用到OPEN表和CLOSED表?；靖拍顮顟B(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第四十七頁，共一百五十二頁。47第七章搜索策略

OPEN表用于存放剛生成的節(jié)點，這些節(jié)點將作為以后待考察的對象。OPEN表是一個“有進有出”的動態(tài)數據結構。

節(jié)點進入OPEN表的排列順序，也是出表的順序。而節(jié)點進入OPEN表的排列順序是由搜索策略決定；基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第四十八頁，共一百五十二頁。48第七章搜索策略CLOSED表用于存放將要擴展或者已經擴展的節(jié)點，這些節(jié)點記錄著求解中的信息。CLOSED表是一個“有進無出”的動態(tài)數據結構，當前節(jié)點進入CLOSED表的最后。

OPEN表和CLOSED表的結構如下所示。節(jié)點父節(jié)點編號節(jié)點父節(jié)點OPEN表CLOSED表基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第四十九頁，共一百五十二頁。49第七章搜索策略

寬度優(yōu)先搜索(Breadth-FirstSearch)又稱為廣度優(yōu)先搜索。1、寬度優(yōu)先搜索的基本思想

寬度優(yōu)先搜索是指從初始節(jié)點S0開始，向下逐層搜索。

在n層節(jié)點未搜索完之前，不進入n+1層搜索。

同層節(jié)點的搜索次序可以任意。

7.2.2寬度優(yōu)先搜索基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第五十頁，共一百五十二頁。50第七章搜索策略具體就是：

先按生成規(guī)則生成第一層節(jié)點，在該層全部節(jié)點中沿寬（廣）度進行橫向掃描，檢查目標節(jié)點Sg是否在這些子節(jié)點中。

若沒有，則再將所有第一層節(jié)點逐一擴展，得到第二層節(jié)點，并逐一檢查第二層節(jié)點中是否包含有Sg，如此依次按照先生成、先檢查、先擴展的原則進行下去，直到發(fā)現Sg為止。所以寬度優(yōu)先搜索是完備的?；靖拍顮顟B(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第五十一頁，共一百五十二頁。51第七章搜索策略基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索廣度優(yōu)先搜索的示例第五十二頁，共一百五十二頁。52第七章搜索策略2、寬度優(yōu)先搜索的流程⑴把初始節(jié)點S0放入OPEN表；⑵如果OPEN表為空，則問題無解，失敗并退出。否則往下。⑶把OPEN表中的第一個節(jié)點取出放入CLOSED表中，并按順序冠以編號n；⑷考察節(jié)點n是否為目標節(jié)點。若是，則求得了問題的解，成功并退出。否則往下。⑸若節(jié)點n不可擴展，則轉第⑵步；⑹擴展節(jié)點n，將其子節(jié)點放到OPEN表的尾部，并為每一個子節(jié)點都配置指向父節(jié)點的指針，然后轉第⑵步?；靖拍顮顟B(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第五十三頁，共一百五十二頁。53第七章搜索策略在寬度優(yōu)先搜索下，如果問題有解，OPEN表中必然出現目標節(jié)點Sg，而且算法一定在⑷停止，這表示解已找到。從該目標節(jié)點Sg根據返回指針往回追溯，直到初始節(jié)點S0，所得到的一條路徑就是問題的解。基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第五十四頁，共一百五十二頁。54第七章搜索策略例7.4

重排九宮問題。在3×3的方格棋盤上,分別放置著標有數字1,2,3,4,5,6,7,8的八張紙牌,并留一個空格。要求是：只允許把空格上、下、左、右的紙牌移入空格，而空格移至該紙牌原有的位置。要求尋找從初始狀態(tài)轉移到目標狀態(tài)的最短途徑。如圖(a)初始狀態(tài)(b)目標狀態(tài)283147652384765S0Sg基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第五十五頁，共一百五十二頁。55第七章搜索策略解：用寬度優(yōu)先搜索法，生成規(guī)則為：紙牌移入空格的次序是由空格左邊開始，順時針方向移動，不允許斜方向移動，不允許返回。所生成的搜索樹如P113例7.4圖(圖7-15)所示。由圖可知，從初始狀態(tài)S0轉移到目標狀態(tài)Sg的最短路徑為：

S0→3→8→16→26（Sg）即為重排九宮問題的解?；靖拍顮顟B(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第五十六頁，共一百五十二頁。56第七章搜索策略1、深度優(yōu)先搜索的基本思想

深度優(yōu)先搜索(Depth-FirstSearch)是一種一直向下的搜索策略。它是從初始節(jié)點S0開始,按生成規(guī)則生成下一級各子節(jié)點，檢查是否出現目標節(jié)點Sg；

若未出現，則按“最晚生成的子節(jié)點優(yōu)先擴展”的原則，再生成再下一級的子節(jié)點，再檢查是否出現Sg；若仍未出現，則再沿著最晚生成的子節(jié)點分枝生成子節(jié)點，如此下去，即逐級“縱向”深入搜索。

7.2.3深度優(yōu)先搜索基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第五十七頁，共一百五十二頁。57第七章搜索策略由于一個有解的問題常常含有無窮分枝，深度優(yōu)先搜索過程如果誤入無窮分枝，就不可能找到目標節(jié)點，所以它是不完備的。

與寬度優(yōu)先搜索不同，深度優(yōu)先搜索找到的解也不一定是最佳的。基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第五十八頁，共一百五十二頁。58第七章搜索策略基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索深度優(yōu)先搜索的示例第五十九頁，共一百五十二頁。59第七章搜索策略2、深度優(yōu)先搜索的流程

深度優(yōu)先搜索的搜索過程如下：⑴把初始節(jié)點S0放入OPEN表；⑵如果OPEN表為空，則問題無解，失敗并退出。⑶把OPEN表中的第一個節(jié)點取出放入CLOSED表中，并按順序冠以編號n；⑷考察節(jié)點n是否為目標節(jié)點。若是，則求得了問題的解，成功并退出。⑸若節(jié)點n不可擴展，則轉第⑵步；⑹擴展節(jié)點n，將其子節(jié)點放到OPEN表的首部，并為其配置指向父節(jié)點的指針，然后轉第⑵步。

基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第六十頁，共一百五十二頁。60第七章搜索策略

如果問題有解，且問題樹沒有無窮分枝，則必在OPEN表中出現Sg，過程必將在⑷停止，搜索成功。所以深度優(yōu)先搜索法僅對有限狀態(tài)空間類問題來說具有算法性，但無可采納性。一般說來它僅是一個過程，需要進一步改進。

例7.5：參見P115基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第六十一頁，共一百五十二頁。61第七章搜索策略1、有限深度優(yōu)先搜索的基本思想在深度優(yōu)先搜索法中，若目標節(jié)點Sg恰好處在最晚生成的子節(jié)點分枝樹中，則可以較快地求得問題的解，效率比寬度優(yōu)先搜索法高。但是，若誤陷入無窮分枝，進入死循環(huán)，則搜索過程無法收斂，不能找到目標節(jié)點。

7.2.4有限深度優(yōu)先搜索基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第六十二頁，共一百五十二頁。62第七章搜索策略

為了改進深度優(yōu)先搜索法，以免搜索過程陷入無窮分枝的死循環(huán)，可以引入搜索深度界限（設為dm）。當沿“最晚”分枝縱向搜索，達到深度dm時，尚未出現目標節(jié)點Sg，則返回，對“次晚”分枝進行搜索，如此按有限深度(d≤dm)搜索下去，直到找到目標節(jié)點Sg為止。

基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第六十三頁，共一百五十二頁。63第七章搜索策略因此，若問題有解（在問題樹中存在目標節(jié)點Sg，且處在有限深度范圍內），當所選取的搜索深度限制值（dm）大于或等于目標節(jié)點Sg所處實際深度時，則有界深度優(yōu)先搜索法一定可以找到目標節(jié)點Sg，保證推理過程的收斂性，求得問題的解。

具有完備性基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第六十四頁，共一百五十二頁。64第七章搜索策略基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索有限深度優(yōu)先搜索的示例第六十五頁，共一百五十二頁。65第七章搜索策略2、有限深度優(yōu)先搜索的流程有限深度優(yōu)先搜索的搜索過程如下所示：⑴把初始節(jié)點S0放入OPEN表中，置S0的深度d(S0)=0；⑵如果OPEN表為空，則問題無解，失敗并退出。⑶把OPEN表中的第１個節(jié)點取出放入CLOSED表中，并按順序冠以編號n；⑷考察節(jié)點n是否為目標節(jié)點。若是，則求得了問題的解，成功并退出。⑸如果節(jié)點n的深度d（n）=dm，則轉第⑵步；⑹如果節(jié)點n不可擴展，則轉第⑵步；⑺擴展節(jié)點n，將其子節(jié)點放入OPEN表的首部，并為其配置指向父節(jié)點的指針。然后轉第⑵步?；靖拍顮顟B(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第六十六頁，共一百五十二頁。66第七章搜索策略例7.6：設深度界限dm=4，用有界深度優(yōu)先搜索方法求解圖7-14所示（如下）的重排九宮問題。其搜索樹如圖7-19所示，解的路徑是：

S0→20→25→26→28（Sg）?；靖拍顮顟B(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索283147652384765(a)初始狀態(tài)(b)目標狀態(tài)第六十七頁，共一百五十二頁。67第七章搜索策略1、啟發(fā)式信息前述的各種搜索方法都是非啟發(fā)式搜索。其共同特點是都沒有利用問題本身的特性信息，在決定要被擴展的節(jié)點時，都沒有考慮該節(jié)點在解的路徑上的可能性有多大，它是否有利于問題求解以及求出的解是否為最優(yōu)解等。因此，這些搜索方法都具有較大的盲目性，產生的無用節(jié)點較多，搜索空間較大，效率不高。

7.2.5啟發(fā)式搜索基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第六十八頁，共一百五十二頁。68第七章搜索策略利用與具體問題的解有關的控制性信息來確定下一個要考察的節(jié)點，這種控制性信息稱之為啟發(fā)式信息。

啟發(fā)式搜索中要用到與問題本身的某些特性有關的啟發(fā)性信息，以指導搜索朝著最有希望的方向前進。由于這種搜索針對性較強，因而原則上只需要搜索問題的部分狀態(tài)空間，效率較高?；靖拍顮顟B(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第六十九頁，共一百五十二頁。69第七章搜索策略2、估價函數在啟發(fā)式搜索中，為了選定下一次要考察的節(jié)點，通過設計一個函數來控制搜索方向，這種函數稱為估價函數。

估價函數能夠提供一個評定候選擴展節(jié)點的方法以便確定哪個節(jié)點最有可能在通向目標的最佳路徑上。

估價函數的任務就是估計OPEN表中各節(jié)點的重要程度，決定它們在OPEN表中的次序，使得搜索沿著那些被認為最有希望的區(qū)域擴展。

基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第七十頁，共一百五十二頁。70第七章搜索策略

估價函數是用于估價節(jié)點重要性的實值函數。它定義為從初始節(jié)點經過x節(jié)點到達目標節(jié)點的最小代價路徑的代價估計值。它綜合考慮了兩方面的因素：

已經付出的代價和將要付出的代價?；靖拍顮顟B(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第七十一頁，共一百五十二頁。71第七章搜索策略

其一般形式為：

f（x）=g（x）+h（x）式中：f（x）表示從初始節(jié)點經過x節(jié)點到達目標節(jié)點的總代價,稱為估價函數；g（x）表示從初始節(jié)點到達x節(jié)點已支付的實際代價；h（x）表示從x節(jié)點到達目標節(jié)點將支付的估計代價，稱為啟發(fā)函數。

基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第七十二頁，共一百五十二頁。72第七章搜索策略

f(x)估價函數可以是任意一種函數。但是,正確地選擇估價函數對確定搜索結果起著決定性的作用。

g(x)可以根據生成的搜索樹實際計算出來。

啟發(fā)信息主要體現在啟發(fā)函數h(x)中，用于對將付出的代價進行估計，選擇節(jié)點。其形式要根據問題的特性確定。它有賴于某種經驗估計。基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第七十三頁，共一百五十二頁。73第七章搜索策略3、關于估價函數f（x）的討論在估價函數f（x）中，g（x）和h（x）各起著不同的角色。假如將估價函數寫成如下的形式：

f（x）=v×g（x）+w×h（x）其中，v、w為權系數。v、w≥0。當w增加，v減小,即h（x）的比重增大,這時表示強調“啟發(fā)信息”的作用和“縱向深入”的搜索。當w減小，v增加,即g（x）的比重增大,這時表示強調“歷史信息”的作用和“橫向掃描”的搜索?；靖拍顮顟B(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第七十四頁，共一百五十二頁。74第七章搜索策略⑴在f（x）中，g（x）的權增大，搜索過程傾向于寬度優(yōu)先搜索，有利于搜索過程的完備性，但抑制了縱向深度前進的速度，降低了搜索過程的啟發(fā)性，不利于提高搜索效率。

例如，在寬度優(yōu)先搜索法中：f（x）=g（x）=d（x）式中：d（x）：搜索深度。

沒有利用啟發(fā)信息，所以h（x）=0或w=0，效率較低?；靖拍顮顟B(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第七十五頁，共一百五十二頁。75第七章搜索策略⑵在f(x)中，h(x)的權增大，搜索過程將傾向于深度優(yōu)先搜索，強調“縱向深入”，沿最有希望的方向前進，利用啟發(fā)性知識，提高搜索效率，壓縮搜索空間，但卻放棄了橫向掃描，降低了搜索過程的完備性。

例如，在深度優(yōu)先搜索法中：

f(x)=h(x)=n(x)式中：n(x)為節(jié)點x在該次生成時的次序。根據“最晚生成的優(yōu)先擴展”的深度優(yōu)先搜索規(guī)則，每次擴展時，將所生成的各子節(jié)點中最晚的，作為控制策略引入到評價函數f(x)中，假定最晚生成的節(jié)點的代價最小，是最有希望的搜索方向。而不論該節(jié)點處在哪一級，已經付出了多少代價，即不考慮g(x)的影響，相當于取v=0或g(x)=0。基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第七十六頁，共一百五十二頁。76第七章搜索策略因此，單純的“寬度優(yōu)先”和“深度優(yōu)先”搜索法是兩種極端的情形。實際上，設計適用的、高效的估價函數，需要根據問題的有關知識及對解的特性的估計，既要考慮已付出的代價g(x)，也要考慮將要付出的代價h(x)，兼顧搜索過程的完備性與啟發(fā)性，在“橫向掃描”與“縱向深入”之間，在“寬度”搜索與“深度”搜索之間，進行權衡，適當協(xié)調配合，才能取得滿意的效果，低代價、高效率、成功地搜索到最優(yōu)解。基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第七十七頁，共一百五十二頁。77第七章搜索策略例7.7利用估價函數方法求解圖7-14所示的重排九宮問題。解：設估價函數為f（x）=d（x）+w（x）

其中：d（x）為搜索樹中節(jié)點x的深度；

w（x）為在節(jié)點x時棋子錯放的個數。這樣，初始狀態(tài)S0的估價函數值為：f（0）=0+3=3。圖中圓圈內的數字表示該節(jié)點的估價值，不帶圈的數字表示節(jié)點擴展的順序。該問題解的路徑是：（見圖7-20所示）

S0→3→4→5→Sg。基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第七十八頁，共一百五十二頁。78第七章搜索策略4、啟發(fā)式搜索算法啟發(fā)式搜索要用啟發(fā)函數來控制搜索方向，其搜索算法就是在一般搜索算法的基礎上再增加啟發(fā)函數值的計算與傳播過程，并且由啟發(fā)函數來確定節(jié)點的擴展順序。

基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第七十九頁，共一百五十二頁。79第七章搜索策略⑴局部擇優(yōu)搜索局部擇優(yōu)搜索是一種啟發(fā)式圖搜索方法,是深度優(yōu)先搜索的一種改進。它在控制策略中引入了啟發(fā)性信息，如關于問題的解的特性、出現規(guī)律等，使搜索過程的估價函數f（x）反映啟發(fā)信息，通過擇優(yōu)比較，選取最有希望逼近目標節(jié)點的方向，逐級沿縱向深度進行搜索，以便加快搜索過程，提高搜索效率。

基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第八十頁，共一百五十二頁。80第七章搜索策略☆局部擇優(yōu)搜索的基本思想當一個節(jié)點被擴展后，按f（x）對每一個子節(jié)點計算估價值，并選擇最小者作為下一個要考察的節(jié)點，由于在搜索過程中，只保留和擴展優(yōu)選的節(jié)點，擇優(yōu)比較只是在被擴展的優(yōu)選節(jié)點的所屬子節(jié)點中進行，是小范圍內的局部優(yōu)選?；靖拍顮顟B(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第八十一頁，共一百五十二頁。81第七章搜索策略☆局部擇優(yōu)搜索的算法①把初始節(jié)點S0放入OPEN表，計算f（S0）；②如果OPEN表為空，則問題無解，失敗并退出。③把OPEN表中的第一個節(jié)點取出放入CLOSED表中，并按順序冠以編號n；④考察節(jié)點n是否為目標節(jié)點。若是，則求得了問題的解，成功并退出。⑤若節(jié)點n不可擴展，則轉第⑵步；⑥擴展節(jié)點n，用估價函數f（x）計算每一個子節(jié)點的估價值，并按估價值從小到大的順序依次放入OPEN表的首部，為每個子節(jié)點配置指向父節(jié)點的指針。然后轉第⑵步。基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第八十二頁，共一百五十二頁。82第七章搜索策略☆局部擇優(yōu)搜索的特點

優(yōu)點：方法簡便、搜索過程快、占用計算機內存少（只需搜索部分狀態(tài)空間，不需存儲全部狀態(tài)空間）。

缺點：只適用于單峰極值、單因素問題；對于多峰極值、多因素問題，可能搜索失敗，找不到所求的目標節(jié)點。因此，局部擇優(yōu)法是不完備的推理?；靖拍顮顟B(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第八十三頁，共一百五十二頁。83第七章搜索策略例7.8用局部擇優(yōu)搜索方法求解重排九宮問題。其中S0與Sg如下所示。

設估價函數為：f（x）=h（x）

（節(jié)點x的格局與目標格局不符合的牌數）其搜索樹如圖7-21所示。

在搜索過程中希望h（x）盡量小，目標狀態(tài)h（Sg）=0。

該問題的解的路徑為：

S0→S1→S2→S3→S4→S5→S6→S7→S8→Sg

基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索2831647512384765S0Sg第八十四頁，共一百五十二頁。84第七章搜索策略⑵全局擇優(yōu)搜索是一種啟發(fā)式圖搜索方法，它彌補了局部擇優(yōu)搜索法的局限性。☆全局擇優(yōu)搜索的基本思想在OPEN表中保留所有已生成而未考察的節(jié)點,并用估價函數f(x)對它們全部進行估價,從中選出最優(yōu)節(jié)點進行考察，而不管這個節(jié)點在搜索樹的什么地方。基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第八十五頁，共一百五十二頁。85第七章搜索策略

☆全局擇優(yōu)搜索的算法

①把初始節(jié)點S0放入OPEN表，計算f（S0）；②如果OPEN表為空，則搜索失敗，失敗并退出。③把OPEN表中的第1個節(jié)點從表中移出放入CLOSED表，并按順序冠以編號n；④考察節(jié)點n是否為目標節(jié)點。若是，則求得了問題的解，成功并退出。⑤若節(jié)點n不可擴展，則轉第⑵步；⑥擴展節(jié)點n，用估價函數f（x）計算每個子節(jié)點的估價值，并為每個子節(jié)點配置指向父節(jié)點的指針，把這些子節(jié)點都送入OPEN表中，然后對OPEN表中的全部節(jié)點按估價值從小到大的順序進行排序。然后轉第⑵步?；靖拍顮顟B(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第八十六頁，共一百五十二頁。86

例7.9用全局優(yōu)先搜索方法求解圖7-14所示的重排九宮問題。設估價函數為:

f(x)=d(x)+h(x)式中:d(x)表示節(jié)點x的深度。h(x)表示節(jié)點x的格局與目標格局不符合的紙牌數。其搜索樹如圖7-22所示，圖中節(jié)點旁的數字為該節(jié)點的估價值。只需四步就搜索成功。

該問題解的路徑為：

S0→S1→S2→S3→Sg。

第八十七頁，共一百五十二頁。87第七章搜索策略課堂練習用全局擇優(yōu)搜索算法解例7.8.f（x）=d（x）+h（x）d（x）表示節(jié)點的深度；h（x）表示節(jié)點的格局與目標格局不符合的字牌數?；靖拍顮顟B(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第八十八頁，共一百五十二頁。88第七章搜索策略

7.1基本概念7.2狀態(tài)空間的搜索技術7.3與/或圖的搜索策略7.4博弈樹搜索

7.3.1與/或圖搜索

7.3.2啟發(fā)式與/或圖搜索第八十九頁，共一百五十二頁。89第七章搜索策略與狀態(tài)空間法類似，與/或圖表示法也是通過搜索實現問題求解的。其搜索策略也分為非啟發(fā)式搜索(盲目搜索)與啟發(fā)式搜索兩大類。本節(jié)首先介紹與/或圖的非啟發(fā)式搜索，然后再給出與/或圖的啟發(fā)式搜索。7.3與/或圖的搜索策略基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第九十頁，共一百五十二頁。90第七章搜索策略

當知識表達方式采用與/或圖形式時，知識推理就要應用與/或圖搜索法。

與/或圖與狀態(tài)圖是兩種結構不同的圖。對狀態(tài)圖而言，在搜索過程中，一旦任何一級，任何一條分支樹，出現目標節(jié)點，就意味著搜索成功。但對與/或圖，由于“與”樹的存在，只有當所有的“子節(jié)點”可解，“與”樹的“父節(jié)點”才是可解的。

7.3.1與/或圖搜索基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第九十一頁，共一百五十二頁。91第七章搜索策略1、與/或圖的一般搜索過程1）基本概念對于一個問題，若用與/或圖方法進行求解，原問題（對應于根節(jié)點）是否可解，將取決于它的子問題，這些子問題對應于子節(jié)點，這些子節(jié)點可以是等價變換后產生的或關系，也可以是分解后產生的與關系，由問題本身決定。

7.3.1與/或圖搜索基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第九十二頁，共一百五十二頁。92第七章搜索策略

根據與/或圖的特點，對于一個“與”節(jié)點，只有當其子節(jié)點全部為可解節(jié)點時，它才為可解節(jié)點，只要子節(jié)點中有一個為不可解節(jié)點，它就是不可解節(jié)點；對于一個“或”節(jié)點，只要子節(jié)點中有一個是可解節(jié)點，它就是可解節(jié)點，只有當全部子節(jié)點都是不可解節(jié)點時，它才是不可解節(jié)點。

7.3.1與/或圖搜索基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第九十三頁，共一百五十二頁。93第七章搜索策略像這樣由可解子節(jié)點來確定其父節(jié)點、祖父節(jié)點等為可解節(jié)點的過程稱為可解標示過程；反之稱為不可解標示過程。在與/或圖的搜索過程中將反復使用這兩個過程，直到初始節(jié)點（即原始問題）被標示為可解或不可解節(jié)點為止。

7.3.1與/或圖搜索基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第九十四頁，共一百五十二頁。94第七章搜索策略2）與/或圖的一般搜索過程

⑴把原始問題作為初始節(jié)點S0，并把它作為當前節(jié)點；⑵應用分解或等價變換算符對當前節(jié)點進行擴展；⑶為每個子節(jié)點設置指向父節(jié)點的指針；⑷選擇合適的子節(jié)點作為當前節(jié)點，反復執(zhí)行第⑵步和第⑶步，在此期間要多次調用可解標示過程和不可解標示過程，直到初始節(jié)點被標示為可解節(jié)點或不可解節(jié)點為止。7.3.1與/或圖搜索基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第九十五頁，共一百五十二頁。95第七章搜索策略

由這個搜索過程所形成的節(jié)點和指針結構稱為搜索樹。

與/或圖搜索的目標是尋找解樹，從而求得原始問題的解。如果在搜索的某一時刻，通過可解標示過程可確定初始節(jié)點是可解的，則由此初始節(jié)點及其下屬的可解節(jié)點就構成了解樹。如果被選為擴展的節(jié)點不可擴展，并且它不是終止節(jié)點，則此節(jié)點就是不可解節(jié)點。此時可應用不可解標示過程確定初始節(jié)點是否為不可解節(jié)點，如果初始節(jié)點是不可解的，則搜索失??；否則繼續(xù)擴展節(jié)點。7.3.1與/或圖搜索基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略第九十六頁，共一百五十二頁。96第七章搜索策略

可解和不可解標示過程都是自下而上進行的，即由子節(jié)點的可解性確定父節(jié)點的可解性。由于與/或圖搜索的目標是尋找解樹，因此，如果已確定某個節(jié)點為可解節(jié)點，則其不可解的后裔節(jié)點就不再有用，可從搜索樹中刪去；同樣，如果確定某個節(jié)點是不可解節(jié)點，則其全部后裔節(jié)點都不再有用，可從搜索樹中刪去，但當前這個不可解節(jié)點還不能刪去，因為在判斷其先輩節(jié)點的可解性時還要用到它。這是與/或圖搜索的兩個特有的性質，可用來提高搜索效率。7.3.1與/或圖搜索基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略第九十七頁，共一百五十二頁。97第七章搜索策略2、與/或圖的寬度優(yōu)先搜索對于與/或圖的搜索策略，在考慮到“與”節(jié)點及“與”樹存在的情況下，也可以采用一般的樹圖搜索的方法。如寬度優(yōu)先搜索法、深度優(yōu)先搜索法、有限深度優(yōu)先搜索法等。與/或圖的寬度優(yōu)先搜索與狀態(tài)空間的寬度優(yōu)先搜索類似，也是按照“先產生的節(jié)點先擴展”的原則進行搜索，只是在搜索過程中要多次調用可解標示過程和不可解標示過程。

7.3.1與/或圖搜索基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略第九十八頁，共一百五十二頁。98第七章搜索策略與/或圖的寬度優(yōu)先搜索過程：⑴把初始節(jié)點S0放入OPEN表；⑵把OPEN表中的第一個節(jié)點取出放入CLOSED表，并按順序冠以編號n；⑶如果節(jié)點n可擴展，則做下列工作：①擴展節(jié)點n，將其子節(jié)點放入OPEN表的尾部，并為每個子節(jié)點配置指向父節(jié)點的指針，以備標示過程使用；②考察這些子節(jié)點中有否終止節(jié)點。若有，則標示這些終止節(jié)點為可解節(jié)點，并應用可解標示過程對其父節(jié)點、祖父節(jié)點等先輩節(jié)點中的可解節(jié)點進行標示。如果初始節(jié)點S0也被標示為可解節(jié)點，就得到了解樹，搜索成功，退出搜索過程；如果不能確定S0為可解節(jié)點，則從OPEN表中刪去具有可解先輩的節(jié)點。轉第⑵步；基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第九十九頁，共一百五十二頁。99第七章搜索策略⑷如果節(jié)點n不可擴展，則做下列工作：①標示節(jié)點n為不可解節(jié)點；②應用不可解標示過程對節(jié)點n的先輩節(jié)點中不可解的節(jié)點進行標示。如果初始節(jié)點S0也被標示為不可解節(jié)點，則搜索失敗，表明原始問題無解，退出搜索過程；如果不能確定S0為不可解節(jié)點，則從OPEN表中刪去具有不可解先輩的節(jié)點；轉第⑵步；基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第一百頁，共一百五十二頁。100第七章搜索策略例：設有如圖7-23所示的與/或圖，節(jié)點按圖中所標注的順序號進行擴展。其中1號節(jié)點為初始節(jié)點，標有t1，t2，t3，t4的節(jié)點均為終止節(jié)點，A和B為不可解的端節(jié)點。

圖7-23與/或圖的寬度優(yōu)先搜索基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索7.3.1與/或圖搜索第一百零一頁，共一百五十二頁。101第七章搜索策略搜索過程為：

⑴首先擴展1號節(jié)點，得到2號節(jié)點和3號節(jié)點，由于這兩個子節(jié)點均不是終止節(jié)點，所以接著擴展2號節(jié)點。此時OPEN表中只剩下3號節(jié)點。⑵擴展2號節(jié)點后，得到4號節(jié)點和t1節(jié)點。此時OPEN表中的節(jié)點有：3號節(jié)點、4號節(jié)點和t1節(jié)點。由于t1是終止節(jié)點，則標示它為可解節(jié)點，并應用可解標示過程，對其先輩節(jié)點中的可解節(jié)點進行標示?；靖拍顮顟B(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索7.3.1與/或圖搜索第一百零二頁，共一百五十二頁。102第七章搜索策略例中，t1的父節(jié)點是一個“與”節(jié)點，因此僅由t1可解尚不能確定2號節(jié)點是否為可解節(jié)點。所以繼續(xù)搜索，下一步擴展的是3號節(jié)點。⑶擴展3號節(jié)點得到5號節(jié)點與B節(jié)點，兩者均不是終止節(jié)點，所以接著擴展4號節(jié)點。⑷擴展4號節(jié)點后得到節(jié)點A和t2。由于t2是終止節(jié)點，所以標示它為可解節(jié)點，并應用可解標示過程標示出4號節(jié)點、2號節(jié)點均為可解節(jié)點，但1號節(jié)點目前還不能確定它是否為可解節(jié)點。此時5號節(jié)點是OPEN表中的第一個待考察的節(jié)點，所以下一步擴展5號節(jié)點?；靖拍顮顟B(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第一百零三頁，共一百五十二頁。103第七章搜索策略⑸擴展5號節(jié)點，得到t3和t4。由于t3和t4均為終止節(jié)點，所以被標示為可解節(jié)點，通過應用可解標示過程可得到5號、3號及1號節(jié)點均為可解節(jié)點。⑹搜索成功，得到了由1，2，3，4，5號節(jié)點及t1，t2，t3，t4節(jié)點構成的解樹。如圖7-23中粗線所示?；靖拍顮顟B(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第一百零四頁，共一百五十二頁。104第七章搜索策略與/或圖的寬度優(yōu)先搜索等都是非啟發(fā)式搜索，其共同點是：⑴搜索從初始節(jié)點開始，先自上而下地進行搜索，尋找終止節(jié)點及端節(jié)點，然后再自下而上地進行可解性標示，一旦初始節(jié)點被標示為可解節(jié)點或不可解節(jié)點，搜索就不再繼續(xù)進行下去。⑵搜索都是按確定路線進行的，當要選擇一個節(jié)點進行擴展時，只是根據節(jié)點在與/或圖中所處的位置，而沒有考慮要付出的代價，因而求得的解樹不一定是代價最小的解樹，即不一定是最優(yōu)解樹。7.3.2啟發(fā)式與/或圖搜索

基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索第一百零五頁，共一百五十二頁。105第七章搜索策略

為了求得最優(yōu)解樹，就要在每次確定欲擴展的節(jié)點時，先往前多看幾步，計算一下擴展這個節(jié)點可能要付出的代價，并選擇代價最小的節(jié)點進行擴展。像這樣根據代價決定搜索路線的方法稱為與/或圖的有序搜索，它是一種重要的啟發(fā)式搜索策略。下面討論與/或圖有序搜索的有關概念及其搜索過程。

基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索7.3.2啟發(fā)式與/或圖搜索

第一百零六頁，共一百五十二頁。106第七章搜索策略1、解樹的代價

解樹的代價就是樹根的代價。

樹根的代價是從樹葉開始自下而上逐層計算求得的。

解樹的根對應的就是初始節(jié)點S0。這就是說，在與/或圖的搜索過程中，代價的計算方向與搜索樹的生長方向相反。這一點是與狀態(tài)圖不同的。基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索7.3.2啟發(fā)式與/或圖搜索

第一百零七頁，共一百五十二頁。107第七章搜索策略具體來講，有下面的計算方法：

設g（x）表示節(jié)點x的代價，c（x，y）表示節(jié)點x到其子節(jié)點y的代價（即邊xy的代價），則⑴若x是“終止節(jié)點”，g（x）=0；⑵若x是“或”節(jié)點，其中y1，y2，…，yn是x的子節(jié)點；基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索7.3.2啟發(fā)式與/或圖搜索

第一百零八頁，共一百五十二頁。108第七章搜索策略⑶若x是“與”節(jié)點，則有兩種計算公式：①稱為和代價法；②稱為最大代價法；其中y1，y2，…，yn是x的子節(jié)點。⑷對“非終止”的端節(jié)點x，g（x）=∞?；靖拍顮顟B(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索7.3.2啟發(fā)式與/或圖搜索

第一百零九頁，共一百五十二頁。109第七章搜索策略例7．11如圖7-24所示的與/或圖，其中包括兩棵解樹，一棵解樹由S0，A，t1和t2組成；另一棵解樹由S0，B，D，G，t4和t5組成。在此與/或圖中，t1，t2，t3，t4，t5為終止節(jié)點；E，F是端節(jié)點，其代價均為∞；邊上的數字是該邊的代價。圖7-24含代價的與/或圖基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索7.3.2啟發(fā)式與/或圖搜索

第一百一十頁，共一百五十二頁。110第七章搜索策略由右邊的解樹可得：按和代價：g（A）=11，g（S0）=13。按最大代價：g（A）=6，g（S0）=8。由左邊的解樹可得：按和代價：g（G）=3，g（D）=4，g（B）=6，g（S0）=8。按最大代價：g（G）=2，g（D）=3，g（B）=5，g（S0）=7?；靖拍顮顟B(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索7.3.2啟發(fā)式與/或圖搜索

第一百一十一頁，共一百五十二頁。111第七章搜索策略顯然，若按和代價計算，左邊的解樹是最優(yōu)解樹，其代價是8；若按最大代價計算，左邊的解樹仍然是最優(yōu)解樹，其代價是7。但有時用不同的計算代價方法得到的最優(yōu)解樹不相同?；靖拍顮顟B(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索7.3.2啟發(fā)式與/或圖搜索

第一百一十二頁，共一百五十二頁。112第七章搜索策略2、希望樹1）節(jié)點x的代價g（x）無論是用和代價法還是最大代價法，當要計算任意節(jié)點x的代價g（x）時，都要求已知其子節(jié)點yi的代價g（yi）。但是，搜索是自上而下進行的，即先有父節(jié)點，后有子節(jié)點，除非節(jié)點x的全部子節(jié)點都是不可擴展節(jié)點，否則子節(jié)點的代價是不知道的。

基本概念狀態(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索7.3.2啟發(fā)式與/或圖搜索

第一百一十三頁，共一百五十二頁。113第七章搜索策略

節(jié)點x的代價g（x）的計算①根據問題本身提供的啟發(fā)性信息定義一個啟發(fā)函數，由啟發(fā)函數估算出子節(jié)點yi的代價g（yi）。②再按和代價或最大代價計算出節(jié)點x的代價值g（x）。③節(jié)點x的父節(jié)點、祖父節(jié)點以及直到初始節(jié)點S0的各先輩節(jié)點的代價g都可自下而上地逐層推算出來?；靖拍顮顟B(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索7.3.2啟發(fā)式與/或圖搜索

第一百一十四頁，共一百五十二頁。114第七章搜索策略

當節(jié)點yi被擴展后，也是先用啟發(fā)函數估算出其子節(jié)點的代價，然后再算出g(yi)。此時算出的g(yi)可能與原先估算出的g(yi)不相同，這時應該用后算出的g(yi)取代原先估算出的g(yi)，并且按此g(yi)自下而上地重新計算各先輩節(jié)點的g值。當節(jié)點yi的子節(jié)點又被擴展時，上述過程又要重復進行一遍?；靖拍顮顟B(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索7.3.2啟發(fā)式與/或圖搜索

第一百一十五頁，共一百五十二頁。115第七章搜索策略

總之，每當有新的一代節(jié)點生成時，都要自下而上地重新計算其先輩節(jié)點的代價g，這是一個自上而下地生成新節(jié)點，又自下而上地計算代價g的反復進行的過程?；靖拍顮顟B(tài)空間的搜索策略與/或圖的搜索策略博弈樹搜索7.3.2啟發(fā)式與/或圖搜索

第一百一十六頁，共一百五十二頁。116第七章搜索策略2）希望樹的定義有序搜索的目的是求出最優(yōu)解樹，即要求搜索過程中任意時刻求出的部分解樹其代價都應是最小的。為此，每次選擇欲擴展