人工智能4與或圖搜索ppt課件.ppt

《人工智能4與或圖搜索ppt課件.ppt》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。

1、第三章與或圖的搜索目標目標初始節(jié)點與或圖（樹）表示問題三解梵塔問題ABC123三解梵塔問題(1,1,1)→(3,3,3)(1,1,1)→(1,2,2)(1,2,2)→(3,2,2)(3,2,2)→(3,3,3)(1,1,1)→(1,1,3)(1,1,3)→(1,2,3)(1,2,3)→(1,2,2)(3,2,2)→(3,2,1)(3,2,1)→(3,3,1)(3,3,1)→(3,3,3)(1,1,1)A,B,C3.1與或圖初始節(jié)點與或圖目標目標初始節(jié)點基本概念與或圖是一個超圖，節(jié)點間通過連接符連接。K-連接符：…...K個與或耗散值的計算k(

2、n,N)=Cn+k(n1,N)+…+k(ni,N)其中：N為終節(jié)點集Cn為連接符的耗散值…...i個nn1n2ni目標目標初始節(jié)點解圖：能解節(jié)點終節(jié)點是能解節(jié)點若非終節(jié)點有“或”子節(jié)點時，當且僅當其子節(jié)點至少有一能解時，該非終節(jié)點才能解。若非終節(jié)點有“與”子節(jié)點時，當且僅當其子節(jié)點均能解時，該非終節(jié)點才能解。不能解節(jié)點沒有后裔的非終節(jié)點是不能解節(jié)點。若非終節(jié)點有“或”子節(jié)點，當且僅當所有子節(jié)點均不能解時，該非終節(jié)點才不能解。若非終節(jié)點有“與”子節(jié)點時，當至少有一個子節(jié)點不能解時，該非終節(jié)點才能解。3.2與或圖啟發(fā)式搜索算法AO*目標目標初始節(jié)

3、點與或圖的啟發(fā)式搜索算法AO*算法105-106兩個過程：圖生成過程，即擴展節(jié)點計算耗散值的過程AO*算法舉例其中：h(n0)=3h(n1)=2h(n2)=4h(n3)=4h(n4)=1h(n5)=1h(n6)=2h(n7)=0h(n8)=0設：K連接符的耗散值為K目標目標初始節(jié)點n0n1n2n3n4n5n6n7n8目標目標初始節(jié)點n0n1n2n3n4n5n6n7n8初始節(jié)點n0n1(2)n4(1)n5(1)紅色：4=1+1+1+1黑色：3=2+1目標目標初始節(jié)點n0n1n2n3n4n5n6n7n8初始節(jié)點n0n4(1)n5(1)紅色：4黑色

4、：6n1n2(4)n3(4)5目標目標初始節(jié)點n0n1n2n3n4n5n6n7n8紅色：5黑色：6初始節(jié)點n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)2目標目標初始節(jié)點n0n1n2n3n4n5n6n7n8紅色：5黑色：6初始節(jié)點n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)213.3博弈樹(Gametree)搜索3.3博弈樹(Gametree)搜索20世紀60年代，研制出的西洋跳棋和國際象棋的博弈程序達到了大師級的水平。1958約翰?麥卡錫提出博弈樹搜索算法1997年，IB

5、M公司研制的“深藍”國際象棋程序，采用博弈樹搜索算法，該程序戰(zhàn)勝了國際象棋世界冠軍卡斯帕羅夫。1.概述博弈問題特點：雙人對弈，輪流走步。信息完備，雙方所得到的信息是一樣的。零和，即對一方有利的棋，對另一方肯定是不利的，不存在對雙方均有利或無利的棋。1.概述博弈的特性兩個棋手交替地走棋；比賽的最終結果，是贏、輸和平局中的一種；可用圖搜索技術進行，但效率很低；博弈的過程，是尋找置對手于必敗態(tài)的過程；雙方都無法干預對方的選擇。1.概述2.Grundy博弈下棋的雙方是對立的，命名博弈的雙方，一方為“正方”，這類節(jié)點稱為“MAX”節(jié)點；另一方為“反方”

6、，這類節(jié)點稱為“MIN”節(jié)點。正方和反方是交替走步的，因此MAX節(jié)點和MIN節(jié)點會交替出現(xiàn)。2.Grundy博弈Grundy博弈是一個分錢幣的游戲。有一堆數(shù)目為N的錢幣，由兩位選手輪流進行分堆，要求每個選手每次只把其中某一堆分成數(shù)目不等的兩小堆。例如，選手甲把N分成兩堆后，輪到選手乙就可以挑其中一堆來分，如此進行下去，直到有一位選手無法把錢幣再分成不相等的兩堆時就得認輸。2.Grundy博弈設初始狀態(tài)為(7，MIN)，建立問題的狀態(tài)空間圖，圖中所有終結點均表示該選手必輸?shù)那闆r，取勝方的目標是設法使棋局發(fā)展為結束在對方走步時的終結點上。（7）（

7、6,1）（5,2）（4,3）（5,1,1）（4,2,1）（3,2,2）（3,3,1）（4,1,1,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）對方-min先走我方-max勝ABC2.Grundy博弈有向圖中有四個出度為零的結點:A,B,C結點A是MAX(我方)的搜索目標，而結點B，C則為MIN(對方)的搜索目標。2.Grundy博弈搜索策略要考慮的問題是：對MIN走步后的每一個MAX結點，必須證明MAX對MIN可能走的每一個棋局對弈后能獲勝，即MAX必須考慮應付MIN的所有招法

8、，這是一個與的含意，因此含有MAX符號的結點可看成與結點。2.Grundy博弈對MAX走步后的每一個MIN結點，只須證明MAX有一步能走贏就可以，即MAX只要考慮能