資源描述：
《人工智能與或圖搜索課件.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、第四章與或圖搜索4.1問題歸約法當(dāng)問題復(fù)雜時(shí)，可把初始問題分解成若干簡單的子問題，若子問題仍復(fù)雜，可再進(jìn)一步分解，直到這些子問題的解可直接得到。這種問題的描述和求解方法，稱為問題歸約法?？芍苯咏獯鸬膯栴}稱為本原問題。歸約法的問題表示可由下列三部分組成：1）??????一個(gè)初始問題的描述2）??????一組把問題變成子問題的算符3）??????一組本原問題的描述4.2與或圖對(duì)問題歸約的描述可以很方便地用一個(gè)與或圖的結(jié)構(gòu)來表示它。與節(jié)點(diǎn)：一個(gè)歸約算符能夠把單個(gè)問題變?yōu)閹讉€(gè)子問題組成的集合，這時(shí)所有子問題都有解，該父輩節(jié)點(diǎn)才有解。這種關(guān)系稱為“與
2、”關(guān)系，對(duì)應(yīng)的節(jié)點(diǎn)成為與節(jié)點(diǎn)?；蚬?jié)點(diǎn)：幾個(gè)算符適用于同一個(gè)問題，從而產(chǎn)生不同的后繼問題集合。這時(shí)只要有一個(gè)后繼集合有解，則意味該父輩問題有解，此時(shí)關(guān)系是“或”關(guān)系，對(duì)應(yīng)節(jié)點(diǎn)為或節(jié)點(diǎn)。在圖中N，M，H是或節(jié)點(diǎn)，B，C，D，E，F(xiàn)分別是與節(jié)點(diǎn)。ANMHBCDEF圖與節(jié)點(diǎn)和或節(jié)點(diǎn)與或節(jié)點(diǎn)是針對(duì)與或樹而言，對(duì)于一般的與或圖有歧義目標(biāo)目標(biāo)初始節(jié)點(diǎn)sabcK—連接符：假設(shè)節(jié)點(diǎn)N被某個(gè)算符歸約為一個(gè)包含K個(gè)子問題的替換集合，K?1，我們用一個(gè)叫做K—連接符的超弧線把它們和節(jié)點(diǎn)N連接起來。每個(gè)K—連接符從一個(gè)父節(jié)點(diǎn)指向一個(gè)含有K個(gè)后繼節(jié)點(diǎn)的集合，并說N有一
3、個(gè)外向連接符K。這種圖稱為超圖，但我們?nèi)园堰@種結(jié)構(gòu)叫與或圖。問題歸約描述對(duì)應(yīng)的結(jié)構(gòu)就是一個(gè)與或圖，原始問題描述對(duì)應(yīng)于起始節(jié)點(diǎn)（或根節(jié)點(diǎn)），本原問題所對(duì)應(yīng)的節(jié)點(diǎn)叫做葉節(jié)點(diǎn)。在某些特殊情況下，不出現(xiàn)任何與節(jié)點(diǎn)，此時(shí)的圖成了普通圖，問題歸約描述也就成為狀態(tài)空間描述。4.3與或圖搜索在與或圖上執(zhí)行搜索的過程，其目的在于表明起始節(jié)點(diǎn)是有解的，也就是說，搜索不是去尋找目標(biāo)節(jié)點(diǎn)，而是尋找一個(gè)解圖。定義：一個(gè)與或圖G中，從節(jié)點(diǎn)n到節(jié)點(diǎn)集N的解圖記為G?，G?是G的子圖。1．若n是N的一個(gè)元素，則G?由一節(jié)點(diǎn)組成；2．若n有一個(gè)指向節(jié)點(diǎn){n1…,nk}的外向
4、連接符K，使得從每一個(gè)ni到N有一個(gè)解圖(i=1,…,k)，則G?由節(jié)點(diǎn)n，連接符K，及{n1,…,nk}中的每一個(gè)節(jié)點(diǎn)到N的解圖所組成；3．否則n到N不存在解圖。目標(biāo)目標(biāo)初始節(jié)點(diǎn)解圖：在搜索解圖的過程中，還需要進(jìn)行耗散值的計(jì)算。設(shè)連接符的耗散值規(guī)定為：k-連接符的耗散值=k，若解圖的耗散值記為k(n,N)，則可遞歸計(jì)算如下：1．若n是N的一個(gè)元素，則k(n,N)=0；2．若n有一個(gè)外向連接符指向后繼節(jié)點(diǎn)(n1…,ni)，并設(shè)該連接符的耗散值為Cn，則k(n,N)=Cn+k(n1,N)+…+k(ni,N)具有最小耗散值的解圖稱為最佳解圖，其
5、值也用h*(n)標(biāo)記。耗散值的計(jì)算:k(n,N)=Cn+k(n1,N)+…+k(ni,N)其中：N為終節(jié)點(diǎn)集Cn為連接符的耗散值…...i個(gè)nn1n2ni搜索過程還要標(biāo)記能解節(jié)點(diǎn)(SOLVED)，為此給出如下定義： 能解節(jié)點(diǎn)終節(jié)點(diǎn)是能解節(jié)點(diǎn)若非終節(jié)點(diǎn)有“或”子節(jié)點(diǎn)時(shí)，當(dāng)且僅當(dāng)其子節(jié)點(diǎn)至少有一能解時(shí)，該非終節(jié)點(diǎn)才能解。若非終節(jié)點(diǎn)有“與”子節(jié)點(diǎn)時(shí)，當(dāng)且僅當(dāng)其子節(jié)點(diǎn)均能解時(shí)，該非終節(jié)點(diǎn)才能解。不能解節(jié)點(diǎn)沒有后裔的非終節(jié)點(diǎn)是不能解節(jié)點(diǎn)。若非終節(jié)點(diǎn)有“或”子節(jié)點(diǎn)，當(dāng)且僅當(dāng)所有子節(jié)點(diǎn)均不能解時(shí)，該非終節(jié)點(diǎn)才不能解。若非終節(jié)點(diǎn)有“與”子節(jié)點(diǎn)時(shí)，當(dāng)至少有
6、一個(gè)子節(jié)點(diǎn)不能解時(shí)，該非終節(jié)點(diǎn)才不能解。不過與或圖搜索與狀態(tài)空間圖搜索有所不同，說明如下：搜索目的是證明起始節(jié)點(diǎn)是否可解，而可解節(jié)點(diǎn)是遞歸定義的，取決于后繼節(jié)點(diǎn)是否可解，即搜索是否找到葉節(jié)點(diǎn)。因此，搜索有可解標(biāo)示過程和不可解標(biāo)示過程。初始節(jié)點(diǎn)被標(biāo)示為可解，則搜索成功結(jié)束，初始節(jié)點(diǎn)被標(biāo)示為不可解，則搜索失敗。普通圖的情況f(n)=g(n)+h(n)對(duì)n的評(píng)價(jià)實(shí)際是對(duì)從s到n這條路徑的評(píng)價(jià)ns與或圖:對(duì)局部圖的評(píng)價(jià)目標(biāo)目標(biāo)初始節(jié)點(diǎn)abc兩個(gè)過程圖生成過程，即擴(kuò)展節(jié)點(diǎn)從最優(yōu)的局部途中選擇一個(gè)節(jié)點(diǎn)擴(kuò)展計(jì)算耗散值的過程對(duì)當(dāng)前的局部圖新計(jì)算耗散值下面我
7、們討論一般與或圖的啟發(fā)式搜索算法——AO*算法。與A*算法不同，其評(píng)價(jià)函數(shù)f(n)=h(n)，只考慮h(n)這個(gè)分量，h(n)作為h*(n)的一個(gè)估計(jì)。過程AO*:1建立一個(gè)搜索圖G，G:=s，計(jì)算q(s)=h(s)，IFGOAL(s)THENM(s,SOLVED)；開始時(shí)圖G只包括s，耗散值估計(jì)為h(s)，若s是終節(jié)點(diǎn),則標(biāo)記上能解。2Untils已標(biāo)記上SOLVED,do:3begin4G?:=FIND(G)；根據(jù)連接符標(biāo)記（指針）找出一個(gè)待擴(kuò)展的局部解圖G?，指針后面步驟有說明。5n:=G?中的任一非終節(jié)點(diǎn);選一個(gè)非終結(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)
8、。6EXPAND(n),生成子節(jié)點(diǎn)集(ni)，G:=ADD((nj),G),計(jì)算q(nj)=h(nj)，其中nj?G，IFGOAL(nj)THENM(nj,SOLVED);把n的
