華中科技大學(xué)人工智能及其應(yīng)用第三章一般搜索原理.pptx

1、第三章 一般搜索原理第三章 一般搜索原理 7/15/20221搜索技術(shù)搜索是人工智能中進(jìn)行問(wèn)題求解的一大類方法根據(jù)是否使用啟發(fā)式信息可分為 ：1，盲目搜索；2，啟發(fā)式搜索；根據(jù)問(wèn)題的表示方式分為：1，狀態(tài)空間搜索；2，與或樹(shù)搜索。 例如：用狀態(tài)空間法來(lái)求解問(wèn)題時(shí)，采用的是狀態(tài)空間搜索；用問(wèn)題歸約方法來(lái)求解問(wèn)題時(shí)，采用的是與或樹(shù)搜索。 第三章 一般搜索原理 3.1概述7/15/20222搜索的特點(diǎn)和通常的搜索空間不同，人工智能中大多數(shù)問(wèn)題的狀態(tài)空間在問(wèn)題求解之前不是全部知道的。所以，人工智能中的搜索可以分成兩個(gè)階段：狀態(tài)空間的生成階段和在該狀態(tài)空間中對(duì)所求解問(wèn)題狀態(tài)的搜索。由于一個(gè)問(wèn)題的整個(gè)空間

2、可能會(huì)非常的大，在搜索之前生成整個(gè)空間會(huì)占用太大的存儲(chǔ)空間。為此，狀態(tài)空間一般是逐漸擴(kuò)展的“目標(biāo)”狀態(tài)是在每次擴(kuò)展的時(shí)候進(jìn)行搜索的。第三章 一般搜索原理 3.1概述7/15/202233.2 盲目搜索第三章 一般搜索原理 3.2 盲目搜索7/15/20224盲目搜索 盲目搜索是按預(yù)定的控制策賂進(jìn)行搜索，沒(méi)有任何關(guān)于問(wèn)題本身的信息，在搜索過(guò)程中獲得的中間信息并不改變控制策略。由于搜索總是按預(yù)先規(guī)定的路線進(jìn)行，沒(méi)有考慮到問(wèn)題本身的特性，因此這種搜索具有盲目性，效率不高，不便于復(fù)雜問(wèn)題的求解。第三章 一般搜索原理 3.2 盲目搜索7/15/20225盲目搜索分類搜索策略可分為三大類不可撤回方式、回朔

3、方式、圖搜索方式不可撤回方式：每一次搜索時(shí)，利用局部知識(shí)根據(jù)最優(yōu)評(píng)價(jià)，選出下一狀態(tài)，選定后不能撤回，只能繼續(xù)回朔方式：在搜索過(guò)程中，有時(shí)會(huì)發(fā)現(xiàn)所選的路徑不適合找到目標(biāo)，這時(shí)允許退回去另選一條路徑。圖搜索方式： 將所有應(yīng)用過(guò)的操作和它們產(chǎn)生的狀態(tài)描述都以圖的形式記錄下來(lái)。由于當(dāng)前可繼續(xù)往下搜索的狀態(tài)不只一個(gè)，因此可以從其中任一個(gè)狀態(tài)往下搜索。圖搜索方式與回溯方式的不同之處在于，回溯方式不記億那些試探失敗的操作和它們產(chǎn)生的狀態(tài)描述，只記憶當(dāng)前正在搜索的路徑。圖搜索方式則保存所有試探過(guò)的路徑，因而可以在任何一條路徑上繼續(xù)搜索第三章 一般搜索原理 3.2 盲目搜索7/15/20226圖搜索方式與回溯方

4、式的不同回溯方式不記憶那些試探失敗的操作和它們產(chǎn)生的狀態(tài)描述，只記憶當(dāng)前正在搜索的路徑。圖搜索方式則保存所有試探過(guò)的路徑，因而可以在任何一條路徑上繼續(xù)搜索第三章 一般搜索原理 3.2 盲目搜索7/15/20227不可撤回搜索策略 不可撤回方式的控制策略是，選擇一條可應(yīng)用的操作作用于當(dāng)前狀態(tài)，不論后果如何都接著做下去。這個(gè)方法類似于高等數(shù)學(xué)中求函數(shù)極值的爬山法。在爬山法中，我們從任一點(diǎn)出發(fā)，在該點(diǎn)的最大梯度方向前進(jìn)一步，得到一個(gè)新的點(diǎn)，再在新點(diǎn)的最大梯度方向上前進(jìn)一步，一直到梯度為0為止，這個(gè)點(diǎn)就是函數(shù)的極大值點(diǎn)。如果函數(shù)只有一個(gè)極大值點(diǎn)則這個(gè)點(diǎn)就是該函數(shù)的最大值點(diǎn)。第三章 一般搜索原理 3.2

5、 盲目搜索7/15/20228不可撤回搜索的實(shí)現(xiàn)不可撤回搜索的實(shí)現(xiàn)是將狀態(tài)描述定義成一個(gè)實(shí)數(shù)值的爬山函數(shù)?？刂撇呗跃屠眠@個(gè)爬山函數(shù)來(lái)選擇一個(gè)可應(yīng)用的操作，施行該操作的結(jié)果應(yīng)使爬山函數(shù)的值得到最大限度的增加。第三章 一般搜索原理 3.2 盲目搜索7/15/20229不可撤回搜索舉例(一)選擇八數(shù)碼問(wèn)題我們選取“不在位”的數(shù)字個(gè)數(shù)的負(fù)值作為爬山函數(shù) 八數(shù)碼游戲的操作可描述為下面的4條產(chǎn)生式規(guī)則 (1) if空格不在最上一行then空格上移 (2) if空格不在最下一行then生格下移 (3) if空格不在最左一列then空格左移 (4) if空格不在最右一列then空格有移2 8 31 6 47

6、 51 2 38 47 6 5目標(biāo)狀態(tài)初始狀態(tài)第三章 一般搜索原理 3.2 盲目搜索7/15/202210不可撤回搜索舉例(二)從初始狀態(tài)出發(fā)，應(yīng)用第一條規(guī)則，空格上移可獲得爬山函數(shù)的最大增加、因此控 制策略選擇第一條規(guī)則作為當(dāng)前的操作。在沒(méi)有操作能夠增加爬山函數(shù)的值時(shí)可任選一個(gè)不減小函數(shù)值的操作，如果不存在這樣的操作，則過(guò)程停止。2 8 31 6 47 52 31 8 47 6 52 8 31 47 6 51 2 38 47 6 5 2 31 8 47 6 5-3-3-4-2-101 2 3 8 47 6 5目標(biāo)狀態(tài)爬山函數(shù)值第三章 一般搜索原理 3.2 盲目搜索7/15/202211不可撤

7、回搜索舉例(三)對(duì)于上例，采用不可撤回策略可以很快得到問(wèn)題的解。但一般來(lái)講，如果爬山函數(shù)有多個(gè)局部極大值存在，該策略可能會(huì)引導(dǎo)到局部極大值點(diǎn)，而達(dá)不到目標(biāo)狀態(tài)。例如當(dāng)八數(shù)碼問(wèn)題的初始狀態(tài)和目標(biāo)狀態(tài)分別如下時(shí)，任意一個(gè)可應(yīng)用的操作都會(huì)降低爬山函數(shù)的值，因此，得不到目標(biāo)：1 2 3 7 48 6 51 2 57 48 6 3目標(biāo)初始狀態(tài)第三章 一般搜索原理 3.2 盲目搜索7/15/202212回溯搜索策略回溯策略是一種試探性方式。在選擇一個(gè)操作時(shí)要建立一個(gè)回溯點(diǎn)。在搜索過(guò)程中，如果遇到了困難，則要返回到最近的一個(gè)回溯點(diǎn)，換一個(gè)操作繼續(xù)進(jìn)行搜索。第三章 一般搜索原理 3.2 盲目搜索7/15/20

8、2213回溯搜索策略舉例例：皇后問(wèn)題第三章 一般搜索原理 3.2 盲目搜索7/15/202214( )皇后問(wèn)題搜索過(guò)程（一）第三章 一般搜索原理 3.2 盲目搜索7/15/202215Q( )(1,1)皇后問(wèn)題搜索過(guò)程（二）第三章 一般搜索原理 3.2 盲目搜索7/15/202216QQ( )(1,1)(1,1) (2,3)皇后問(wèn)題搜索過(guò)程（三）第三章 一般搜索原理 3.2 盲目搜索7/15/202217Q( )(1,1)(1,1) (2,3)皇后問(wèn)題搜索過(guò)程（四）第三章 一般搜索原理 3.2 盲目搜索7/15/202218QQ( )(1,1)(1,1) (2,3)(1,1) (2,4)皇后問(wèn)

9、題搜索過(guò)程（五）第三章 一般搜索原理 3.2 盲目搜索7/15/202219QQQ( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)皇后問(wèn)題搜索過(guò)程（六）第三章 一般搜索原理 3.2 盲目搜索7/15/202220QQ( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)皇后問(wèn)題搜索過(guò)程（七）第三章 一般搜索原理 3.2 盲目搜索7/15/202221Q( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)皇后問(wèn)題搜索過(guò)程（八）第三章 一般搜索原理 3.2 盲目搜索7/1

10、5/202222( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)皇后問(wèn)題搜索過(guò)程（九）第三章 一般搜索原理 3.2 盲目搜索7/15/202223Q( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)(1,2)皇后問(wèn)題搜索過(guò)程（十）第三章 一般搜索原理 3.2 盲目搜索7/15/202224QQ( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)(1,2)(1,2) (2,4)皇后問(wèn)題搜索過(guò)程（十一）第三章 一般搜索原理 3.2 盲目搜索7/15/202225QQQ

11、( )(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)皇后問(wèn)題搜索過(guò)程（十二）第三章 一般搜索原理 3.2 盲目搜索7/15/202226QQQQ( )(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)皇后問(wèn)題搜索過(guò)程（十三）第三章 一般搜索原理 3.2 盲目搜索7/15/202227回溯搜索算法回溯搜索可以用遞歸的方法來(lái)實(shí)現(xiàn)下面的算法是一個(gè)

12、用遞歸實(shí)現(xiàn)的算法：BACKTRACK（DATA）DATA：當(dāng)前狀態(tài)。返回值：從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的路徑（以規(guī)則表的形式表示）或FAIL。第三章 一般搜索原理 3.2 盲目搜索7/15/202228回溯搜索算法（一）BACKTRACK(DATA)1, IF TERM(DATA) RETURN NIL;2, IF DEADEND(DATA) RETURN FAIL;3, RULES:=APPRULES(DATA);TERM: 找目標(biāo)DEADEND: 狀態(tài)不合法,無(wú)法繼續(xù)搜索APPRULES: 取可應(yīng)用規(guī)則集第三章 一般搜索原理 3.2 盲目搜索7/15/202229回溯搜索算法（二）4, LOOP

13、: IF NULL(RULES) RETURN FAIL;5, R:=FIRST(RULES);6, RULES:=TAIL(RULES);7, RDATA:=GEN(R, DATA);8, PATH:=BACKTRACK(RDATA);9, IF PATH=FAIL GO LOOP;10, RETURN CONS(R, PATH);TAIL: 刪除頭條規(guī)則GEN: 調(diào)用規(guī)則作用于當(dāng)前狀態(tài)CONS: 獲取解路徑規(guī)則表第三章 一般搜索原理 3.2 盲目搜索7/15/202230存在問(wèn)題及解決辦法問(wèn)題：深度問(wèn)題:如果深度太深死循環(huán)問(wèn)題: 如果狀態(tài)出現(xiàn)重復(fù)解決辦法：對(duì)搜索深度加以限制記錄從初始狀態(tài)到

14、當(dāng)前狀態(tài)的路徑第三章 一般搜索原理 3.2 盲目搜索7/15/202231增加約束后的回溯搜索算法BACKTRACK1（DATALIST）DATALIST：從初始到當(dāng)前的狀態(tài)表（逆向）返回值：從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的路徑（以規(guī)則表的形式表示）或FAIL。第三章 一般搜索原理 3.2 盲目搜索7/15/202232增加約束后的回溯搜索算法(一)1, DATA:=FIRST(DATALIST)2, IF MENBER(DATA, TAIL(DATALIST) RETURN FAIL;3, IF TERM(DATA) RETURN NIL;4, IF DEADEND(DATA) RETURN FAIL

15、;5, IF LENGTH(DATALIST)BOUND RETURN FAIL;第三章 一般搜索原理 3.2 盲目搜索7/15/202233增加約束后的回溯搜索算法(二)6, RULES:=APPRULES(DATA);7, LOOP: IF NULL(RULES) RETURN FAIL;8,R:=FIRST(RULES);9,RULES:=TAIL(RULES);第三章 一般搜索原理 3.2 盲目搜索7/15/202234增加約束后的回溯搜索算法(三)10,RDATA:=GEN(R, DATA);11,RDATALIST:=CONS(RDATA, DATALIST);12,PATH:=B

16、ACKTRCK1(RDATALIST)13,IF PATH=FAIL GO LOOP;14,RETURN CONS(R, PATH);第三章 一般搜索原理 3.2 盲目搜索7/15/202235圖搜索策略圖搜索策略就是在圖中尋找從起始點(diǎn)到目標(biāo)點(diǎn)的路徑的方法圖搜索的一般過(guò)程是構(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.2 盲目搜索7/15/202236圖搜索包括寬度優(yōu)先搜索：搜索以接近起始節(jié)點(diǎn)的程度依次擴(kuò)展節(jié)點(diǎn)，在對(duì)下一層搜索前

17、，必須搜索完本層的所有節(jié)點(diǎn)。深度優(yōu)先搜索：搜索首先擴(kuò)展最新產(chǎn)生的節(jié)點(diǎn)。等代價(jià)搜索：搜索沿最小代價(jià)節(jié)點(diǎn)進(jìn)行擴(kuò)展。第三章 一般搜索原理 3.2 盲目搜索7/15/202237圖搜索的一般過(guò)程成功是把第一個(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)始第三章 一般搜索原理 3.2 盲目搜索7/15/202238圖搜索過(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表中的

18、節(jié)點(diǎn)或者是已被擴(kuò)展而不能生成后繼節(jié)點(diǎn)的那些端節(jié)點(diǎn)，或者是搜索樹(shù)的非端節(jié)點(diǎn)重排OPEN表，實(shí)際上就是在選擇搜索順序，也就是擴(kuò)展的節(jié)點(diǎn)的順序。第三章 一般搜索原理 3.2 盲目搜索7/15/202239節(jié)點(diǎn)類型說(shuō)明.mj.mk.ml擴(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)第三章 一般搜索原理 3.2 盲目搜索7/15/202240圖搜索過(guò)程的圖示（一）現(xiàn)要擴(kuò)展它第三章 一般搜索原理 3.2 盲目搜索7/15/202241圖搜索過(guò)程的圖示（二）修改父子關(guān)系現(xiàn)要擴(kuò)展它第三章 一般搜索原理 3.2 盲目搜索7/15/202242圖搜

19、索過(guò)程的圖示（三）修改父子關(guān)系修改父子關(guān)系第三章 一般搜索原理 3.2 盲目搜索7/15/202243寬度優(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.2 盲目搜索7/15/202244目標(biāo)2 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7

20、 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 51256731 2 3 8 47 6 582 3 41 8 7 6 54八數(shù)碼難題的寬度優(yōu)先搜索樹(shù)按上下左右序走步第三章 一般搜索原理 3.2 盲目搜索7/15/202245寬度優(yōu)先搜索的性質(zhì)當(dāng)問(wèn)題有解時(shí)，一定能找到解當(dāng)問(wèn)題為單位代價(jià)值，且問(wèn)題有解時(shí)，一定能找到最優(yōu)解方法與問(wèn)題無(wú)關(guān)，具有通用性效率較低第三章 一般搜索原理 3.2 盲目搜索7/15/202246深度優(yōu)先搜索成功是把第一個(gè)節(jié)點(diǎn)(n)從OPEN表移至CLOSED表把n

21、的后繼節(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)？否成功第三章 一般搜索原理 3.2 盲目搜索7/15/2022472 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1

22、2 37 8 4 6 51 2 38 47 6 5123456789abcd1 2 3 8 47 6 5目標(biāo)。八數(shù)碼難題的深度優(yōu)先搜索樹(shù)第三章 一般搜索原理 3.2 盲目搜索7/15/202248深度優(yōu)先搜索的性質(zhì)一般不能保證找到最優(yōu)解當(dāng)深度限制不合理時(shí)，可能找不到解，可以將算法改為可變深度限制最壞情況時(shí)，搜索空間等同于窮舉是一個(gè)通用的與問(wèn)題無(wú)關(guān)的方法第三章 一般搜索原理 3.2 盲目搜索7/15/202249等代價(jià)搜索搜索樹(shù)的每條弧線上可能有代價(jià)值有些問(wèn)題要求搜索代價(jià)最小的解當(dāng)搜索樹(shù)的每條弧線上的代價(jià)值都為1時(shí)，寬度優(yōu)先搜索可以看成是最小代價(jià)搜索推廣寬度優(yōu)先搜索，以獲得最小代價(jià)的搜索方法稱為

23、等代價(jià)搜索第三章 一般搜索原理 3.2 盲目搜索7/15/202250等代價(jià)搜索成功是把具有最小g(i)值的節(jié)點(diǎn)i從OPEN表移至CLOSED表計(jì)算其后繼節(jié)點(diǎn)j的g(j)值。把其后繼節(jié)點(diǎn)放入OPEN表把S放入OPEN表否否OPEN為空？失敗開(kāi)始 i是否為目標(biāo)節(jié)點(diǎn)？是S是否為目標(biāo)節(jié)點(diǎn)？否成功是令g(s)=0第三章 一般搜索原理 3.2 盲目搜索7/15/2022513.3 啟發(fā)式搜索第三章 一般搜索原理 3.3 啟發(fā)式搜索7/15/202252為何引入啟發(fā)式信息盲目搜索的效率低，耗費(fèi)過(guò)多的計(jì)算時(shí)間和空間，容易產(chǎn)生組合爆炸。利用知識(shí)來(lái)引導(dǎo)搜索，達(dá)到減少搜索范圍，降低問(wèn)題復(fù)雜度的目的。對(duì)搜索產(chǎn)生幫助

24、的信息稱為啟發(fā)信息第三章 一般搜索原理 3.3 啟發(fā)式搜索7/15/202253啟發(fā)式信息對(duì)搜索方法的影響啟發(fā)信息的多少用啟發(fā)信息強(qiáng)度來(lái)表示不同的啟發(fā)信息對(duì)搜索方法帶來(lái)不同的影響：強(qiáng)：降低搜索工作量，但可能導(dǎo)致找不到最優(yōu)解弱：一般導(dǎo)致工作量加大，極限情況下變?yōu)槊つ克阉?，但可能可以找到最?yōu)解第三章 一般搜索原理 3.3 啟發(fā)式搜索7/15/202254啟發(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ù)中拋

25、棄或修剪。用來(lái)估算節(jié)點(diǎn)希望程度的方法為估價(jià)函數(shù)體現(xiàn)問(wèn)題自身的啟發(fā)性信息的函數(shù)稱為啟發(fā)函數(shù)第三章 一般搜索原理 3.3 啟發(fā)式搜索7/15/202255對(duì)啟發(fā)式搜索的認(rèn)識(shí)有些啟發(fā)信息能夠大大減少搜索工作量，但不能保證能夠得到最小代價(jià)路徑我們往往希望獲得路徑代價(jià)和求該路徑所需的搜索代價(jià)的綜合為最小由于計(jì)算綜合代價(jià)很困難，因此，比較兩種方法的優(yōu)劣，依賴使用的經(jīng)驗(yàn)第三章 一般搜索原理 3.3 啟發(fā)式搜索7/15/202256有序搜索若按估價(jià)函數(shù)的增序?qū)PEN表進(jìn)行排序，這種搜索方法叫做有序搜索或最佳優(yōu)先搜索有序搜索的有效性取決于估價(jià)函數(shù)的選擇，否則有可能失去一個(gè)最好的解甚至全部的解如果沒(méi)有合適的選擇

26、，可考慮兩個(gè)方面的內(nèi)容：一個(gè)是時(shí)間和空間的折中保證有一個(gè)解第三章 一般搜索原理 3.3 啟發(fā)式搜索7/15/202257有序搜索框圖成功是選取f值最小的節(jié)點(diǎn)i，從OPEN表移至CLOSED表擴(kuò)展i，計(jì)算后繼節(jié)點(diǎn)j的f(j)，對(duì)OPEN表重排序，調(diào)整親子關(guān)系把S放入OPEN表，計(jì)算f(s)是否否OPEN為空？i是目標(biāo)節(jié)點(diǎn)？失敗開(kāi)始第三章 一般搜索原理 3.3 啟發(fā)式搜索7/15/202258估價(jià)函數(shù)：f(n)=d(n)+w(n) 其中， d(n):節(jié)點(diǎn)的深度 w(n):節(jié)點(diǎn)放錯(cuò)棋子數(shù)目八數(shù)碼難題的有序搜索樹(shù)2 8 31 6 47 52 31 8 47 6 52 8 31 47 6 52 31 8

27、 47 6 52 8 31 47 6 51 2 38 47 6 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 51 2 37 8 4 6 5 2 31 8 47 6 554646677567551 2 3 8 47 6 5目標(biāo)5估價(jià)函數(shù)值第三章 一般搜索原理 3.3 啟發(fā)式搜索7/15/202259A算法A算法是一種有序搜索的啟發(fā)式搜索算法。估價(jià)函數(shù)的形式： f(n) = g(n) + h(n)g(n)是從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)n的實(shí)際代價(jià)h(n)是從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)Sg的最小路徑代價(jià)h*(n)的啟發(fā)式估計(jì)

28、h(n)稱為啟發(fā)函數(shù)：第三章 一般搜索原理 3.3 啟發(fā)式搜索7/15/202260A算法流程1, OPEN:=(s), f(s):=g(s)+h(s);2, LOOP: IF OPEN=( ) THEN EXIT(FAIL);3, n:=FIRST(OPEN);4, IF GOAL(n) THEN EXIT(SUCCESS);5, REMOVE(n, OPEN), ADD(n, CLOSED);6, EXPAND(n) mi, 計(jì)算f(n, mi):=g(n, mi)+h(mi);第三章 一般搜索原理 3.3 啟發(fā)式搜索7/15/202261A算法流程（續(xù)）ADD(mj, OPEN), 標(biāo)記

29、mj到n的指針；IF f(n, mk)f(mk) THEN f(mk):=f(n, mk), 標(biāo)記mk到n的指針；IF f(n, ml)f(ml,) THEN f(ml):=f(n, ml),標(biāo)記ml到n的指針, ADD(ml, OPEN);7, OPEN中的節(jié)點(diǎn)按f值從小到大排序；8, GO LOOP；第三章 一般搜索原理 3.3 啟發(fā)式搜索7/15/202262最佳圖搜索算法A*（A*算法）在A算法中，如果對(duì)于任意點(diǎn)n滿足條件：h(n)h*(n)則A算法稱為A*算法。如果存在從初始節(jié)點(diǎn)S0目標(biāo)節(jié)點(diǎn)Sg的最小路徑， A*算法就一定能搜索到第三章 一般搜索原理 3.3 啟發(fā)式搜索7/15/20

30、2263A*算法估價(jià)函數(shù)舉例在問(wèn)題求解過(guò)程中，不可能明確知道h*(n) ，可根據(jù)經(jīng)驗(yàn)估計(jì)下界范圍條件例如，8數(shù)碼問(wèn)題如取h(n) = “不在位”的牌數(shù)，可估計(jì)出至少要移動(dòng)h(n) 步，才能達(dá)到目標(biāo)，因此，有h(n) h*(n) 如取h (n) = 每個(gè)牌與目標(biāo)位置的距離和，同樣可估計(jì)出至少要移動(dòng)h(n) 步，才能達(dá)到目標(biāo)，因此，有h(n) h*(n) 2 8 31 6 47 51 2 38 47 6 5第三章 一般搜索原理 3.3 啟發(fā)式搜索7/15/2022643.4 與或樹(shù)搜索第三章 一般搜索原理 3.4 與或樹(shù)搜索7/15/202265與或樹(shù)搜索 與或樹(shù)的搜索是實(shí)現(xiàn)用與或樹(shù)表示的問(wèn)題的求

31、解。與或樹(shù)的搜索過(guò)程將形成一棵與或樹(shù)，這種由搜索過(guò)程形成的與或樹(shù)稱為搜索樹(shù)。與或樹(shù)的搜索過(guò)程實(shí)際上是一個(gè)不斷尋找解樹(shù)的過(guò)程。第三章 一般搜索原理 3.4 與或樹(shù)搜索7/15/202266幾個(gè)概念由可解節(jié)點(diǎn)構(gòu)成，并且由這些可解節(jié)點(diǎn)可以推出初始節(jié)點(diǎn)為可解節(jié)點(diǎn)的子樹(shù)稱為解樹(shù)，解樹(shù)中一定包含初始節(jié)點(diǎn)。沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)稱為端節(jié)點(diǎn)。本原問(wèn)題所對(duì)應(yīng)的節(jié)點(diǎn)稱為終止節(jié)點(diǎn)?？山鈫?wèn)題所對(duì)應(yīng)的節(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)至少一個(gè)子節(jié)點(diǎn)是可解節(jié)點(diǎn)的或節(jié)點(diǎn)是可解節(jié)點(diǎn)。第三章 一般搜索原理 3.4 與或樹(shù)搜索7/15/202267與或樹(shù)搜索的一般過(guò)程(1)把原

32、始問(wèn)題作為初始節(jié)點(diǎn)S0，并把它作為當(dāng)前節(jié)點(diǎn)；(2)應(yīng)用分解或等價(jià)變換操作對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行擴(kuò)展(3)為每個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針(4)選擇合適的子節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)，反復(fù)執(zhí)行第(2)步和第(3)步，多次調(diào)用標(biāo)記過(guò)程，直到初始節(jié)點(diǎn)被標(biāo)記。如果某個(gè)節(jié)點(diǎn)被標(biāo)記為可解節(jié)點(diǎn)，則其不可解的后繼節(jié)點(diǎn)就可從搜索樹(shù)中刪去；如果被標(biāo)記為不可解節(jié)點(diǎn)則其后繼節(jié)點(diǎn)也可從搜索樹(shù)中刪去。第三章 一般搜索原理 3.4 與或樹(shù)搜索7/15/202268寬度優(yōu)先搜索成功是把第一個(gè)節(jié)點(diǎn)(n)從OPEN表移至CLOSED表可擴(kuò)展處理把S放入OPEN表是否否OPEN為空？節(jié)點(diǎn)(n)是否有可擴(kuò)展？失敗開(kāi)始不可擴(kuò)展處理S標(biāo)為可解節(jié)點(diǎn)？是否S

33、標(biāo)為不可解節(jié)點(diǎn)？是否失敗第三章 一般搜索原理 3.4 與或樹(shù)搜索7/15/202269寬度優(yōu)先搜索（續(xù)）可擴(kuò)展處理把節(jié)點(diǎn)(n)標(biāo)記為不可解節(jié)點(diǎn)把n的后繼節(jié)點(diǎn)放入OPEN表的末端，提供返回節(jié)點(diǎn)n的指針不可擴(kuò)展處理若n的后繼節(jié)點(diǎn)中有終節(jié)點(diǎn)，則標(biāo)記其為可解節(jié)點(diǎn)從OPEN表中刪去具有可解先輩的節(jié)點(diǎn)調(diào)用可解標(biāo)記過(guò)程，標(biāo)記其先輩節(jié)點(diǎn)從OPEN表中刪去具有不可解先輩的節(jié)點(diǎn)調(diào)用不可解標(biāo)記過(guò)程，標(biāo)記其先輩節(jié)點(diǎn)返回返回第三章 一般搜索原理 3.4 與或樹(shù)搜索7/15/202270寬度優(yōu)先搜索舉例（一） t1,t2,t3為終節(jié)點(diǎn)ABC為端節(jié)點(diǎn)搜索過(guò)程：擴(kuò)展1號(hào)生成2、3號(hào)節(jié)點(diǎn)，都是非終節(jié)點(diǎn)擴(kuò)展2號(hào)生成A、4號(hào)節(jié)點(diǎn)，

34、都是非終節(jié)點(diǎn) 擴(kuò)展3號(hào)生成t1、5號(hào)節(jié)點(diǎn)，t1是終節(jié)點(diǎn)，標(biāo)記為可解節(jié)點(diǎn)，調(diào)用可解標(biāo)記過(guò)程，由于t1的父節(jié)點(diǎn)是與節(jié)點(diǎn)，不能確定其父節(jié)點(diǎn)是可解t2A13542BCt1t3第三章 一般搜索原理 3.4 與或樹(shù)搜索7/15/202271寬度優(yōu)先搜索舉例（二）A是端節(jié)點(diǎn)，不可擴(kuò)展，調(diào)用不可解標(biāo)記過(guò)程，由于A的父節(jié)點(diǎn)是或節(jié)點(diǎn)，不能確定其父節(jié)點(diǎn)是不可解擴(kuò)展4號(hào)生成t2、B節(jié)點(diǎn)，t2是終節(jié)點(diǎn)，標(biāo)記為可解節(jié)點(diǎn)，調(diào)用可解標(biāo)記過(guò)程，由于t2的父節(jié)點(diǎn)是或節(jié)點(diǎn)，標(biāo)節(jié)點(diǎn)4為可解，繼續(xù)向上，標(biāo)節(jié)點(diǎn)2為可解，但無(wú)法確定標(biāo)節(jié)點(diǎn)1擴(kuò)展5號(hào)生成t3、C節(jié)點(diǎn)，t3是終節(jié)點(diǎn)，標(biāo)記為可解節(jié)點(diǎn)，調(diào)用可解標(biāo)記過(guò)程，由于t3的父節(jié)點(diǎn)是或節(jié)點(diǎn)，

35、標(biāo)節(jié)點(diǎn)5為可解，繼續(xù)向上，標(biāo)節(jié)點(diǎn)3為可解，最后可確定節(jié)點(diǎn)1為可解t2A13542BCt1t3第三章 一般搜索原理 3.4 與或樹(shù)搜索7/15/202272深度優(yōu)先搜索成功是把第一個(gè)節(jié)點(diǎn)(n)從OPEN表移至CLOSED表可擴(kuò)展處理把S放入OPEN表是否否OPEN為空？節(jié)點(diǎn)(n)是否有可擴(kuò)展？失敗開(kāi)始不可擴(kuò)展處理S標(biāo)為可解節(jié)點(diǎn)？是否S標(biāo)為不可解節(jié)點(diǎn)？是否失敗節(jié)點(diǎn)(n)深度=d？是否第三章 一般搜索原理 3.4 與或樹(shù)搜索7/15/202273深度優(yōu)先搜索（續(xù)）可擴(kuò)展處理把節(jié)點(diǎn)(n)標(biāo)記為不可解節(jié)點(diǎn)把n的后繼節(jié)點(diǎn)放入OPEN表的前端，提供返回節(jié)點(diǎn)n的指針不可擴(kuò)展處理若n的后繼節(jié)點(diǎn)中有終節(jié)點(diǎn)，則標(biāo)記

36、其為可解節(jié)點(diǎn)從OPEN表中刪去具有可解先輩的節(jié)點(diǎn)調(diào)用可解標(biāo)記過(guò)程，標(biāo)記其先輩節(jié)點(diǎn)從OPEN表中刪去具有不可解先輩的節(jié)點(diǎn)調(diào)用不可解標(biāo)記過(guò)程，標(biāo)記其先輩節(jié)點(diǎn)返回返回第三章 一般搜索原理 3.4 與或樹(shù)搜索7/15/2022743.5 與或樹(shù)的啟發(fā)式搜索第三章 一般搜索原理 3.5 與或樹(shù)的啟發(fā)式搜索7/15/202275與或樹(shù)的啟發(fā)式搜索 與或樹(shù)的啟發(fā)式搜索過(guò)程是一種利用搜索過(guò)程所得到的啟發(fā)性信息尋找最優(yōu)解樹(shù)的過(guò)程。對(duì)搜索的每一步，算法都試圖找到一個(gè)最有希望成為最優(yōu)解樹(shù)的子樹(shù)。最優(yōu)解樹(shù)是指代價(jià)最小的那棵解樹(shù)。第三章 一般搜索原理 3.5 與或樹(shù)的啟發(fā)式搜索7/15/202276解樹(shù)的代價(jià)設(shè)n為節(jié)點(diǎn)

37、，n1，n2，nk為其子節(jié)點(diǎn)， h(n)為節(jié)點(diǎn)n的代價(jià)， c(n，ni)為節(jié)點(diǎn)n到其子節(jié)點(diǎn)ni的邊代價(jià)若n為終節(jié)點(diǎn)，則h(n)0。若n為或節(jié)點(diǎn)，則h(n)min(c(n，ni)+h(ni)若n為與節(jié)點(diǎn)，則n的代價(jià)可用和代價(jià)法或最大代價(jià)法。和代價(jià)法：h(n)(c(n，ni)+h(ni)最大代價(jià)法：h(n)maxc(n，ni)+h(ni) 若n是端節(jié)點(diǎn)，但非終節(jié)點(diǎn)，則n不可擴(kuò)展，h(n)。解樹(shù)的代價(jià)，為根節(jié)點(diǎn)的代價(jià)。第三章 一般搜索原理 3.5 與或樹(shù)的啟發(fā)式搜索7/15/202277解樹(shù)的代價(jià)舉例圖中與或樹(shù)包括兩棵解樹(shù)左邊的解樹(shù)由S、A、t1、C及t3組成右邊的解樹(shù)由S、B、t2、D及t4組成。

38、t1、t2、t3、t4為終節(jié)點(diǎn)E 、 F是端節(jié)點(diǎn)左邊的解樹(shù):按和代價(jià)：h(S)2+4+6+214按最大代價(jià)：h(S)2+6+210右邊的解樹(shù):按和代價(jià)：h(S)1+5+3+211按最大代價(jià)：h(S)1+5+28可見(jiàn)，右邊的解樹(shù)是最優(yōu)解樹(shù)。t2SBDCAEFt1t3t464222351第三章 一般搜索原理 3.5 與或樹(shù)的啟發(fā)式搜索7/15/202278希望解樹(shù) 為了找到最優(yōu)解樹(shù)，搜索過(guò)程的任何時(shí)刻都應(yīng)該選擇那些最有希望成為最優(yōu)解樹(shù)一部分的節(jié)點(diǎn)進(jìn)行擴(kuò)展由于這些節(jié)點(diǎn)及其父節(jié)點(diǎn)所構(gòu)成的與或樹(shù)最有可能成為最優(yōu)解樹(shù)的一部分，因此稱為希望解樹(shù)，簡(jiǎn)稱為希望樹(shù)。需要注意，希望解樹(shù)是會(huì)隨搜索過(guò)程而不斷變化的。希

39、望樹(shù)定義：初始節(jié)點(diǎn)S在希望樹(shù)T中若n為具有子節(jié)點(diǎn)n1，n2，nk的或節(jié)點(diǎn)，其子節(jié)點(diǎn)ni在希望樹(shù)T中的充分必要條件： h(ni)min(c(n，nt)+h(nt)若n為與節(jié)點(diǎn)，其子節(jié)點(diǎn)都在希望樹(shù)T。第三章 一般搜索原理 3.5 與或樹(shù)的啟發(fā)式搜索7/15/202279與或樹(shù)的啟發(fā)式搜索過(guò)程成功是計(jì)算希望樹(shù)T可擴(kuò)展處理把S放入OPEN表，計(jì)算h(S)是否否節(jié)點(diǎn)(n)是否可擴(kuò)展？開(kāi)始終節(jié)點(diǎn)處理S標(biāo)為可解節(jié)點(diǎn)？是否S標(biāo)為不可解節(jié)點(diǎn)？是否失敗把OPEN表中第一個(gè)屬于T的節(jié)點(diǎn)(n)移至CLOSED表節(jié)點(diǎn)(n)是終節(jié)點(diǎn)？不可擴(kuò)展處理第三章 一般搜索原理 3.5 與或樹(shù)的啟發(fā)式搜索7/15/202280與或樹(shù)

40、的啟發(fā)式搜索過(guò)程（續(xù)1）可擴(kuò)展處理把節(jié)點(diǎn)(n)標(biāo)記為不可解節(jié)點(diǎn)把n的后繼節(jié)點(diǎn)放入OPEN表的末端，提供返回節(jié)點(diǎn)n的指針不可擴(kuò)展處理計(jì)算這些子節(jié)點(diǎn)及其先輩節(jié)點(diǎn)的h值從OPEN表中刪去具有不可解先輩的節(jié)點(diǎn)在T上運(yùn)用不可解標(biāo)記過(guò)程，標(biāo)記其先輩節(jié)點(diǎn)返回返回第三章 一般搜索原理 3.5 與或樹(shù)的啟發(fā)式搜索7/15/202281與或樹(shù)的啟發(fā)式搜索過(guò)程（續(xù)2）把節(jié)點(diǎn)(n)標(biāo)記為可解節(jié)點(diǎn)終節(jié)點(diǎn)處理從OPEN表中刪去具有可解先輩的節(jié)點(diǎn)在T上運(yùn)用可解標(biāo)記過(guò)程，標(biāo)記其先輩節(jié)點(diǎn)返回第三章 一般搜索原理 3.5 與或樹(shù)的啟發(fā)式搜索7/15/202282與或樹(shù)的啟發(fā)式搜索舉例 在該例子中，搜索過(guò)程每次擴(kuò)展節(jié)點(diǎn)時(shí)都同時(shí)擴(kuò)展

41、兩層，且按一層或節(jié)點(diǎn)、一層與節(jié)點(diǎn)的間隔方式進(jìn)行擴(kuò)展。后面將要討論的博弈樹(shù)就是這種結(jié)構(gòu)。第三章 一般搜索原理 3.5 與或樹(shù)的啟發(fā)式搜索7/15/202283擴(kuò)展初始節(jié)點(diǎn)S后S擴(kuò)展后如圖所示B、C、E、F的h值由啟發(fā)函數(shù)估計(jì)節(jié)點(diǎn)S、A、D的h值按和代價(jià)法計(jì)算。此時(shí)，S的右子樹(shù)是當(dāng)前的希望樹(shù)接著，對(duì)右子樹(shù)的E節(jié)點(diǎn)進(jìn)行擴(kuò)展SDFCA8338372BE第三章 一般搜索原理 3.5 與或樹(shù)的啟發(fā)式搜索7/15/202284右子樹(shù)的E節(jié)點(diǎn)擴(kuò)展后E擴(kuò)展后如圖所示各端節(jié)點(diǎn)h值由啟發(fā)函數(shù)估計(jì)先輩節(jié)點(diǎn)的h值按和代價(jià)法計(jì)算。此時(shí)，S的左子樹(shù)代價(jià)小，因此，當(dāng)前左子樹(shù)又變成了希望樹(shù)接著，對(duì)左子樹(shù)的B節(jié)點(diǎn)進(jìn)行擴(kuò)展SDFC

42、A8339116BEF372272第三章 一般搜索原理 3.5 與或樹(shù)的啟發(fā)式搜索27/15/202285H左子樹(shù)的B節(jié)點(diǎn)擴(kuò)展后S9CA833F372DF11E76220206JL22K2IGB第三章 一般搜索原理 3.5 與或樹(shù)的啟發(fā)式搜索7/15/202286H左子樹(shù)的C節(jié)點(diǎn)擴(kuò)展后9833F372DF11E76220206JL22K2SIGBN020952PMCA第三章 一般搜索原理 3.5 與或樹(shù)的啟發(fā)式搜索7/15/2022873.6 博弈樹(shù)搜索第三章 一般搜索原理 3.6 博弈樹(shù)搜索7/15/202288博弈博弈是一類富有智能行為的競(jìng)爭(zhēng)活動(dòng)，如下棋、打牌、戰(zhàn)爭(zhēng)等博弈可分為雙人完備信息

43、博弈奔和機(jī)遇性博弈雙人完備信息博弈：兩位選手對(duì)壘，輪流走步，每一方不僅知道對(duì)方已經(jīng)走過(guò)的棋步，而且還能估計(jì)出對(duì)方未來(lái)的走步。對(duì)弈的結(jié)果是一方贏，另一方輸；或者雙方和局。例如，有象棋、圍棋等。機(jī)遇性博弈：指存在不可預(yù)測(cè)性的博弈，例如擲幣等。我們只討論雙人完備信息博弈問(wèn)題。第三章 一般搜索原理 3.6 博弈樹(shù)搜索7/15/202289博弈過(guò)程分析在博弈過(guò)程的每一步，可供雙方選擇的行動(dòng)方案都可能有多種。雙方都希望自己能夠獲勝。任何一方走步時(shí)，都是選澤對(duì)自己最為有利，而對(duì)另一方最為不利的行動(dòng)方案。雙方交替選擇行動(dòng)方案，直到一方勝利或雙方和局。第三章 一般搜索原理 3.6 博弈樹(shù)搜索7/15/202290從MAX方看博弈假設(shè)博弈的一方為MAX，另一方為MIN。可供自己選擇的行動(dòng)方案之間是“或”的關(guān)系主動(dòng)權(quán)掌握在自己手里，選擇哪個(gè)方案完全由自己決定；可供MIN選擇的行動(dòng)方案之間是“與”的關(guān)系主動(dòng)權(quán)掌握在MIN的手里，任何一個(gè)方案都有可能被MIN選中，MAX必須防止那種對(duì)自己最為不利的情況的發(fā)生。第三章 一般搜索原理 3.6 博弈樹(shù)搜索