第2章-基于圖的知識表示與圖搜索技術(shù)

第2章基于圖的學問表示與圖搜尋技術(shù)2023/2/28人工智能2第2章基于圖的學問表示與圖搜尋技術(shù)2.1概述2.2狀態(tài)空間圖表示2.3狀態(tài)空間圖的盲目搜尋2.4狀態(tài)空間圖的啟發(fā)式搜尋2.5與或圖表示及搜尋技術(shù)2.6博弈樹及搜尋技術(shù)2023/2/28人工智能32.1概述2.1.1學問與問題求解框架2.1.2學問表示2.1.3圖搜尋技術(shù)2023/2/28人工智能42.1.1學問與問題求解框架(1)1.學問的定義心理學：個體通過與環(huán)境相互作用后獲得的信息及其組織。費根鮑姆：學問是經(jīng)過消減、塑造、說明和轉(zhuǎn)換的信息。博恩斯坦（Bernstein）：學問是由特定領域的描述、關(guān)系和過程組成的。概括地說，學問是高度組織起來的信息集團，是人們在長期的生活和社會實踐中、科學探討和科學試驗中積累起來的閱歷或?qū)陀^世界規(guī)律的相識等。2.1.1學問與問題求解框架(2)2.學問的分類（1）從應用領域來劃分常識性學問領域（專業(yè)）性學問（2）從在問題求解中的作用來劃分敘述性學問過程性學問限制性學問（3）從確定性來劃分確定性學問非確定性學問（4）從學問的表現(xiàn)形式來劃分，可分為文字、符號、聲音、圖形、圖像等。2023/2/28人工智能52.1.1學問與問題求解框架(3)3.問題求解框架問題：是指事務或事物的已知或當前狀態(tài)與目標狀態(tài)之間有差異。問題求解：是指在確定的限制策略下，通過一系列的操作或運算來變更問題的狀態(tài)，使之與目標狀態(tài)接近或一樣。例如，李明在北京，他要去西安（辦事）。又如，博弈問題。問題的求解框架（1）敘述性學問：描述問題的狀態(tài)有關(guān)的各種學問。（2）過程性學問：描述狀態(tài)之間的變換關(guān)系的各種學問。（3）限制性學問：描述如何在當前狀態(tài)下選擇合適操作的學問。2023/2/28人工智能62023/2/28人工智能72.1.2學問表示(1)學問表示：就是探討在計算機中如何用最合適的形式表示問題求解過程中所須要的各種學問，包括構(gòu)成問題求解框架的全部學問。常用的學問表示形式狀態(tài)空間圖與或圖謂詞邏輯產(chǎn)生式框架語義網(wǎng)絡……2.1.2學問表示(2)2023/2/28人工智能8例2.1麥卡賽問題。在一個2n2n的方格棋盤中，去掉對角的兩個方格，如圖（a），問能否將它全部劃成若干12的小長方塊？目標狀態(tài)初始狀態(tài)可達狀態(tài)同構(gòu)問題同態(tài)問題2023/2/28人工智能92.1.3圖搜尋技術(shù)(1)1.搜尋搜尋，簡潔地說就是“找尋”，目的是找到問題的解。在問題求解過程中，待求解的問題被抽象成確定空間上的圖，搜尋過程就是從圖中初始節(jié)點動身，沿著與之相連的邊摸索著前進，找尋目標節(jié)點或可解節(jié)點的過程。2.搜尋樹搜尋過程中經(jīng)過（考察過）的節(jié)點和邊，按原圖的連接關(guān)系，便會構(gòu)成一個樹型的有向圖，稱為搜尋樹。搜尋樹是一個搜尋過程的搜尋軌跡，或稱之為搜尋空間。2.1.3圖搜尋技術(shù)(2)2023/2/28人工智能10圖2-2搜尋空間示意圖問題的狀態(tài)空間、搜尋空間及解的示意圖：2.1.3圖搜尋技術(shù)(3)3.搜尋策略搜尋策略將確定搜尋過程依據(jù)什么樣的依次考察節(jié)點和經(jīng)過狀態(tài)空間圖的哪些節(jié)點。盲目搜尋：無向?qū)У乃褜?，也稱窮舉搜尋。啟發(fā)式搜尋：利用“啟發(fā)性信息”作為導航的搜尋過程。對于較大或無限狀態(tài)空間問題，盲目搜尋效率太低，所以在實際當中往往是不行行的。啟發(fā)式搜尋廣泛地應用于實際問題求解中，如博弈、機器學習、數(shù)據(jù)挖掘、智能檢索等。2023/2/28人工智能112023/2/28人工智能122.2狀態(tài)空間圖表示2.2.1狀態(tài)空間圖2.2.2隱式狀態(tài)空間圖2023/2/28人工智能132.2.1狀態(tài)空間圖（1）1.狀態(tài)狀態(tài)對應敘述性學問，描述一個問題在起先、結(jié)束或中間的某一時刻所處的狀況或狀態(tài)。通常引進一組變量q1,q2,…,qn，表示與問題狀態(tài)相關(guān)的各種要素，并用這組變量所構(gòu)成的多元組(q1,q2,…,qn)來表示狀態(tài)。狀態(tài)在狀態(tài)圖中表示為節(jié)點。2023/2/28人工智能142.2.1狀態(tài)空間圖（2）2.操作操作對應過程性學問，即狀態(tài)轉(zhuǎn)換規(guī)則，描述狀態(tài)之間的關(guān)系。描述一個操作要包含兩個部分條件:指明被作用的狀態(tài)要滿足的約束條件動作:指明一個操作對狀態(tài)的重量所做的變更。操作的表示形式可以是一個機械性的步驟、過程、規(guī)則或算子。操作在狀態(tài)圖中表示為邊。在程序中，狀態(tài)轉(zhuǎn)換規(guī)則可用數(shù)據(jù)對、條件語句、規(guī)則、函數(shù)、過程等表示。如：假如室內(nèi)溫度低于26度，則關(guān)閉空調(diào)。2023/2/28人工智能152.2.1狀態(tài)空間圖（3）3.狀態(tài)空間圖問題的狀態(tài)空間圖是一個描述該問題全部可能的狀態(tài)及相互關(guān)系的圖，如考慮操作的代價，狀態(tài)空間圖就是一個賦值有向圖。狀態(tài)空間常記為三元組：

S：初始狀態(tài)的集合

F：操作的集合

G：目標狀態(tài)的集合。由問題的狀態(tài)空間表示就可以構(gòu)造出狀態(tài)空間圖。2.2.1狀態(tài)空間圖（4）4.求解在狀態(tài)空間表示法中，問題求解過程轉(zhuǎn)化為在圖中找尋從初始狀態(tài)Qs動身到達目標狀態(tài)Qg的路徑問題，也就是找尋操作序列的問題。狀態(tài)空間的解為三元組<Qs,a,Qg>Qs：某個初始狀態(tài)Qg：某個目標狀態(tài)a：把Qs變換成Qg的有限的操作序列狀態(tài)轉(zhuǎn)換圖S1S3S2…f1f2f3f4QsQgfn2023/2/28人工智能162023/2/28人工智能17例2.2翻轉(zhuǎn)錢幣問題（1）三枚錢幣處于反、正、反狀態(tài)，每次只許翻動一枚錢幣，問連續(xù)翻動三次后，能否出現(xiàn)全正或全反狀態(tài)。初始狀態(tài)Qs目標狀態(tài)集合{Q0,Q7}例2.2翻轉(zhuǎn)錢幣問題（2）引入一個三元組(q0,q1,q2)來描述總狀態(tài)，錢幣正面為0，反面為1，全部可能的狀態(tài)為：

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)。翻動錢幣的操作抽象為變更上述狀態(tài)的算子，即F＝{a,b,c}a:把錢幣q1翻轉(zhuǎn)一次b:把錢幣q2翻轉(zhuǎn)一次c:把錢幣q3翻轉(zhuǎn)一次問題的狀態(tài)空間為<{Q5},{a,b,c}，{Q0Q7}>2023/2/28人工智能18例2.2翻轉(zhuǎn)錢幣問題（4）3.狀態(tài)空間圖問題的狀態(tài)空間為：

2023/2/28人工智能19構(gòu)造狀態(tài)空間圖：

aabababaabbbbcccbcccb例2.2翻轉(zhuǎn)錢幣問題（5）2023/2/28人工智能20圖2-5翻動三次后三枚錢幣問題的狀態(tài)變更翻轉(zhuǎn)錢幣問題狀態(tài)空間圖的另一種表示：2023/2/28人工智能21例2.3修道士和野人問題（1）在河的左岸有三個修道士、三個野人和一條船，修道士們想用這條船將全部的人都運過河去，但受到以下條件的限制：（1）修道士和野人都會劃船，但船一次最多只能運兩個人；（2）在任何岸邊野人數(shù)目都不得超過修道士，否則修道士就會被野人吃掉。假定野人會聽從任何一種過河支配，試規(guī)劃出一種確保修道士平安過河方案。2023/2/28人工智能22例2.3修道士和野人問題（2）1、問題的狀態(tài)可以用一個三元數(shù)組來描述：

S＝(m,c,b)

m：左岸的修道士數(shù)

c：左岸的野人數(shù)

b：左岸的船數(shù)右岸的狀態(tài)不必標出，因為：

右岸的修道士數(shù)m’＝3－m

右岸的野人數(shù)c’＝3－c

右岸的船數(shù)b’＝1－b2023/2/28人工智能23例2.3修道士和野人問題（3）狀態(tài)m,c,b狀態(tài)m,c,b狀態(tài)m,c,b狀態(tài)m,c,bS0331S8131S16330S24130S1321S9121S17320S25120S2311S10111S18310S26110S3301S11101S19300S27100S4231S12031S20230S28

030S5221S13021S21220S29020S6211S14011S22210S30010S7201S15001S23200S310002023/2/28人工智能24例2.3修道士和野人問題（4）2.操作集F＝{p01,p10,p11,p02,p20,q01,q10,q11,q02,q20}q20b=0,(m=0,c=2)或(m=1,c=1)b=1,m=m+2q02b=0,m=0或3,c≤2b=1,c=c+2q11b=0,m=c,c≤2b=1,m=m+1,c=c+1q10b=0,(m=0,c=1)或(m=2,c=2)b=1,m=m+1q01b=0,m=0或3,c≤2b=1,c=c+1p20b=1,(m=3,c=1)或(m=2,c=2)b=0,m=m-2p02b=1,m=0或3,c≥2b=0,c=c-2p11b=1,m=c,c≥1b=0,m=m-1,c=c-1p10b=1,(m=3,c=2)或(m=1,c=1)b=0,m=m-1p01b=1,m=0或3,c≥1b=0,c=c-1操作符條件動作例2.3修道士和野人問題（5）3.狀態(tài)空間給出狀態(tài)和操作的描述之后，該問題的狀態(tài)空間是：{{S0}，{P

01，P

10，P

11，P

02，P

20，Q01，Q

10，Q

11，Q

02，Q

20}，{S31}}。2023/2/28人工智能26例2.3修道士和野人問題（6）S0(3,3,1)S18(3,1,0)p02q02S17(3,2,0)p01q01S21(2,2,0)p11q11S1(3,2,1)q01p01p10q10S19(3,0,0)q02p02S2(3,1,1)q01p01S26(1,1,0)q20p20S31(0,0,0)q11p11S14(0,1,1)p01q01p02q02S10(1,1,1)p10q10S13(0,2,1)q01p01S30(0,1,0)p02q02S12(0,3,1)p01q01S29(0,2,0)p20q20S5(2,2,1)q11p114.狀態(tài)空間圖：四條S0到S31長度相等的最短路徑，對應的操作序列就是該問題的四個最優(yōu)解2023/2/28人工智能272.2.2隱式狀態(tài)空間圖顯式狀態(tài)空間圖：表示了問題全部可能的狀態(tài)及狀態(tài)之間的關(guān)系，這種表示方式稱為顯式狀態(tài)空間圖，或稱為狀態(tài)空間圖的顯示表示。隱式狀態(tài)空間圖：利用有關(guān)狀態(tài)描述和狀態(tài)轉(zhuǎn)換（操作）的學問定義的狀態(tài)空間圖。在計算機中僅存儲描述問題狀態(tài)及操作的有關(guān)學問，包括該問題的各狀態(tài)重量的取值狀況、重量之間的約束條件、起先狀態(tài)、終止狀態(tài)，以及全部操作的條件和動作等。隱式狀態(tài)空間圖也稱為是狀態(tài)空間圖的隱式表示或隱式圖。重排九宮問題的隱式圖描述為：（1）有關(guān)狀態(tài)的學問：狀態(tài)S的定義：S＝(X0，X1，X2，X3，X4，X5，X6，X7，X8)其中，Xi｛0，1，2，3，4，5，6，7，8｝，，且。初始狀態(tài)：S0＝（0，1，2，3，5，6，4，7，8）目標狀態(tài)：Sg＝（0，1，2，3，4，5，6，7，8）重排九宮問題的狀態(tài)表示例2.4重排九宮問題（八數(shù)碼問題）

例2.4重排九宮問題（2）（2）有關(guān)操作的學問（規(guī)則）：0組規(guī)則R1(X0=0)(X2=n)X0=nX2=0；R2(X0=0)(X4=n)X0=nX4=0；R3(X0=0)(X6=n)X0=nX6=0；R4(X0=0)(X8=n)X0=nX8=0；1組規(guī)則R5(X1=0)(X2=n)X1=nX2=0；R6(X1=0)(X8=n)X1=nX8=0；8組規(guī)則:R22(X8=0)(X1=n)X8=nX1=0；R23(X8=0)(X0=n)X8=nX0=0；R24(X8=0)(X7=n)X8=nX7=0；……例2.4重排九宮問題（3）八數(shù)碼的狀態(tài)圖可表示為（{S0},{r1,r2,…,r24},{Sg}）

八數(shù)碼問題狀態(tài)圖僅給出了初始節(jié)點和目標節(jié)點，其余節(jié)點需用狀態(tài)轉(zhuǎn)換規(guī)則來產(chǎn)生。類似于這樣表示的狀態(tài)圖稱為隱式狀態(tài)圖，或者說狀態(tài)圖的隱式表示。例2.4重排九宮問題（4）（3）隱式圖搜尋初始狀態(tài)S＝（0，1，2，3，5，6，4，7，8）滿足條件X0=0，故可以運用第0組的四條規(guī)則：假如選擇規(guī)則R1，則狀態(tài)轉(zhuǎn)換為：S1＝（2，1，0，3，5，6，4，7，8)2023/2/28人工智能32例2.5旅行商問題(TSP)(1)---（選學）設有n個相互可直達的城市，某推銷商準備從其中的A城動身，周游各城市一遍，最終又回到A城。要求為該推銷商規(guī)劃一條最短的旅行路途。（1）狀態(tài)描述：該問題的狀態(tài)為以A打頭城市序列：=AA1…Ai…Aj…A’其中：A、Ai、Aj、A’為城市名，1i、jn-1，AjA，AiA；1||n+1；當ij時，AiAj；當且僅當||=n+1時，A’=A。初始狀態(tài)：=A，||=1終止狀態(tài)：=AA1A2…A，||=n+1例2.5旅行商問題(TSP)(2)（2）操作描述（狀態(tài)轉(zhuǎn)換規(guī)則）：規(guī)則1：假如=AA1…Ai…Aj…，且||n，但A’，則置=A。即沒遍歷完時，在城市序列中添加一個沒有到過的城市。規(guī)則2：假如||=n，置=A，即從當前城市返回A城。（3）隱式圖搜尋對于有A、B、C、D四個城市所組成的連通城市網(wǎng)，初始狀態(tài)：=A，||=1，滿足規(guī)則1，則操作的結(jié)果為：=AB、或=AC、或=AD，接著運用規(guī)則1，直到生成包含四個城市的序列出現(xiàn)，再運用規(guī)則2。2023/2/28人工智能33補充例

二階梵塔問題（1）---（選學）

一號桿有A、B兩個金盤，A小于B。要求將A、B移至三號桿，每次只可移動一個盤子，任何時刻B不能在A上。（1）有關(guān)狀態(tài)的學問：用二元組（SA，SB）表示狀態(tài)，SA表示A所在桿號，SB表示B所在桿號。其中:SA,SB{1,2,3},則全部狀態(tài)如下：（1，1），（1，2），（1，3）（2，1），（2，2），（2，3）（3，1），（3，2），（3，3）初始狀態(tài)為（1，1），終止狀態(tài)為：（3，3）。2023/2/28人工智能34AB123S0：（1，1）123S1：（1，2）123S2：（1，3）AA123S5：（2，3）123S4：（2，2）123S3：（2，1）123S8：（3，3）123S7：（3，2）123S6：（3，1）AAAAABABBBBB補充例

二階梵塔問題（2）2023/2/28人工智能35（2）有關(guān)操作的學問（規(guī)則）：A（i，j）表示金盤A從第I號桿移到j號桿，B（i，j）表示金盤B從第i號桿移到j號桿，其中：i,j{1,2,3}，但ij，全部操作為：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）分析每個操作的條件和動作，得到下表：補充例

二階梵塔問題（3）2023/2/28人工智能36補充例

二階梵塔問題（4）操作符條件動作A（1，2）SA=1SA=2A（1，3）SA=1SA=3A（2，1）SA=2SA=1A（2，3）SA=2SA=3A（3，1）SA=3SA=1A（3，2）SA=3SA=2B（1，2）SB=1，SA1,2或SA=3SB=2B（1，3）SB=1，SA1,3或SA=2SB=3B（2，1）SB=2，SA1,2或SA=3SB=1B（2，3）SB=2，SA2,3或SA=1SB=3B（3，1）SB=3，SA1,3或SA=2SB=1B（3，2）SB=3，SA2,3或SA=1SB=22023/2/28人工智能37補充例

二階梵塔問題（5）（3）狀態(tài)空間圖1,12,13,12,33,31,33,21,22,2A(1,2)A(1,3)B(1,2)A(3,2)A(1,2)B(3,2)A(3,1)B(1,3)A(2,3)2023/2/28人工智能382.3狀態(tài)空間圖的盲目搜尋盲目搜尋:搜尋時不參考與具體待求解問題相關(guān)的任何信息，只是按預先設定的依次逐個考察節(jié)點。盲目搜尋與問題無關(guān)，具有通用性。算法中運用的數(shù)據(jù)結(jié)構(gòu):OPEN表：特地登記已經(jīng)生成但還沒有考察的節(jié)點，即待考察節(jié)點。CLOSED表：用來記錄考察過的節(jié)點以及節(jié)點之間的關(guān)系，如每個節(jié)點指向父節(jié)點的編號（返回指針）。CLOSED表中存放的就是確定搜尋策略下的搜尋樹。2023/2/28人工智能39節(jié)點父節(jié)點編號編號節(jié)點父節(jié)點編號OPEN表CLOSED表2023/2/28人工智能402.3狀態(tài)空間圖的盲目搜尋2.3.1廣度優(yōu)先搜尋2.3.2深度優(yōu)先搜尋2023/2/28人工智能412.3.1廣度優(yōu)先搜尋（1）廣度優(yōu)先搜尋基本思想：廣度優(yōu)先搜尋是嚴格按節(jié)點在樹中的出現(xiàn)位置一層一層向下的搜尋過程。通過將OPEN表設計為一個隊列來實現(xiàn)，將新生成的子節(jié)點放在OPEN表的后面，保證先生成的節(jié)點先考察。廣度優(yōu)先搜尋算法：步1把初始節(jié)點S0放入OPEN表中；步2若OPEN表為空，則搜尋失敗，退出；步3否則，取OPEN表中第一個節(jié)點N放在CLOSED表中；并冠以依次編號n；步4若節(jié)點N為目標節(jié)點，則搜尋成功。利用CLOSED表中的返回指針找出S0到N的路徑即為所求解，退出；步5若N不行擴展，轉(zhuǎn)步2；步6否則，擴展N，將其全部子節(jié)點配上指向N的返回指針放入OPEN表的尾部，轉(zhuǎn)步2。2.3.1廣度優(yōu)先搜尋（2）2023/2/28人工智能43例2.6運用廣度優(yōu)先搜尋算法求解重排九宮問題1238574611238567481382574610123845767123845766138257461112384576212385746313825746412378546122318574613123847651412345876151285374617135827461881325746191237854620231857462112843765221238574651238476523八數(shù)碼廣度優(yōu)先搜尋12853746916123856742023/2/28人工智能442.3.1廣度優(yōu)先搜尋廣度優(yōu)先搜尋的特點：廣度優(yōu)先中OPEN表是一個隊列，CLOSED表是一個依次表，表中各節(jié)點按依次編號，正被考察的節(jié)點在表中編號最大。廣度優(yōu)先搜尋又稱為寬度優(yōu)先或橫向搜尋。廣度優(yōu)先策略是完備的，即假如問題的解存在，則它確定可以找到解，并且找到的解還是最優(yōu)解。廣度優(yōu)先搜尋策略與問題無關(guān)，具有通用性。缺點搜尋效率低。2023/2/28人工智能452.3.2深度優(yōu)先搜尋(1)深度優(yōu)先搜尋的基本思想：深度優(yōu)先搜尋是一種始終向下的搜尋過程，它優(yōu)先在自己的子節(jié)點集合中選擇下一個被考察的節(jié)點，不斷向縱深方向前進，直到到達葉子節(jié)點或受到深度限制時，才返回到上一級節(jié)點沿另一方向接著前進。深度優(yōu)先搜尋算法：與廣度優(yōu)先搜尋策略的唯一不同點就是OPEN表被設計成后進先出的棧，新生成的子節(jié)點放在OPEN表的前面，后生成的節(jié)點優(yōu)先被考察。深度優(yōu)先搜尋算法只需將寬度優(yōu)先搜尋算法步6修改為：步6否則，擴展N，將其全部子節(jié)點配上指向N的指針放入OPEN表的首部，轉(zhuǎn)步2。例2.7運用深度優(yōu)先搜尋算法求解重排九宮問題12385746112384576312384576

123845761382574612385746123847654128437651238574621238476552023/2/28人工智能472.3.2深度優(yōu)先搜尋深度優(yōu)先搜尋的特點：OPEN表為一個堆棧。深度優(yōu)先又稱縱向搜尋。一般不能保證找到最優(yōu)解。如下圖所示：圖2-13深度優(yōu)先搜尋不具有完備性示意圖2023/2/28人工智能481.有界深度優(yōu)先搜尋（Acd）為克服深度優(yōu)先搜尋的不足，可以對其深度進行限制深度界限的選擇很重要dm若太小，則達不到解的深度，得不到解；若太大，既奢侈了計算機的存儲空間與時間，又降低了搜尋效率。由于解的路徑長度事先難以預料，所以要恰當?shù)亟o出dm的值是比較困難的。即使能求出解，它也不確定是最優(yōu)解。2.可變界深度優(yōu)先搜尋算法(1)當在dm界限之內(nèi)找不到解時，可以將深度界限dm不斷擴大，每次增加一個深度增量d，直到找到解，或者搜尋完整棵樹。這樣算法的完備性得到了保證，稱為可變界深度優(yōu)先搜尋算法(或迭代加深搜尋)。當⊿d=1時，算法起先蛻變?yōu)閺V度優(yōu)先搜尋算法。

2.可變界深度優(yōu)先搜尋算法(2)迭代加深搜尋過程：步1把初始節(jié)點S0放入OPEN表中，置S0的深度d（S0）＝0，dm為隨意初值。步2若OPEN表為空，則考查CLOSED表是否有待擴展節(jié)點：①若無，則問題無解，退出。②若有，則取出CLOSED表中待擴展節(jié)點放入到OPEN表中，令dm=dm+⊿d。

2.可變界深度優(yōu)先搜尋算法(3)步3取OPEN表中第一個節(jié)點N放在CLOSED表中；并冠以編號n；步4若節(jié)點N為目標節(jié)點，成功退出。步5若N的深度d（N）＞dm（深度限制值），則標N為待擴展節(jié)點，則轉(zhuǎn)步2；步6N無子節(jié)點，則轉(zhuǎn)步2；步7擴展N，將其全部子節(jié)點Ni配上指向N的指針放入OPEN首部，置d（Ni）＝d（N）＋1，轉(zhuǎn)步2。3.可接受的有界深度優(yōu)先搜尋算法(1)—選學問題：當⊿d

>1時，是否能保證找到最優(yōu)解？2023/2/28人工智能543.可接受的有界深度優(yōu)先搜尋算法(2)步1把初始節(jié)點S0放入OPEN表中，置d(S0)=0，dm=dm0，G=NULL。步2若OPEN表為空，則考察CLOSED表是否有待擴展節(jié)點：（1）若無待擴展節(jié)點，則推斷G表是否為空：若為空，搜尋失敗，退出；否則，取出G表最終面的節(jié)點Sg，Sg即為所求最優(yōu)解，搜尋成功，退出；（2）若有待擴展節(jié)點，則取出CLOSED表中待擴展節(jié)點放入到OPEN表中，令dm=dm+⊿d，轉(zhuǎn)步2；3.可接受的有界深度優(yōu)先搜尋算法(3)步3取OPEN表中首部的節(jié)點N放在CLOSED表中；并冠以依次編號n；步4若d（N）＞dm，則標N為待擴展節(jié)點，轉(zhuǎn)步2；步5若N是目標節(jié)點Sg，則令dm＝d（Sg）-1，把Sg放到G表的尾部，轉(zhuǎn)步2。步6若N不行擴展，則轉(zhuǎn)步2；步7否則，擴展N，將其全部子節(jié)點Ni配上指向N的返回指針放入OPEN表首部，置d（Ni）＝d（N）＋1，轉(zhuǎn)步2。2023/2/28人工智能55第1次作業(yè)細致復習課件；完成課后第6題；嘗試用編程方法實現(xiàn)廣度優(yōu)先和深度優(yōu)先算法；命名：學號-姓名-第1次作業(yè).docx;截止時間：下周上課之前；提交到FTP://13,AI/AI2.4狀態(tài)空間圖的啟發(fā)式搜尋(1)1.啟發(fā)性學問與啟發(fā)函數(shù)啟發(fā)性學問就是與被求解問題自身特性相關(guān)的學問，包括被求解問題的解的特性、解的分布規(guī)律和在實際當中求解此類問題的閱歷、技巧等，對應于問題求解框架中的限制性學問。啟發(fā)函數(shù)要實現(xiàn)啟發(fā)式搜尋，須要把啟發(fā)性學問形式化，即用確定的函數(shù)表示出來，通過函數(shù)計算來評價每種選擇的價值大小，用以指導搜尋過程，這樣的函數(shù)稱為啟發(fā)函數(shù)。572023/2/28人工智能582.4狀態(tài)空間圖的啟發(fā)式搜尋(2)2.啟發(fā)函數(shù)的設計在實際設計過程中，啟發(fā)函數(shù)是用來估計搜尋樹節(jié)點x與目標節(jié)點接近程度的一種函數(shù)，通常記為h（x）。啟發(fā)函數(shù)可以是：（1）一個節(jié)點到目標節(jié)點的某種距離或差異的量度；（2）一個節(jié)點處在最佳路徑上的概率；（3）依據(jù)主觀閱歷的主觀打分等。2023/2/28人工智能592.4狀態(tài)空間圖的啟發(fā)式搜尋(3)2.4.1啟發(fā)式搜尋算法2.4.2啟發(fā)式搜尋的A算法和A*算法2.4.3A*算法在游戲中的應用2023/2/28人工智能602.4.1啟發(fā)式搜尋算法（1）啟發(fā)式搜尋用啟發(fā)函數(shù)來導航，其搜尋算法就要在狀態(tài)圖一般搜尋算法基礎上再增加啟發(fā)函數(shù)值的計算與傳播過程，并且由啟發(fā)函數(shù)值來確定節(jié)點的擴展依次。按選擇范圍不同，啟發(fā)式搜尋分為：全局擇優(yōu)搜尋局部擇優(yōu)搜尋2023/2/28人工智能612.4.1啟發(fā)式搜尋算法（2）1.全局擇優(yōu)搜尋基本思想：在OPEN表中保留全部已生成而未考察的節(jié)點，并用啟發(fā)函數(shù)h(x)對它們?nèi)窟M行估價，從中選出最優(yōu)節(jié)點進行擴展，而不管這個節(jié)點出現(xiàn)在搜尋樹的什么地方。2.4.1啟發(fā)式搜尋算法（3）全局擇優(yōu)搜尋算法：步1把初始節(jié)點S0放入OPEN表中，計算h(S0)；步2若OPEN表為空，則搜尋失敗，退出；步3否則，移出OPEN表中第一個節(jié)點N放入CLOSED表中，并冠以序號n；步4若目標節(jié)點Sg＝N，則搜尋成功，利用CLOSED表中的返回指針找出S0到N的路徑即為所求解，退出；步5若N不行擴展，則轉(zhuǎn)步2；步6否則，擴展N，計算N的每個子節(jié)點x的函數(shù)值，并將N全部子節(jié)點x配以指向N的返回指針后放入OPEN表中，依據(jù)啟發(fā)函數(shù)對節(jié)點的計算，再對OPEN表中全部節(jié)點按其啟發(fā)函數(shù)值的大小以升序排列，轉(zhuǎn)步2。2023/2/28人工智能622.4.1啟發(fā)式搜尋算法（4）2.局部擇優(yōu)搜尋基本思想：局部擇優(yōu)搜尋是在啟發(fā)性學問導航下的深度優(yōu)先搜尋，在OPEN表中保留全部已生成而未考察的節(jié)點，對其中新生成的每個子節(jié)點x計算啟發(fā)函數(shù)，從全部子節(jié)點中選出最優(yōu)節(jié)點進行擴展，其選擇下一個要考察節(jié)點的范圍是剛剛生成的全部子節(jié)點。局部擇優(yōu)搜尋算法：與全局擇優(yōu)搜尋算法的區(qū)分僅在步6：步6否則，擴展N，計算N的每個子節(jié)點x的函數(shù)值，并將N的全部子節(jié)點x配以指向節(jié)點N的指針后，將全部子節(jié)點按啟發(fā)函數(shù)值升序排列后放入OPEN表的首部，轉(zhuǎn)步2。2023/2/28人工智能632.4.2啟發(fā)式搜尋的A算法和A*算法（1）啟發(fā)函數(shù)是對當前節(jié)點到達目標節(jié)點將來可能要付出的代價的估計。在全局擇優(yōu)和局部擇優(yōu)搜尋算法中，都沒有考慮從初始節(jié)點到當前節(jié)點已經(jīng)付出的實際代價。在很多實際問題中，已經(jīng)付出的實際代價是必需考慮的，如TSP問題等。將兩者同時考慮，用于指導搜尋的算法稱為A算法和A*算法。2023/2/28人工智能652.4.2啟發(fā)式搜尋的A算法和A*算法（2）1.A算法估價函數(shù)f（x）:為了防止在單獨利用啟發(fā)函數(shù)的時候誤入歧途，將啟發(fā)函數(shù)h（x）與代價函數(shù)g（x）相結(jié)合，即初始節(jié)點S0到達節(jié)點x處已付出的代價與節(jié)點x到達目標節(jié)點Sg的接近程度估計值總和。f（x）＝g（x）＋h（x）g（x）代價函數(shù)：初始節(jié)點S0到達節(jié)點x處已付出的代價，有利于搜尋縱向發(fā)展，提高搜尋效率，但影響完備性。h（x）啟發(fā)函數(shù)：節(jié)點x到達目標節(jié)點Sg的接近程度估計值。有利于搜尋橫向發(fā)展，提高搜尋的完備性，但影響搜尋效率。2.4.2啟發(fā)式搜尋的A算法和A*算法（3）代價g（x）的計算

g（x）表示從初始節(jié)點S0到節(jié)點x的代價：

g（S0）＝0

g（xj

）＝g（xi

）＋c（xi，xj）

其中，c（xi，xj）表示父節(jié)點xi到子節(jié)點xj的代價ADCEB464332323462344632C1B1D1D2E1C2E2D3C3B2E4E36B32023/2/28人工智能662.4.2啟發(fā)式搜尋的A算法和A*算法（4）對估價函數(shù)f（x）＝g（x）＋h（x）令其中的h（x）=0時，這時得到的是代價樹的非啟發(fā)式搜尋算法。按對節(jié)點的考察范圍不同，可分為兩種搜尋策略：分支界限法將全局擇優(yōu)搜尋算法中的h（x）替換為g（x），即可得到分支界限搜尋算法。瞎子爬山法將局部擇優(yōu)搜尋算法中的h（x）替換為g（x），即可得到瞎子爬山搜尋算法。2023/2/28人工智能67樹形圖樹式搜尋策略比較全局局部深度d(x)寬度優(yōu)先搜索深度優(yōu)先搜索啟發(fā)值h(x)全局擇優(yōu)搜索局部擇優(yōu)搜索代價值g(x)分支界限法瞎子爬山法范圍標準S0Sg23ab4615cdgfhijk5f543789h（x），有利于搜尋縱向發(fā)展，提高搜尋效率，但影響完備性。g（x），有利于搜尋橫向發(fā)展，提高完備性，但影響搜尋效率。窮舉式搜尋啟發(fā)式搜尋加權(quán)狀態(tài)圖搜尋2023/2/28人工智能692.4.2啟發(fā)式搜尋的A算法和A*算法（5）A算法步1把附有f（S0）的初始節(jié)點S0放入OPEN表中；步2若OPEN表為空，則搜尋失敗，退出；步3否則，移出OPEN表中第一個節(jié)點N放入CLOSED表中，并冠以依次編號n；步4若目標節(jié)點Sg＝N，則搜尋成功，利用CLOSED表中的返回指針找出S0到N的路徑即為所求解，退出。步5若N不行擴展，則轉(zhuǎn)步2；2.4.2啟發(fā)式搜尋的A算法和A*算法（6）步6否則，擴展N，生成一組子節(jié)點xi，計算f（xi），并對這組節(jié)點xi作如下處理：1）若xi是N的先輩節(jié)點，則刪除之。2）若xi存在于OPEN或CLOSED表中，也刪除之，但表明此時存在兩條初始節(jié)點S0到xi的路徑；假如新路徑較短，則修改xi節(jié)點的返回指針（指向N），并修改xi及其后裔節(jié)點和f值；同時若xi存在于CLOSED表中，則將其移出放入OPEN表重新考察。3）對其余子節(jié)點配上指向N的返回指針放入OPEN表。步7對OPEN表中全部節(jié)點按f值以升序排列，轉(zhuǎn)步2。2023/2/28人工智能702023/2/28人工智能712.4.2啟發(fā)式搜尋的A算法和A*算法（7）對A算法再限制其估價函數(shù)中的啟發(fā)函數(shù)h(x)滿足：對全部的節(jié)點x均有：h（x）h*（x）其中h*（x）是從節(jié)點x到目標節(jié)點的最小代價，這就稱為A*算法。A*算法也稱為最佳圖搜尋算法，利用A*算法，假如問題存在最優(yōu)解，就保證能找到最優(yōu)解。2023/2/28人工智能722.4.3A*算法在游戲中的應用（1）啟發(fā)式算法漸漸發(fā)展成為路徑搜尋算法的核心，除了A*算法以外，國內(nèi)外探討者還在此基礎上漸漸發(fā)展了很多其它智能算法，包括IDA*算法、D*算法等，它們的基本原理都借鑒了A*算法中的估價函數(shù)思想。目前，游戲業(yè)界的標準是運用A*算法或IDA*算法，A*算法一般要快一些，而IDA*算法則比A*算法要運用更少的內(nèi)存。2.4.3A*算法在游戲中的應用（2）假如游戲僅僅要求出從點A到達點B的一條最短路徑的話，那么運用A*算法，將h(x)設計為對x點到B點的最短路徑的估計就可以完成此任務；然而，真實游戲中往往還要考慮路上的障礙物、或者在從點A到點B的途中避開被看到或被射擊到、以及敵方的位置和火力線等。在游戲設計中，運用A*算法找尋路徑時，啟發(fā)函數(shù)h(x)的設計還須要考慮更多的因素，如路徑的距離、途中的障礙物、地形允許的行走速度、是否敵人視線與火力之下的位置、敵我雙方暴露的時間和次數(shù)、敵方的威逼是否動態(tài)的、有掩護物和隱身處的路徑等因素。2.4.3A*算法在游戲中的應用（3）比如：對那些暴露在敵方火力偵查或是覆蓋之下的位置增加其代價值，使得A*算法生成一條盡量避開敵人偵查或射擊的路徑；假如敵方的飛機處于被我方地對空導彈防衛(wèi)的區(qū)域，那么，同樣暴露20秒，是一次暴露20秒，還是分四次暴露，一次暴露5秒，明顯對我方來說代價是不一樣的；另外，敵方的威逼是靜態(tài)的或動態(tài)的，估價函數(shù)值計算出來也應當不同。當然，考慮更多的因素確定會增加代價計算量，所以，在實際當中，運用A*算法進行游戲設計時，還須要在獲得戰(zhàn)術(shù)實力和所付出的計算量之間做出權(quán)衡。2023/2/28人工智能752.5與或圖表示及搜尋技術(shù)2.5.1與或圖表示2.5.2與或樹的盲目搜尋2.5.3與或樹的啟發(fā)式搜尋2.5.1

與或圖表示（1）問題分解：在問題求解過程中，常常將一個困難的問題P分解為一組子問題，當這些子問題全部可解時，原問題P可解；任何一個子問題無解時，都將導致原問題P無解。即一個問題與一組子問題的“與”等價。如：保送探討生的條件是每門課程成果都在85分以上。問題變換：有時將一個困難的問題P變換為與之等價的一組子問題，其中任何一個子問題可解時，原問題P可解；全部子問題無解時，原問題P無解。即一個問題與一組子問題的“或”等價。如：保送探討生的條件中，要求英語成果是通過六級考試，或者通過GRE考試。與或圖：將問題對應節(jié)點，分解或變換關(guān)系對應邊，這樣，就可以將一個問題求解過程中的分解和變換過程表示為一棵與或圖。與狀態(tài)空間圖的意義不同，這里的與或圖對應的是問題空間圖。2023/2/28人工智能762.5.1

與或圖表示（2）與或圖的概念來源于問題求解中的分解和變換一個困難的問題P常常可以分解為與之等價的一組子問題P1，P2，…Pn，當這些問題全部可解時，問題可解；任何一個子問題無解時，都將導致原問題P無解。即一個問題與一組子問題的與等價。一個困難的問題P常?？梢苑謩e變換為與之等價的一組子問題P1，P2，…Pn，其中任何一個子問題可解時，問題可解；全部子問題無解時，原問題P無解。即一個問題與一組子問題的或等價。2.5.1

與或圖表示（3）例2.10猴子摘香蕉問題房間內(nèi)有一只猴子位于A處，有一只箱子位于B處，還有一架梯子位于C處，A到B的距離與A到C是距離相同，梯子和箱子的重量相同。屋頂上D處掛著一串香蕉，猴子爬到梯子上或箱子上都能摘到香蕉。2023/2/28人工智能782.5.1

與或圖表示（4）2023/2/28人工智能79定義五個動作：f1(x,y)：表示猴子從x處走到y(tǒng)處；f2(x,y)：表示猴子推箱子從x處走到y(tǒng)處；f3(x,y)：表示猴子搬梯子從x處走到y(tǒng)處；f4()

：表示登上箱子；f5()：表示登上梯子；f6()

：表示摘到香蕉；則猴子摘香蕉問題的分解變換過程可用如下與或圖表示：2023/2/28人工智能802.5.1

與或圖表示（5）例2.11證明四邊形全等。分析：連接BD，B′D′，原來問題可以分解為兩個子問題：

Q1：證明ΔABD≌ΔA′B′D′Q2：證明ΔBCD≌ΔB′C′D′原來問題可以分為兩個子問題解決。ABDCA′B′D′C′2.5.1

與或圖表示（6）問題Q1還可以再被分解為：

Q11

：證明AB＝A′B′Q12

：證明AD＝A′D′Q13

：證明∠A＝∠A′或

Q11′：證明AB＝A′B′Q12′：證明AD＝A′D′Q13′：證明BD＝B′D′問題Q2還可以再被分解為：

Q21

：證明BC＝B′C′Q22

：證明CD＝C′D′Q23

：證明∠C＝∠C′或

Q21′：證明BC＝B′C′Q22′：證明CD＝C′D′Q23′：證明BD＝B′D′′2023/2/28人工智能822.5.1

與或圖表示（7）將原問題用圖的形式表示如下：QQ1Q2Q11Q12Q13Q11'Q12'Q13'Q21Q22Q23Q21'Q22'Q23'弧線表示所連邊為“與”的關(guān)系不帶弧線的邊為或關(guān)系2.5.1

與或圖表示（8）例2.12梵塔問題。

有1、2、3號桿，1號桿自上而下串著從小到大的n個金盤，要把1號桿上的n個金盤移到3號桿上。移動金盤的規(guī)則是：一次只能移一個金盤；移動的過程中不允許大盤壓在小盤上。2023/2/28人工智能833123122.5.1

與或圖表示（9）(1,1,1)=>(3,3,3)(1,1,1)=>(1,1,3)(1,2,3)=>(1,2,2)(3,2,2)=>(3,2,1)(3,3,1)=>(3,3,3)(1,1,3)=>(1,2,3)(3,2,1)=>(3,3,1)(1,1,1)=>(1,2,2)(1,2,2)=>(3,2,2)(3,2,2)=>(3,3,3)三階梵塔問題的與或樹2023/2/28人工智能852.5.1

與或圖表示（10）與或圖的幾個概念：干脆可解的問題稱為本原問題。本原問題對應的節(jié)點稱為終止節(jié)點。無子節(jié)點的節(jié)點稱為端節(jié)點。子節(jié)點為與關(guān)系，則該節(jié)點為與節(jié)點。子節(jié)點為或關(guān)系，則該節(jié)點為或節(jié)點。與或圖一般表示問題的變換過程，就是從原問題動身，運用某些規(guī)則不斷的進行問題的分解（得到與分支）和變換（得到或分支），而得到一個與或圖，與或圖的節(jié)點一般代表問題，整個圖就表示問題空間。2023/2/28人工智能862.5.1

與或圖表示（11）與或圖也可以用三元組表示：（Q0,F,Qn）

Q0表示初始問題

F表示問題變換規(guī)則集

Qn表示本原問題集2.5.1

與或圖表示（12）節(jié)點的可解性判別：（1）終止節(jié)點是可解節(jié)點；（2）一個與節(jié)點可解，當且僅當其全部子節(jié)點可解；（3）一個或節(jié)點可解，只要其子節(jié)點至少有一個可解。（4）非終止節(jié)點的端節(jié)點是不行解節(jié)點；（5）一個與節(jié)點不行解，只要其子節(jié)點至少有一個不行解；（6）一個或節(jié)點不行解，當且僅當其全部子節(jié)點不行解。與或樹的解樹：由能判別（標記）根節(jié)點是可解節(jié)點的全部節(jié)點和邊所組成的子樹。2.5.1

與或圖表示（13）四邊形相等問題分解樹：2023/2/28人工智能882023/2/28人工智能892.5.2與或樹的盲目搜尋（1）--選學與或樹搜尋與狀態(tài)樹搜尋的不同之處在于：（1）搜尋過程中包含可解性標記過程。一旦生成已知可解或不行解的節(jié)點，須要向上標記其先輩節(jié)點的可解性，當根節(jié)點的可解性得到標記后，搜尋終止，依據(jù)根節(jié)點的可解性返回解樹或證明問題無解。（2）包含從OPEN表中刪除“具有可解或不行解先輩節(jié)點”的節(jié)點的過程。因為先輩節(jié)點的可解性或不行解性一旦確定之后，就不須要再通過其他子節(jié)點對它進行標記。2.5.2與或樹的盲目搜尋（2）2023/2/28人工智能902023/2/28人工智能912.5.2與或樹的盲目搜尋（3）1.廣度優(yōu)先搜尋算法：步1把初始節(jié)點S0放入OPEN表。步2把OPEN表中的第一個節(jié)點（記為節(jié)點N）取出放入CLOSED表，并冠以編號n。步3假如節(jié)點n可擴展，則作下列工作：(1)擴展節(jié)點N，將其子節(jié)點放入OPEN表尾部，并為每個子節(jié)點配置指向父節(jié)點的指針，以備標示過程中運用。(2)考查這些節(jié)點中是否有終止節(jié)點。若有，將它們放入CLOSED表，標示這些節(jié)點為可解節(jié)點，并用可解標示過程對其先輩節(jié)點中的可解節(jié)點進行標示。假如S0也被標示為可解節(jié)點，就得到解樹，搜尋成功，退出。(3)若S0不能確定為可解節(jié)點，則從OPEN表中刪除具有可解先輩節(jié)點。轉(zhuǎn)步2。2023/2/28人工智能922.5.2與或樹的盲目搜尋（4）步4假如節(jié)點N不行擴展，則作如下工作：（1）標示節(jié)點N為不行解節(jié)點。（2）應用不行解節(jié)點標示過程對節(jié)點N的先輩節(jié)點中不行解的節(jié)點進行標示。假如初始節(jié)點S0也被標示為不行解節(jié)點，則搜尋失敗，退出搜尋過程；（3）假如不能確定S0為不行解節(jié)點，則從OPEN表中刪去具有不行解先輩的節(jié)點。轉(zhuǎn)步2。2.5.2與或樹的盲目搜尋（5）例2.13與或樹的廣度優(yōu)先搜尋。與或樹如下圖。2023/2/28人工智能942.5.2與或樹的盲目搜尋（6）2023/2/28人工智能952.5.2與或樹的盲目搜尋（7）2.與或樹的深度優(yōu)先搜尋策略將與或樹的廣度優(yōu)先搜尋算法的步3中（1）做如下修改：步3假如節(jié)點N

可擴展，則做下列工作：（1）擴展節(jié)點N，將其子節(jié)點放入OPEN表首部，并為每個子節(jié)點配置指向父節(jié)點N的返回指針。2023/2/28人工智能962.5.3與或樹的啟發(fā)式搜尋--選學與或樹的啟發(fā)式搜尋也叫有序搜尋，其困難是：在與或樹的搜尋過程中，搜尋樹的生長方向是從根節(jié)點起先，自上而下進行的；而與或樹的解樹是由終止節(jié)點（可解節(jié)點）自下而上進行標記的。有代價時，代價的計算也是自下而上進行的；在搜尋沒到達終止節(jié)點和端節(jié)點之前，無法知道根節(jié)點和中間節(jié)點的實際代價，在與或樹的搜尋過程中，代價的計算方向與搜尋樹的生長方向相反。2.5.3與或樹的啟發(fā)式搜尋(1)盲目搜尋的特點搜尋從初始節(jié)點起先，先自上而下地進行搜尋，找尋終止節(jié)點及端節(jié)點，然后再自下而上地進行可解性標記，搜尋終止條件是初始節(jié)點被標記為可解節(jié)點或不行解節(jié)點。搜尋都是按確定路途進行的，選擇節(jié)點進行擴展時，只考慮位置，而沒考慮代價，因而求得的解樹不確定是代價最小的解樹，即不確定是最優(yōu)解樹。2.5.3與或樹的啟發(fā)式搜尋(2)有序搜尋為求得代價最小的解樹，在每次確定欲擴展的節(jié)點時，先往前多看幾步，計算擴展這個節(jié)點可能要付出的代價，并選擇代價最小的節(jié)點進行擴展，這種依據(jù)代價確定搜尋路途的方法稱為與或樹的有序搜尋。2.5.3與或樹的啟發(fā)式搜尋(3)解樹的代價（樹根的代價）狀態(tài)圖從初始節(jié)點計算代價。與或樹中解樹的代價從樹葉起先自下而上逐層計算而求得的。而解樹的根對應的是初始節(jié)點S0。這就是說，在與或樹的搜尋過程中，代價的計算方向與搜尋樹的生長方向相反。2.5.3與或樹的啟發(fā)式搜尋(4)解樹代價的計算方法g(x)表示節(jié)點x的代價，c(x,y)表示節(jié)點x到其子節(jié)點y的代價(即邊xy的代價)，則

(1)若x是終止節(jié)點，g(x)＝0；

(2)若x是或節(jié)點

(3)若x是與節(jié)點x，則有兩種計算公式。①和代價法②最大代價法

(4)對非終止的端節(jié)點x，g(x)＝∞2.5.3與或樹的啟發(fā)式搜尋(5)例2.15有代價的與或樹2023/2/28人工智能1022.5.3與或樹的啟發(fā)式搜尋(6)與或樹的啟發(fā)式搜尋也叫有序搜尋，其困難是：在與或樹的搜尋過程中，搜尋樹的生長方向是從根節(jié)點起先，自上而下進行的；與或樹的解樹是由終止節(jié)點（可解節(jié)點）自下而上進行標記的。有代價時，代價的計算也是自下而上進行的；在搜尋沒到達終止節(jié)點和端節(jié)點之前，無法知道根節(jié)點和中間節(jié)點的實際代價，在確定擴展哪些節(jié)點時只能利用啟發(fā)信息先估計其代價，選擇代價小的節(jié)點進行擴展。2023/2/28人工智能1032.5.3與或樹的啟發(fā)式搜尋（7）有序搜尋思路：（1）按擴展深度擴展節(jié)點，得到新的子節(jié)點x，用估價函數(shù)來計算x的代價g(x)稱為x的估計值。（2）按代價計算方法向上倒推計算x的父節(jié)點及先輩節(jié)點y的代價，稱為y的倒推值，并用y的倒推值代替y原來的估計值。（3）重復步（1）、（2），直到擴展到終止節(jié)點或端節(jié)點，能夠標記初始節(jié)點的可解性為止。不斷用節(jié)點的倒推值代替其估計值的依據(jù)是：越接近終止節(jié)點，估計越精確。2.5.3與或樹的啟發(fā)式搜尋（8）希望樹有序搜尋的目的是求得最優(yōu)解樹，這就要求在搜尋過程中任一時刻求出的部分解樹都是代價最小的。每次選擇欲擴展的節(jié)點是都應當選擇有希望成為最優(yōu)解樹一部分的節(jié)點進行擴展。由這些節(jié)點及其先輩節(jié)點所構(gòu)成的與或樹都有可能成為最優(yōu)解樹的一部分，稱為希望樹。搜尋過程中希望樹也是不斷變更的。2023/2/28人工智能1052.5.3與或樹的啟發(fā)式搜尋（9）希望樹的定義如下：（1）初始節(jié)點S0在希望解樹中。（2）節(jié)點x在希望解樹中，則確定有：假如x是具有子節(jié)點的或節(jié)點，則它具有最小代價的子節(jié)點確定在希望解樹中。假如x是具有子節(jié)點的與節(jié)點，則它的全部子節(jié)點都在希望解樹中。與或樹的有序搜尋過程就是找尋希望樹的過程，隨著擴展深度的增加，希望樹也會不斷變更。2023/2/28人工智能1062.5.3與或樹的啟發(fā)式搜尋（10）與或樹的有序搜尋過程步1把初始節(jié)點S0放入OPEN表中；步2求出希望樹T：依據(jù)當前搜尋樹中節(jié)點的代價值求出以S0為根的希望樹T；步3依次把OPEN表中T的末端節(jié)點N選出放入CLOSED表中；步4假如節(jié)點N是終止節(jié)點，則做下列工作：（1）標記N為可解節(jié)點；（2）對T應用可解標記過程，標記N的先輩節(jié)點；（3）若初始節(jié)點S0被標記為可解節(jié)點，則T就是最優(yōu)解樹，成功退出；（4）否則，從OPEN表中刪去具有可解先輩的全部節(jié)點；2023/2/28人工智能1072.5.3與或樹的啟發(fā)式搜尋（11）步5假如節(jié)點N是不行擴展節(jié)點，則做下列工作：（1）標記N為不行解節(jié)點；（2）對T應用不行解標記過程，標記N的先輩節(jié)點；（3）若初始節(jié)點S0被標記為不行解節(jié)點，則失敗退出；（4）否則，從OPEN表中刪去具有不行解先輩的全部節(jié)點；步6假如節(jié)點N可擴展，則：（1）擴展節(jié)點N，產(chǎn)生N的全部子節(jié)點。并把這些子節(jié)點都放入OPEN表中，并為每一個子節(jié)點配置指向父節(jié)點（節(jié)點N）的指針；（2）用估價函數(shù)計算這些子節(jié)點的估計值，并計算其先輩節(jié)點的倒推值；步7否則，轉(zhuǎn)步2。2.5.3與或樹的啟發(fā)式搜尋（12）2023/2/28人工智能1092.5.3與或樹的啟發(fā)式搜尋（13）例2.16與或樹有序搜尋過程。（邊代價按1算）設初始節(jié)點為S0，每次擴展兩層，并設S0經(jīng)擴展后得到(a)所示的與或樹（a）用和代價法計算872023/2/28人工智能1102.5.3與或樹的啟發(fā)式搜尋（14）擴展右邊的子樹：7671182023/2/28人工智能1112.5.3與或樹的啟發(fā)式搜尋（15）2638112023/2/28人工智能1122.5.3與或樹的啟發(fā)式搜尋（16）32238S可解，搜尋結(jié)束2023/2/28人工智能1132.6博弈樹及搜尋技術(shù)2.6.1博弈樹2.6.2博弈樹搜尋2.6.3剪枝技術(shù)在博弈問題中的應用2023/2/28人工智能1142.6.1博弈樹（1）1.博弈問題的狀態(tài)空間博弈問題中，棋局用狀態(tài)表示，對弈雙方隨意合法地走一步，都使棋局從一個狀態(tài)變到另一個狀態(tài)，所以，全部合法的走步就是操作。開局是初始狀態(tài)，終局可能有多種，站在某一方的角度，有勝局、和局和負局之分。博弈樹：博弈問題的狀態(tài)空間就是以狀態(tài)為節(jié)點、以合法走步為邊的一個樹形圖，稱為博弈樹。2.6.1博弈樹（2）2.博弈樹的特點假設博弈過程是由雙方來完成的，稱我方為MAX方，對方為MIN方。在博弈樹中，存在與、或兩種節(jié)點：與節(jié)點：博弈過程中，對手（MIN）每走一著棋（半個回合），都力圖干擾MAX的選擇，使其偏離取勝的目標。因此，站在我方（MAX）的立場上，由MIN出棋的節(jié)點具有與節(jié)點的性質(zhì)?；蚬?jié)點：博弈過程中，我方（MAX）每走一著棋（半個回合），都力圖使自己通往取勝的目標。MAX出棋的節(jié)點具有或節(jié)點的性質(zhì)。博弈的過程是雙方輪番走步，因此，博弈樹中的與、或節(jié)點就會按層交替出現(xiàn)。2023/2/28人工智能1152023/2/28人工智能1162.6.2博弈樹搜尋（1）二人零和、全信息、非偶然博弈：“二人零和”是指對弈雙方的利益是完全沖突的，利益之和恒久為零；博弈的結(jié)果有三種狀況：MAX方勝，MIN方敗；MAX方敗，MIN方勝；雙方平局。很多博弈問題都滿足“二人零和”這一條件，如國際象棋。但囚徒逆境是經(jīng)典的非零和博弈例子?！叭畔ⅰ笔侵冈趯倪^程中，當前的格局及雙方對弈的歷史是公開的?！胺桥既恍浴笔侵笇碾p方的每一步選擇都是“理智”的，即在實行行動前，都要依據(jù)自己的靜態(tài)估值函數(shù)（啟發(fā)函數(shù)）進行得失分析，選取對自己最有利而對對方最不利的對策，不存在“碰運氣”式的隨機因素。2023/2/28人工智能1172.6.2博弈樹搜尋（2）1.微小極大化分析靜態(tài)估值：為了找到當前的最佳走步，一般要向前看幾個甚至多個回合。為此，須要依據(jù)問題的特性信息（來自于博弈者的閱歷）定義一個靜態(tài)估值函數(shù)，估價當前博弈樹末端節(jié)點的得分，稱為格局的靜態(tài)估值。倒推值：當末端節(jié)點的估值計算出來后，再向上推算出各節(jié)點的得分，稱為倒推值。微小極大化分析法：對與節(jié)點求微小值、對或節(jié)點求極大值計算各先輩節(jié)點倒推值的方法。2023/2/28人工智能1182.6.2博弈樹搜尋（3）用微小極大分析方法求最佳走步的具體過程是：首先，按擴展深度限制（回合數(shù)）擴展節(jié)點，對末端節(jié)點求靜態(tài)估值；然后，對內(nèi)部節(jié)點按微小極大化分析方法求倒推值；最終，依據(jù)根節(jié)點的倒推值確定一個最佳走步；重復上面分析過程，直到擴展到終局。每擴展一次，對內(nèi)部節(jié)點都用新的倒推值代替原來的靜態(tài)估值或原來的倒推值。假如一個行動方案能獲得較大的倒推值，則它就是當前最好的行動方案。2023/2/28人工智能1192.6.2博弈樹搜尋（4）例2.17用微小極大分析方法求最佳走步。2023/2/28人工智能1202.6.2博弈樹搜尋（5）例2.18一字棋游戲。設有如圖3—19(a)所示的九個空格，由A，B二人對弈，輪到誰走棋誰就往空格上放一只自己的棋子，誰先使自己的棋子構(gòu)成“三子成一線”誰就取得了成功。ba2023/2/28人工智能1212.6.2博弈樹搜尋（6）棋盤上的整行、整列和對角線稱為路（線）。假如一條路上只有i方的棋子，則稱該路為留給i方的路。假如一條路上只有i方的k個棋子，則稱該路為留給i方的k階路。估價函數(shù)定義h1(x)如下：設棋局為P，估價函數(shù)為e(P)。(1)若P是A必勝的棋局，則h1(x)==+∞。(2)若P是B必勝的棋局，則h1(x)==-∞。(3)若x是輸贏未定的棋局，則h1(x)=“×”方的路數(shù)－“O”方的路數(shù)2023/2/28人工智能1222.6.2博弈樹搜尋（7）上圖（a）所示棋局，h1（P)=6-4=2對圖（b）所示棋局，h1(p)=6-4=2（a）和（b）具有對稱性，可以作為一個棋局。baab（a）（b）2023/2/28人工智能1232.6.2博弈樹搜尋（8）用這樣的靜態(tài)估值可得第一步的微小極大分析圖，其中擴展深度為2aaababa10ba-101babababa－100－2－1ababab21baab－1－2112023/2/28人工智能1242.6.2博弈樹搜尋（9）ba10abaaabaababa000babababababaabbababaabab0baabababbaab121abbababababababababaabba210111baabbaabbaabaabbaabb100001baab111012023/2/28人工智能1252.6.2博弈樹搜尋（10）2.-剪枝α剪枝：對于一個與節(jié)點