華工人工智能老師上課課件第二章.ppt

1、1,第二章 與或圖搜索問題,2,2.1 基本概念,與或圖是一個超圖，節(jié)點間通過連接符連接。 K-連接符：,3,耗散值的計算,k(n, N) = Cn+k(n1, N)+k(ni, N) 其中：N為終節(jié)點集 Cn為連接符的耗散值,4,目標,目標,初始節(jié)點,解圖：,5,能解節(jié)點,終節(jié)點是能解節(jié)點 若非終節(jié)點有“或”子節(jié)點時，當且僅當其子節(jié)點至少有一能解時，該非終節(jié)點才能解。 若非終節(jié)點有“與”子節(jié)點時，當且僅當其子節(jié)點均能解時，該非終節(jié)點才能解。,6,不能解節(jié)點,沒有后裔的非終節(jié)點是不能解節(jié)點。 若非終節(jié)點有“或”子節(jié)點，當且僅當所有子節(jié)點均不能解時，該非終節(jié)點才不能解。 若非終節(jié)點有“與”子節(jié)點

2、時，當至少有一個子節(jié)點不能解時，該非終節(jié)點才不能解。,7,普通圖搜索的情況,f(n) = g(n) + h(n) 對n的評價實際是對從s到n這條路徑的評價,n,s,8,與或圖: 對局部圖的評價,目標,目標,初始節(jié)點,a,b,c,9,兩個過程,圖生成過程，即擴展節(jié)點 從最優(yōu)的局部途中選擇一個節(jié)點擴展 計算耗散值的過程 對當前的局部圖從新計算耗散值,10,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 設：K連接符 的耗散值為K,11,初始節(jié)點,n0,n1(2),n4(1),n5

3、(1),紅色：4 黃色：3,12,目標,目標,初始節(jié)點,n0,n1,n2,n3,n4,n5,n6,n7,n8,紅色：4 黃色：6,n1,n2(4),n3(4),5,13,目標,目標,初始節(jié)點,n0,n1,n2,n3,n4,n5,n6,n7,n8,紅色：5 黃色：6,2,14,目標,目標,初始節(jié)點,n0,n1,n2,n3,n4,n5,n6,n7,n8,紅色：5 黃色：6,2,1,15,2.3 博弈樹搜索,博弈問題 雙人 一人一步 雙方信息完備 零和,16,分錢幣問題,（7）,（6,1）,（5,2）,（4,3）,（5,1,1）,（4,2,1）,（3,2,2）,（3,3,1）,（4,1,1,1）,（

4、3,2,1,1）,（2,2,2,1）,（3,1,1,1,1）,（2,2,1,1,1）,（2,1,1,1,1,1）,對方先走,我方必勝,17,中國象棋,一盤棋平均走50步，總狀態(tài)數(shù)約為10的161次方。 假設1毫微秒走一步，約需10的145次方年。 結(jié)論：不可能窮舉。,18,1，極小極大過程,0,-3,3,-3,-3,-2,1,-3,6,-3,0,3,1,6,0,1,1,極大,極小,a,b,19,-剪枝,極大節(jié)點的下界為。 極小節(jié)點的上界為。 剪枝的條件： 后輩節(jié)點的值祖先節(jié)點的值時， 剪枝 后輩節(jié)點的 值祖先節(jié)點的值時， 剪枝 簡記為： 極小極大，剪枝 極大極小，剪枝,20,8,6,-3,1,4,5,3,-3,5,0,-剪枝（續(xù)）,3,-3,0,2,2,-3,0,-2,3,0,9,-3,0,0,-3,0,3,3,0,5,4,1,1,-