人工智能chp3

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

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

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

4、。具有最小耗散值的路徑是搜索算法尋找的最佳解路徑，記為h*(n0)=5。可解結點: (1) 葉結點是可解結點；(2) n有與子結點，則n可解同一規(guī)則下的所有與子結點可解；(3) n有或子結點，則n可解至少有一或子結點可解?？山鈽酥具^程：按照某種搜索算法尋找與或圖的最佳解圖過程中，標記可解結點的過程稱為可解標志過程。6第三章 可分解產(chǎn)生式系統(tǒng)搜索策略耗散值計算的直觀方法: 如左圖是一個與或圖,右圖是它的一個解圖。解圖耗散值的計算入土所示。 一般葉結點的耗散值為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中選任一結點為當前結點(?)(6) Expand(n),生子結點集nj,G:=Add(nj,G),算q(nj)=h(nj),nj不屬于G If Goal(nj) Then M(nj,Solved); Solved表示可解標志操作(7) S:=n; 建立含n的單一結點集S8第三章 可分解產(chǎn)生式系

6、統(tǒng)搜索策略(8)Until S 為空，do(9) Begin (10) Remove(m,S),mc不屬于S;m的子結點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ù)，并各結點給出估計值，看應用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是目標結點(葉結點)，應用算法求解的四個循環(huán)過程如圖。n0n1n3n4n2n5n6n7n8n1n3n5n6n7n8n0n1n5n4n0n2n1n5n45n04n344n4n2554400554004tt10第三章 可分解產(chǎn)生式系統(tǒng)搜索策略AO*與算法A的區(qū)別: (1) AO*評價

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

9、) AO*向下擴展結點的過程; (2) 逆向的耗散值計算傳遞過程; (3) 逆向的可解標志過程; (4) 一個結點的h(n)值是估計最佳圖，而不是估計解路徑。12第三章 可分解產(chǎn)生式系統(tǒng)搜索策略 3.2 與或圖的啟發(fā)式搜索算法AO*算法應用若干問題: (1) 在算法的6步若不存在后繼結點，則到11步時賦予其一個高的q值使其在以后的擴展中不被列入侯選結點集； (2) 第5步選擇G中的待擴展結點一般是選那些最可能導致該局部解圖耗散值發(fā)生較大變化的結點，也使能夠及時修改局部解圖的標記； (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的結點是與結點。相應的含有Min的結點看成或結點。(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ù)庫對應根結點，規(guī)則對應k-連接弧，目標數(shù)據(jù)庫對應一組葉結點?？刂撇呗允菑某跏冀Y點找到到這組葉結點的解圖。解圖的耗散值由遞歸定義計算； (2)