




版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
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
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 唐山市常態(tài)化管理辦法
- 地鐵防水施工管理辦法
- 如何開展科研管理辦法
- 科技轉移機構管理辦法
- 肥胖中醫(yī)辨證課件
- 野外測量培訓課件
- 供電公司青年培訓課件
- 房石鎮(zhèn)九年級數學試卷
- 福建閩侯小升初數學試卷
- 定興期末考試數學試卷
- 2025年廣東省高考政治試卷真題(含答案解析)
- 公園亭子拆除方案(3篇)
- 2024年宜昌市檢察機關招聘檢察輔助人員筆試真題
- Unit 2 Home Sweet Home 第2課時(Section A Pronunciation 2a-2e) 2025-2026學年人教版英語八年級下冊
- 2025年中國繼電保護裝置行業(yè)市場調查、投資前景及策略咨詢報告
- 2025-2030年中國非球面玻璃鏡片行業(yè)市場現(xiàn)狀供需分析及投資評估規(guī)劃分析研究報告
- 中國文化概論-華南師范大學中國大學mooc課后章節(jié)答案期末考試題庫2023年
- GB/T 18451.1-2022風力發(fā)電機組設計要求
- 援絕神丹_集成良方三百種_方劑加減變化匯總
- 公路工程通用表格
- 中藥飲片GMP認證檢查指導原則
評論
0/150
提交評論