人工智能chp3

1、(AI)第三章 可分解產(chǎn)生式系統(tǒng)搜索策略3.1 與或圖搜索3.2 與或圖的啟發(fā)式搜索算法AO*3.3 博弈樹的搜索參考書：人工智能基礎 高 濟、朱淼良 高等教育出版社1第三章 可分解產(chǎn)生式系統(tǒng)搜索策略 3.1 與或圖搜索一般與或圖:k-連接符是從一個父結(jié)點指向一組k個后繼結(jié)點的結(jié)點集。右圖中結(jié)點n0有兩個連接符：1-連接符指向n1,2-連接符指向n4,n5。沒有父結(jié)點的結(jié)點稱為根結(jié)點，沒有任何后繼結(jié)點的結(jié)點稱為端結(jié)點，端結(jié)點分為死結(jié)點和葉結(jié)點。 一個可分解的產(chǎn)生式系統(tǒng)規(guī)定了一個隱含的與或圖。初始數(shù)據(jù)庫對應初始結(jié)點，規(guī)則對應兩結(jié)點間的連接弧。滿足系統(tǒng)結(jié)束條件的數(shù)據(jù)庫就是葉結(jié)點，控制系統(tǒng)負責搜索從

2、初始結(jié)點到目標結(jié)點的解圖。2第三章 可分解產(chǎn)生式系統(tǒng)搜索策略 3.1 與或圖搜索n0n1n3n4n2n5n6n7n8n1n3n5n6n7n8n0n5n4n7n8n0n5n4n7n8n0tt3第三章 可分解產(chǎn)生式系統(tǒng)搜索策略無環(huán)圖解圖遞歸定義：與或圖G從n到結(jié)點集N的解圖記為G，是G的子圖。滿足:(1) 若n是N的一個元素，則G由單一結(jié)點組成； (2) 若n有一指向n1,nk的外向連接符K,使從每一ni到N有一解圖，則G由結(jié)點n,連接符K,及n1,nk中每一個結(jié)點到N的解圖所組成； (3) 否則n到N不存在解圖。4第三章 可分解產(chǎn)生式系統(tǒng)搜索策略*解圖另外一種定義方法可解結(jié)點：1. 葉結(jié)點是可解

3、結(jié)點；2. 若一結(jié)點有或子結(jié)點，那么該結(jié)點可解當且僅當至少有一個子結(jié)點是可解結(jié)點；3. 若一結(jié)點有與子結(jié)點，那么該結(jié)點可解當且僅當其所有子結(jié)點都是可解結(jié)點。解圖：與或圖的解圖是它的一個包含初始結(jié)點的子圖，該子圖的所有結(jié)點都是可解結(jié)點，且若n屬于該子圖，又不是葉結(jié)點，則子圖必須包含n的k連接弧的全部子結(jié)點。ttt5第三章 可分解產(chǎn)生式系統(tǒng)搜索策略具有耗散值的解圖耗散值遞歸定義:(1) 若nN,則k(n,N)=0；(2) 若n有一個外向連接符指向后繼結(jié)點n1,ni,且設該連接符的耗散值為Cn,則 k(n,N)=Cn+ k(n1,N) +k(ni,N)，具此前述三個解圖的耗散值計算分別為：8、7、5

4、。具有最小耗散值的路徑是搜索算法尋找的最佳解路徑，記為h*(n0)=5?？山饨Y(jié)點: (1) 葉結(jié)點是可解結(jié)點；(2) n有與子結(jié)點，則n可解同一規(guī)則下的所有與子結(jié)點可解；(3) n有或子結(jié)點，則n可解至少有一或子結(jié)點可解。可解標志過程：按照某種搜索算法尋找與或圖的最佳解圖過程中，標記可解結(jié)點的過程稱為可解標志過程。6第三章 可分解產(chǎn)生式系統(tǒng)搜索策略耗散值計算的直觀方法: 如左圖是一個與或圖,右圖是它的一個解圖。解圖耗散值的計算入土所示。 一般葉結(jié)點的耗散值為0。n0n1n3n4n2n5n6n7n8n1n3n5n6n7n8n0tt00226787第三章 可分解產(chǎn)生式系統(tǒng)搜索策略 3.2 與或圖的

5、啟發(fā)式搜索算法AO*AO*算法：(1) G:=s,計算q(s)=h(s),If Goal(s) Then M(s,solved);(2) Until s to be Solved, do: (3) Begin (4) G:=Find(G); 根據(jù)連接符找出一待擴展的局部解圖G(?)(5) n:=G; 從G中選任一結(jié)點為當前結(jié)點(?)(6) Expand(n),生子結(jié)點集nj,G:=Add(nj,G),算q(nj)=h(nj),nj不屬于G If Goal(nj) Then M(nj,Solved); Solved表示可解標志操作(7) S:=n; 建立含n的單一結(jié)點集S8第三章 可分解產(chǎn)生式系

6、統(tǒng)搜索策略(8)Until S 為空，do(9) Begin (10) Remove(m,S),mc不屬于S;m的子結(jié)點mc不在S中(11) 修改m的耗散值q(m),對m指向n1i,nki計算每個qi，qi(m)=Ci+q(n1i)+q(nki),q(m):=minqi(m); 加指針到q(m)所取的那個min qi(m)上，刪除不一致的舊指針 If M(nji,Solved) Then M(m,Solved); 若所有i可解，則m可解(12) If M(m,Solved)(q(m)q0(m) Then Add(ma,S);若m可解或新耗散值與原值不同，則把m的所有先輩ma加入S中(13) e

7、nd (14)end9第三章 可分解產(chǎn)生式系統(tǒng)搜索策略算法應用舉例：對于前節(jié)的與或圖定義了某個啟發(fā)式函數(shù)，并各結(jié)點給出估計值，看應用AO*算法求最佳解樹的搜索過程。h(n0)=3,h(n1)=2,h(n2)=4,h(n3)=4,h(n4) =1,h(n5)=1,h(n6)=2,h(n7)=h(n8)=0，其中n7、n8是目標結(jié)點(葉結(jié)點)，應用算法求解的四個循環(huán)過程如圖。n0n1n3n4n2n5n6n7n8n1n3n5n6n7n8n0n1n5n4n0n2n1n5n45n04n344n4n2554400554004tt10第三章 可分解產(chǎn)生式系統(tǒng)搜索策略AO*與算法A的區(qū)別: (1) AO*評價

8、函數(shù)只考慮h(n)分量，因算法是自底向上的耗散值操作，局部耗散值的比較是在s處，獲得估計效果，沒必要計算g的值; (2) k-連接符連接的父結(jié)點是否可解與每個子結(jié)點都相關(guān)，因此對父結(jié)點可解與否看每個k-連接符總體耗散值的大小; (3) AO*算法只適應于無環(huán)圖的搜索，否則耗散值遞歸計算不收斂，因此在算法中必須檢查新生成的結(jié)點已在圖中時是否是正被擴展的先輩結(jié)點; (4) A算法中設有Open和Closed表，而算法AO*中只有一個結(jié)構(gòu)G，他代表到目前止已明顯生成的部分搜索圖，圖中每一個結(jié)點的h(n)值是估計最佳圖，而不是估計解路徑。11第三章 可分解產(chǎn)生式系統(tǒng)搜索策略AO*算法的基本特點: (1

9、) AO*向下擴展結(jié)點的過程; (2) 逆向的耗散值計算傳遞過程; (3) 逆向的可解標志過程; (4) 一個結(jié)點的h(n)值是估計最佳圖，而不是估計解路徑。12第三章 可分解產(chǎn)生式系統(tǒng)搜索策略 3.2 與或圖的啟發(fā)式搜索算法AO*算法應用若干問題: (1) 在算法的6步若不存在后繼結(jié)點，則到11步時賦予其一個高的q值使其在以后的擴展中不被列入侯選結(jié)點集； (2) 第5步選擇G中的待擴展結(jié)點一般是選那些最可能導致該局部解圖耗散值發(fā)生較大變化的結(jié)點，也使能夠及時修改局部解圖的標記； (3) 與A算法類似，若sN存在解圖，當h(n)h*(n)且h(n)滿足單調(diào)限制條件時,AO*一定可找到最佳解圖,

10、而h(n)=0時AO*變?yōu)閷挾葍?yōu)先搜索算法。13第三章 可分解產(chǎn)生式系統(tǒng)搜索策略 3.3 博弈樹搜索Grundy博弈：一堆數(shù)目為N的錢幣由兩位選手輪流分堆，每個選手每次只把其中某一堆分成數(shù)目不等的兩小堆，直到不能再分為數(shù)目不等的兩堆時認輸。下面是對應的產(chǎn)生式系統(tǒng)描述。綜合數(shù)據(jù)庫：無序數(shù)字序列x1,xn表示n堆錢幣不同的個數(shù)，M表示對應的選手標志，組合(x1,xn,M)表示了選手走步的狀態(tài)。規(guī)則：If (x1,xn,M)(xi=y+z,yz) Then (x1,xi-1,y,z,xi+1,xn,M)Grundy博弈問題搜索的狀態(tài)空間圖。14第三章 可分解產(chǎn)生式系統(tǒng)搜索策略 控制策略的思想是在Mi

11、n走出第一步后Max必須考慮應付的所有招法。因此含有Max的結(jié)點是與結(jié)點。相應的含有Min的結(jié)點看成或結(jié)點。(7,Min)(6,1,Max)(5,2,Max)(4,3,Max)(5,1,1,Min)(4,2,1,Min)(3,2,2,Min)(3,3,1,Min)(4,1,1,1,Max)(3,2,1,1,Max)(2,2,2,1,Max)(3,1,1,1,1,Min)(2,2,1,1,1,Min)(2,1,1,1,1,1,Max)15第三章 可分解產(chǎn)生式系統(tǒng)搜索策略本章小節(jié): (1) 可分解產(chǎn)生式系統(tǒng)求解問題相當于對一個隱含的與或圖進行搜索。初始數(shù)據(jù)庫對應根結(jié)點，規(guī)則對應k-連接弧，目標數(shù)據(jù)庫對應一組葉結(jié)點?？刂撇呗允菑某跏冀Y(jié)點找到到這組葉結(jié)點的解圖。解圖的耗散值由遞歸定義計算； (2)