第5章 搜索求解策略

1、第 5 章 搜索求解策略,教材： 王萬良《人工智能及其應(yīng)用》（第2版） 高等教育出版社，2008. 6,2,第5章 搜索求解策略,5.1 搜索的概念5.2 狀態(tài)空間的搜索策略5.3 盲目的圖搜索策略5.4 啟發(fā)式圖搜索策略5.5 與/或圖搜索策略,3,第5章 搜索求解策略,5.1 搜索的概念5.2 狀態(tài)空間知識(shí)表示方法5.3 盲目的圖搜索策略5.4 啟發(fā)式圖搜索

2、策略5.5 與/或圖搜索策略,4,5.1 搜索的概念,問題求解：?jiǎn)栴}的表示。 選擇一種相對(duì)合適的求解方法。問題求解的基本方法：搜索法、歸約法、歸結(jié)法、推理法及產(chǎn)生式等。,5,5.1 搜索的概念,5.1.1 搜索的基本問題與主要過程5.1.2 搜索策略,6,5.1.1 搜索的基本問題與主要過程,搜索中需要解決的基本問題：（1）是否一定能找到一個(gè)解。（2）是否終止運(yùn)行或是否會(huì)陷入一個(gè)死循環(huán)。（3）找到的解是否是最

3、佳解。（4）時(shí)間與空間復(fù)雜性如何。,7,5.1.1 搜索的基本問題與主要過程,搜索的主要過程：(1) 從初始或目的狀態(tài)出發(fā)，并將它作為當(dāng)前狀態(tài)。(2) 掃描操作算子集，將適用當(dāng)前狀態(tài)的一些操作算子作用于當(dāng)前狀態(tài)而得到新的狀態(tài)，并建立指向其父結(jié)點(diǎn)的指針 。(3) 檢查所生成的新狀態(tài)是否滿足結(jié)束狀態(tài)，如果滿足，則得到問題的一個(gè)解，并可沿著有關(guān)指針從結(jié)束狀態(tài)反向到達(dá)開始狀態(tài)，給出一解答路徑；否則，將新狀態(tài)作為當(dāng)前狀態(tài)，返回第(

4、2)步再進(jìn)行搜索。,8,5.1.2 搜索策略,1. 搜索方向： (1) 數(shù)據(jù)驅(qū)動(dòng)：從初始狀態(tài)出發(fā)的正向搜索。,正向搜索——從問題給出的條件（一個(gè)用于狀態(tài)轉(zhuǎn)換的操作算子集合）出發(fā)。,逆向搜索：先從想達(dá)到的目的入手，看哪些操作算子能產(chǎn)生該目的以及應(yīng)用這些操作算子產(chǎn)生目的時(shí)需要哪些條件。,(2) 目的驅(qū)動(dòng)：從目的狀態(tài)出發(fā)的逆向搜索。,9,5.1.2 搜索策略,1. 搜索方向： (3) 雙向搜索,雙向搜索：從開始狀態(tài)出發(fā)作

5、正向搜索，同時(shí)又從目的狀態(tài)出發(fā)作逆向搜索，直到兩條路徑在中間的某處匯合為止。,10,5.1.2 搜索策略,2. 盲目搜索與啟發(fā)式搜索:（1）盲目搜索：在不具有對(duì)特定問題的任何有關(guān)信息的條件下，按固定的步驟（依次或隨機(jī)調(diào)用操作算子）進(jìn)行的搜索。 （2）啟發(fā)式搜索：考慮特定問題領(lǐng)域可應(yīng)用的知識(shí)，動(dòng)態(tài)地確定調(diào)用操作算子的步驟，優(yōu)先選擇較適合的操作算子，盡量減少不必要的搜索，以求盡快地到達(dá)結(jié)束狀態(tài)。,11,第5章 搜索求解策略,5.1

6、 搜索的概念5.2 狀態(tài)空間知識(shí)表示方法5.3 盲目的圖搜索策略5.4 啟發(fā)式圖搜索策略5.5 與/或圖搜索策略,12,5.2 狀態(tài)空間知識(shí)表示方法,5.2.1 狀態(tài)空間表示法5.2.2 狀態(tài)空間的圖描述,13,5.2.1 狀態(tài)空間表示法,狀態(tài)：表示系統(tǒng)狀態(tài)、事實(shí)等敘述型知識(shí)的一組變量或數(shù)組：,,,操作：表示引起狀態(tài)變化的過程型知識(shí)的一組關(guān) 系或函數(shù)：,T,14,5.2.1 狀態(tài)空間表示法,狀態(tài)空

7、間：利用狀態(tài)變量和操作符號(hào)，表示系統(tǒng)或問題的有關(guān)知識(shí)的符號(hào)體系，狀態(tài)空間是一個(gè)四元組：,,,,,,,,：狀態(tài)集合。 ：操作算子的集合。 ：包含問題的初始狀態(tài)是 的非空子集。 ：若干具體狀態(tài)或滿足某些性質(zhì)的路徑信息描述。,15,5.2.1 狀態(tài)空間表示法,求解路徑：從 結(jié)點(diǎn)到 結(jié)點(diǎn)的路徑。,,,,,：狀態(tài)空間的一個(gè)解。,狀態(tài)空間的一個(gè)解：一個(gè)有限的操作算子序列。,

8、16,,例1 八數(shù)碼問題的狀態(tài)空間。,5.2.1 狀態(tài)空間表示法,狀態(tài)集 ：所有擺法,操作算子：,將空格向上移Up將空格向左移Left將空格向下移Down將空格向右移Right,17,5.2.2 狀態(tài)空間的圖描述,,,,,,,,,,,,,,,狀態(tài)空間的有向圖描述,18,5.2.2 狀態(tài)空間的圖描述,八數(shù)碼狀態(tài)空間圖,19,例2 旅行商問題（traveling salesman problem, TSP

9、）或郵遞員路徑問題。,5.2.2 狀態(tài)空間的圖描述,可能路徑：費(fèi)用為375的路徑（A，B，C，D，E，A）,,,,,,20,5.2.2 狀態(tài)空間的圖描述,,,21,第5章 搜索求解策略,5.1 搜索的概念5.2 狀態(tài)空間知識(shí)表示方法5.3 盲目的圖搜索策略5.4 啟發(fā)式圖搜索策略5.5 與/或圖搜索策略,22,5.3 盲目的圖搜索策略,5.3.1 回溯策略5.3.2 寬度優(yōu)先搜索策略5.3.3 深度優(yōu)

10、先搜索策略,23,5.3.1 回溯策略,帶回溯策略的搜索： 從初始狀態(tài)出發(fā)，不停地、試探性地尋找路徑，直到它到達(dá)目的或“不可解結(jié)點(diǎn)”，即“死胡同”為止。若它遇到不可解結(jié)點(diǎn)就回溯到路徑中最近的父結(jié)點(diǎn)上，查看該結(jié)點(diǎn)是否還有其他的子結(jié)點(diǎn)未被擴(kuò)展。若有，則沿這些子結(jié)點(diǎn)繼續(xù)搜索；如果找到目標(biāo)，就成功退出搜索，返回解題路徑。,24,,遞歸過程：,5.3.1 回溯策略,Step Track (DataList)：Data：=

11、First(DataList);if Member(Data, Tail(DataList)) then return FAIL; *回老路退回if Goal(Data) then return NIL; *達(dá)到目的地成功返回if DeadEnd(Data) then return FAIL; *達(dá)到不合理狀態(tài)，退出

12、if Length(DataList) > Bound then return FAIL; *已到深度限制，退回Rules：= AppRules(Data); *得出可應(yīng)用的規(guī)則集Loop：if Null(Rules) then return FAIL; *進(jìn)入死胡同，退回R：= First(Rules);

13、 *取出第一條可用規(guī)則Rules：= Tail(Rules); Newdata：= Gen(R,Data); *運(yùn)用規(guī)則，生成新狀態(tài)NewDataList：= Cons(Newdata, DataList);Path：= Back Track(NewDataList); *遞歸If Path：= FAI

14、L then go loop else return Cons(R, Path);,25,5.3.1 回溯策略,,回溯搜索示意圖,,,,,,,,,,,,,,,,,,,,,,26,5.3.1 回溯策略,回溯搜索的算法(1) PS（path states）表：保存當(dāng)前搜索路徑上的狀態(tài)。如果找到了目的，PS就是解路徑上的狀態(tài)有序集。 (2) NPS（new path states）表：新的路徑狀態(tài)表。它包含了等待搜索的狀

15、態(tài)，其后裔狀態(tài)還未被搜索到，即未被生成擴(kuò)展 。(3) NSS（no solvable states）表：不可解狀態(tài)集，列出了找不到解題路徑的狀態(tài)。如果在搜索中擴(kuò)展出的狀態(tài)是它的元素，則可立即將之排除，不必沿該狀態(tài)繼續(xù)搜索。,27,,5.3.1 回溯策略,Function backtrack：begin PS：= [Start]; NPS：= [Start]; NSS：= [ ]; CS：= Start; *初始化

16、 while NPS[ ] do begin if CS=目的狀態(tài) then return(PS); *成功，返回解題路徑 if CS沒有子狀態(tài)（不包括PS，NPS和NSS中已有的狀態(tài)） then begin while（(PS非空) and (CS=PS中的第一個(gè)元素)）do

17、 begin 將CS加入NSS *標(biāo)明此狀態(tài)不可解 從PS中刪除第一個(gè)元素CS *回溯 從NPS中刪除第一個(gè)元素CS； CS：= NPS中的第一個(gè)元素；,28,,5.3.1 回溯策略,end;

18、 將CS加入PS； endelse begin 將CS子狀態(tài)（不包括PS、NPS和NSS中已有的）加入NPS； CS：= NPS中第一個(gè)元素； 將CS加入到PS； end end； return FAIL; end.,29,,回溯

19、搜索示意圖的回溯軌跡： 初值：PS=[A]； NPS=[A]； NSS=[ ]； CS=A。,5.3.1 回溯策略,30,5.3.1 回溯策略,圖搜索算法（深度優(yōu)先、寬度優(yōu)先、最好優(yōu)先搜索等）的回溯思想：,（1）用未處理狀態(tài)表（NPS）使算法能返回（回溯）到其 中任一狀態(tài)。 （2）用一張“死胡同”狀態(tài)表（NSS）來避免算法重新搜索 無解的路徑。 （3）在PS 表中記錄當(dāng)前搜索路

20、徑的狀態(tài)，當(dāng)滿足目的時(shí)可 以將它作為結(jié)果返回。 （4）為避免陷入死循環(huán)必須對(duì)新生成的子狀態(tài)進(jìn)行檢查， 看它是否在該三張表中 。,31,5.3.2 寬度優(yōu)先搜索策略,,,open表（NPS表）：已經(jīng)生成出來但其子狀態(tài)未被搜索的狀態(tài)。closed表（ PS表和NSS表的合并）：記錄了已被生成擴(kuò)展過的狀態(tài)。,寬度優(yōu)先搜索法中狀態(tài)的搜索次序,32,5.3.2 寬度優(yōu)先搜索策略,Procedure

21、breadth_first_searchbeginopen：= [start]; closed：= [ ] *初始化while open [ ] do begin 從open表中刪除第一個(gè)狀態(tài)，稱之為n； 將n放入closed表中； if n = 目的狀態(tài) then return (success); 生成n的所有子狀態(tài)； 從n的

22、子狀態(tài)中刪除已在open或closed表中出現(xiàn)的狀態(tài)； 將n的其余子狀態(tài)，按生成的次序加入到open表的后段。 end; end;,open表：隊(duì)列結(jié)構(gòu)，即先進(jìn)先出（FIFO）的數(shù)據(jù)結(jié)構(gòu),33,例3 通過搬動(dòng)積木塊，希望從初始狀態(tài)達(dá)到一個(gè)目的狀態(tài)，即三塊積木堆疊在一起。,5.3.2 寬度優(yōu)先搜索策略,,34,操作算子為MOVE（X，Y）：把積木X搬到Y(jié)（積木或桌面）上面。,5.3.2 寬度優(yōu)先搜索策

23、略,MOVE（A，Table）：“搬動(dòng)積木A到桌面上”。,操作算子可運(yùn)用的先決條件：（1）被搬動(dòng)積木的頂部必須為空。（2）如果 Y 是積木，則積木 Y 的頂部也必須為空。（3）同一狀態(tài)下，運(yùn)用操作算子的次數(shù)不得多于一次。,35,,,5.3.2 寬度優(yōu)先搜索策略,,,,,,,,,,,,36,5.3.3 深度優(yōu)先搜索策略,,37,在深度優(yōu)先搜索中，當(dāng)搜索到某一個(gè)狀態(tài)時(shí)，它所有的子狀態(tài)以及子狀態(tài)的后裔狀態(tài)都必須先于該狀態(tài)的兄弟狀態(tài)被

24、搜索。 為了保證找到解，應(yīng)選擇合適的深度限制值，或采取不斷加大深度限制值的辦法，反復(fù)搜索，直到找到解。,5.3.3 深度優(yōu)先搜索策略,38,深度優(yōu)先搜索過程：,5.3.3 深度優(yōu)先搜索策略,Procedure depth_first_searchbeginopen:=[start];closed:=[ ];d:=深度限制值while open[ ] dobegin從open表中刪除第一個(gè)狀態(tài)，稱之為n;將n放入clos

25、ed表中；if n=目的狀態(tài) then return (success);if n的深度>d then continue;生成n的所有子狀態(tài)；從n的子狀態(tài)中刪除已在open或closed表中出現(xiàn)的狀態(tài)；將n的其余子狀態(tài)，按生成的次序加入到open 表的前端。endend。,open表：堆棧結(jié)構(gòu)，即先進(jìn)后出（FILO）的數(shù)據(jù)結(jié)構(gòu)。open表：所有已生成但未作擴(kuò)展的狀態(tài),closed表記錄了已擴(kuò)展過的狀態(tài),39,深

26、度優(yōu)先搜索并不能保證第一次搜索到的某個(gè)狀態(tài)時(shí)的路徑是到這個(gè)狀態(tài)的最短路徑。 對(duì)任何狀態(tài)而言，以后的搜索有可能找到另一條通向它的路徑。如果路徑的長(zhǎng)度對(duì)解題很關(guān)鍵的話，當(dāng)算法多次搜索到同一個(gè)狀態(tài)時(shí)，它應(yīng)該保留最短路徑。,5.3.3 深度優(yōu)先搜索策略,40,例4 卒子穿陣問題，要求一卒子從頂部通過下圖所示的陣列到達(dá)底部。卒子行進(jìn)中不可進(jìn)入到代表敵兵駐守的區(qū)域（標(biāo)注1），并不準(zhǔn)后退。假定深度限制值為5。,5.3.3 深度優(yōu)先搜索策略,

27、,陣列圖,41,,5.3.3 深度優(yōu)先搜索策略,,,,,,,open表：S17、S18closed表：S0～S16,,卒子穿陣的深度優(yōu)先搜索樹,42,第5章 搜索求解策略,5.1 搜索的概念5.2 狀態(tài)空間知識(shí)表示方法5.3 盲目的圖搜索策略5.4 啟發(fā)式圖搜索策略5.5 與/或圖搜索策略,43,5.4 啟發(fā)式圖搜索策略,5.4.1 啟發(fā)式策略5.4.2 啟發(fā)信息和估價(jià)函數(shù)5.4.3 A搜索算法5.

28、4.4 A*搜索算法及其特性分析,44,5.4.1 啟發(fā)式策略,“啟發(fā)”（heuristic）：關(guān)于發(fā)現(xiàn)和發(fā)明操作算子及搜索方法的研究。在狀態(tài)空間搜索中，啟發(fā)式被定義成一系列操作算子，并能從狀態(tài)空間中選擇最有希望到達(dá)問題解的路徑。啟發(fā)式策略：利用與問題有關(guān)的啟發(fā)信息進(jìn)行搜索。,45,5.4.1 啟發(fā)式策略,運(yùn)用啟發(fā)式策略的兩種基本情況： （1）一個(gè)問題由于在問題陳述和數(shù)據(jù)獲取方面固有 的模糊性，可能會(huì)使它沒

29、有一個(gè)確定的解。 （2）雖然一個(gè)問題可能有確定解，但是其狀態(tài)空間 特別大，搜索中生成擴(kuò)展的狀態(tài)數(shù)會(huì)隨著搜索 的深度呈指數(shù)級(jí)增長(zhǎng)。,46,例5 一字棋。在九宮棋盤上，從空棋盤開始，雙方輪流在棋盤上擺各自的棋子 ? 或 ? （每次一枚），誰先取得三子一線（一行、一列或一條對(duì)角線）的結(jié)果就取勝。,5.4.1 啟發(fā)式策略,,,? 和 ? 能夠在棋盤中擺成的各種不同的棋局就是問題空間中的不同狀態(tài)。

30、 9個(gè)位置上擺放{空， ? ， ?}有 39 種棋局。 可能的走法 ： 。,47,5.4.1 啟發(fā)式策略,啟發(fā)式策略的運(yùn)用,?,?,?,48,,5.4.1 啟發(fā)式策略,,,,,,啟發(fā)式搜索下縮減的狀態(tài)空間,49,5.4.2 啟發(fā)信息和估價(jià)函數(shù),在具體求解中，能夠利用與該問題有關(guān)的信息來簡(jiǎn)化搜索過程，稱此類信息為啟發(fā)信息。啟發(fā)式搜索：利用啟發(fā)信息的搜索過程。,50,5.4.2

31、 啟發(fā)信息和估價(jià)函數(shù),求解問題中能利用的大多是非完備的啟發(fā)信息：（1）求解問題系統(tǒng)不可能知道與實(shí)際問題有關(guān)的全部信息，因而無法知道該問題的全部狀態(tài)空間，也不可能用一套算法來求解所有的問題。（2）有些問題在理論上雖然存在著求解算法，但是在工程實(shí)踐中，這些算法不是效率太低，就是根本無法實(shí)現(xiàn)。,一字棋：9！，西洋跳棋：1078，國(guó)際象棋：10120，圍棋：10761。假設(shè)每步可以搜索一個(gè)棋局，用極限并行速度（10-104年/步）來處理，

32、搜索一遍國(guó)際象棋的全部棋局也得1016年即1億億年才可以算完！,51,5.4.2 啟發(fā)信息和估價(jià)函數(shù),啟發(fā)信息的分類： （1）陳述性啟發(fā)信息 （2）過程性啟發(fā)信息 （3）控制性啟發(fā)信息利用控制性的啟發(fā)信息的情況： （1）沒有任何控制性知識(shí)作為搜索的依據(jù)，因而搜索的每一步完全是隨意的。 （2）有充分的控制知識(shí)作為依據(jù)，因而搜索的每一步選擇都是正確的，但這是不現(xiàn)實(shí)的。,52,5.4.2 啟發(fā)信息和估價(jià)函

33、數(shù),估價(jià)函數(shù)的任務(wù)就是估計(jì)待搜索結(jié)點(diǎn)的“有希望”程度，并依次給它們排定次序（在open表中）。,,,,估價(jià)函數(shù) ：從初始結(jié)點(diǎn)經(jīng)過 結(jié)點(diǎn)到達(dá)目的 結(jié)點(diǎn)的路徑的最小代價(jià)估計(jì)值，其一般形式是,,,,,一般地，在 中， 的比重越大，越傾向于寬度優(yōu)先搜索方式，而 的比重越大，表示啟發(fā)性能越強(qiáng)。,53,例6 八數(shù)碼的估價(jià)函數(shù)設(shè)計(jì)方法有多種，并且不同的估價(jià)函數(shù)對(duì)求解八數(shù)碼問題有不同的影響。 最簡(jiǎn)單的估價(jià)函數(shù)：

34、取一格局與目的格局相比，其位置不符的將牌數(shù)目。 較好的估價(jià)函數(shù)：各將牌移到目的位置所需移動(dòng)的距離的總和。 第三種估價(jià)函數(shù)：對(duì)每一對(duì)逆轉(zhuǎn)將牌乘以一個(gè)倍數(shù)。 第四種估價(jià)函數(shù)：克服了僅計(jì)算將牌逆轉(zhuǎn)數(shù)目策略的局限，將位置不符將牌數(shù)目的總和與3倍將牌逆轉(zhuǎn)數(shù)目相加。,5.4.2 啟發(fā)信息和估價(jià)函數(shù),54,5.4.3 A搜索算法,啟發(fā)式圖搜索法的基本特點(diǎn)：如何尋找并設(shè)計(jì)一個(gè)與問題有關(guān)的 及構(gòu)出

35、 ， 然后以 的大小來排列待擴(kuò)展?fàn)顟B(tài)的次序，每次選擇 值最小者進(jìn)行擴(kuò)展。,,,,,open表：保留所有已生成而未擴(kuò)展的狀態(tài)。 closed表：記錄已擴(kuò)展過的狀態(tài)。 進(jìn)入open表的狀態(tài)是根據(jù)其估值的大小插入到表中合適的位置，每次從表中優(yōu)先取出啟發(fā)估價(jià)函數(shù)值最小的狀態(tài)加以擴(kuò)展。,55,一般啟發(fā)式圖搜索算法（簡(jiǎn)記為A）,5.4.3 A搜索算法,procedure heuristic_se

36、archopen：=[start]；closed：=[ ]；f(s)：=g(s)+h(s)；*初始化while open≠[ ] dobegin從open表中刪除第一個(gè)狀態(tài)，稱之為n；if n=目的狀態(tài)then return(success)；生成n的所有子狀態(tài)；if n沒有任何子狀態(tài)then continue；for n的每個(gè)子狀態(tài)docase子狀態(tài)is not already on open表or closed表

37、；begin計(jì)算該子狀態(tài)的估價(jià)函數(shù)值；將該子狀態(tài)加到open表中； end；,56,,5.4.3 A搜索算法,case子狀態(tài)is already on open表：if該子狀態(tài)是沿著一條比在open表已有的更短路徑而到達(dá)then 記錄更短路徑走向及其估價(jià)函數(shù)值；case子狀態(tài)is already on closed表：if該子狀態(tài)是沿著一條比在closed表已有的更短路徑而到達(dá)thenbeg

38、in將該子狀態(tài)從closed表移到open表中；記錄更短路徑走向及其估價(jià)函數(shù)值；end；case end；將n放入closed表中；根據(jù)估價(jià)函數(shù)值，從小到大重新排列open表；end；*open表中結(jié)點(diǎn)已耗盡return(failure)；end.,57,5.4.3 A搜索算法,每次重復(fù)時(shí)，A搜索算法從open表中取出第一個(gè)狀態(tài)，如果該狀態(tài)滿足目的條件，則算法返回到該狀態(tài)的搜索路徑。如果open表的第一個(gè)

39、狀態(tài)不是目的狀態(tài)，則算法利用與之相匹配的一系列操作算子進(jìn)行相應(yīng)的操作來產(chǎn)生它的子狀態(tài)。如果某個(gè)子狀態(tài)已在open表（或closed表）中出現(xiàn)過，即該狀態(tài)再一次被發(fā)現(xiàn)時(shí)，則通過刷新它的祖先狀態(tài)的歷史記錄，使算法極有可能找到到達(dá)目的狀態(tài)的更短的路徑接著，A搜索算法open表中每個(gè)狀態(tài)的估價(jià)函數(shù)值，按照值的大小重新排序，將值最小的狀態(tài)放在表頭，使其第一個(gè)被擴(kuò)展。,58,,5.4.3 A搜索算法,59,5.4.3 A搜索算法,例7 利

40、用A搜索算法求解八數(shù)碼問題的搜索樹，其估價(jià)函數(shù)定義為 ：狀態(tài)的深度，每步為單位代價(jià)。 ：以“不在位”的將牌數(shù)作為啟發(fā)信息的度量。,,,：為狀態(tài) 到目的狀態(tài)的最優(yōu)路徑的代價(jià)。 ：A搜索算法 → A*搜索算法。,60,,5.4.3 A搜索算法,,61,open表和closed表內(nèi)狀態(tài)排列的變化情況,5.4.3 A搜索算法,62,如果某一問題有解，那么利用A*搜索算法對(duì)該問題進(jìn)行搜索則

41、一定能搜索到解，并且一定能搜索到最優(yōu)的解而結(jié)束。上例中的八數(shù)碼A搜索樹也是A*搜索樹，所得的解路（s，B，E，I，K，L）為最優(yōu)解路，其步數(shù)為狀態(tài)L（5）上所標(biāo)注的5 。,5.4.4 A*搜索算法及其特性分析,63,1. 可采納性 當(dāng)一個(gè)搜索算法在最短路徑存在時(shí)能保證找到它，就稱它是可采納的。2. 單調(diào)性 搜索算法的單調(diào)性：在整個(gè)搜索空間都是局部可采納的。一個(gè)狀態(tài)和任一個(gè)子狀態(tài)之間的差由該狀態(tài)與其子狀態(tài)之間的實(shí)際

42、代價(jià)所限定。,5.4.4 A*搜索算法及其特性分析,64,3. 信息性 在兩個(gè)A*啟發(fā)策略的 中，如果對(duì)搜索空間中的任一狀態(tài) 都有 ，就稱策略 具有更多的信息性。,5.4.4 A*搜索算法及其特性分析,65,第5章 搜索求解策略,5.1 搜索的概念5.2 狀態(tài)空間知識(shí)表示方法5.3 盲目的圖搜索策略5.4 啟發(fā)式圖搜索策略5.5 與/或圖搜索策略,66,5.5

43、 與/或圖搜索策略,1. 分解──與樹,,,與樹問題分解,67,5.5.1 與/或圖表表達(dá)法,2. 變換──或樹,或樹問題變換,5.5 與/或圖搜索策略,68,5.5.1 與/或圖表表達(dá)法,例8 猴子和香蕉問題。,5.5 與/或圖搜索策略,,,猴子和香蕉問題,69,5.5 與/或圖搜索策略,,,設(shè)系統(tǒng)的狀態(tài)用四元數(shù)組描述：,,,,,,：猴子所處水平位置 ：臺(tái)子所在水平位置 ：猴子是否在臺(tái)子上（ ，在；