人工智能一般搜索原理

搜索技術(shù)問題提出：有了知識表示方法之后，就需求有處理問題的方法，也就是搜索技術(shù)。所謂搜索，就是尋覓一條從初始問題到問題解的途徑本章內(nèi)容：搜索技術(shù)有許多種，本章引見一些早期的、比較簡單的搜索原理：1，盲目搜索；2，啟發(fā)式搜索；3，消解原理；4，通用問題求解技術(shù)關(guān)鍵問題： 如何利用知識，盡能夠有效地找到問題的解(最正確解)。第三章普通搜索原理12/25/20231普通搜索原理搜索戰(zhàn)略可分為三大類不可撤回方式、回朔方式、圖搜索方式不可撤回方式：每一次搜索時，利用部分知識根據(jù)最優(yōu)評價，選出下一形狀，選定后不能撤回，只能繼續(xù)回朔方式：在搜索過程中，有時會發(fā)現(xiàn)所選的途徑不適宜找到目的，這時允許退回去另選一條途徑。圖搜索方式：假設(shè)把問題求解過程用圖來表示。節(jié)點代表問題的形狀，弧代表形狀變化的方向，那么搜索就變成對圖進(jìn)展從初始節(jié)點開場，到目的節(jié)點途徑的搜索。第三章普通搜索原理3.1盲目搜索12/25/20232回溯搜索戰(zhàn)略例：皇后問題第三章普通搜索原理3.1盲目搜索12/25/20233()皇后問題搜索過程〔一〕第三章普通搜索原理3.1盲目搜索12/25/20234Q()((1,1))皇后問題搜索過程〔二〕第三章普通搜索原理3.1盲目搜索12/25/20235QQ()((1,1))((1,1)(2,3))皇后問題搜索過程〔三〕第三章普通搜索原理3.1盲目搜索12/25/20236Q()((1,1))((1,1)(2,3))皇后問題搜索過程〔四〕第三章普通搜索原理3.1盲目搜索12/25/20237QQ()((1,1))((1,1)(2,3))((1,1)(2,4))皇后問題搜索過程〔五〕第三章普通搜索原理3.1盲目搜索12/25/20238QQQ()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))第三章普通搜索原理3.1盲目搜索皇后問題搜索過程〔六〕12/25/20239QQ()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))第三章普通搜索原理3.1盲目搜索皇后問題搜索過程〔七〕12/25/202310Q()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))第三章普通搜索原理3.1盲目搜索皇后問題搜索過程〔八〕12/25/202311()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))第三章普通搜索原理3.1盲目搜索皇后問題搜索過程〔九〕12/25/202312Q()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))((1,2))第三章普通搜索原理3.1盲目搜索皇后問題搜索過程〔十〕12/25/202313QQ()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))((1,2))((1,2)(2,4))第三章普通搜索原理3.1盲目搜索皇后問題搜索過程〔十一〕12/25/202314QQQ()((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盲目搜索皇后問題搜索過程〔十二〕12/25/202315QQQQ()((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盲目搜索皇后問題搜索過程〔十三〕12/25/202316遞歸的思想從前有座山……從前有座山……從前有座山……第三章普通搜索原理3.1盲目搜索12/25/202317一個遞歸的例子intListLenght(LIST*pList){ if(pList==NULL)return0; elsereturnListLength(pList->next)+1;}第三章普通搜索原理3.1盲目搜索12/25/202318回溯搜索算法闡明 BACKTRACK〔DATA〕

DATA：當(dāng)前形狀。 前往值：從當(dāng)前形狀到目的形狀的途徑 〔以規(guī)那么表的方式表示〕 或FAIL。第三章普通搜索原理3.1盲目搜索12/25/202319回溯搜索算法〔一〕遞歸過程BACKTRACK(DATA)1, IFTERM(DATA)RETURNNIL;2, IFDEADEND(DATA)RETURNFAIL;3, RULES:=APPRULES(DATA);第三章普通搜索原理3.1盲目搜索TERM:找目的DEADEND:形狀不合法,無法繼續(xù)搜索APPRULES:取可運用規(guī)那么集12/25/202320回溯搜索算法〔二〕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)前形狀CONS:獲取解途徑規(guī)那么表12/25/202321存在問題及處理方法問題：深度問題:假設(shè)深度太深死循環(huán)問題:假設(shè)形狀出現(xiàn)反復(fù)處理方法：對搜索深度加以限制記錄從初始形狀到當(dāng)前形狀的途徑第三章普通搜索原理3.1盲目搜索12/25/202322添加約束后的回溯搜索算法BACKTRACK1〔DATALIST〕

DATALIST：從初始到當(dāng)前的形狀表〔逆向〕 前往值：從當(dāng)前形狀到目的形狀的途徑 〔以規(guī)那么表的方式表示〕 或FAIL。第三章普通搜索原理3.1盲目搜索12/25/202323添加約束后的回溯搜索算法(一)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盲目搜索12/25/202324添加約束后的回溯搜索算法(二)6, RULES:=APPRULES(DATA);7,LOOP:IFNULL(RULES)RETURNFAIL;8, R:=FIRST(RULES);9, RULES:=TAIL(RULES);第三章普通搜索原理3.1盲目搜索12/25/202325添加約束后的回溯搜索算法(三)10, RDATA:=GEN(R,DATA);11, RDATALIST:=CONS(RDATA,DATALIST);12, PATH:=BACKTRCK1(RDATALIST)13, IFPATH=FAILGOLOOP;14, RETURNCONS(R,PATH);第三章普通搜索原理3.1盲目搜索12/25/202326一些深化的問題失敗緣由分析、多步回溯QQ第三章普通搜索原理3.1盲目搜索12/25/202327一些深化問題〔續(xù)〕回溯搜索中知識的利用 根本思想： 盡能夠選取劃去對角線上位置數(shù)最少的。QQQQ4334第三章普通搜索原理3.1盲目搜索12/25/202328方式導(dǎo)向搜索這個算法是將遞歸搜索運用到謂詞演算的通用搜索算法要判別一個謂詞表達(dá)式是某個斷言集合的邏輯結(jié)論首先謂詞表達(dá)式作為目的，運用合一來選擇能與其后件匹配的蘊涵式并把得到的置換運用于該蘊涵式的前件這個前件成了新的目的—稱其為子目的運用遞歸搜索解這個子目的假設(shè)與現(xiàn)實相匹配，那么搜索結(jié)實

第三章普通搜索原理3.1盲目搜索12/25/202329方式導(dǎo)向搜索算法描畫一Functionpattern_search(current_goal)beginifcurrent_goalisinclosedthenreturnFAILelseputcurrent_goalintoclosedwhileeveryruleandfactsdobegincasecurrent_goal與現(xiàn)實合一returnSUCCESS

第三章普通搜索原理3.1盲目搜索12/25/202330方式導(dǎo)向搜索算法描畫二current_goal是合取式beginforevery合取項itemdoret=pattern_search(item)ifret==FAILthenreturnFAILendcurrent_goal與規(guī)那么的后件合一begin對前件q運用對應(yīng)的合一置換ret=pattern_search(q)ifret==FAILthenreturnFAILelseSUCCESSendendreturnFAILend第三章普通搜索原理3.1盲目搜索12/25/202331圖搜索戰(zhàn)略圖搜索戰(zhàn)略就是在圖中尋覓從起始點到目的點的途徑的方法圖搜索的普經(jīng)過程是構(gòu)造搜索圖的過程。令搜索圖開場時只需起始點S0，然后逐漸擴(kuò)展節(jié)點，直到將目的點擴(kuò)展到搜索圖里為止。擴(kuò)展的過程就是搜索的過程擴(kuò)展節(jié)點的方法不同，就意味著搜索的方法不同，也就是搜索的途徑不同。

第三章普通搜索原理3.1盲目搜索12/25/202332圖搜索戰(zhàn)略圖示S0Sg第三章普通搜索原理3.1盲目搜索12/25/202333節(jié)點擴(kuò)展擴(kuò)展一個節(jié)點 生成出該節(jié)點的一切后繼節(jié)點，并給出它們之間的代價值。這一過程稱為“擴(kuò)展一個節(jié)點〞。第三章普通搜索原理3.1盲目搜索12/25/202334途徑途徑 設(shè)一節(jié)點序列為(n0,n1,…,nk)，對于i=1…k，假設(shè)節(jié)點ni-1具有一個后繼節(jié)點ni，那么該序列稱為從n0到nk的途徑。途徑的代價值 一條途徑的代價值等于銜接這條途徑各節(jié)點間一切代價值的總和。用C(ni,nj)表示從ni到nj的途徑的代價值。第三章普通搜索原理3.1盲目搜索12/25/202335節(jié)點深度節(jié)點深度： 根節(jié)點深度=0 其它節(jié)點深度=父節(jié)點深度+10123第三章普通搜索原理3.1盲目搜索12/25/202336圖搜索的普經(jīng)過程第三章普通搜索原理3.1盲目搜索勝利是把第一個節(jié)點(n)從OPEN表移至CLOSED表把n的后繼節(jié)點放入OPEN表的末端，提供前往節(jié)點n的指針修正指針方向把S放入OPEN表重排OPEN表是否否OPEN為空？n為目的節(jié)點？失敗開場12/25/202337圖搜索過程闡明我們在搜索過程中用到了OPEN表和CLOSED表兩個數(shù)據(jù)構(gòu)造OPEN表中的節(jié)點都是搜索樹的端節(jié)點，即至今尚未被選作為擴(kuò)展的節(jié)點CLOSED表中的節(jié)點或者是已被擴(kuò)展而不能生成后繼節(jié)點的那些端節(jié)點，或者是搜索樹的非端節(jié)點重排OPEN表，實踐上就是在選擇搜索順序，也就是擴(kuò)展的節(jié)點的順序。第三章普通搜索原理3.1盲目搜索12/25/202338節(jié)點類型闡明…...mj…...mk…...…...…...ml第三章普通搜索原理3.1盲目搜索擴(kuò)展的節(jié)點OPEN表沒有的部分?jǐn)U展的節(jié)點在已在close表中的部分?jǐn)U展的節(jié)點已在OPEN表中的部分選定的擴(kuò)展節(jié)點12/25/202339第三章普通搜索原理3.1盲目搜索圖搜索過程的圖示〔一〕現(xiàn)要擴(kuò)展它12/25/202340第三章普通搜索原理3.1盲目搜索圖搜索過程的圖示〔二〕修正父子關(guān)系現(xiàn)要擴(kuò)展它12/25/202341第三章普通搜索原理3.1盲目搜索圖搜索過程的圖示〔三〕修正父子關(guān)系修正父子關(guān)系12/25/202342盲目搜索概述盲目搜索也叫無信息搜索盲目搜索實踐上是對解空間的遍歷盲目搜索包括有：寬度優(yōu)先搜索：搜索以接近起始節(jié)點的程度依次擴(kuò)展節(jié)點，在對下一層搜索前，必需搜索完本層的一切節(jié)點。深度優(yōu)先搜索：搜索首先擴(kuò)展最新產(chǎn)生的節(jié)點。等代價搜索：搜索沿最小代價節(jié)點進(jìn)展擴(kuò)展。

第三章普通搜索原理3.1盲目搜索12/25/202343寬度優(yōu)先搜索勝利是把第一個節(jié)點(n)從OPEN表移至CLOSED表把n的后繼節(jié)點放入OPEN表的末端，提供前往節(jié)點n的指針把S放入OPEN表是否否OPEN為空？能否有任何后繼節(jié)點為目的節(jié)點？失敗開場第三章普通搜索原理3.1盲目搜索12/25/202344目的231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765125673123847658234187654第三章普通搜索原理3.1盲目搜索八數(shù)碼難題的寬度優(yōu)先搜索樹按上下左右序走步12/25/202345寬度優(yōu)先搜索的性質(zhì)當(dāng)問題有解時，一定能找到解當(dāng)問題為單位代價值，且問題有解時，一定能找到最優(yōu)解方法與問題無關(guān)，具有通用性效率較低屬于圖搜索方法第三章普通搜索原理3.1盲目搜索12/25/202346第三章普通搜索原理3.1盲目搜索深度優(yōu)先搜索勝利是把第一個節(jié)點(n)從OPEN表移至CLOSED表把n的后繼節(jié)點放入OPEN表的前端，提供前往節(jié)點n的指針把S放入OPEN表是否否OPEN為空？節(jié)點n的深度能否等于深度界限？失敗開場能否有任何后繼節(jié)點為目的節(jié)點？是否S能否為目的節(jié)點？否勝利12/25/202347231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765123456789abcd12384765目的。。。。。。。。。。第三章普通搜索原理3.1盲目搜索八數(shù)碼難題的深度優(yōu)先搜索樹12/25/202348深度優(yōu)先搜索的性質(zhì)普通不能保證找到最優(yōu)解當(dāng)深度限制不合理時，能夠找不到解，可以將算法改為可變深度限制最壞情況時，搜索空間等同于窮舉是一個通用的與問題無關(guān)的方法第三章普通搜索原理3.1盲目搜索12/25/202349第三章普通搜索原理3.1盲目搜索等代價搜索勝利是把具有最小g(i)值的節(jié)點i從OPEN表移至CLOSED表計算其后繼節(jié)點j的g(j)值。把其后繼節(jié)點放入OPEN表把S放入OPEN表否否OPEN為空？失敗開場i能否為目的節(jié)點？是S能否為目的節(jié)點？否勝利是令g(s)=012/25/202350什么是啟發(fā)式搜索盲目搜索的效率低，耗費過多的計算時間和空間，容易產(chǎn)生組合爆炸。利用知識來引導(dǎo)搜索，到達(dá)減少搜索范圍，降低問題復(fù)雜度的目的。對搜索產(chǎn)生協(xié)助的信息稱為啟發(fā)信息第三章普通搜索原理3.2啟發(fā)式搜索12/25/202351啟發(fā)式信息對搜索方法的影響啟發(fā)信息的多少用啟發(fā)信息強(qiáng)度來表示不同的啟發(fā)信息對搜索方法帶來不同的影響：強(qiáng)：降低搜索任務(wù)量，但能夠?qū)е抡也坏阶顑?yōu)解弱：普通導(dǎo)致任務(wù)量加大，極限情況下變?yōu)槊つ克阉鳎軌蚩梢哉业阶顑?yōu)解第三章普通搜索原理3.2啟發(fā)式搜索12/25/202352啟發(fā)式搜索類型啟發(fā)信息按用途可分為3類：用于決議要擴(kuò)展的下一個節(jié)點〔這個節(jié)點稱為最有希望的節(jié)點〕，以免像在寬度優(yōu)先或深度優(yōu)先搜索中那樣盲目地擴(kuò)展在擴(kuò)展一個節(jié)點的過程中，用于決議要生成哪些其后繼節(jié)點，以免盲目地生成一切節(jié)點。用于決議哪些節(jié)點應(yīng)從搜索樹中丟棄或修剪。用來估算節(jié)點希望程度的方法為估價函數(shù)第三章普通搜索原理3.2啟發(fā)式搜索12/25/202353對啟發(fā)式搜索的認(rèn)識有些啟發(fā)信息可以大大減少搜索任務(wù)量，但不能保證可以得到最小代價途徑我們往往希望獲得途徑代價和求該途徑所需的搜索代價的綜合為最小由于計算綜合代價很困難，因此，比較兩種方法的優(yōu)劣，依賴運用的閱歷運用估價函數(shù)實踐是對OPEN表進(jìn)展排序，再按順序擴(kuò)展節(jié)點，進(jìn)展搜索第三章普通搜索原理3.2啟發(fā)式搜索12/25/202354有序搜索假設(shè)按估價函數(shù)的增序?qū)PEN表進(jìn)展排序，這種搜索方法叫做有序搜索或最正確優(yōu)先搜索有序搜索的有效性取決于估價函數(shù)的選擇，否那么有能夠失去一個最好的解甚至全部的解假設(shè)沒有適宜的選擇，可思索兩個方面的內(nèi)容：一個是時間和空間的折中保證有一個解第三章普通搜索原理3.2啟發(fā)式搜索12/25/202355有序搜索框圖第三章普通搜索原理3.2啟發(fā)式搜索勝利是選取f值最小的節(jié)點i，從OPEN表移至CLOSED表擴(kuò)展i，計算后繼節(jié)點j的f(j)，對OPEN表重排序，調(diào)整親子關(guān)系把S放入OPEN表，計算f(s)是否否OPEN為空？i是目的節(jié)點？失敗開場12/25/202356估價函數(shù)：f(n)=d(n)+w(n)其中，d(n):節(jié)點的深度w(n):節(jié)點放錯棋子數(shù)目第三章普通搜索原理3.2啟發(fā)式搜索八數(shù)碼難題的有序搜索樹28316475231847652831476523184765283147651238476528314765283164752831647528371465832147651237846523184765546466775675512384765目的5估價函數(shù)值12/25/202357A算法A算法是一種有序搜索的啟發(fā)式搜索算法。它采用估算節(jié)點n的兩個代價：從起始點s到n的最小代價途徑的代價從n到某個目的節(jié)點的最小代價途徑的代價估價函數(shù)的方式： f(n)=g(n)+h(n)其中：g(n)：是對g*(n)的估價值h(n)：是對h*(n)的估價值,稱為啟發(fā)函數(shù)第三章普通搜索原理3.2啟發(fā)式搜索12/25/202358A算法估價函數(shù)的闡明g*(n)：從s到n的最正確途徑的代價h*(n)：從n到某個目的節(jié)點的最正確途徑的代價f*(n)=g*(n)+h*(n)：從s經(jīng)過n到某個目的節(jié)點的最正確途徑的代價g(n)、h(n)、f(n)分別是g*(n)、h*(n)、f*(n)的估計值闡明，估價函數(shù)f(n)是對從起始點s經(jīng)過n到某個目的節(jié)點的最正確途徑的代價的估計值第三章普通搜索原理3.2啟發(fā)式搜索12/25/202359A算法流程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}, 計算f(n,mi):=g(n,mi)+h(mi);

第三章普通搜索原理3.2啟發(fā)式搜索12/25/202360A算法流程〔續(xù)〕 ADD(mj,OPEN),標(biāo)志mj到n的指針； IFf(n,mk)<f(mk)THENf(mk):=f(n,mk), 標(biāo)志mk到n的指針； IFf(n,ml)<f(ml,)THENf(ml):=f(n,ml), 標(biāo)志ml到n的指針, ADD(ml,OPEN);7,OPEN中的節(jié)點按f值從小到大排序；8,GOLOOP；第三章普通搜索原理3.2啟發(fā)式搜索12/25/202361最正確圖搜索算法A*〔A*算法〕在A算法中，假設(shè)對于恣意點n滿足條件： h(n)≤h*(n) 那么A算法稱為A*算法。第三章普通搜索原理3.2啟發(fā)式搜索12/25/202362A*算法估價函數(shù)舉例在問題求解過程中，不能夠明確知道h*(n)，可根據(jù)閱歷估計下界范圍條件例如，8數(shù)碼問題如取h(n)=“不在位〞的牌數(shù)，可估計出至少要挪動h(n)步，才干到達(dá)目的，因此，有h(n)≤h*(n)如取h(n)=每個牌與目的位置的間隔和，同樣可估計出至少要挪動h(n)步，才干到達(dá)目的，因此，有h(n)≤h*(n)第三章普通搜索原理3.2啟發(fā)式搜索283164751238476512/25/202363博弈中的啟發(fā)式搜索博弈空間的極小極大搜索:假定對手具有一樣的關(guān)于形狀空間的知識,且用該知識以一致方式競賽.博弈中的對手分別稱為MIN和MAX一種余一棋變體：博弈雙方要交替地將一堆牌分成數(shù)量不同的兩堆牌,最先無法分堆的棋手為失敗第三章普通搜索原理3.2啟發(fā)式搜索12/25/202364窮舉式的極小極大搜索博弈過程可以用一個樹來表示標(biāo)志葉節(jié)點假設(shè)MIN獲勝標(biāo)0,MAX獲勝標(biāo)1,標(biāo)志MIN節(jié)點為其子節(jié)點值中的最大值標(biāo)志MAX節(jié)點為其子節(jié)點值中的最小值這樣向上傳播,直至根節(jié)點第三章普通搜索原理3.2啟發(fā)式搜索12/25/202365第三章普通搜索原理3.2啟發(fā)式搜索一種余一棋變體樹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-10MINMAXMINMAXMINMAX12/25/202366固定層深的極小極大搜索這種戰(zhàn)略稱為n-層預(yù)判用于形狀空間不能夠全部展開的情形，比如國際象棋的形狀數(shù)大約是10120n的值由可用的時間和空間資源而定由于葉節(jié)點不是博弈的最終形狀,不能用勝利或失敗來標(biāo)志需用某個啟發(fā)評價函數(shù)的值來標(biāo)志這個向上傳播的值不表示能否可以勝利,只表示經(jīng)過n步可到達(dá)的最正確形狀,也能夠是完全誤導(dǎo)性的大多數(shù)博弈都為設(shè)計啟發(fā)提供了無限的想象空間第三章普通搜索原理3.2啟發(fā)式搜索12/25/202367第三章普通搜索原理3.2啟發(fā)式搜索一種九宮游戲的啟發(fā)函數(shù)啟發(fā)值為對MAX來說存在的一切能夠勝利道路,減去對MIN來說存在的一切能夠勝利道路XOXOXOX有6條,O有5條能夠的勝利道路E(n)=6-5=1X有4條,O有6條能夠的勝利道路E(n)=4-6=-2X有5條,O有4條能夠的勝利道路E(n)=5-4=112/25/202368第三章普通搜索原理3.2啟發(fā)式搜索α-β搜索單純的極小極大搜索需求對搜索空間進(jìn)展兩遍分析,效率低α-β搜索對極小極大搜索進(jìn)展改良根本思想：不搜索預(yù)判深度的整個空間，對能判別不起作用的分支那么去掉，不搜索以深度優(yōu)先方式到達(dá)預(yù)判層，在不斷剪枝的過程中，向上傳播評價值α值是與MAX節(jié)點關(guān)聯(lián)的不減小值β值是與MIN節(jié)點關(guān)聯(lián)的不增大值12/25/202369第三章普通搜索原理3.2啟發(fā)式搜索α-β搜索舉例MINMAXMINMAX235907421563907263023≥2≤3≥5≥2≤0≤2××≥3×12/25/202370雙向搜索搜索可以是從初始形狀開場向目的形狀的正向搜索；搜索也可以是從目的形狀開場向初始形狀的逆向搜索再能夠是同時從初始形狀向目的形狀的正向搜索和從目的形狀向初始形狀的逆向搜索，直至這兩條途徑在中途某處小結(jié)接為止，這種搜索戰(zhàn)略稱為雙向搜索第三章普通搜索原理3.2啟發(fā)式搜索12/25/202371消解原理概述消解原理又稱為歸結(jié)原理是一種重要的推理規(guī)那么它來源于定理證明：F1∧F2∧…∧Fn→W用反證法證：F=F1∧F2∧…∧Fn∧～W為永假等價于證明：F對應(yīng)的子句集S為不可滿足的歸結(jié)原理的根本思緒是：尋覓將S擴(kuò)展后的子句集S1，它可滿足性與S一樣，且容易判別可滿足性，從而知道S的可滿足性，那么定理得證第三章普通搜索原理3.3消解原理12/25/202372消解過程原子公式和原子公式的否認(rèn)稱為文字文字的析取構(gòu)成的公式稱為子句假設(shè)S中存在空子句，S為不可滿足的將F化為對應(yīng)的子句集S將S擴(kuò)展為可滿足性一樣的子句集S1，這個擴(kuò)展的過程就是歸結(jié)的過程 判別S1能否存在空子句第三章普通搜索原理3.3消解原理12/25/202373消解過程舉例E2∨E1〔前提〕 ～E2∨E3〔前提〕〔消解式〕E1∨E3〔結(jié)論〕第三章普通搜索原理3.3消解原理12/25/202374建立子句集消去蘊涵符號：～P∨Q取代P→Q減少否認(rèn)符號的管轄域?qū)ψ兞恳?guī)范化消去存在量詞化為前束形化為合取范式：如：PΛ(P∨Q〕Λ(～P∨Q〕消去全稱量詞獲得子句集改換變量名第三章普通搜索原理3.3消解原理12/25/202375化子句集例例：(z)(x)(y){[(P(x)Q(x))R(y)]U(z)}1,消蘊涵符 實際根據(jù)：ab=>~ab (z)(x)(y){[~(P(x)Q(x))R(y)]U(z)}2,挪動否認(rèn)符 實際根據(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消解原理12/25/202376化子句集例〔續(xù)1〕3,變量規(guī)范化 即：對于不同的約束，對應(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化〕 原那么：對于一個受存在量詞約束的變量，假設(shè)他不受全程量詞約束，那么該變量用一個常量替代，假設(shè)他受全程量詞約束，那么該變量用一個函數(shù)替代。 (z)(x)(y){[(~P(x)~Q(x))R(y)]U(z)}=>(x){[(~P(x)~Q(x))R(f(x))]U(a)}第三章普通搜索原理3.3消解原理12/25/202377化子句集例〔續(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消解原理12/25/202378化子句集例〔續(xù)3〕8,表示為子句集{~P(x)R(f(x))U(a),~Q(x))R(f(x))U(a)}9,變量規(guī)范化〔變量換名〕{~P(x1)R(f(x1))U(a),~Q(x2))R(f(x2))U(a)}第三章普通搜索原理3.3消解原理12/25/202379消解推理規(guī)那么L1、L2為任一原子公式，他們具有一樣的謂詞符號，但普通變量名不同知兩子句L1∨α和～L2∨β假設(shè)L1、L2具有最普通合一者σ那么可得新子句(α∨β)σ這個新子句叫做消解式第三章普通搜索原理3.3消解原理12/25/202380命題邏輯的消解推理舉例第三章普通搜索原理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〕12/25/202381謂詞邏輯的消解推理舉例第三章普通搜索原理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)/z12/25/202382消解反演求解過程消解反演是利用消解原理進(jìn)展命題證明。給定公式集S和目的公式L證明公式L的步驟如下：否認(rèn)L，得～L把～L添加到S中去把新產(chǎn)生的集合{～L,S}化成子句集運用消解原理力圖推導(dǎo)出一個表示矛盾的空子句第三章普通搜索原理3.3消解原理12/25/202383命題邏輯消解反演的例子設(shè)公理集： P, (PQ)R, (ST)Q, T求證：R子句集： (1)P (2)~P~QR (3)~SQ (4)~TQ (5)T (6)~R〔目的求反〕化子句集： (PQ)R=>~(PQ)R=>~P~QR (ST)Q=>~(ST)Q=>(~S~T)Q=>(~SQ)(~TQ)=>{~SQ,~TQ}第三章普通搜索原理3.3消解原理12/25/202384命題邏輯消解反演的例子〔續(xù)〕子句集： (1)P (2)~P~QR (3)~SQ (4)~TQ (5)T (6)~R〔目的求反〕歸結(jié)： (7)~P~Q(2,6) (8)~Q (1,7)(9)~T(4,8)(10)nil(5,9)第三章普通搜索原理3.3消解原理12/25/202385謂詞邏輯消解反演的例子例：知：IfFidogoeswhereverJohngoesandifJohnisatschool,whereisFido?(x)[AT(John,x)AT(Fido,x)] AT(John,School)求證：(x)AT(Fido,x)子句集：~AT(John,y)AT(Fido,y)AT(John,