人工智能導論課件：第三章 與或圖的搜索

1、上次課程回顧,盲目搜索策略 啟發(fā)式搜索策略,第三章 與或圖的搜索,2 3 1 8 4 7 6 5,1,2,3,4,5,6,7,8,9,a,b,c,d,目標,或,或,或,引入,上章介紹了狀態(tài)空間問題以及搜索算法，其特點是： 結點的后繼結點是或的關系，只要一個后繼節(jié)點得以求解，該節(jié)點也就被求解。 從初始結點到目標結點，求解的是一條路徑，也就是結點的序列。,引入,方法1 滿足子問題1 一個問題有多個解法 方法2 滿足子問題2 方法3 滿足子問題3 一個結點是否被求解，取決于該結點的部分或者全部結點（與的關系）被求解，而非一個后續(xù)結點被求解 用與或圖表示。,“或”,“與”,搜索從初始節(jié)點到一組終節(jié)點集

2、N的一個解圖。,與或圖的搜索,與的關系（超弧線，連接符）,根結點：沒有任何父結點的結點。,端結點：沒有任何后繼結點的結點。,3.1 基本概念,與或圖是一個超圖，節(jié)點間通過連接符連接。（其特例是普通圖) K-連接符： 是從一個父結點指向一組k個后繼結點的結點集。,耗散值的計算,k(n, N) = Cn+k(n1, N)+k(ni, N) 其中：N為終節(jié)點集 Cn為連接符的耗散值 * 明顯的，若n是N的一個 元素，則k(n, N) =0,解圖,在普通圖中，從初始結點到目標結點，求解的是一條解路徑。 與或圖中某一個結點n到目標結點集N的解圖類似于普通圖中的一條解路徑。 解圖的求法是：從節(jié)點n開始，正

3、確選擇一個外向連接符，再從該連接符所指的每一個后繼結點出發(fā)，繼續(xù)選一個外向連接符，如此進行下去直到由此產生的每一個后繼節(jié)點成為集合N中的一個元素為止。 具有最小耗散值的解圖稱為最佳解圖。,目標,目標,初始節(jié)點s,解圖：,能解節(jié)點（SOLVED),終節(jié)點是能解節(jié)點 若非終節(jié)點有“或”子節(jié)點時，當且僅當其子節(jié)點至少有一個能解時，該非終節(jié)點才能解。 若非終節(jié)點有“與”子節(jié)點時，當且僅當其子節(jié)點均能解時，該非終節(jié)點才能解。,不能解節(jié)點(UNSOLVED),沒有后裔的非終節(jié)點是不能解節(jié)點。 若非終節(jié)點有“或”子節(jié)點，當且僅當所有子節(jié)點均不能解時，該非終節(jié)點才不能解。 若非終節(jié)點有“與”子節(jié)點時，當至少有

4、一個子節(jié)點不能解時，該非終節(jié)點才不能解。,第10次課 10月07日,上次課程回顧,與或圖搜索:搜索從初始節(jié)點到一組終節(jié)點集N的一個解圖。 對于與或圖搜索，是通過對局部圖的評價來選擇待擴展的節(jié)點。 解圖的求法是：從節(jié)點n開始，正確選擇一個外向連接符，再從該連接符所指的每一個后繼結點出發(fā)，繼續(xù)選一個外向連接符，如此進行下去直到由此產生的每一個后繼節(jié)點成為集合N中的一個元素為止。 具有最小耗散值的解圖稱為最佳解圖。 能解節(jié)點 不能解節(jié)點,與或圖的啟發(fā)式搜索算法AO*,啟發(fā)式與或圖搜索過程和普通圖類似，也是通過評價函數f(n)來引導搜索過程。 對于與或圖，由于局部圖有多個葉結點，不能象普通圖那樣，通過

5、對某一個結點的評價來實現(xiàn)對整個局部圖的評價。 對于與或圖搜索，是通過對局部圖的評價來選擇待擴展的節(jié)點。,普通圖的情況,f(n) = g(n) + h(n) 表面上是對結點n的評價，實際上是對從s到目標結點（通過n）的這條路徑的評價。,n,s,與或圖: 對局部圖的評價,目標,目標,初始節(jié)點,a,b,c,把普通圖的思想應用到與或圖中，對解圖進行評價，解圖相當于解路徑。紅色和藍色都是局部圖，具體選擇那條路徑，選擇f值最小的。,有與的關系，有或的關系，評價起來復雜一些,AO*算法,過程AO*: 建立一個搜索圖G，G:=s，計算q(s)=h(s)，IF GOAL(s) THEN M(s, SOLVED)

6、； Until s已標記為SOLVED, do: Begin G:=FIND(G)； n:=G中的任一非終節(jié)點（選一個非終節(jié)點作為當前節(jié)點）。 EXPAND(n),生成子節(jié)點集ni，其中niG， G:=ADD(ni,G),計算q(ni)=h(ni)，IF GOAL(ni) THEN M(ni, SOLVED);,開始時圖G只包括s，耗散值估計為h(s)，若s是終節(jié)點,則標記上能解。,根據連接符標記（指針）找出一個待擴展的局部解圖G,對G中未出現(xiàn)的子結點添加到G中, 并計算其耗散值，若有終節(jié)點則加能解標記。,圖生成過程,S:=n;建立含n的單一節(jié)點集合S.（待修正的節(jié)點集合） Until S為空

7、, do: Begin REMOVE(m, S),mc(S);這個m的子結點mc應不在S中。 修改m的耗散值q(m): 對m指向節(jié)點集(n1i,n2i,nki)的每個連接符i分別計算qi, qi (m)=Ci+q(n1i)+q(nki), q(m):= minqi(m); 加指針到minqi(m)的連接符上,或把指針修改到minqi(m)的連接符上,即原來指針與新確定的不一致時應刪去. IF M(nji,SOLVED) THEN M(m, SOLVED),(j=1,k） IF M(m, SOLVED)(q(m) q0(m) THEN ADD(ma, S); end (與9匹配) end (與3

8、匹配),m 能解或修正的耗散值與 原先估算q0不同,則把m的 所有先輩節(jié)點ma,添加到S 中. （修正向上傳遞）,若該連接符的所有子節(jié)點都是能解的,則m也標上能解.,對m的i個連接符，取計算結果最小的哪個耗散值為q（m）,耗散值修正,AO*算法說明,算法劃分成兩個階段： 1）是一個自上而下的圖生長過程，先通過有標記的連接符，找到目前為止最好的一個局部解圖， 2）是一個自下而上的耗散值修正計算，連接符的標記以及結點的能解標記。,AO*算法舉例,其中： h(n0)=3 h(n1)=2 h(n2)=4 h(n3)=4 h(n4)=1 h(n5)=1 h(n6)=2 h(n7)=0 h(n8)=0 設

9、：K連接符 的耗散值為K,紅色：4 黃色：3,1次循環(huán)之后,目標,目標,初始節(jié)點,n0,n1,n2,n3,n4,n5,n6,n7,n8,紅色：4 藍色：6,n1,5,2次循環(huán)之后,目標,目標,初始節(jié)點,n0,n1,n2,n3,n4,n5,n6,n7,n8,紅色：5 藍色：6,2,3次循環(huán)之后,目標,目標,初始節(jié)點,n0,n1,n2,n3,n4,n5,n6,n7,n8,紅色：5 藍色：6,2,1,4次循環(huán)之后,兩個過程,圖生成過程，即擴展節(jié)點 從最優(yōu)的局部圖中選擇一個節(jié)點擴展 計算耗散值的過程 對當前的局部圖重新計算耗散值,對于2次循環(huán)中，先擴展結點n4還是n5好呢？ 一般選擇一個最可能導致該局

10、部圖耗散值發(fā)生較大變化的結點先擴展（因為選擇這個結點先擴展，會促使及時修改局部解圖的標志。,3.3 博弈樹搜索,博弈問題 雙人 一人一步 雙方信息完備 (對壘雙方看到的信息是一樣的，不存在一方看到另一方看不到的情況） 零和（對一方有利的走棋，對另一方是不利的，不存在對雙方均有利或者均無利的棋）,Grundy博弈（分錢幣游戲）,有一堆數目為N的錢幣，有兩個選手輪流分堆，要求每個選手每次只把其中某一堆分成數目不相等的兩小堆（如果分的相等的話，輸） 以7個錢幣為例。,分錢幣問題,（7）,（6,1）,（5,2）,（4,3）,（5,1,1）,（4,2,1）,（3,2,2）,（3,3,1）,（4,1,1,

11、1）,（3,2,1,1）,（2,2,2,1）,（3,1,1,1,1）,（2,2,1,1,1）,（2,1,1,1,1,1）,對方先走,我方必勝,分錢幣問題狀態(tài)空間圖,中國象棋,一盤棋平均走50步，總狀態(tài)數約為10的161次方。 假設1毫微秒走一步，約需10的145次方年。 結論：不可能窮舉。 目標：尋找一步好棋，等對手回敬后在考慮尋找另一步好棋這種實際可行的策略。,1，極小極大搜索過程（1）,是博弈樹搜索的基本方法，目前常用的-剪枝搜索方法，也從極小極大搜索過程發(fā)展而來。 假定一個評價函數可以對所有的棋局進行評價： 當評價函數0時,表示對我方有利，越大越有利； 當評價函數0時,表示對對方有利，越

12、小越有利。,極小極大搜索過程（2）,假定雙方都是對弈高手，在決定走棋時，會盡可能多看幾步，并都選評價函數有利的走棋。 極小極大搜索過程模擬人下棋的思考過程,策略,極小極大搜索策略是考慮雙方對弈若干步之后，從可能的走步中選一個相對較好的走法來走，即在有限的搜索深度范圍內進行求解。 定義靜態(tài)估計函數f, 以便對棋局作出優(yōu)劣估值，主要對端結點的“價值”進行度量。 f0, 表對我方有利，f0,表對方有利，f=0,表勢均力敵；f=,表我方勝，f=- 表對方勝,1，極小極大過程,0,-3,3,-3,-3,-2,1,-3,6,-3,0,3,1,6,0,1,1,極大,極小,a,b,端結點給出數字使用靜態(tài)函數f

13、計算得到，其他的使用倒推方法取值,算法的三個階段,用寬度優(yōu)先法生成規(guī)定深度的全部博弈樹，然后對其端結點計算其靜態(tài)估計函數。 從底向上逐級求非端結點的倒推估計值，直到求出初始結點的倒推值f(s)為止。 再由f(s)選出相對較好的走步。,算法,極大極小過程MINIMAX： 1. T:=(s, MAX)，OPEN:=(s)，CLOSED:=( );開始時樹由初始節(jié)點構成，OPEN表只含有S. 2. LOOP1: IF OPEN =( ) THEN GO LOOP2; 3. n:=FIRST(OPEN)，REMOVE(n,OPEN)，ADD(n,CLOSED);將n放到CLOSED表的前面， 4. I

14、F n可直接判定為贏, 輸或平局 THEN f(n):= -0，GO LOOP1 ELSE EXPAND(n)ni， ADD (ni ，T) IF dni k THEN ADD(ni, OPEN) ,GO LOOP1 ELSE 計算f(ni); ni達到深度k,計算各端節(jié)點f值.,算法(續(xù)）,5. LOOP2：IF CLOSED=NIL,THEN GO LOOP3 ELSE nd=FIRST(CLOSED); 6.IF(nd MAX) (f(nci MIN)有值) THEN f(nd):=maxf(nci),REMOVE(nd，CLOSED), GO LOOP2; 若MAX所有子節(jié)點均有值,則

15、該MAX取其極大值. ELSE IF(nd MIN) (f(nci MAX)有值) THEN f(nd):=minf(nci),REMOVE(nd，CLOSED), GO LOOP2; 若MIN所有子節(jié)點均有值，則該MIN取其極小值. 7. GO LOOP2; 8.LOOP3:IF f(s)NIL THEN EXIT(END M(Move,T) ; s有值,或則結束或標記走步。,算法的一點說明,對手回應后，再以當時的狀態(tài)作為起始狀態(tài)s，重復調用該過程。 原理性的，對復雜的問題不實用的,舉例九宮格棋牌,在九宮格棋盤上，兩選手（MAX和MIN）輪流在棋牌中擺各自的棋子（一次一枚），誰先取得三子一線

16、的結果就獲勝。 設MAX用（）表示，MIN用（ O ）表示，f(p)表示對格局p的評價值。 若p對任何一方都不是獲勝的格局，則 f(p)=(所有空格都放上MAX的棋子之后，MAX的行，列，對角線成三子一線的總和)-(所有空格都放上MIN的棋子之后，MIN的行，列，對角線成三子一線的總和),f(p)的計算,若當前的格局p如圖： 所有空格都放上MAX的棋子之后，MAX的行，列，對角線成三子一線的情況（總數=6）,f(p)的計算,若當前的格局p如圖： 所有空格都放上MIN的棋子之后，MIN的行，列，對角線成三子一線的情況（總數=4） 則f(p)=6-4=2,一字棋第1階段的搜索樹,最好走棋是中間位置

17、,引入：-剪枝,MINMAX過程是把搜索樹的生成和棋局估值兩個過程分開進行： 即先生成全部的搜索樹，然后再進行端節(jié)點靜態(tài)估值和倒推值計算， 這會導致效率大大降低（缺點）。 考慮：把生成和倒推估計結合在一起，再根據一定的條件，盡早剪除一些無用的分支- -過程的思想。,回顧：極小極大過程,0,-3,3,-3,-3,-2,1,-3,6,-3,0,3,1,6,0,1,1,極大,極小,a,b,端結點給出數字使用靜態(tài)函數f計算得到，其他的使用倒推方法取值,回顧：極小極大過程,0,-3,3,0,3,0,極大,極小,a,b,端結點給出數字使用靜態(tài)函數f計算得到，其他的使用倒推方法取值,-搜索過程,可以看到，在

18、上例中，實際上是把生成和倒推估值結合起來進行，再根據一定的條件判定，有可能盡早剪掉一些無用的分支，但不影響效果，這就是-過程的基本思想。,-剪枝,極大節(jié)點的下界為。 極小節(jié)點的上界為。,剪枝,剪枝：若任一極小值層節(jié)點的值它任一先輩極大值層節(jié)點的值， 即 后輩節(jié)點的值祖先節(jié)點的值時， 則終止該極小值層中這個MIN節(jié)點以下的搜索，并設置這個MIN節(jié)點的最終的倒推值為。(極小值層節(jié)點的剪枝),剪枝,剪枝：若任一極大值層節(jié)點的值大于或等于它任一先輩極小值層節(jié)點的值， 即（后繼層）（先輩層） 則終止該極大值層中這個MAX節(jié)點以下的搜索過程，并設置這個MAX節(jié)點的最終倒推值為。 (極大值層節(jié)點的剪枝),剪枝的條件： 后輩節(jié)點的值祖先節(jié)點的值時， 剪枝 后輩節(jié)點的值祖先節(jié)點的值時， 剪枝 簡記為： 極小極大，剪枝 極大極小，剪枝,0, (2) 0,(3),5,(4)=0, (5) 0,(6),-3,(7) -3,(8) =0, (9) 0,(10),3,(11) =3,(12) 3,(13) =0, (14) 0,(15),5,(16) 5,(17),4,(18) 4,(19),1,(20) =1,(21) 1