人工智能搜索2

1、4.3問(wèn)題歸約法問(wèn)題歸約法n歸約歸約(Reduction)問(wèn)題：現(xiàn)有煤氣灶、水龍頭、水壺和火柴，問(wèn)題：現(xiàn)有煤氣灶、水龍頭、水壺和火柴，你怎樣燒水？你怎樣燒水？答：向水壺中注滿水，把水壺放在煤氣灶上，答：向水壺中注滿水，把水壺放在煤氣灶上，擦火柴點(diǎn)燃煤氣灶。擦火柴點(diǎn)燃煤氣灶。 問(wèn)題可轉(zhuǎn)化為：在四個(gè)單位正方形內(nèi)，任意放置5個(gè)點(diǎn)，至少有兩個(gè)點(diǎn)在同一正方形內(nèi)。例2 n在邊長(zhǎng)為2的正方形內(nèi)，任意放置5個(gè)點(diǎn)，求證其中必存在兩個(gè)點(diǎn)，它們之間的距離不大于2。. . . . . IIIII123I例3:假定我們已經(jīng)會(huì)求矩形的面積，現(xiàn)在要求如圖所示的五邊形的面積。求解步驟：求五邊形面積求 1面積求 2面積求 3面

2、積求 I面積求 II面積求 III面積求 面積求 面積求 面積123IIIIIIn本原問(wèn)題本原問(wèn)題n可直接得到答案的問(wèn)題稱為本原問(wèn)題可直接得到答案的問(wèn)題稱為本原問(wèn)題n例例1中的原始的燒水問(wèn)題中的原始的燒水問(wèn)題n例例2中根據(jù)鴿巢原理直接可回答的問(wèn)題中根據(jù)鴿巢原理直接可回答的問(wèn)題n例例3中求矩形面積的問(wèn)題中求矩形面積的問(wèn)題n歸約法歸約法n把原問(wèn)題轉(zhuǎn)化把原問(wèn)題轉(zhuǎn)化(分解分解)為一個(gè)或幾個(gè)子問(wèn)題，為一個(gè)或幾個(gè)子問(wèn)題，對(duì)子問(wèn)題再歸約，直至成為可以直接求解對(duì)子問(wèn)題再歸約，直至成為可以直接求解的本原問(wèn)題。的本原問(wèn)題。問(wèn)題歸約問(wèn)題歸約n復(fù)雜問(wèn)題的解決方法復(fù)雜問(wèn)題的解決方法n問(wèn)題歸約問(wèn)題歸約:n含義含義: 把復(fù)

3、雜問(wèn)題轉(zhuǎn)換為若干需要同時(shí)處理的較為把復(fù)雜問(wèn)題轉(zhuǎn)換為若干需要同時(shí)處理的較為簡(jiǎn)單的子問(wèn)題后再加以分別求解的策略簡(jiǎn)單的子問(wèn)題后再加以分別求解的策略,可以遞歸可以遞歸地進(jìn)行地進(jìn)行,直到把問(wèn)題轉(zhuǎn)換為本原問(wèn)題的集合直到把問(wèn)題轉(zhuǎn)換為本原問(wèn)題的集合.n方法方法: 分解分解,變換變換4.3.1與與/或圖的表示法或圖的表示法n與或圖是一個(gè)超圖，節(jié)點(diǎn)間通過(guò)連接符連接。nK-連接符：.K個(gè)n與或圖表示法與或圖表示法n與節(jié)點(diǎn)與節(jié)點(diǎn)n將一個(gè)問(wèn)題分解為若干子問(wèn)將一個(gè)問(wèn)題分解為若干子問(wèn)題，題， 所有的子問(wèn)題有解，原所有的子問(wèn)題有解，原問(wèn)題才有解。問(wèn)題才有解。nK-聯(lián)接符聯(lián)接符n與節(jié)點(diǎn)與節(jié)點(diǎn)n將一個(gè)問(wèn)題轉(zhuǎn)化為若干子問(wèn)將一個(gè)問(wèn)題

4、轉(zhuǎn)化為若干子問(wèn)題，只要一個(gè)子問(wèn)題有解，題，只要一個(gè)子問(wèn)題有解，原問(wèn)題就有解。原問(wèn)題就有解。n單線聯(lián)接符單線聯(lián)接符AP1P2PkP1P2Pk與或圖的表示法與或圖的表示法n與或圖的構(gòu)成n與節(jié)點(diǎn)：分解問(wèn)題n或節(jié)點(diǎn)：變換問(wèn)題n弧:相關(guān)節(jié)點(diǎn)的聯(lián)結(jié)n終止節(jié)點(diǎn)：本原問(wèn)題與或圖表示法特點(diǎn)與或圖表示法特點(diǎn)n與或圖表示問(wèn)題特點(diǎn)與或圖表示問(wèn)題特點(diǎn)n可分解的問(wèn)題可分解的問(wèn)題n可變換的問(wèn)題可變換的問(wèn)題n例：如何上班問(wèn)題例：如何上班問(wèn)題n開(kāi)自家車開(kāi)自家車n車況好（自己修車，他人修車）車況好（自己修車，他人修車）n足夠燃料（車開(kāi)到加油站，自帶燃料）足夠燃料（車開(kāi)到加油站，自帶燃料）n步行步行n身體狀況好身體狀況好n足夠的時(shí)

5、間足夠的時(shí)間n公交車公交車n步行到車站步行到車站n騎車到車站騎車到車站n例：如何上班問(wèn)題例：如何上班問(wèn)題 上班問(wèn)題上班問(wèn)題開(kāi)自家車開(kāi)自家車步行步行乘公交車乘公交車車況好車況好燃料足燃料足他人修他人修自己修自己修他人修他人修加油站加油站自帶燃油自帶燃油燃油箱燃油箱身體好身體好時(shí)間夠時(shí)間夠步行到車站步行到車站騎車到車站騎車到車站n與或圖表示法與或圖表示法n與節(jié)點(diǎn)，或節(jié)點(diǎn)與節(jié)點(diǎn)，或節(jié)點(diǎn)n終止節(jié)點(diǎn)終止節(jié)點(diǎn):本原問(wèn)題本原問(wèn)題n端節(jié)點(diǎn)端節(jié)點(diǎn):無(wú)子節(jié)點(diǎn)的節(jié)點(diǎn)無(wú)子節(jié)點(diǎn)的節(jié)點(diǎn)可解節(jié)點(diǎn)定義：可解節(jié)點(diǎn)定義： n（1）終止節(jié)點(diǎn)是可解節(jié)點(diǎn)（因?yàn)樗鼈兣c本原）終止節(jié)點(diǎn)是可解節(jié)點(diǎn)（因?yàn)樗鼈兣c本原問(wèn)題相關(guān)聯(lián)）問(wèn)題相關(guān)聯(lián)）n（2

6、）如果某個(gè)非葉節(jié)點(diǎn)是含有或后繼節(jié)點(diǎn)，）如果某個(gè)非葉節(jié)點(diǎn)是含有或后繼節(jié)點(diǎn)，那么只有當(dāng)后繼節(jié)點(diǎn)至少有一個(gè)是可解的時(shí)，那么只有當(dāng)后繼節(jié)點(diǎn)至少有一個(gè)是可解的時(shí)，此非葉節(jié)點(diǎn)才是可解的。此非葉節(jié)點(diǎn)才是可解的。n（3）如果某個(gè)非終止節(jié)點(diǎn)含有與后繼節(jié)點(diǎn)，）如果某個(gè)非終止節(jié)點(diǎn)含有與后繼節(jié)點(diǎn)，那么只要當(dāng)其后繼節(jié)點(diǎn)全部為可解時(shí)，此非那么只要當(dāng)其后繼節(jié)點(diǎn)全部為可解時(shí)，此非終止節(jié)點(diǎn)才是可解的。終止節(jié)點(diǎn)才是可解的。不可解節(jié)點(diǎn)定義：不可解節(jié)點(diǎn)定義： n（1）沒(méi)有后裔的非終止節(jié)點(diǎn)為不可解節(jié)點(diǎn)）沒(méi)有后裔的非終止節(jié)點(diǎn)為不可解節(jié)點(diǎn)n（2）如果某個(gè)非終止節(jié)點(diǎn)含有或后繼節(jié)點(diǎn)，）如果某個(gè)非終止節(jié)點(diǎn)含有或后繼節(jié)點(diǎn)，那么只要當(dāng)其全部后裔為不

7、可解時(shí)，此非終那么只要當(dāng)其全部后裔為不可解時(shí)，此非終止節(jié)點(diǎn)才是不可解節(jié)點(diǎn)止節(jié)點(diǎn)才是不可解節(jié)點(diǎn)n（3）如果某個(gè)非終止節(jié)點(diǎn)含有與后繼節(jié)點(diǎn)，）如果某個(gè)非終止節(jié)點(diǎn)含有與后繼節(jié)點(diǎn)，那么只要當(dāng)其后裔至少有一個(gè)為不可解節(jié)點(diǎn)那么只要當(dāng)其后裔至少有一個(gè)為不可解節(jié)點(diǎn)時(shí)，此非終止節(jié)點(diǎn)才是不可解的時(shí)，此非終止節(jié)點(diǎn)才是不可解的n與或圖解圖與或圖解圖1可解節(jié)點(diǎn)可解節(jié)點(diǎn)23B端節(jié)點(diǎn)（不可擴(kuò)展節(jié)點(diǎn)）端節(jié)點(diǎn)（不可擴(kuò)展節(jié)點(diǎn)）54t1At2t3t4終止節(jié)點(diǎn)終止節(jié)點(diǎn)n問(wèn)題歸約舉例: 上班問(wèn)題開(kāi)自家車步行車況好燃料足自己修他人修加油站自帶燃油燃油箱身體好時(shí)間夠步行到車站騎車到車站上班問(wèn)題乘公交車問(wèn)題歸約舉例問(wèn)題歸約舉例(“梵塔梵塔”問(wèn)

8、題問(wèn)題)3階階“梵塔梵塔”問(wèn)題問(wèn)題(Tower of Hanoi Problem):n有三個(gè)柱子有三個(gè)柱子(1，2和和3)和兩個(gè)不同尺寸的圓盤(pán)和兩個(gè)不同尺寸的圓盤(pán)(A，B，C)。在每個(gè)圓盤(pán)的中心有個(gè)孔，所以圓盤(pán)可以堆疊。在每個(gè)圓盤(pán)的中心有個(gè)孔，所以圓盤(pán)可以堆疊在柱子上在柱子上,最初最初,全部三個(gè)圓盤(pán)都堆在柱子全部三個(gè)圓盤(pán)都堆在柱子1上上(最大的最大的在底部在底部,最小的在頂部最小的在頂部)。要求把所有。要求把所有 圓盤(pán)都移到另圓盤(pán)都移到另一個(gè)柱子上，搬動(dòng)規(guī)則為：一個(gè)柱子上，搬動(dòng)規(guī)則為： (1)一次只能搬一個(gè)圓盤(pán)一次只能搬一個(gè)圓盤(pán) (2)不能將大圓盤(pán)放在小圓盤(pán)上不能將大圓盤(pán)放在小圓盤(pán)上 (3)可

9、以利用空柱子。可以利用空柱子。n用問(wèn)題分解方法來(lái)描述問(wèn)題用問(wèn)題分解方法來(lái)描述問(wèn)題：n狀態(tài)的表示n柱的編號(hào)用i,j,k來(lái)代表 (i,j,k)表示問(wèn)題的狀態(tài)其中: i代表A所在的柱子, j 代表B所在的柱子，k代表C所在的柱子n初始狀態(tài)(1,1,1)，目標(biāo)狀態(tài)(2,2,2) (3,3,3,)(1,1,1)132C(2,2,2)123AB(3,3,3)123ABABCCn初始狀態(tài)(1,1,1)，目標(biāo)狀態(tài) (3,3,3,)n分解的關(guān)鍵狀態(tài)(1,2,2)132C(3,2,2)123AB(3,3,3)123ABABCCn3階“梵塔”問(wèn)題與或圖方法(1,1,1)(3,3,3)(1,1,1)(1,2,2) (

10、1,2,2)(3,2,2)(3,2,2)(3,3,3)(1,1,1)(1,1,3) (1,2,3)(1,2,2)(1,1,3)(1,2,3)(3,2,2)(3,3,3)(3,2,2)(3,2,1)(3,3,1)(3,3,3)4.3.2 與或圖的搜索與或圖的搜索n與或圖搜索的一般過(guò)程與或圖搜索的一般過(guò)程n可解標(biāo)示過(guò)程與不可解標(biāo)示過(guò)程可解標(biāo)示過(guò)程與不可解標(biāo)示過(guò)程n與或圖的基本搜索方法與或圖的基本搜索方法n與或圖搜索與圖搜索的不同與或圖搜索與圖搜索的不同耗散值耗散值(代價(jià)代價(jià))k(n, N) = Cn+k(n1, N)+k(ni, N)其中：其中：N為終節(jié)點(diǎn)集為終節(jié)點(diǎn)集 Cn為連接符的耗散值為連接符

11、的耗散值.i個(gè)個(gè)nn1n2nin例例n5n6non2n3n4n7n8n1與或樹(shù)搜索的一般過(guò)程與或樹(shù)搜索的一般過(guò)程n基本思想：基本思想：n擴(kuò)展（自上而下）擴(kuò)展（自上而下）n標(biāo)示（自下而上）標(biāo)示（自下而上）n結(jié)束條件：初始節(jié)點(diǎn)為可解或不可解結(jié)束條件：初始節(jié)點(diǎn)為可解或不可解n搜索過(guò)程：搜索過(guò)程：（1 1）把原始問(wèn)題作為初始節(jié)點(diǎn)）把原始問(wèn)題作為初始節(jié)點(diǎn)S0,S0,并將其作為當(dāng)前節(jié)點(diǎn)并將其作為當(dāng)前節(jié)點(diǎn)（2 2）按解圖生成的方法按解圖生成的方法,分步生成候選的局部解圖集分步生成候選的局部解圖集,從中選擇從中選擇局部解圖局部解圖 擴(kuò)展，同時(shí)使用標(biāo)示過(guò)程擴(kuò)展，同時(shí)使用標(biāo)示過(guò)程對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行擴(kuò)展對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行擴(kuò)

12、展（3 3）為每個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針）為每個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針（4 4）用適當(dāng)?shù)牟呗裕▽挾壬疃葐l(fā)式）選擇）用適當(dāng)?shù)牟呗裕▽挾壬疃葐l(fā)式）選擇局部解圖擴(kuò)展局部解圖擴(kuò)展,反復(fù)反復(fù)應(yīng)用（應(yīng)用（2 2）（）（3 3）步，在此期間要多次應(yīng)用可解標(biāo)示過(guò)程和不）步，在此期間要多次應(yīng)用可解標(biāo)示過(guò)程和不可解標(biāo)示過(guò)程，直到初始節(jié)點(diǎn)被標(biāo)示為可解節(jié)點(diǎn)或不可解節(jié)可解標(biāo)示過(guò)程，直到初始節(jié)點(diǎn)被標(biāo)示為可解節(jié)點(diǎn)或不可解節(jié)點(diǎn)。點(diǎn)。n可解與不可解標(biāo)示過(guò)程可解與不可解標(biāo)示過(guò)程n可解標(biāo)示過(guò)程：由可解子節(jié)點(diǎn)來(lái)確定父節(jié)可解標(biāo)示過(guò)程：由可解子節(jié)點(diǎn)來(lái)確定父節(jié)點(diǎn)，祖父節(jié)點(diǎn)等為可解節(jié)點(diǎn)的過(guò)程點(diǎn)，祖父節(jié)點(diǎn)等為可解節(jié)點(diǎn)的過(guò)程n不可解

13、標(biāo)示過(guò)程：由不可解子節(jié)點(diǎn)來(lái)確定不可解標(biāo)示過(guò)程：由不可解子節(jié)點(diǎn)來(lái)確定父節(jié)點(diǎn)，祖父節(jié)點(diǎn)等為不可解節(jié)點(diǎn)的過(guò)程父節(jié)點(diǎn)，祖父節(jié)點(diǎn)等為不可解節(jié)點(diǎn)的過(guò)程n與或樹(shù)的搜索方法分類與或樹(shù)的搜索方法分類n盲目搜索盲目搜索n啟法式搜索啟法式搜索n有序搜索有序搜索n博奕樹(shù)博奕樹(shù)與或圖搜索與圖搜索的不同與或圖搜索與圖搜索的不同n終止搜索的條件不同 n對(duì)已生成結(jié)點(diǎn)處理不同 n結(jié)果不同 n例 梵塔問(wèn)題4.3.3與或圖的啟發(fā)式搜索與或圖的啟發(fā)式搜索n局部圖局部圖n局部圖定義局部圖定義n局部圖代價(jià)計(jì)算舉例局部圖代價(jià)計(jì)算舉例n希望圖希望圖n基本思想基本思想n搜索算法使用的數(shù)據(jù)結(jié)構(gòu)搜索算法使用的數(shù)據(jù)結(jié)構(gòu)n與或圖的啟發(fā)式搜索方法與或圖

14、的啟發(fā)式搜索方法n解圖的代價(jià):k(n,N)nn是局部圖中的一個(gè)葉節(jié)點(diǎn)是局部圖中的一個(gè)葉節(jié)點(diǎn), 則則 k(n,N)=h(n)nn是是K-連接節(jié)點(diǎn)連接節(jié)點(diǎn), n1,n2,.ni是它的子節(jié)點(diǎn),k(n,N)=Cn+k(n1,N)+h(n2,N)+.+k(ni,N)n例例n例（局部解圖的計(jì)算例（局部解圖的計(jì)算Cn=k,h值如圖）值如圖）S0(9)A(8)B(3)D(11)C(3)E(7)F(2)n希望圖希望圖：在搜索過(guò)程中任一時(shí)刻求出的局部解圖其代價(jià)都是最小的。這個(gè)局部解圖即是希望圖n例例A(8)D(7)C(3)E(3)F(2)h(S0)=8B(3)f(S0)=9n例（局部解圖的計(jì)算Cn=k）S0（8）

15、A(8)B(3)D(7)C(3)E(3)F(2)基本思想基本思想n目標(biāo)：尋找最小代價(jià)的解樹(shù)，最優(yōu)解圖(樹(shù))n方法：按解圖生成的方法,分步生成局部解圖,重新計(jì)算節(jié)點(diǎn)的耗散值（代價(jià)）, 從中選擇一個(gè)代價(jià)最小的局部解圖用于擴(kuò)展，同時(shí)使用標(biāo)示過(guò)程。搜索算法使用的數(shù)據(jù)結(jié)構(gòu)搜索算法使用的數(shù)據(jù)結(jié)構(gòu)n基本數(shù)據(jù)結(jié)構(gòu)基本數(shù)據(jù)結(jié)構(gòu) nG: 搜索圖搜索圖nG: 被選中的待擴(kuò)展局部解圖被選中的待擴(kuò)展局部解圖(希望圖希望圖)nS: 待重新估值的節(jié)點(diǎn)集合待重新估值的節(jié)點(diǎn)集合ns: 根節(jié)點(diǎn)根節(jié)點(diǎn),即初始狀態(tài)節(jié)點(diǎn)即初始狀態(tài)節(jié)點(diǎn)nn: 被選中的待擴(kuò)展節(jié)點(diǎn)被選中的待擴(kuò)展節(jié)點(diǎn)n連結(jié)符標(biāo)記（指針），擴(kuò)展指針連結(jié)符標(biāo)記（指針），擴(kuò)展指針

16、估價(jià)函數(shù)估價(jià)函數(shù)hn設(shè)設(shè)h*(n)是從搜索圖中一個(gè)節(jié)點(diǎn)是從搜索圖中一個(gè)節(jié)點(diǎn)n到一個(gè)終節(jié)到一個(gè)終節(jié)點(diǎn)集合的一個(gè)解圖的實(shí)際耗散值點(diǎn)集合的一個(gè)解圖的實(shí)際耗散值, h(n)是對(duì)是對(duì)h*(n)的估計(jì)的估計(jì). 若在若在n的一個(gè)解圖中的一個(gè)解圖中, n有有k個(gè)與個(gè)與后繼節(jié)點(diǎn)后繼節(jié)點(diǎn)n1, nk, 且且 h(n) C(n)+h(n1)+ +h(nk) 其中其中, C(n)為為k連接符的連接符的(總總)耗散值耗散值, 又若又若n為為終節(jié)點(diǎn)終節(jié)點(diǎn), 則則h(n)=0, 則我們稱則我們稱h(n)滿足單調(diào)滿足單調(diào)限制限制. 可證可證, 對(duì)于所有節(jié)點(diǎn)有對(duì)于所有節(jié)點(diǎn)有h(n) h*(n), 即即h是是h*的下界的下界.n

17、舉例說(shuō)明舉例說(shuō)明nAO*算法算法n若若h(n)滿足單調(diào)限制滿足單調(diào)限制, 則下面的與或則下面的與或圖搜索算法稱為圖搜索算法稱為AO*算法算法(1)建立一個(gè)搜索圖建立一個(gè)搜索圖G, 使其僅包含起始節(jié)點(diǎn)使其僅包含起始節(jié)點(diǎn)S, 對(duì)應(yīng)對(duì)應(yīng) 于節(jié)點(diǎn)于節(jié)點(diǎn)S的費(fèi)用為的費(fèi)用為q(S)=h(S), 如如S為終節(jié)點(diǎn)為終節(jié)點(diǎn), 則則標(biāo)記標(biāo)記S為為SOLVED(2)until S已標(biāo)記為已標(biāo)記為SOLVED do(3)begin(4)通過(guò)跟蹤通過(guò)跟蹤G中從中從S出發(fā)的有標(biāo)記的連接符出發(fā)的有標(biāo)記的連接符, 計(jì)算計(jì)算 G中的一個(gè)局部解圖中的一個(gè)局部解圖G(5)選擇選擇G的任一未標(biāo)記為的任一未標(biāo)記為SOLVED的葉節(jié)點(diǎn)的

18、葉節(jié)點(diǎn)n(6)擴(kuò)展節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn)n, 生成它的全部后繼節(jié)點(diǎn)加入生成它的全部后繼節(jié)點(diǎn)加入G中中. 對(duì)對(duì) 于未曾在于未曾在G中出現(xiàn)過(guò)的每一個(gè)后繼節(jié)點(diǎn)中出現(xiàn)過(guò)的每一個(gè)后繼節(jié)點(diǎn)nj, 相應(yīng)的相應(yīng)的 費(fèi)用費(fèi)用q(nj)=h(nj). 對(duì)其中的終節(jié)點(diǎn)對(duì)其中的終節(jié)點(diǎn), 標(biāo)記標(biāo)記SOLVED, 相應(yīng)的相應(yīng)的q值為值為0(7)建立一個(gè)只包含節(jié)點(diǎn)建立一個(gè)只包含節(jié)點(diǎn)n的集合的集合M(8)until M為空為空 do(9)begin(10)從從M中移出后裔不在中移出后裔不在M中的節(jié)點(diǎn)中的節(jié)點(diǎn)m(即自下而上即自下而上)(11)根據(jù)以下步驟修改節(jié)點(diǎn)根據(jù)以下步驟修改節(jié)點(diǎn)m的費(fèi)用的費(fèi)用q(m):若若m有有j個(gè)或分枝個(gè)或分枝,

19、對(duì)于對(duì)于m的每個(gè)或分枝的每個(gè)或分枝 i 的與的與 后繼節(jié)點(diǎn)集后繼節(jié)點(diǎn)集n1i , n ki, 計(jì)算計(jì)算 qi(m)=Ci(m)+q(n1i)+ +q(nki)1 i j 令令 q(m)=min(qi(m)1 i j 并對(duì)這個(gè)具有最小值的分枝連接符加以標(biāo)記并對(duì)這個(gè)具有最小值的分枝連接符加以標(biāo)記, 如如 果以前標(biāo)記在其他分枝連接符上果以前標(biāo)記在其他分枝連接符上, 則刪除以前的則刪除以前的 標(biāo)記標(biāo)記; 如果該連接符的全部后繼節(jié)點(diǎn)都已標(biāo)記如果該連接符的全部后繼節(jié)點(diǎn)都已標(biāo)記 為為SOLVED, 則標(biāo)記則標(biāo)記m為為SOLVED(12)如果如果m已標(biāo)記為已標(biāo)記為SOLVED, 或或q(m)不同于以前不同于以

20、前計(jì)算的費(fèi)用計(jì)算的費(fèi)用, 則把通過(guò)有標(biāo)記連接符連到則把通過(guò)有標(biāo)記連接符連到m上的所上的所有祖先節(jié)點(diǎn)都添加到有祖先節(jié)點(diǎn)都添加到M中去中去(13)end (9)(14)end (3)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è)：K連接符的耗散值為K目標(biāo)目標(biāo)初始節(jié)點(diǎn)n0n1n2n3n4n5n6n7n8目標(biāo)目標(biāo)初始節(jié)點(diǎn)n0n1n2n3n4n5n6n7n8初始節(jié)點(diǎn)n0n1(2)n4(1)n5(1)紅色：4綠色：3目標(biāo)目標(biāo)初始節(jié)點(diǎn)n0n1n2n3n4n5n6n7n8初始節(jié)點(diǎn)n0n4(1

21、)n5(1)紅色：4綠色：6n1n2(4)n3(4)5目標(biāo)目標(biāo)初始節(jié)點(diǎn)n0n1n2n3n4n5n6n7n8紅色：5綠色：6初始節(jié)點(diǎn)n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)2目標(biāo)目標(biāo)初始節(jié)點(diǎn)n0n1n2n3n4n5n6n7n8紅色：5綠色：6初始節(jié)點(diǎn)n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)21n與與A*算法比較算法比較n估價(jià)函數(shù)只考慮估價(jià)函數(shù)只考慮h(n), 因?yàn)樗惴ㄓ凶韵乱驗(yàn)樗惴ㄓ凶韵露系男拚M(fèi)用的的操作而上的修正費(fèi)用的的操作, 實(shí)際上局部實(shí)際上局部解圖費(fèi)用值的估計(jì)是在起始節(jié)點(diǎn)解圖費(fèi)用值的估計(jì)是在起始節(jié)點(diǎn)S比較比

22、較, 計(jì)算計(jì)算g既無(wú)必要也不可能既無(wú)必要也不可能.nK-連接符對(duì)父節(jié)點(diǎn)的可解性及費(fèi)用值連接符對(duì)父節(jié)點(diǎn)的可解性及費(fèi)用值的估計(jì)都產(chǎn)生影響的估計(jì)都產(chǎn)生影響, 因而不能象因而不能象A*算算法那樣優(yōu)先擴(kuò)展具有最小費(fèi)用的節(jié)點(diǎn)法那樣優(yōu)先擴(kuò)展具有最小費(fèi)用的節(jié)點(diǎn).n沒(méi)有沒(méi)有OPEN表和表和CLOSED表表, 增加了局增加了局部解圖部解圖G, h(n)是最佳解圖的費(fèi)用估是最佳解圖的費(fèi)用估計(jì)計(jì), 而不是最佳路徑的估計(jì)而不是最佳路徑的估計(jì).4.3.4 博弈樹(shù)的啟發(fā)式搜索博弈樹(shù)的啟發(fā)式搜索n問(wèn)題提出問(wèn)題提出n博弈樹(shù)的概念博弈樹(shù)的概念n博弈樹(shù)的搜索方法極大極小分析法博弈樹(shù)的搜索方法極大極小分析法n 剪枝枝術(shù)剪枝枝術(shù)問(wèn)題的

23、提出問(wèn)題的提出n問(wèn)題：分錢(qián)幣游戲：有一堆數(shù)目為問(wèn)題：分錢(qián)幣游戲：有一堆數(shù)目為N的錢(qián)幣，兩的錢(qián)幣，兩個(gè)選手輪流將它一分為二，規(guī)則是無(wú)論哪個(gè)選手個(gè)選手輪流將它一分為二，規(guī)則是無(wú)論哪個(gè)選手分幣時(shí)，一次只能挑選其中的一堆把它分為兩小分幣時(shí)，一次只能挑選其中的一堆把它分為兩小堆，而且必須滿足分堆后兩小堆的錢(qián)數(shù)不能相等，堆，而且必須滿足分堆后兩小堆的錢(qián)數(shù)不能相等，直到哪個(gè)選手無(wú)法再分時(shí)，即碰到每堆錢(qián)幣數(shù)為直到哪個(gè)選手無(wú)法再分時(shí)，即碰到每堆錢(qián)幣數(shù)為1或或2的情況，他即為輸家的情況，他即為輸家.設(shè)設(shè)N=6,選手甲，乙，數(shù)選手甲，乙，數(shù)字序列字序列x1,x2xn為為n堆錢(qián)幣不同的個(gè)數(shù)。堆錢(qián)幣不同的個(gè)數(shù)。n例例

24、（6，甲，甲(MAX)）表示甲從一堆（）表示甲從一堆（6個(gè)）錢(qián)幣開(kāi)個(gè)）錢(qián)幣開(kāi) 始分始分 ,（5，1，乙，乙(MIN)）乙要分的狀態(tài)）乙要分的狀態(tài)n分錢(qián)幣的搜索樹(shù)S0(6,MAX)S1(5,1,MIN)S4(3,2,1,MAX)S2(4,2,MIN)S6(2,2,1,1,MIN)S3(4,1,1,MAX)S7(2,1,1,1,1,MAX)S5(3,1,1,1,MIN)MIN輸MAX輸博奕樹(shù)博奕樹(shù)n博弈樹(shù)：以一方立場(chǎng)（我方）來(lái)看博弈博弈樹(shù)：以一方立場(chǎng)（我方）來(lái)看博弈過(guò)程用圖表示出來(lái)，得到的與或樹(shù)過(guò)程用圖表示出來(lái)，得到的與或樹(shù)n初始節(jié)點(diǎn)為博弈的初始格局。初始節(jié)點(diǎn)為博弈的初始格局。n與或節(jié)點(diǎn)交替出現(xiàn)，

25、我方擴(kuò)展節(jié)點(diǎn)之與或節(jié)點(diǎn)交替出現(xiàn)，我方擴(kuò)展節(jié)點(diǎn)之間是間是“或或”的關(guān)系，敵方為的關(guān)系，敵方為“與與”節(jié)節(jié)點(diǎn)。點(diǎn)。n使我方獲勝的終局都是本原問(wèn)題，使使我方獲勝的終局都是本原問(wèn)題，使敵方獲勝的終局都是不可解節(jié)點(diǎn)敵方獲勝的終局都是不可解節(jié)點(diǎn)n博弈的特點(diǎn)：二人零和，全信息，非偶博弈的特點(diǎn)：二人零和，全信息，非偶然然n二人零和：結(jié)果必有一方獲勝，或平二人零和：結(jié)果必有一方獲勝，或平局。局。n全信息：參與者都了解對(duì)手當(dāng)前和過(guò)全信息：參與者都了解對(duì)手當(dāng)前和過(guò)去的走步，也可以推測(cè)出將要走的招去的走步，也可以推測(cè)出將要走的招術(shù)。術(shù)。n非偶然非偶然:根據(jù)當(dāng)前情況（一般不能看到根據(jù)當(dāng)前情況（一般不能看到終局），終局）

26、，選取對(duì)自己最為有利而對(duì)對(duì)選取對(duì)自己最為有利而對(duì)對(duì)方最為不利的對(duì)策方最為不利的對(duì)策n分錢(qián)幣的搜索樹(shù)（分錢(qián)幣的搜索樹(shù)（MAX必贏）必贏）S0(6,MAX)S1(5,1,MIN)S4(3,2,1,MAX)S2(4,2,MIN)S6(2,2,1,1,MIN)S3(4,1,1,MAX)S7(2,1,1,1,1,MAX)S5(3,1,1,1,MIN)MAX贏贏MAX輸輸n分錢(qián)幣的搜索樹(shù)（MIN可能贏）S0(6,MAX)S1(5,1,MIN)S4(3,2,1,MAX)S2(4,2,MIN)S6(2,2,1,1,MIN)S3(4,1,1,MAX)S7(2,1,1,1,1,MAX)S5(3,1,1,1,MIN

27、)MIN輸MIN贏分錢(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,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ì)方先走我方必勝n如何找到博弈必勝的策略如何找到博弈必勝的策略n思路：盡選擇對(duì)自己有利的方案，向前盡量多看幾步思路：盡選擇對(duì)自己有利的方案，向前盡量多看幾步n基本概念基本概念n靜態(tài)估值：每個(gè)結(jié)點(diǎn)的勢(shì)態(tài)估計(jì)值。靜態(tài)估值：每個(gè)結(jié)點(diǎn)的勢(shì)態(tài)估計(jì)值。n 倒推值：由每個(gè)結(jié)點(diǎn)的靜態(tài)估值倒推出父結(jié)點(diǎn)的估計(jì)值。倒推值：由每個(gè)結(jié)點(diǎn)的靜態(tài)估值倒推出父結(jié)點(diǎn)的估計(jì)值。n 或節(jié)點(diǎn)或

28、節(jié)點(diǎn)(MAX節(jié)點(diǎn)節(jié)點(diǎn))，其倒推值選，其倒推值選 取各分枝中最大值。取各分枝中最大值。n與節(jié)點(diǎn)與節(jié)點(diǎn)(MIN節(jié)點(diǎn)節(jié)點(diǎn))，其倒推值選取各分枝中最小值。，其倒推值選取各分枝中最小值。n基本思想基本思想(極大極小法極大極小法)。n以一定深度生成博奕樹(shù)以一定深度生成博奕樹(shù)(擴(kuò)展一級(jí)或二級(jí)擴(kuò)展一級(jí)或二級(jí)),應(yīng)用各節(jié)點(diǎn)的靜應(yīng)用各節(jié)點(diǎn)的靜態(tài)估計(jì)值計(jì)算出態(tài)估計(jì)值計(jì)算出(倒推出倒推出)每個(gè)非端節(jié)點(diǎn)的倒退值。每個(gè)非端節(jié)點(diǎn)的倒退值。n選取選取”或或”節(jié)點(diǎn)節(jié)點(diǎn)(我方，我方，MAX)得分極大的棋步得分極大的棋步(對(duì)或節(jié)點(diǎn)來(lái)對(duì)或節(jié)點(diǎn)來(lái)說(shuō)說(shuō))n 選取選取”與與”節(jié)點(diǎn)節(jié)點(diǎn)(敵方，敵方，MIN)得分極小的棋步得分極小的棋步(對(duì)與

29、節(jié)點(diǎn)來(lái)對(duì)與節(jié)點(diǎn)來(lái)說(shuō)說(shuō))逐級(jí)搜索，求解博奕問(wèn)題。逐級(jí)搜索，求解博奕問(wèn)題。n例 計(jì)算倒推值（向前看兩步）321-124 -2 6 4 364-56186 328562-12-243-51322343323中國(guó)象棋n一盤(pán)棋平均走50步，總狀態(tài)數(shù)約為10的161次方。n假設(shè)1毫微秒走一步，約需10的145次方年。n結(jié)論：不可能窮舉。極大極小分析法極大極小分析法1.設(shè)博弈的雙方中一方為設(shè)博弈的雙方中一方為A,另一方為另一方為B.極大極小分析法是為其極大極小分析法是為其中的一方中的一方(例如例如A)尋找一個(gè)最優(yōu)行動(dòng)方案的方法。尋找一個(gè)最優(yōu)行動(dòng)方案的方法。2.為找到當(dāng)前的最優(yōu)行動(dòng)方案，需要對(duì)各個(gè)方案可能產(chǎn)生

30、的后為找到當(dāng)前的最優(yōu)行動(dòng)方案，需要對(duì)各個(gè)方案可能產(chǎn)生的后果進(jìn)行比較。即要考慮每一方案實(shí)施后對(duì)方可能采取的所有果進(jìn)行比較。即要考慮每一方案實(shí)施后對(duì)方可能采取的所有行動(dòng)，并計(jì)算可能的得分。行動(dòng)，并計(jì)算可能的得分。3為計(jì)算得分，需要根據(jù)問(wèn)題的特性信息定義一個(gè)估價(jià)函數(shù)，用為計(jì)算得分，需要根據(jù)問(wèn)題的特性信息定義一個(gè)估價(jià)函數(shù)，用來(lái)估算當(dāng)前博弈樹(shù)端節(jié)點(diǎn)的得分，此時(shí)估算出來(lái)的得分稱為來(lái)估算當(dāng)前博弈樹(shù)端節(jié)點(diǎn)的得分，此時(shí)估算出來(lái)的得分稱為靜態(tài)估值。靜態(tài)估值。4當(dāng)端節(jié)點(diǎn)的估值計(jì)算出來(lái)后，再推算出其父節(jié)點(diǎn)的得分。當(dāng)端節(jié)點(diǎn)的估值計(jì)算出來(lái)后，再推算出其父節(jié)點(diǎn)的得分。推算方法：推算方法：“或或”節(jié)點(diǎn)取其子節(jié)點(diǎn)中最大的得分作

31、為父節(jié)點(diǎn)的節(jié)點(diǎn)取其子節(jié)點(diǎn)中最大的得分作為父節(jié)點(diǎn)的得分。得分。 “與與”節(jié)點(diǎn)取其子節(jié)點(diǎn)中最小的得分作為父節(jié)點(diǎn)的得節(jié)點(diǎn)取其子節(jié)點(diǎn)中最小的得分作為父節(jié)點(diǎn)的得分。這樣計(jì)算出的父節(jié)點(diǎn)的得分稱為倒推值。分。這樣計(jì)算出的父節(jié)點(diǎn)的得分稱為倒推值。5如果一個(gè)方案能獲得較大的倒推值，則它就是當(dāng)前最好的行動(dòng)如果一個(gè)方案能獲得較大的倒推值，則它就是當(dāng)前最好的行動(dòng)方案。方案。n求解過(guò)程求解過(guò)程n搜索樹(shù)搜索樹(shù)n端節(jié)點(diǎn)的估計(jì)值端節(jié)點(diǎn)的估計(jì)值n- 表示表示MAX不可再分不可再分n+ 表示表示MIN不可再分不可再分n極大極小分析方法計(jì)算倒推值極大極小分析方法計(jì)算倒推值n選取對(duì)選取對(duì)MAX最有利的方案最有利的方案n分錢(qián)幣的搜索樹(shù)

32、（分錢(qián)幣的搜索樹(shù)（MAX必贏）必贏）S0(6,MAX)S1(5,1,MIN)S4(3,2,1,MAX)S2(4,2,MIN)S6(2,2,1,1,MIN)S3(4,1,1,MAX)S7(2,1,1,1,1,MAX)S5(3,1,1,1,MIN)MAX贏贏MAX輸輸- + - - + - + + 例例 極大極小法（向前看兩步）極大極小法（向前看兩步）321-124 -2 6 4 364-56186328562-12-243-51322343323極大極小搜索法舉例極大極小搜索法舉例:n一字棋一字棋n在博奕樹(shù)中一般用方塊表示輪到我方走棋的在博奕樹(shù)中一般用方塊表示輪到我方走棋的節(jié)點(diǎn)節(jié)點(diǎn), 稱為最大節(jié)

33、點(diǎn)稱為最大節(jié)點(diǎn); 用圓圈表示輪到對(duì)方用圓圈表示輪到對(duì)方走棋的節(jié)點(diǎn)走棋的節(jié)點(diǎn), 稱為最小節(jié)點(diǎn)稱為最小節(jié)點(diǎn). 棋局中, 我方(MAX)棋子用表示, 對(duì)方(MIN)棋子用表示. 開(kāi)始由我方先走, 搜索深度為2. 估價(jià)函數(shù): 我方獲勝e(p)= - 對(duì)方獲勝 空格視為時(shí)我方三連子數(shù)-其他情況 空格視為時(shí)對(duì)方三連子數(shù)1-1-211010-1-10-10-2 12 11213121010201112231221100 111212-101001122111-ABCD算法討論算法討論n存在問(wèn)題n改進(jìn)方法n 黑 紅n車 18 18n馬 0 8n炮 10 0n象 4 4n士 4 4n兵 4 2總和 40 364.3.5 剪枝枝術(shù)剪枝枝術(shù)n基本思想n值n剪枝枝術(shù)的一般規(guī)律n例n基本思想SABC=2D=7E=1F未定 值值與節(jié)點(diǎn)取當(dāng)前子節(jié)點(diǎn)中最小倒推值作為其倒推值的與節(jié)點(diǎn)取當(dāng)前子節(jié)點(diǎn)中最小倒推值作為其倒推值的上界上界- 值值或節(jié)點(diǎn)取當(dāng)前子節(jié)點(diǎn)中最大倒推值作為其倒推值的或節(jié)點(diǎn)取當(dāng)前子節(jié)點(diǎn)中最大倒推值作為其倒推值的下界下界- 值值n 剪枝枝術(shù)的一般規(guī)律剪枝枝術(shù)的一般規(guī)律n任何任何“或或”節(jié)點(diǎn)節(jié)