人工智能一般搜索原理

搜索技術(shù)問(wèn)題提出：有了知識(shí)表示方法之后，就需要有處理問(wèn)題方法，也就是搜索技術(shù)。所謂搜索，就是尋找一條從初始問(wèn)題到問(wèn)題解路徑本章內(nèi)容：搜索技術(shù)有許各種，本章介紹一些早期、比較簡(jiǎn)單搜索原理：1，盲目搜索；2，啟發(fā)式搜索；3，消解原理；4，通用問(wèn)題求解技術(shù)關(guān)鍵問(wèn)題： 怎樣利用知識(shí)，盡可能有效地找到問(wèn)題解(最正確解)。第三章普通搜索原理10/1/1人工智能一般搜索原理第1頁(yè)普通搜索原理搜索策略可分為三大類不可撤回方式、回朔方式、圖搜索方式不可撤回方式：每一次搜索時(shí)，利用局部知識(shí)依據(jù)最優(yōu)評(píng)價(jià)，選出下一狀態(tài)，選定后不能撤回，只能繼續(xù)回朔方式：在搜索過(guò)程中，有時(shí)會(huì)發(fā)覺(jué)所選路徑不適合找到目標(biāo)，這時(shí)允許退回去另選一條路徑。圖搜索方式：假如把問(wèn)題求解過(guò)程用圖來(lái)表示。節(jié)點(diǎn)代表問(wèn)題狀態(tài)，弧代表狀態(tài)改變方向，則搜索就變成對(duì)圖進(jìn)行從初始節(jié)點(diǎn)開(kāi)始，到目標(biāo)節(jié)點(diǎn)路徑搜索。第三章普通搜索原理3.1盲目搜索10/1/2人工智能一般搜索原理第2頁(yè)回溯搜索策略例：皇后問(wèn)題第三章普通搜索原理3.1盲目搜索10/1/3人工智能一般搜索原理第3頁(yè)()皇后問(wèn)題搜索過(guò)程（一）第三章普通搜索原理3.1盲目搜索10/1/4人工智能一般搜索原理第4頁(yè)Q()((1,1))皇后問(wèn)題搜索過(guò)程（二）第三章普通搜索原理3.1盲目搜索10/1/5人工智能一般搜索原理第5頁(yè)QQ()((1,1))((1,1)(2,3))皇后問(wèn)題搜索過(guò)程（三）第三章普通搜索原理3.1盲目搜索10/1/6人工智能一般搜索原理第6頁(yè)Q()((1,1))((1,1)(2,3))皇后問(wèn)題搜索過(guò)程（四）第三章普通搜索原理3.1盲目搜索10/1/7人工智能一般搜索原理第7頁(yè)QQ()((1,1))((1,1)(2,3))((1,1)(2,4))皇后問(wèn)題搜索過(guò)程（五）第三章普通搜索原理3.1盲目搜索10/1/8人工智能一般搜索原理第8頁(yè)QQQ()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))第三章普通搜索原理3.1盲目搜索皇后問(wèn)題搜索過(guò)程（六）10/1/9人工智能一般搜索原理第9頁(yè)QQ()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))第三章普通搜索原理3.1盲目搜索皇后問(wèn)題搜索過(guò)程（七）10/1/10人工智能一般搜索原理第10頁(yè)Q()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))第三章普通搜索原理3.1盲目搜索皇后問(wèn)題搜索過(guò)程（八）10/1/11人工智能一般搜索原理第11頁(yè)()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))第三章普通搜索原理3.1盲目搜索皇后問(wèn)題搜索過(guò)程（九）10/1/12人工智能一般搜索原理第12頁(yè)Q()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))((1,2))第三章普通搜索原理3.1盲目搜索皇后問(wèn)題搜索過(guò)程（十）10/1/13人工智能一般搜索原理第13頁(yè)QQ()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))((1,2))((1,2)(2,4))第三章普通搜索原理3.1盲目搜索皇后問(wèn)題搜索過(guò)程（十一）10/1/14人工智能一般搜索原理第14頁(yè)QQQ()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))((1,2))((1,2)(2,4))((1,2)(2,4)(3,1))第三章普通搜索原理3.1盲目搜索皇后問(wèn)題搜索過(guò)程（十二）10/1/15人工智能一般搜索原理第15頁(yè)QQQQ()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))((1,2))((1,2)(2,4))((1,2)(2,4)(3,1))((1,2)(2,4)(3,1)(4,3))第三章普通搜索原理3.1盲目搜索皇后問(wèn)題搜索過(guò)程（十三）10/1/16人工智能一般搜索原理第16頁(yè)遞歸思想從前有座山……從前有座山……

從前有座山……第三章普通搜索原理3.1盲目搜索10/1/17人工智能一般搜索原理第17頁(yè)一個(gè)遞歸例子intListLenght(LIST*pList){ if(pList==NULL)return0; elsereturnListLength(pList->next)+1;}第三章普通搜索原理3.1盲目搜索10/1/18人工智能一般搜索原理第18頁(yè)回溯搜索算法說(shuō)明 BACKTRACK（DATA）

DATA：當(dāng)前狀態(tài)。 返回值：從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)路徑 （以規(guī)則表形式表示） 或FAIL。第三章普通搜索原理3.1盲目搜索10/1/19人工智能一般搜索原理第19頁(yè)回溯搜索算法（一）遞歸過(guò)程BACKTRACK(DATA)1, IFTERM(DATA)RETURNNIL;2, IFDEADEND(DATA)RETURNFAIL;3, RULES:=APPRULES(DATA);第三章普通搜索原理3.1盲目搜索TERM:找目標(biāo)DEADEND:狀態(tài)不正當(dāng),無(wú)法繼續(xù)搜索APPRULES:取可應(yīng)用規(guī)則集10/1/20人工智能一般搜索原理第20頁(yè)回溯搜索算法（二）4, LOOP:IFNULL(RULES)RETURNFAIL;5, R:=FIRST(RULES);6, RULES:=TAIL(RULES);7, RDATA:=GEN(R,DATA);8, PATH:=BACKTRACK(RDATA);9, IFPATH=FAILGOLOOP;10, RETURNCONS(R,PATH);第三章普通搜索原理3.1盲目搜索TAIL:刪除頭條規(guī)則GEN:調(diào)用規(guī)則作用于當(dāng)前狀態(tài)CONS:獲取解路徑規(guī)則表10/1/21人工智能一般搜索原理第21頁(yè)存在問(wèn)題及處理方法問(wèn)題：深度問(wèn)題:假如深度太深死循環(huán)問(wèn)題:假如狀態(tài)出現(xiàn)重復(fù)處理方法：對(duì)搜索深度加以限制統(tǒng)計(jì)從初始狀態(tài)到當(dāng)前狀態(tài)路徑第三章普通搜索原理3.1盲目搜索10/1/22人工智能一般搜索原理第22頁(yè)增加約束后回溯搜索算法BACKTRACK1（DATALIST）

DATALIST：從初始到當(dāng)前狀態(tài)表（逆向） 返回值：從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)路徑 （以規(guī)則表形式表示） 或FAIL。第三章普通搜索原理3.1盲目搜索10/1/23人工智能一般搜索原理第23頁(yè)增加約束后回溯搜索算法(一)1, DATA:=FIRST(DATALIST)2, IFMENBER(DATA,TAIL(DATALIST)) RETURNFAIL;

3, IFTERM(DATA)RETURNNIL;4, IFDEADEND(DATA)RETURNFAIL;5, IFLENGTH(DATALIST)>BOUND RETURNFAIL;第三章普通搜索原理3.1盲目搜索10/1/24人工智能一般搜索原理第24頁(yè)增加約束后回溯搜索算法(二)6, RULES:=APPRULES(DATA);7,LOOP:IFNULL(RULES)RETURNFAIL;8, R:=FIRST(RULES);9, RULES:=TAIL(RULES);第三章普通搜索原理3.1盲目搜索10/1/25人工智能一般搜索原理第25頁(yè)增加約束后回溯搜索算法(三)10, RDATA:=GEN(R,DATA);11, RDATALIST:=CONS(RDATA,DATALIST);12, PATH:=BACKTRCK1(RDATALIST)13, IFPATH=FAILGOLOOP;14, RETURNCONS(R,PATH);第三章普通搜索原理3.1盲目搜索10/1/26人工智能一般搜索原理第26頁(yè)一些深入問(wèn)題失敗原因分析、多步回溯QQ第三章普通搜索原理3.1盲目搜索10/1/27人工智能一般搜索原理第27頁(yè)一些深入問(wèn)題（續(xù)）回溯搜索中知識(shí)利用 基本思想： 盡可能選取劃去對(duì)角線上位置數(shù)最少。QQQQ4334第三章普通搜索原理3.1盲目搜索10/1/28人工智能一般搜索原理第28頁(yè)模式導(dǎo)向搜索這個(gè)算法是將遞歸搜索應(yīng)用到謂詞演算通用搜索算法要判斷一個(gè)謂詞表示式是某個(gè)斷言集合邏輯結(jié)論首先謂詞表示式作為目標(biāo)，使用合一來(lái)選擇能與其后件匹配蘊(yùn)涵式并把得到置換利用于該蘊(yùn)涵式前件這個(gè)前件成了新目標(biāo)—稱其為子目標(biāo)應(yīng)用遞歸搜索解這個(gè)子目標(biāo)假如與事實(shí)相匹配，則搜索堅(jiān)固

第三章普通搜索原理3.1盲目搜索10/1/29人工智能一般搜索原理第29頁(yè)模式導(dǎo)向搜索算法描述一Functionpattern_search(current_goal)beginifcurrent_goalisinclosedthenreturnFAILelseputcurrent_goalintoclosedwhileeveryruleandfactsdobegincasecurrent_goal與事實(shí)合一returnSUCCESS

第三章普通搜索原理3.1盲目搜索10/1/30人工智能一般搜索原理第30頁(yè)模式導(dǎo)向搜索算法描述二

current_goal是合取式beginforevery合取項(xiàng)itemdoret=pattern_search(item)ifret==FAILthenreturnFAILendcurrent_goal與規(guī)則后件合一begin對(duì)前件q應(yīng)用對(duì)應(yīng)合一置換ret=pattern_search(q)ifret==FAILthenreturnFAILelseSUCCESSendendreturnFAILend第三章普通搜索原理3.1盲目搜索10/1/31人工智能一般搜索原理第31頁(yè)圖搜索策略圖搜索策略就是在圖中尋找從起始點(diǎn)到目標(biāo)點(diǎn)路徑方法圖搜索普通過(guò)程是結(jié)構(gòu)搜索圖過(guò)程。令搜索圖開(kāi)始時(shí)只有起始點(diǎn)S0，然后逐步擴(kuò)展節(jié)點(diǎn)，直到將目標(biāo)點(diǎn)擴(kuò)展到搜索圖里為止。擴(kuò)展過(guò)程就是搜索過(guò)程擴(kuò)展節(jié)點(diǎn)方法不一樣，就意味著搜索方法不一樣，也就是搜索路徑不一樣。

第三章普通搜索原理3.1盲目搜索10/1/32人工智能一般搜索原理第32頁(yè)圖搜索策略圖示S0Sg第三章普通搜索原理3.1盲目搜索10/1/33人工智能一般搜索原理第33頁(yè)節(jié)點(diǎn)擴(kuò)展擴(kuò)展一個(gè)節(jié)點(diǎn) 生成出該節(jié)點(diǎn)全部后繼節(jié)點(diǎn)，并給出它們之間代價(jià)值。這一過(guò)程稱為“擴(kuò)展一個(gè)節(jié)點(diǎn)”。第三章普通搜索原理3.1盲目搜索10/1/34人工智能一般搜索原理第34頁(yè)路徑路徑 設(shè)一節(jié)點(diǎn)序列為(n0,n1,…,nk)，對(duì)于i=1…k，若節(jié)點(diǎn)ni-1含有一個(gè)后繼節(jié)點(diǎn)ni，則該序列稱為從n0到nk路徑。路徑代價(jià)值 一條路徑代價(jià)值等于連接這條路徑各節(jié)點(diǎn)間全部代價(jià)值總和。用C(ni,nj)表示從ni到nj路徑代價(jià)值。第三章普通搜索原理3.1盲目搜索10/1/35人工智能一般搜索原理第35頁(yè)節(jié)點(diǎn)深度節(jié)點(diǎn)深度： 根節(jié)點(diǎn)深度=0 其它節(jié)點(diǎn)深度=父節(jié)點(diǎn)深度+10123第三章普通搜索原理3.1盲目搜索10/1/36人工智能一般搜索原理第36頁(yè)圖搜索普通過(guò)程第三章普通搜索原理3.1盲目搜索成功是把第一個(gè)節(jié)點(diǎn)(n)從OPEN表移至CLOSED表把n后繼節(jié)點(diǎn)放入OPEN表末端，提供返回節(jié)點(diǎn)n指針修改指針?lè)较虬裇放入OPEN表重排OPEN表是否否OPEN為空？n為目標(biāo)節(jié)點(diǎn)？失敗開(kāi)始10/1/37人工智能一般搜索原理第37頁(yè)圖搜索過(guò)程說(shuō)明我們?cè)谒阉鬟^(guò)程中用到了OPEN表和CLOSED表兩個(gè)數(shù)據(jù)結(jié)構(gòu)OPEN表中節(jié)點(diǎn)都是搜索樹(shù)端節(jié)點(diǎn)，即至今還未被選作為擴(kuò)展節(jié)點(diǎn)CLOSED表中節(jié)點(diǎn)或者是已被擴(kuò)展而不能生成后繼節(jié)點(diǎn)那些端節(jié)點(diǎn)，或者是搜索樹(shù)非端節(jié)點(diǎn)重排OPEN表，實(shí)際上就是在選擇搜索次序，也就是擴(kuò)展節(jié)點(diǎn)次序。第三章普通搜索原理3.1盲目搜索10/1/38人工智能一般搜索原理第38頁(yè)節(jié)點(diǎn)類型說(shuō)明…...mj…...mk…...…...…...ml第三章普通搜索原理3.1盲目搜索擴(kuò)展節(jié)點(diǎn)OPEN表沒(méi)有部分?jǐn)U展節(jié)點(diǎn)在已在close表中部分?jǐn)U展節(jié)點(diǎn)已在OPEN表中部分選定擴(kuò)展節(jié)點(diǎn)10/1/39人工智能一般搜索原理第39頁(yè)第三章普通搜索原理3.1盲目搜索圖搜索過(guò)程圖示（一）現(xiàn)要擴(kuò)展它10/1/40人工智能一般搜索原理第40頁(yè)第三章普通搜索原理3.1盲目搜索圖搜索過(guò)程圖示（二）修改父子關(guān)系現(xiàn)要擴(kuò)展它10/1/41人工智能一般搜索原理第41頁(yè)第三章普通搜索原理3.1盲目搜索圖搜索過(guò)程圖示（三）修改父子關(guān)系修改父子關(guān)系10/1/42人工智能一般搜索原理第42頁(yè)盲目搜索概述盲目搜索也叫無(wú)信息搜索盲目搜索實(shí)際上是對(duì)解空間遍歷盲目搜索包含有：寬度優(yōu)先搜索：搜索以靠近起始節(jié)點(diǎn)程度依次擴(kuò)展節(jié)點(diǎn)，在對(duì)下一層搜索前，必須搜索完本層全部節(jié)點(diǎn)。深度優(yōu)先搜索：搜索首先擴(kuò)展最新產(chǎn)生節(jié)點(diǎn)。等代價(jià)搜索：搜索沿最小代價(jià)節(jié)點(diǎn)進(jìn)行擴(kuò)展。

第三章普通搜索原理3.1盲目搜索10/1/43人工智能一般搜索原理第43頁(yè)寬度優(yōu)先搜索成功是把第一個(gè)節(jié)點(diǎn)(n)從OPEN表移至CLOSED表把n后繼節(jié)點(diǎn)放入OPEN表末端，提供返回節(jié)點(diǎn)n指針把S放入OPEN表是否否OPEN為空？是否有任何后繼節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)？失敗開(kāi)始第三章普通搜索原理3.1盲目搜索10/1/44人工智能一般搜索原理第44頁(yè)目標(biāo)231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765125673123847658234187654第三章普通搜索原理3.1盲目搜索八數(shù)碼難題寬度優(yōu)先搜索樹(shù)按上下左右序走步10/1/45人工智能一般搜索原理第45頁(yè)寬度優(yōu)先搜索性質(zhì)當(dāng)問(wèn)題有解時(shí)，一定能找到解當(dāng)問(wèn)題為單位代價(jià)值，且問(wèn)題有解時(shí)，一定能找到最優(yōu)解方法與問(wèn)題無(wú)關(guān)，含有通用性效率較低屬于圖搜索方法第三章普通搜索原理3.1盲目搜索10/1/46人工智能一般搜索原理第46頁(yè)第三章普通搜索原理3.1盲目搜索深度優(yōu)先搜索成功是把第一個(gè)節(jié)點(diǎn)(n)從OPEN表移至CLOSED表把n后繼節(jié)點(diǎn)放入OPEN表前端，提供返回節(jié)點(diǎn)n指針把S放入OPEN表是否否OPEN為空？節(jié)點(diǎn)n深度是否等于深度界限？失敗開(kāi)始是否有任何后繼節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)？是否S是否為目標(biāo)節(jié)點(diǎn)？否成功10/1/47人工智能一般搜索原理第47頁(yè)231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765123456789abcd12384765目標(biāo)。。。。。。。。。。第三章普通搜索原理3.1盲目搜索八數(shù)碼難題深度優(yōu)先搜索樹(shù)10/1/48人工智能一般搜索原理第48頁(yè)深度優(yōu)先搜索性質(zhì)普通不能確保找到最優(yōu)解當(dāng)深度限制不合理時(shí)，可能找不到解，能夠?qū)⑺惴ǜ臑榭勺兩疃认拗谱顗那闆r時(shí)，搜索空間等同于窮舉是一個(gè)通用與問(wèn)題無(wú)關(guān)方法第三章普通搜索原理3.1盲目搜索10/1/49人工智能一般搜索原理第49頁(yè)第三章普通搜索原理3.1盲目搜索等代價(jià)搜索成功是把含有最小g(i)值節(jié)點(diǎn)i從OPEN表移至CLOSED表計(jì)算其后繼節(jié)點(diǎn)jg(j)值。把其后繼節(jié)點(diǎn)放入OPEN表把S放入OPEN表否否OPEN為空？失敗開(kāi)始i是否為目標(biāo)節(jié)點(diǎn)？是S是否為目標(biāo)節(jié)點(diǎn)？否成功是令g(s)=010/1/50人工智能一般搜索原理第50頁(yè)什么是啟發(fā)式搜索盲目搜索效率低，花費(fèi)過(guò)多計(jì)算時(shí)間和空間，輕易產(chǎn)生組合爆炸。利用知識(shí)來(lái)引導(dǎo)搜索，到達(dá)降低搜索范圍，降低問(wèn)題復(fù)雜度目標(biāo)。對(duì)搜索產(chǎn)生幫助信息稱為啟發(fā)信息第三章普通搜索原理3.2啟發(fā)式搜索10/1/51人工智能一般搜索原理第51頁(yè)啟發(fā)式信息對(duì)搜索方法影響啟發(fā)信息多少用啟發(fā)信息強(qiáng)度來(lái)表示不一樣啟發(fā)信息對(duì)搜索方法帶來(lái)不一樣影響：強(qiáng)：降低搜索工作量，但可能造成找不到最優(yōu)解弱：普通造成工作量加大，極限情況下變?yōu)槊つ克阉鳎赡苣軌蛘业阶顑?yōu)解第三章普通搜索原理3.2啟發(fā)式搜索10/1/52人工智能一般搜索原理第52頁(yè)啟發(fā)式搜索類型啟發(fā)信息按用途可分為3類：用于決定要擴(kuò)展下一個(gè)節(jié)點(diǎn)（這個(gè)節(jié)點(diǎn)稱為最有希望節(jié)點(diǎn)），以免像在寬度優(yōu)先或深度優(yōu)先搜索中那樣盲目地?cái)U(kuò)展在擴(kuò)展一個(gè)節(jié)點(diǎn)過(guò)程中，用于決定要生成哪些其后繼節(jié)點(diǎn)，以免盲目地生成全部節(jié)點(diǎn)。用于決定哪些節(jié)點(diǎn)應(yīng)從搜索樹(shù)中拋棄或修剪。用來(lái)估算節(jié)點(diǎn)希望程度方法為估價(jià)函數(shù)第三章普通搜索原理3.2啟發(fā)式搜索10/1/53人工智能一般搜索原理第53頁(yè)對(duì)啟發(fā)式搜索認(rèn)識(shí)有些啟發(fā)信息能夠大大降低搜索工作量，但不能確保能夠得到最小代價(jià)路徑我們往往希望取得路徑代價(jià)和求該路徑所需搜索代價(jià)綜合為最小因?yàn)橛?jì)算綜合代價(jià)很困難，所以，比較兩種方法優(yōu)劣，依賴使用經(jīng)驗(yàn)使用估價(jià)函數(shù)實(shí)際是對(duì)OPEN表進(jìn)行排序，再按次序擴(kuò)展節(jié)點(diǎn)，進(jìn)行搜索第三章普通搜索原理3.2啟發(fā)式搜索10/1/54人工智能一般搜索原理第54頁(yè)有序搜索若按估價(jià)函數(shù)增序?qū)PEN表進(jìn)行排序，這種搜索方法叫做有序搜索或最正確優(yōu)先搜索有序搜索有效性取決于估價(jià)函數(shù)選擇，不然有可能失去一個(gè)最好解甚至全部解假如沒(méi)有適當(dāng)選擇，可考慮兩個(gè)方面內(nèi)容：一個(gè)是時(shí)間和空間折中確保有一個(gè)解第三章普通搜索原理3.2啟發(fā)式搜索10/1/55人工智能一般搜索原理第55頁(yè)有序搜索框圖第三章普通搜索原理3.2啟發(fā)式搜索成功是選取f值最小節(jié)點(diǎn)i，從OPEN表移至CLOSED表擴(kuò)展i，計(jì)算后繼節(jié)點(diǎn)jf(j)，對(duì)OPEN表重排序，調(diào)整親子關(guān)系把S放入OPEN表，計(jì)算f(s)是否否OPEN為空？i是目標(biāo)節(jié)點(diǎn)？失敗開(kāi)始10/1/56人工智能一般搜索原理第56頁(yè)估價(jià)函數(shù)：f(n)=d(n)+w(n)其中，d(n):節(jié)點(diǎn)深度w(n):節(jié)點(diǎn)放錯(cuò)棋子數(shù)目第三章普通搜索原理3.2啟發(fā)式搜索八數(shù)碼難題有序搜索樹(shù)28316475231847652831476523184765283147651238476528314765283164752831647528371465832147651237846523184765546466775675512384765目標(biāo)5估價(jià)函數(shù)值10/1/57人工智能一般搜索原理第57頁(yè)A算法A算法是一個(gè)有序搜索啟發(fā)式搜索算法。它采取估算節(jié)點(diǎn)n兩個(gè)代價(jià)：從起始點(diǎn)s到n最小代價(jià)路徑代價(jià)從n到某個(gè)目標(biāo)節(jié)點(diǎn)最小代價(jià)路徑代價(jià)估價(jià)函數(shù)形式： f(n)=g(n)+h(n)其中：g(n)：是對(duì)g*(n)估價(jià)值h(n)：是對(duì)h*(n)估價(jià)值,稱為啟發(fā)函數(shù)第三章普通搜索原理3.2啟發(fā)式搜索10/1/58人工智能一般搜索原理第58頁(yè)A算法估價(jià)函數(shù)說(shuō)明g*(n)：從s到n最正確路徑代價(jià)h*(n)：從n到某個(gè)目標(biāo)節(jié)點(diǎn)最正確路徑代價(jià)f*(n)=g*(n)+h*(n)：從s經(jīng)過(guò)n到某個(gè)目標(biāo)節(jié)點(diǎn)最正確路徑代價(jià)g(n)、h(n)、f(n)分別是g*(n)、h*(n)、f*(n)預(yù)計(jì)值表明，估價(jià)函數(shù)f(n)是對(duì)從起始點(diǎn)s經(jīng)過(guò)n到某個(gè)目標(biāo)節(jié)點(diǎn)最正確路徑代價(jià)預(yù)計(jì)值第三章普通搜索原理3.2啟發(fā)式搜索10/1/59人工智能一般搜索原理第59頁(yè)A算法流程1,OPEN:=(s),f(s):=g(s)+h(s);2,LOOP:IFOPEN=()THENEXIT(FAIL);3,n:=FIRST(OPEN);4,IFGOAL(n)THENEXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,EXPAND(n)→{mi},

計(jì)算f(n,mi):=g(n,mi)+h(mi);

第三章普通搜索原理3.2啟發(fā)式搜索10/1/60人工智能一般搜索原理第60頁(yè)A算法流程（續(xù)）

ADD(mj,OPEN),標(biāo)識(shí)mj到n指針； IFf(n,mk)<f(mk)THENf(mk):=f(n,mk),

標(biāo)識(shí)mk到n指針； IFf(n,ml)<f(ml,)THENf(ml):=f(n,ml), 標(biāo)識(shí)ml到n指針, ADD(ml,OPEN);7,OPEN中節(jié)點(diǎn)按f值從小到大排序；8,GOLOOP；第三章普通搜索原理3.2啟發(fā)式搜索10/1/61人工智能一般搜索原理第61頁(yè)最正確圖搜索算法A*（A*算法）在A算法中，假如對(duì)于任意點(diǎn)n滿足條件： h(n)≤h*(n) 則A算法稱為A*算法。第三章普通搜索原理3.2啟發(fā)式搜索10/1/62人工智能一般搜索原理第62頁(yè)A*算法估價(jià)函數(shù)舉例在問(wèn)題求解過(guò)程中，不可能明確知道h*(n)，可依據(jù)經(jīng)驗(yàn)預(yù)計(jì)下界范圍條件比如，8數(shù)碼問(wèn)題如取h(n)=“不在位”牌數(shù)，可預(yù)計(jì)出最少要移動(dòng)h(n)步，才能到達(dá)目標(biāo)，所以，有h(n)≤h*(n)如取h(n)=每個(gè)牌與目標(biāo)位置距離和，一樣可預(yù)計(jì)出最少要移動(dòng)h(n)步，才能到達(dá)目標(biāo)，所以，有h(n)≤h*(n)第三章普通搜索原理3.2啟發(fā)式搜索2

831

64751

238

476510/1/63人工智能一般搜索原理第63頁(yè)博弈中啟發(fā)式搜索博弈空間極小極大搜索:假定對(duì)手含有相同關(guān)于狀態(tài)空間知識(shí),且用該知識(shí)以一致方式比賽.博弈中對(duì)手分別稱為MIN和MAX一個(gè)余一棋變體：博弈雙方要交替地將一堆牌分成數(shù)量不一樣兩堆牌,最先無(wú)法分堆棋手為失敗第三章普通搜索原理3.2啟發(fā)式搜索10/1/64人工智能一般搜索原理第64頁(yè)窮舉式極小極大搜索博弈過(guò)程能夠用一個(gè)樹(shù)來(lái)表示標(biāo)識(shí)葉節(jié)點(diǎn)若MIN獲勝標(biāo)0,MAX獲勝標(biāo)1,標(biāo)識(shí)MIN節(jié)點(diǎn)為其子節(jié)點(diǎn)值中最大值標(biāo)識(shí)MAX節(jié)點(diǎn)為其子節(jié)點(diǎn)值中最小值這么向上傳輸,直至根節(jié)點(diǎn)第三章普通搜索原理3.2啟發(fā)式搜索10/1/65人工智能一般搜索原理第65頁(yè)第三章普通搜索原理3.2啟發(fā)式搜索一個(gè)余一棋變體樹(shù)4-34-2-15-1-175-22-2-1-1-13-2-1-16-14-1-1-12-2-2-13-1-1-1-12-1-1-1-1-13-2-200110111111003-3-10MINMAXMINMAXMINMAX10/1/66人工智能一般搜索原理第66頁(yè)固定層深極小極大搜索這種策略稱為n-層預(yù)判用于狀態(tài)空間不可能全部展開(kāi)情形，比如國(guó)際象棋狀態(tài)數(shù)大約是10120n值由可用時(shí)間和空間資源而定因?yàn)槿~節(jié)點(diǎn)不是博弈最終狀態(tài),不能用勝利或失敗來(lái)標(biāo)識(shí)需用某個(gè)啟發(fā)評(píng)定函數(shù)值來(lái)標(biāo)識(shí)這個(gè)向上傳輸值不表示是否能夠勝利,只表示經(jīng)過(guò)n步可到達(dá)最正確狀態(tài),也可能是完全誤導(dǎo)性大多數(shù)博弈都為設(shè)計(jì)啟發(fā)提供了無(wú)限想象空間第三章普通搜索原理3.2啟發(fā)式搜索10/1/67人工智能一般搜索原理第67頁(yè)第三章普通搜索原理3.2啟發(fā)式搜索一個(gè)九宮游戲啟發(fā)函數(shù)啟發(fā)值為對(duì)MAX來(lái)說(shuō)存在全部可能勝利路線,減去對(duì)MIN來(lái)說(shuō)存在全部可能勝利路線XOXOXOX有6條,O有5條可能勝利路線E(n)=6-5=1X有4條,O有6條可能勝利路線E(n)=4-6=-2X有5條,O有4條可能勝利路線E(n)=5-4=110/1/68人工智能一般搜索原理第68頁(yè)第三章普通搜索原理3.2啟發(fā)式搜索α-β搜索單純極小極大搜索需要對(duì)搜索空間進(jìn)行兩遍分析,效率低α-β搜索對(duì)極小極大搜索進(jìn)行改進(jìn)基本思想：不搜索預(yù)判深度整個(gè)空間，對(duì)能判斷不起作用分支則去掉，不搜索以深度優(yōu)先方式抵達(dá)預(yù)判層，在不停剪枝過(guò)程中，向上傳輸評(píng)定值α值是與MAX節(jié)點(diǎn)關(guān)聯(lián)不減小值β值是與MIN節(jié)點(diǎn)關(guān)聯(lián)不增大值10/1/69人工智能一般搜索原理第69頁(yè)第三章普通搜索原理3.2啟發(fā)式搜索α-β搜索舉例MINMAXMINMAX235907421563907263023≥2≤3≥5≥2≤0≤2××≥

3×10/1/70人工智能一般搜索原理第70頁(yè)雙向搜索搜索能夠是從初始狀態(tài)開(kāi)始向目標(biāo)狀態(tài)正向搜索；搜索也能夠是從目標(biāo)狀態(tài)開(kāi)始向初始狀態(tài)逆向搜索再可能是同時(shí)從初始狀態(tài)向目標(biāo)狀態(tài)正向搜索和從目標(biāo)狀態(tài)向初始狀態(tài)逆向搜索，直至這兩條路徑在中途某處小結(jié)接為止，這種搜索策略稱為雙向搜索第三章普通搜索原理3.2啟發(fā)式搜索10/1/71人工智能一般搜索原理第71頁(yè)消解原理概述消解原理又稱為歸結(jié)原理是一個(gè)主要推理規(guī)則它起源于定理證實(shí)：F1∧F2∧…∧Fn→W用反證法證：F=F1∧F2∧…∧Fn∧～W為永假等價(jià)于證實(shí)：F對(duì)應(yīng)子句集S為不可滿足歸結(jié)原理基本思緒是：尋找將S擴(kuò)充后子句集S1，它可滿足性與S相同，且輕易判斷可滿足性，從而知道S可滿足性，則定理得證第三章普通搜索原理3.3消解原理10/1/72人工智能一般搜索原理第72頁(yè)消解過(guò)程原子公式和原子公式否定稱為文字文字析取組成公式稱為子句若S中存在空子句，S為不可滿足將F化為對(duì)應(yīng)子句集S將S擴(kuò)充為可滿足性相同子句集S1，這個(gè)擴(kuò)充過(guò)程就是歸結(jié)過(guò)程 判斷S1是否存在空子句第三章普通搜索原理3.3消解原理10/1/73人工智能一般搜索原理第73頁(yè)消解過(guò)程舉例E2∨E1（前提）

～E2∨E3（前提）（消解式）E1∨E3（結(jié)論）第三章普通搜索原理3.3消解原理10/1/74人工智能一般搜索原理第74頁(yè)建立子句集消去蘊(yùn)涵符號(hào)：～

P∨Q取代P→Q降低否定符號(hào)管轄域?qū)ψ兞繕?biāo)準(zhǔn)化消去存在量詞化為前束形化為合取范式：如：PΛ(P∨Q）Λ(～P∨Q）消去全稱量詞取得子句集更換變量名第三章普通搜索原理3.3消解原理10/1/75人工智能一般搜索原理第75頁(yè)化子句集例例：(z)(x)(y){[(P(x)Q(x))R(y)]U(z)}1,消蘊(yùn)涵符 理論依據(jù)：ab=>~ab (z)(x)(y){[~(P(x)Q(x))R(y)]U(z)}2,移動(dòng)否定符 理論依據(jù)：~(ab)=>~a~b ~(ab)=>~a~b ~(x)P(x)=>(x)~P(x) ~(x)P(x)=>(x)~P(x)

(z)(x)(y){[(~P(x)~Q(x))R(y)]U(z)}第三章普通搜索原理3.3消解原理10/1/76人工智能一般搜索原理第76頁(yè)化子句集例（續(xù)1）3,變量標(biāo)準(zhǔn)化 即：對(duì)于不一樣約束，對(duì)應(yīng)于不一樣變量 (x)A(x)(x)B(x)=>(x)A(x)(y)B(y)4,量詞左移

(x)A(x)(y)B(y)=>(x)(y){A(x)B(y)}5,消存在量詞(skolem化） 標(biāo)準(zhǔn)：對(duì)于一個(gè)受存在量詞約束變量，假如他不受全程量詞約束，則該變量用一個(gè)常量代替，假如他受全程量詞約束，則該變量用一個(gè)函數(shù)代替。

(z)(x)(y){[(~P(x)~Q(x))R(y)]U(z)}=>(x){[(~P(x)~Q(x))R(f(x))]U(a)}第三章普通搜索原理3.3消解原理10/1/77人工智能一般搜索原理第77頁(yè)化子句集例（續(xù)2）6,化為合取范式 即(ab)(cd)(ef)形式

(x){[(~P(x)~Q(x))R(f(x))]U(a)}=>(x){(~P(x)~Q(x))R(f(x))U(a)}=>(x){[~P(x)R(f(x))U(a)]

[~Q(x))R(f(x))U(a)]}7,隱去全程量詞 {[~P(x)R(f(x))U(a)][~Q(x))R(f(x))U(a)]}第三章普通搜索原理3.3消解原理10/1/78人工智能一般搜索原理第78頁(yè)化子句集例（續(xù)3）8,表示為子句集{~P(x)R(f(x))U(a),~Q(x))R(f(x))U(a)}9,變量標(biāo)準(zhǔn)化（變量換名）{~P(x1)R(f(x1))U(a),~Q(x2))R(f(x2))U(a)}第三章普通搜索原理3.3消解原理10/1/79人工智能一般搜索原理第79頁(yè)消解推理規(guī)則L1、L2為任一原子公式，他們含有相同謂詞符號(hào)，但普通變量名不一樣已知兩子句L1∨α和～L2∨β假如L1、L2含有最普通合一者σ那么可得新子句(α∨β)σ這個(gè)新子句叫做消解式第三章普通搜索原理3.3消解原理10/1/80人工智能一般搜索原理第80頁(yè)命題邏輯消解推理舉例第三章普通搜索原理3.3消解原理假言推理：P～P∨Q(P→Q）消解式：Q合并：P∨Q～P∨Q消解式：Q∨Q=Q重言式：P∨Q～P∨～Q消解式：P∨～P或Q∨～Q空子句：P～P消解式：NIL三段論：～P∨Q(P→Q）～Q∨R(Q→R）消解式：～P∨R(P→Q）10/1/81人工智能一般搜索原理第81頁(yè)謂詞邏輯消解推理舉例第三章普通搜索原理3.3消解原理B(x)～B(x)∨C(x）消解式：C(x)P(x)∨Q(x）～Q[f(y)]消解式：P[f(y)]置換：f(y)/xP[x,f(y)]∨Q(x)∨R[f(a),y]～P[f(f(a)),z]∨R(z,w）消解式：Q[f(f(a))]∨R[f(a),y]∨R[f(y),w]置換：f(f(a))/x,f(y)/z10/1/82人工智能一般搜索原理第82頁(yè)消解反演求解過(guò)程消解反演是利用消解原理進(jìn)行命題證實(shí)。給定公式集S和目標(biāo)公式L證實(shí)公式L步驟以下：

否定L，得～L

把～L添加到S中去把新產(chǎn)生集合{～L,S}化成子句集應(yīng)用消解原理力圖推導(dǎo)出一個(gè)表示矛盾空子句第三章普通搜索原理3.3消解原理10/1/83人工智能一般搜索原理第83頁(yè)命題邏輯消解反演例子設(shè)公理集： P, (PQ)R, (ST)Q, T求證：R子句集： (1)P (2)~P~QR (3)~SQ (4)~TQ (5)T (6)~R（目標(biāo)求反）化子句集：

(PQ)R=>~(PQ)R=>~P~QR (ST)Q=>~(ST)Q=>(~S~T)Q=>(~SQ)(~TQ)=>{~SQ,~TQ}第三章普通搜索原理3.3消解原理10/1/84人工智能一般搜索原理第84頁(yè)命題邏輯消解反演例子（續(xù)）子句集： (1)P (2)~P~QR (3)~SQ (4)~TQ (5)T (6)~R（目標(biāo)求反）歸結(jié)： (7)~P~Q(2,6) (8)~Q (1,7)(9)~T(4,8)(10)nil(5,9)第三章普通搜索原理3.3消解原理10/1/85人工智能一般搜索原理第85頁(yè)謂詞邏輯消解反演例子例：已知：IfFidogoeswhereverJohngoesandifJohnisatschool,whereisFido?(x)[AT(John,x)AT(Fido,x)] AT(John,School)求證：(x)AT(Fido,x)子句集：~AT(John,y)AT(Fido,y)AT(