人工智能導(dǎo)論課件：第三章 與或圖的搜索

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

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

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

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

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

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

7、, do: Begin REMOVE(m, S),mc(S);這個(gè)m的子結(jié)點(diǎn)mc應(yīng)不在S中。 修改m的耗散值q(m): 對(duì)m指向節(jié)點(diǎn)集(n1i,n2i,nki)的每個(gè)連接符i分別計(jì)算qi, qi (m)=Ci+q(n1i)+q(nki), q(m):= minqi(m); 加指針到minqi(m)的連接符上,或把指針修改到minqi(m)的連接符上,即原來(lái)指針與新確定的不一致時(shí)應(yīng)刪去. 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é)點(diǎn)ma,添加到S 中. （修正向上傳遞）,若該連接符的所有子節(jié)點(diǎn)都是能解的,則m也標(biāo)上能解.,對(duì)m的i個(gè)連接符，取計(jì)算結(jié)果最小的哪個(gè)耗散值為q（m）,耗散值修正,AO*算法說(shuō)明,算法劃分成兩個(gè)階段： 1）是一個(gè)自上而下的圖生長(zhǎng)過(guò)程，先通過(guò)有標(biāo)記的連接符，找到目前為止最好的一個(gè)局部解圖， 2）是一個(gè)自下而上的耗散值修正計(jì)算，連接符的標(biāo)記以及結(jié)點(diǎn)的能解標(biāo)記。,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 設(shè)

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

10、部圖耗散值發(fā)生較大變化的結(jié)點(diǎn)先擴(kuò)展（因?yàn)檫x擇這個(gè)結(jié)點(diǎn)先擴(kuò)展，會(huì)促使及時(shí)修改局部解圖的標(biāo)志。,3.3 博弈樹(shù)搜索,博弈問(wèn)題 雙人 一人一步 雙方信息完備 (對(duì)壘雙方看到的信息是一樣的，不存在一方看到另一方看不到的情況） 零和（對(duì)一方有利的走棋，對(duì)另一方是不利的，不存在對(duì)雙方均有利或者均無(wú)利的棋）,Grundy博弈（分錢(qián)幣游戲）,有一堆數(shù)目為N的錢(qián)幣，有兩個(gè)選手輪流分堆，要求每個(gè)選手每次只把其中某一堆分成數(shù)目不相等的兩小堆（如果分的相等的話，輸） 以7個(gè)錢(qián)幣為例。,分錢(qián)幣問(wèn)題,（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）,對(duì)方先走,我方必勝,分錢(qián)幣問(wèn)題狀態(tài)空間圖,中國(guó)象棋,一盤(pán)棋平均走50步，總狀態(tài)數(shù)約為10的161次方。 假設(shè)1毫微秒走一步，約需10的145次方年。 結(jié)論：不可能窮舉。 目標(biāo)：尋找一步好棋，等對(duì)手回敬后在考慮尋找另一步好棋這種實(shí)際可行的策略。,1，極小極大搜索過(guò)程（1）,是博弈樹(shù)搜索的基本方法，目前常用的-剪枝搜索方法，也從極小極大搜索過(guò)程發(fā)展而來(lái)。 假定一個(gè)評(píng)價(jià)函數(shù)可以對(duì)所有的棋局進(jìn)行評(píng)價(jià)： 當(dāng)評(píng)價(jià)函數(shù)0時(shí),表示對(duì)我方有利，越大越有利； 當(dāng)評(píng)價(jià)函數(shù)0時(shí),表示對(duì)對(duì)方有利，越

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

13、計(jì)算得到，其他的使用倒推方法取值,算法的三個(gè)階段,用寬度優(yōu)先法生成規(guī)定深度的全部博弈樹(shù)，然后對(duì)其端結(jié)點(diǎn)計(jì)算其靜態(tài)估計(jì)函數(shù)。 從底向上逐級(jí)求非端結(jié)點(diǎn)的倒推估計(jì)值，直到求出初始結(jié)點(diǎn)的倒推值f(s)為止。 再由f(s)選出相對(duì)較好的走步。,算法,極大極小過(guò)程MINIMAX： 1. T:=(s, MAX)，OPEN:=(s)，CLOSED:=( );開(kāi)始時(shí)樹(shù)由初始節(jié)點(diǎn)構(gòu)成，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 計(jì)算f(ni); ni達(dá)到深度k,計(jì)算各端節(jié)點(diǎn)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é)點(diǎn)均有值,則

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

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

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

18、上例中，實(shí)際上是把生成和倒推估值結(jié)合起來(lái)進(jìn)行，再根據(jù)一定的條件判定，有可能盡早剪掉一些無(wú)用的分支，但不影響效果，這就是-過(guò)程的基本思想。,-剪枝,極大節(jié)點(diǎn)的下界為。 極小節(jié)點(diǎn)的上界為。,剪枝,剪枝：若任一極小值層節(jié)點(diǎn)的值它任一先輩極大值層節(jié)點(diǎn)的值， 即 后輩節(jié)點(diǎn)的值祖先節(jié)點(diǎn)的值時(shí)， 則終止該極小值層中這個(gè)MIN節(jié)點(diǎn)以下的搜索，并設(shè)置這個(gè)MIN節(jié)點(diǎn)的最終的倒推值為。(極小值層節(jié)點(diǎn)的剪枝),剪枝,剪枝：若任一極大值層節(jié)點(diǎn)的值大于或等于它任一先輩極小值層節(jié)點(diǎn)的值， 即（后繼層）（先輩層） 則終止該極大值層中這個(gè)MAX節(jié)點(diǎn)以下的搜索過(guò)程，并設(shè)置這個(gè)MAX節(jié)點(diǎn)的最終倒推值為。 (極大值層節(jié)點(diǎn)的剪枝),剪枝的條件： 后輩節(jié)點(diǎn)的值祖先節(jié)點(diǎn)的值時(shí)， 剪枝 后輩節(jié)點(diǎn)的值祖先節(jié)點(diǎn)的值時(shí)， 剪枝 簡(jiǎn)記為： 極小極大，剪枝 極大極小，剪枝,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