1、第二章與或圖搜索問題22.1基本概念2.2 AO*算法2.3博弈樹捜索C f (D. C (M, B f (M,(B,L)B)M)B, M)2A基本概念與節(jié)點：復合數(shù)據(jù)庫分解后產(chǎn)生若干分量，這些分量稱為對應于其父節(jié)點的與節(jié)點或節(jié)點：分量數(shù)據(jù)庫經(jīng)規(guī)則作用后產(chǎn)生一組節(jié)點這些節(jié)點稱為對應于該分量的或節(jié)點伊：初始數(shù)據(jù)庫= （C, B, Z ,目標Dg二（兒MM） 僅含M 規(guī)則集R, R1：R2:Rb：R4:AND節(jié)點尼AND U A9bUAUN必陽口朗晶(D . L )(U B D( L )(M , U )M )( U )伏態(tài)空冋m是(C、B、Z)叫與節(jié)點呢？還是(Ch (Bh (Z)?是指下面的J個

2、是與關(guān)系是關(guān)于父節(jié)點的與節(jié)點HHffiHnm34注h 個節(jié)點可以是某個節(jié)點的與節(jié)點，但同時又是另外一個節(jié)點的或節(jié)點.超圖：由節(jié)點集和若干連接符組成的圖廉一連接符：從一個父節(jié)點指向一組K個后繼節(jié)點的K條連線.如1_連接符內(nèi)的K條邊彼此之間是與關(guān)系.注意： 小一個連接符之間的所有邊:任何2個連接符之間是或的關(guān)系. 一個連接符是一條路.-SIWHUA UNW豆RSTMRESS例題:4如何在上面的超圖中找出一個解圖n根節(jié)點, 葉節(jié)點:不存在任何父節(jié)點的節(jié)點 不存在任何后繼節(jié)點的節(jié)點筒夠ch學岀版社ghuaunwBSJtyRss-6求解圖的方法X （從節(jié)點n到目標節(jié)點集N的解圖 從節(jié)點“開始.正確選擇一

3、個外向連接符就是按照現(xiàn)有連接符的箭頭方向去找不能逆著箭頭走 從該連接符指向的毎個后繼節(jié)點出發(fā)繼續(xù)選擇一個外向連接符 依次類推，直到由此產(chǎn)生的每個后繼節(jié)點都是N中的一個元素為止nn解圖1解圖23M2HUA UNW宜y-無環(huán)解圖的構(gòu)成定義一個與或圖(：中從節(jié)點n到節(jié)點集N的 解圖記為心如果節(jié)點n是N中一個元索，則G由 單一元素組成如果節(jié)點n有一個指向節(jié)點集 nl, n2. nk 的外向連接符K,使得從每個 ni到N有一個解圖(i=U.k).則(T由 節(jié)點11、連接符K及nl,n2. nk 中的 每個節(jié)點到N的解圖組成2否則從I，到N不存在解圖.NNN凍紂字dbHH3皿忖UA UNWERS)工y-解

4、圖的耗散值計算：設K連接符的耗散值為K, G的耗散值為若n是N的一個元素 MijK(n,N)=O若n有一個到解圖中后維節(jié)點集 B1.I12ni )的外向連接符，設該連接 符的耗散值為Cm則K(iiN) = Cn+ K(iibN)+ K(ii2JS)+ .-+K(ni8nWMGRPA uzyfRSn、朗Ed左圖耗散值 + Kfns) - 2+ l+KliisNi + 2+K(n7，N) 2+ 1+ 2+K(n7*N) +K(ng,N| + Z+KdhN) +K(ii(,N)-2+ 1+ 2+ 0+ + 2+ 0+ 0 -7g能解節(jié)點定義： 終節(jié)點是能解節(jié)點. 如果非終節(jié)點有“或”子節(jié)點，當且僅當

5、其子節(jié)點至少有一個能解，則該 非終節(jié)點是能解節(jié)點。 如果非終節(jié)點有“與”子節(jié)點，當且僅當英子節(jié)點都能解，則該非終節(jié)點 是能解節(jié)點.不能解節(jié)點定義： 沒有后裔的非終節(jié)點是不能解節(jié)點（該節(jié)點是葉節(jié)點但不在N中）. 如果非終節(jié)點有“或”子節(jié)點，當且僅當所有子節(jié)點都不能解，則該非終 節(jié)點是不能解節(jié)點. 如果菲終節(jié)點有“與”子節(jié)點，至少有一個子節(jié)點不能解，則該非終節(jié)點是22.2AO*算法1建立一個搜索圖G,僅包含初始節(jié)點爲S的耗徴值為qG)=h),如果S是終 節(jié)點，則標記S為SOLVED2. t ntil s已標記SOI-VED do:3- begin4.6.7.8從S出發(fā)沿著有標記的連接持找出一個G的

6、待擴充的局部解圖G 任取2中一個非終節(jié)點n作為當前節(jié)點.擴丸節(jié)點,生成n的全部子節(jié)點并將其加入到G中.對于未在G中出現(xiàn) 過的子節(jié)點Hj,計算其耗散值q(llj)=h(iij)；對于子節(jié)點中屬于終節(jié)點者, 標記SOLVED并賦值為0建丑一個僅包含節(jié)點n的單一節(jié)點集S Until S為空do;12.12CONTIME11I_AUNyER沁必9.10.It13.begin從S中移出這樣節(jié)Am.該m節(jié)點的子節(jié)點不在S中D計算修改m耗散值q(m):對扌旨尙節(jié)點集t恂刀 的每個連接 符i,分別計算 q/mkCkqUm)* q(n2i)+. + q(ii|o)令：q(m)= min qm)即：取耗散值最小妁

7、連接符的耗散值作為q(m) 標記該具有最小耗散值的連接符，如果憑來對m的茉個連接符所做的標記與新標記的連接符不同，則保留新標記，去悴原來標記. 如果該連接符的所有后繼節(jié)點梆巳標記SOLVED,則此m節(jié)點標記 SOLVED如果m巳標記SOLVED或者m修正后的耗散值與原來的耗It值不同，則 將m的所有父節(jié)點加入到S中，這些父節(jié)點必須通過有標記的連按符與 節(jié)點m相連end 14. end位置2個標記：連按符標記和節(jié)點標記.特征13例題，(預先給出了各節(jié)點h值的估計值，實際的h值在搜索中計算得出)循環(huán)hh (no) =Co+h (n,) =1+2=3 h (nQ =Co+h (nJ +h (n4)

8、：取 q(no)= min 3, V節(jié)點m無標記 Ah(no)=0. h (n,) =2, h (盹) h (皿)=4 h (114)= h (njR h (ng) =2. h(n7)= h(n8)=0N= 擴充節(jié)點n, 得到n“%并加入G中，計算各節(jié)點耗散值得：h(ni)=2, h(115)=1. h(n4)=l.組成單一節(jié)點集S二% 內(nèi)循環(huán)：取出節(jié)點%有2個外向連接符，分別計算：(L連接符) =2+l+l=4(2_連接符)4 = 3.標記選定的1_連接符 節(jié)點不能標記.內(nèi)循環(huán)結(jié)束14詹華:二字出;K迷h S亞做邊24 UZERS( TYARMS Z外循環(huán)：沿標記取當前節(jié)點n=ni擴充節(jié)點I

9、h，得到循環(huán)2：q(ni)= min 5.rb并加入G中，計算耗散值得* h(n=4, h(rh)=4 組成單一節(jié)點|feS=n,內(nèi)循環(huán)：取出節(jié)點w叫有2個外向連接符，分別計算： h (n|)=Ci+h (ng) =1+4=5(左 1_連接符)h(ni)=C,+h (nj) =1+4=5(右 1_ 連按符)5 = 5.按照自然排序標記選定的左1.連接符取*節(jié)點112無標記節(jié)點叫不能標記節(jié)點叫的h值由原來的2修改為5, A將叫的父節(jié)點no加入到單一節(jié)點集S中 重新計算h(no)h (no)=q,+h (n,)=l+5=6(1_連接符)h(no)=Co+h (ns) +旗) =2+l + l=4(

10、2_連接符)取q(no)=niin 6, 4)= 4,取消廉來口。-* n】標記，莖新標記2_連接符V節(jié)點m，%無標記節(jié)點不能標記，內(nèi)循環(huán)結(jié)束15循環(huán)3：內(nèi)循環(huán)*內(nèi)循環(huán):沿標記取當前節(jié)點n=n5，擴充節(jié)點“5 .得到Ih，Hr并加入G中，計算耗散值得：h(n6)=2. h(n7)=0 , h(n8)=0組成單一節(jié)點集S二%* n?. rig是終節(jié)點，節(jié)點n?, tig取出節(jié)點嗎，嗎有2個外向連接符，分別計算： h (nJ 毛+h (聰)=1+2=3(1_謹接符)h(n5)=C5+h(n (n=2+0 +0 =2 (2_連接符) 3. 2 = 2,記選定的2_連接符標記節(jié)點嗎并將加的父節(jié)點no加

11、入到S中外循環(huán):/取 q(n5)= min*-*節(jié)點n?. m有標記 取0,計算h (no) =Co+h (ni)=1+5=6(1_3$ 接符)h(no)=Co+h(n5)+h(th)=2+2+1=5 (2_連接符)/.取q(no)=min 6, 5 = 5,原來連接不變節(jié)點Ib有標記但是m無標記 A節(jié)點n。不能標記，內(nèi)循環(huán)結(jié)束16外循環(huán)*循環(huán)4:內(nèi)循環(huán)塔沿標記取當前節(jié)點n二n54擴充節(jié)點比，得皿，m ,計算耗散值得：h (ng) =2, h(18)=0組成單一節(jié)點集$=114取節(jié)點山，叫有2個外向連接符，計算：hg)毛+h(n5)=1+2 =3 (左 1_連接符)h (np =C+h (ng

12、) =1+0 =2 (右 1 _連接符)取 q(n4)= min 節(jié)點n?, ng有標記內(nèi)循環(huán)：取no，計算h (no)=Co+h (ni)=l+5= (1_連接符)h(no)=Co+h (ng) (%) =2+2+1=5(2_連接符):.取q(no)= min (6, 5) = 5,原來連接不變V節(jié)點加，m有標記/.標記節(jié)點no，內(nèi)、外循環(huán)結(jié)束，算法結(jié)束1732=標記節(jié)點叫并將叫的父節(jié)點no加入到S中2,記選定的右1_違接符-i給出每次循環(huán)后的搜索圖，并給出IK某問題狀態(tài)圖如圖4所示。假定k連接符的耗散值為k。各節(jié)點的h值假 定為：h(A)=3,h(B)=2,h(C)=6, h(D)=3,h

13、(E)=4. h(F)=2, hG)=3, h(ll=h(l)=O (目標節(jié)點)，用算法求解該問題， 求得的解圖。_y廠f-2 d .-Ir19IBM的深藍正在與下棋的卡斯帕羅夫rCT ：5 Ai96年2月第一次比賽結(jié)杲：深藍:勝、負、平、平、負、負97年5月第二次比賽結(jié)杲：“深藍:負、勝、平、平、平、勝2023IBM的“深藍”（續(xù)2）J深藍的技術(shù)指標:32 個 C PU-每個CPU有16個協(xié)處理器-每個CPU冇256M內(nèi)存1991 年，1999年，2001 年，-每個CPU的處理速度為200丿j步/秒“邦里茨”問世“弗里茨”升級為更弗里茨(Deep Fri“更弗里茨”更新了程序，擊敗了卡斯帕

14、羅犬和阿南徳，以及除了克拉姆尼克之外的所育排名 吐界詢I位的棋于2002年10刀，“更刃:里茨”與克拉姆尼克在巴林進 行“人機大戰(zhàn)”，思考速度為每秒600萬步，雙方4比 4戰(zhàn)平2003年12月“更年少者”與卡斯帕羅夫舉行人機 對抗，雙方3比3戰(zhàn)平23博弈樹搜索博弈樹搜索是什么呢？實際上就是一種下棋，博弈就是下棋博弈問題有很多, 在這里主要是以下棋的方式為主，比如，中國象棋，國際象棋，圍棋尊尊這類下 棋程序，這類下棋程序有什么特點呢？1、博弈問題特點雙人.2個人玩一人一步：雙方輪流走.沒有連走情況，雙方信息完備雙方看到的信息是一樣的，比如中國瑕棋來說，甲方在棋上 看到的與乙方看到的相同零和：雙方

15、是個敵對的關(guān)系，走一步棋對自己好的話，對對方就不好.沒有 說步棋對雙方都好的，或沒有說一步棋對雙方都不好的ggHUAUNgB沁朗電232.舉例.分錢幣的侃子問描述T有一摞錢幣由2個人輪流將它分成2堆，第一個人先將這堆錢幣分成2 堆，第二個人將從這2堆中選擇一堆，然后再分成2堆，第一個人然后又從3堆中 選擇一堆，然后再分成2堆，變成4堆如何決定勝負：一旦一選手先無法把錢幣再分成不相等的兩堆時，就得認輸對方對方對方先走(4,3)的 UNyERS疔、朋. I、(5,2)、(44J4)(321,1)(2,2,2,1)對方(2,234,1)(2X144,1)注問題規(guī)模比較小, 枚錢幣不對方怎走,（$3,

16、1）我方必勝可以把所有狀態(tài)搜索出來看有沒有決勝的策略-對于7 我方都可以走成（4, 2. 1）這個狀態(tài)，從而取得勝利.25414 UNyERST、朋丄3、博弈問題存在的問存在問JR：是不是對于任何一個博弈問題都可以得到這樣一個對象策略呢？不是因為問 題太復雜是不可能搜索出所有的狀態(tài)，就拿中國象棋來說.一盤棋平均走50 步，總狀態(tài)數(shù)大是10假設1毫秒走一步地話，大約需要10倔年。解決問題：通過索的辦法，一個水平高的棋子，為什么高7除了各種各樣的經(jīng)驗外， 他會算，如何算呢？并不是一下就能看出勝負，而是在當前狀態(tài)下，這步 棋我方有幾種走法，對方有幾種走法，這樣反復的看下去幾步后，他選擇出 他認為一個

17、比較好的，就是這樣子，那么，能不能把這種思想應用到真實的 博弈中，這就是我們下面將要研究的內(nèi)容.;別紂字出籃%假定：4、極小極大過程通過例子來看被稱為極小極大的*過程圓罔表赤對方在此下戰(zhàn) 方框表赤我方在此下棋532-O30AK6任何一種棋局有_種估計的辦法，估計棋局格局好 壞的辦法，假定能夠算，而且算呢？是能夠用數(shù)字來表示28端節(jié)點數(shù)字是用評估函數(shù)計算得到的.其他節(jié)點是不能用評估函數(shù)計算的.評估函數(shù)大于仇 對我方有利對方不利，越大對我方越有利評估函數(shù)小于山 對我方不利，對方有利，越大對我方越不利-” f超紂:字出版迪ggHUA uzy理SB朗氐圓圈衷示對方 方框表示X我方If6O4端節(jié)點數(shù)字是

18、用評估函數(shù)計算得到的，其他節(jié)點是不能用評估函數(shù)計算的TSlNGnUA UNST、丘題圓圈衷示對方 方框表示*我方w32極小極大的索過程問題: 搜*了兒步節(jié)點仍然足很幺.這卑毎一步只產(chǎn)卞2或3個狀態(tài).對中國象機 來講，每個狀態(tài)都冇十兒種走法，這樣搜索幾步，會產(chǎn)牛一個爆炸戌的狀態(tài)。 把捜常樹的牛成和格局佔值分開進行-亍致了低效率神態(tài)估值和倒推fff汁仲問題解決:將不必塑的分支剪切和搜索樹的牛成和格局佔值緊密結(jié)介，就足卜面講的 a -P劉枝。詹華:穴學出磁比=8恥加4姑必RSL315. G -P剪枝定義：極大節(jié)點的下界是a,（因為極大節(jié)點每次都選擇函數(shù)值極大的，那它 實際上是極大節(jié)點的值是一直增加的，所以我們選擇一個下界）極小節(jié) 點的上界*P剪枝的條件X后輩節(jié)點的P 和先節(jié)點的a值時.a剪枝.后輩節(jié)點的a 旳先節(jié)點的P值時.P剪枝.例子，通過例子我們學習一下a-P剪枝是如何進行的，為了使生成和估計過程R密結(jié)合.采用有界度優(yōu)先策略進行捜索 生成到一定深度節(jié)點時.立即計算評價函數(shù)，非終結(jié)點有條件確定倒推值時就立即計算值SJTY極大結(jié)點極小結(jié)點5-華/川勺蟲 /V氏 C3 3 3 -3A9 O030-235如何剪？a,這時達到了搜索深度限制從左到右,達到搜索深度.就可以進行剪枝了.搜索的順序：從f開始，到d、b、遇到分支我們就擴展左邊節(jié)點然后再擴展右邊節(jié)點.33淸華加出