機器人第六章 迷宮比賽與搜索算法

1、機器人第六章 迷宮比賽與搜索算法第1頁，共110頁，2022年，5月20日，2點19分，星期四本章內容1. 迷宮比賽簡介2. 搜索的基本知識3. 狀態(tài)空間的搜索策略4. 與/或樹的搜索策略5. 搜索策略性能的評價第2頁，共110頁，2022年，5月20日，2點19分，星期四1、迷宮比賽簡介比賽內容 制造一個自主控制的機器人，能在迷宮模型中運動，并盡快找到出口離開迷宮。第3頁，共110頁，2022年，5月20日，2點19分，星期四場地1、迷宮比賽簡介起始區(qū)終止區(qū)（迷宮場地參考圖）第4頁，共110頁，2022年，5月20日，2點19分，星期四場地1、迷宮比賽簡介起始區(qū)終止區(qū)紅色色塊黃色色塊黑色色塊

2、（機器人經過相應的色塊將被加時間）第5頁，共110頁，2022年，5月20日，2點19分，星期四簡單的行走策略左手規(guī)則（障礙在機器人的左邊）1、前方沒有發(fā)現障礙，左邊發(fā)現障礙，機器人繼續(xù)前進2、如果機器人前方發(fā)現障礙，則原地右轉避開障礙3、如果機器人前方和左邊都沒有發(fā)現障礙，左轉，尋找左側障礙1、迷宮比賽簡介第6頁，共110頁，2022年，5月20日，2點19分，星期四簡單的行走策略左手規(guī)則1、迷宮比賽簡介第7頁，共110頁，2022年，5月20日，2點19分，星期四簡單的行走策略右手規(guī)則（障礙在機器人的右邊）1、前方沒有發(fā)現障礙，右邊發(fā)現障礙，機器人繼續(xù)前進2、如果機器人前方發(fā)現障礙，則原地

3、左轉避開障礙3、如果機器人前方和右邊都沒有發(fā)現障礙，右轉，尋找右側障礙1、迷宮比賽簡介第8頁，共110頁，2022年，5月20日，2點19分，星期四簡單的行走策略1、迷宮比賽簡介第9頁，共110頁，2022年，5月20日，2點19分，星期四簡單的行走策略1、迷宮比賽簡介怎樣找到路徑和最佳路徑？第10頁，共110頁，2022年，5月20日，2點19分，星期四2、搜索的基本知識搜索的概念根據問題的實際情況，不斷尋找可利用的知識，從而構造一條可行的推理路線，使問題得到解決的過程。第11頁，共110頁，2022年，5月20日，2點19分，星期四2、搜索的基本知識搜索的使用場合1、在知識不完全，沒有成熟

4、的算法可使用。2、理論上有算法，但問題的復雜度高，用計算機求解有時間、空間的局限性。第12頁，共110頁，2022年，5月20日，2點19分，星期四2、搜索的基本知識搜索的分類盲目搜索啟發(fā)式搜索第13頁，共110頁，2022年，5月20日，2點19分，星期四2、1 搜索的分類盲目搜索按預定的控制策略進行搜索，在搜索過程中獲得的中間信息不用來改進控制策略。通用，效率低，不便于復雜問題的求解。是一種不得已而采取的方法第14頁，共110頁，2022年，5月20日，2點19分，星期四2、1 搜索的分類啟發(fā)式搜索在搜索過程中，根據問題本身的特性或搜索過程中產生的一些與問題有關的啟發(fā)信息，指導搜索朝著最有

5、希望的推理方向前進，加速問題的求解過程，并找到最優(yōu)解。 第15頁，共110頁，2022年，5月20日，2點19分，星期四2、1 搜索的分類查找第16頁，共110頁，2022年，5月20日，2點19分，星期四2、2 狀態(tài)空間表示法狀態(tài)空間表示法用來表示問題及其搜索過程的一種方法。包含三個元素：狀態(tài)、算符、狀態(tài)空間。第17頁，共110頁，2022年，5月20日，2點19分，星期四2、2 狀態(tài)空間表示法狀態(tài)描述問題求解過程中不同時刻的狀況。 Sk = (Sk0, Sk1 , Skn) Skn：代表每個具體的狀態(tài)。 其中還包括初始狀態(tài)、目標狀態(tài)。第18頁，共110頁，2022年，5月20日，2點19分

6、，星期四2、2 狀態(tài)空間表示法算符使問題從一種狀態(tài)變化為另一種狀態(tài)的操作。狀態(tài)空間由問題的全部狀態(tài)及一切可用算符所構成的集合。狀態(tài)空間圖狀態(tài)空間的圖示形式。是一個有向圖，節(jié)點表示狀態(tài)，有向邊表示算符。第19頁，共110頁，2022年，5月20日，2點19分，星期四2、2 狀態(tài)空間表示法(舉例)二階漢諾塔問題 要求把A、B兩塊金片全部移到另一個鋼針上。規(guī)定每次只能移動一片，并且任何時刻不能出現B在A的上面。第20頁，共110頁，2022年，5月20日，2點19分，星期四2、2 狀態(tài)空間表示法(舉例)二階漢諾塔問題 用二元組SK=(SA,SB)表示問題的狀態(tài), SA表示金盤A所在的桿號, SB表示

7、金盤B所在的桿號。 全部可能的狀態(tài)有9種, 可表示如下： S0=(1,1), S1=(1,2) , S2=(1,3)S3=(2,1), S4=(2,2) , S5=(2,3)S6=(3,1), S7=(3,2) , S8=(3,3)問題的初始狀態(tài)集合為S=S0,目標狀態(tài)集合為G=S4,S8。第21頁，共110頁，2022年，5月20日，2點19分，星期四2、2 狀態(tài)空間表示法(舉例)二階漢諾塔問題9種狀態(tài)第22頁，共110頁，2022年，5月20日，2點19分，星期四2、2 狀態(tài)空間表示法(舉例)二階漢諾塔問題算符分別用A(i,j)及B(i,j)表示： A(i,j)表示把A盤從第i號桿移到第j

8、號桿上; B(i,j)表示把B盤從第i號桿移到第j號桿上。則，算符共有12個。A(1,2),A(1,3),A(2,1),A(2,3),A(3,1),A(3,2)B(1,2),B(1,3),B(2,1),B(2,3),B(3,1),B(3,2)第23頁，共110頁，2022年，5月20日，2點19分，星期四2、2 狀態(tài)空間表示法(舉例)二階漢諾塔問題 由9種可能的狀態(tài)和12個算符, 二階漢諾塔問題的狀態(tài)空間圖如下：從(1,1)到(2,2)或(3,3)的任何一條通路都是問題的一個解。第24頁，共110頁，2022年，5月20日，2點19分，星期四2、2 狀態(tài)空間表示法(舉例)猴子和香蕉在一個房間內

9、有一只猴子、一個箱子和一束香蕉。香蕉掛在天花板下方，但猴子的高度不足以碰到它。那么這只猴子怎樣才能摘到香蕉呢? 第25頁，共110頁，2022年，5月20日，2點19分，星期四2、2 狀態(tài)空間表示法(舉例)猴子和香蕉用一個四元表列(W,x,Y,z)來表示這個問題的狀態(tài)， 其中W猴子的水平位置x當猴子在箱子頂上時取x=1；否則取x=0Y箱子的水平位置z當猴子摘到香蕉時取z=1；否則取z=0 。 第26頁，共110頁，2022年，5月20日，2點19分，星期四2、2 狀態(tài)空間表示法(舉例)猴子和香蕉 全部可能的狀態(tài)有13種, 可表示如下： S0=(a,0,b,0), S1=(a,0,c,0) ,

10、S2=(a,0,a,0), S3=(c,0,b,0) , S4=(c,0,c,0), S5=(c,0,a,0), S6=(b,0,b,0), S7=(b,0,c,0), S8=(b,0,a,0), S9=(a,1,a,0), S10=(b,1,b,0), S11=(c,1,c,0),S12=(c,1,c,1)問題的初始狀態(tài)集合為S=S0,目標狀態(tài)集合為G=S12。第27頁，共110頁，2022年，5月20日，2點19分，星期四2、2 狀態(tài)空間表示法(舉例)猴子和香蕉算符用下面的表示： (1) goto(U)猴子走到相鄰的水平位置U (2) pushbox(V)猴子把箱子推到相鄰的水平位置V (

11、3) climbbox猴子爬上箱頂 (4) godownbox猴子爬下箱子 (5) grasp猴子摘到香蕉 則，算符共有11個，包括猴子移動的4個，箱子移動的4個，猴子爬上箱子1個、爬下箱子1個，猴子摘到香蕉1個。第28頁，共110頁，2022年，5月20日，2點19分，星期四2、2 狀態(tài)空間表示法(舉例)猴子和香蕉 由13種可能的狀態(tài)和11個算符, 猴子和香蕉問題的狀態(tài)空間圖如下：第29頁，共110頁，2022年，5月20日，2點19分，星期四2、2 狀態(tài)空間表示法需要定義狀態(tài)、算符。問題的求解過程，是一個不斷把算符作用于狀態(tài)的過程。問題的解是從初始狀態(tài)到目標狀態(tài)所用算符構成的序列。使用算符

12、最少的解是最優(yōu)解。對一個狀態(tài)選取哪個算符操作，取決于搜索策略。不同的搜索策略，操作順序不一定相同。(重點討論的問題)第30頁，共110頁，2022年，5月20日，2點19分，星期四2、3 與/或樹表示法與/或樹表示法用于表示問題及其求解過程的一種方法，通常用于表示比較復雜問題的求解。對于一個復雜問題，直接求解往往比較困難，可以對其進行簡化。簡化使用的兩個操作：分解、等價變換第31頁，共110頁，2022年，5月20日，2點19分，星期四2、3 與/或樹表示法分解把一個復雜問題分解為若干個較為容易求解的子問題。每個子問題又可繼續(xù)分解。不斷重復，直到不需要或者不能再分解為止。復合各子問題的解就得到

13、原問題的解。第32頁，共110頁，2022年，5月20日，2點19分，星期四2、3 與/或樹表示法分解PP1P2P3與樹分解形成“與”樹第33頁，共110頁，2022年，5月20日，2點19分，星期四2、3 與/或樹表示法等價變換把一個原問題變換為若干個較為容易求解的新問題。若新問題中有一個可求解，則就得到了原問題的解。第34頁，共110頁，2022年，5月20日，2點19分，星期四2、3 與/或樹表示法等價變換等價變換形成“或”樹PP1P2P3或樹第35頁，共110頁，2022年，5月20日，2點19分，星期四2、3 與/或樹表示法分解、等價變換結合使用兩種方法結合使用形成“與/或”樹第36

14、頁，共110頁，2022年，5月20日，2點19分，星期四2、3 與/或樹表示法本原問題不能再分解或變換，而且是直接可解的子問題。端節(jié)點沒有子節(jié)點的節(jié)點終止節(jié)點本原問題對應的節(jié)點Pttt第37頁，共110頁，2022年，5月20日，2點19分，星期四2、3 與/或樹表示法可解節(jié)點是一個終止節(jié)點。是一個”或“節(jié)點，并且子節(jié)點中至少有一個是可解節(jié)點。是一個”與“節(jié)點，并且子節(jié)點全部是可解節(jié)點。不可解節(jié)點不屬于可解節(jié)點的節(jié)點。第38頁，共110頁，2022年，5月20日，2點19分，星期四2、3 與/或樹表示法解樹要判斷原問題是否可解，就必須要找出一棵解樹。解樹：由可解節(jié)點構成，并且由這些可解節(jié)點能

15、夠推出初始節(jié)點為可解節(jié)點的子樹。第39頁，共110頁，2022年，5月20日，2點19分，星期四2、3 與/或樹表示法PtttPttt解樹第40頁，共110頁，2022年，5月20日，2點19分，星期四2、3 與/或樹表示法(舉例)三階漢諾塔問題 要求把A、B、C三塊金片全部移到另一個鋼針上。規(guī)定每次只能移動一片，并且任何時刻不能出現大的金片在小的金片上面。第41頁，共110頁，2022年，5月20日，2點19分，星期四2、3 與/或樹表示法(舉例)三階漢諾塔問題可把三階梵塔問題分解為下面的三個子問題： (1) 把A、B盤從1號桿移到2號桿。 (2) 把C盤從1號桿移到3號桿。 (3) 把A、

16、B盤從2號桿移到3號桿。其中子問題(1)、(3)又分別可分解為三個子問題。 第42頁，共110頁，2022年，5月20日，2點19分，星期四2、3 與/或樹表示法(舉例)三階漢諾塔問題用三元組表示問題在任一時刻的狀態(tài)：(i, j, k)其中，i,j,k分別表示金片A、B、C所在的桿號。第43頁，共110頁，2022年，5月20日，2點19分，星期四2、3 與/或樹表示法(舉例)三階漢諾塔問題三階漢諾塔問題的與/或樹 第44頁，共110頁，2022年，5月20日，2點19分，星期四2、3 與/或樹表示法(舉例)三階漢諾塔問題問題的解：(1, 1, 1)(3, 1, 1)(3, 1, 1)(3,

17、2, 1)(3, 2, 1)(2, 2, 1)(2, 2, 1)(2, 2, 3)(2, 2, 3)(1, 2, 3)(1, 2, 3)(1, 3, 3)(1, 3, 3) (3, 3, 3) 第45頁，共110頁，2022年，5月20日，2點19分，星期四3、 狀態(tài)空間的搜索策略使用搜索求解問題時的狀態(tài)關系圖。第46頁，共110頁，2022年，5月20日，2點19分，星期四3、 狀態(tài)空間的搜索策略基本思想：通過搜索尋找一個操作算符的調用序列，使問題從初始狀態(tài)變遷到目標狀態(tài)。變遷過程中的狀態(tài)序列，或相應的操作算符調用序列稱為從初始狀態(tài)到目標狀態(tài)的解答路徑。搜索空間的壓縮程度取決于采用的搜索算法

18、。第47頁，共110頁，2022年，5月20日，2點19分，星期四3、 狀態(tài)空間的搜索策略分類第48頁，共110頁，2022年，5月20日，2點19分，星期四3、1 狀態(tài)空間的一般搜索過程搜索過程要使用的兩個表OPEN表-存放待擴展節(jié)點CLOSED表-存放已被擴展節(jié)點s-指示初始狀態(tài)節(jié)點G-指示搜索圖，其中的節(jié)點存放在OPEN表或CLOSED表中第49頁，共110頁，2022年，5月20日，2點19分，星期四3、1 狀態(tài)空間的一般搜索過程一般搜索過程 1) G:=s; /算法開始時搜索圖只包括初始狀態(tài)節(jié)點；2) OPEN:=(s), CLOSED:=( ); /此時僅有作為待擴展節(jié)點，而CLO

19、SED表為空；3) 若OPEN是空表，則搜索失敗，結束；/因為此時并未搜索到解答（目標狀態(tài)），但又無法繼續(xù)搜索；第50頁，共110頁，2022年，5月20日，2點19分，星期四3、1 狀態(tài)空間的一般搜索過程一般搜索過程 4) 取OPEN表的首節(jié)點作為當前要被擴展的節(jié)點n，同時將節(jié)點n移至CLOSED表； 5) 若n是目標狀態(tài)節(jié)點，則搜索成功結束，給出解答路徑； 6) 擴展節(jié)點n，將節(jié)點n的子節(jié)點置于子節(jié)點集合，并加入搜索圖G中；第51頁，共110頁，2022年，5月20日，2點19分，星期四3、1 狀態(tài)空間的一般搜索過程7) 標記和修改指針：全新節(jié)點未曾在G中出現過（加入OPEN表，并建立從子

20、節(jié)點到父節(jié)點n的指針）已在OPEN表的節(jié)點（比較子節(jié)點經由新、老父節(jié)點到達初始狀態(tài)節(jié)點s的路徑代價，若經由新父節(jié)點的代價較小，則修改子節(jié)點的指針，指向新父節(jié)點）已在CLOSED表的節(jié)點（與第2類同樣的處理，并把這些子節(jié)點從CLOSED表中移出，重新加入OPEN表）第52頁，共110頁，2022年，5月20日，2點19分，星期四3、1 狀態(tài)空間的一般搜索過程8) 按某種原則重新排序OPEN表中的節(jié)點；9） 返回 3）第53頁，共110頁，2022年，5月20日，2點19分，星期四3、1 狀態(tài)空間的一般搜索過程開始把S放入OPEN表OPEN表為空表？是失敗否把第一個節(jié)點（n）從OPEN移至CLOS

21、ED表n為目標節(jié)點？是成功否把n的后繼節(jié)點放入OPEN表，提供返回節(jié)點n的指針修改指針方向重排OPEN表第54頁，共110頁，2022年，5月20日，2點19分，星期四3、1 狀態(tài)空間的一般搜索過程二階漢諾塔的一般搜索過程第55頁，共110頁，2022年，5月20日，2點19分，星期四3、1 狀態(tài)空間的一般搜索過程一些說明上述是一個通用過程，各種搜索策略的主要區(qū)別是對OPEN表中節(jié)點排序的準則不同。如果子節(jié)點的算符有多個，則擴展時會生成一組子節(jié)點。但不能把該節(jié)點的先輩節(jié)點作為它當前擴展的子節(jié)點。一個新生成的節(jié)點，它可能是第一次被生成，也可能是被再次生成的。此時，一般由原始節(jié)點到該節(jié)點的代價來決

22、定其父節(jié)點，代價小的相應節(jié)點就作為父節(jié)點。(例)第56頁，共110頁，2022年，5月20日，2點19分，星期四3、1 狀態(tài)空間的一般搜索過程一些說明在搜索過程中，一旦某個被考察的節(jié)點是目標節(jié)點，就得到了一個解。該解由從初始節(jié)點到該目標節(jié)點路徑上的算符構成。如果在搜索中一直找不到目標節(jié)點，而且OPEN表中不再有可供擴展的節(jié)點，則搜索失敗。第57頁，共110頁，2022年，5月20日，2點19分，星期四3、1 狀態(tài)空間的一般搜索過程修改父節(jié)點指針示例 返回第58頁，共110頁，2022年，5月20日，2點19分，星期四3、2 廣度優(yōu)先搜索基本思想從初始節(jié)點開始，逐層對節(jié)點進行擴展并考察是否為目標

23、節(jié)點，在第n層的節(jié)點沒有全部擴展前，不對第n+1層的節(jié)點進行擴展?？墒褂靡话闼阉鬟^程，但OPEN表中的節(jié)點進行先進先出排序。第59頁，共110頁，2022年，5月20日，2點19分，星期四3、2 廣度優(yōu)先搜索開始把S放入OPEN表OPEN表為空表？是失敗否把第一個節(jié)點（n）從OPEN移至CLOSED表n為目標節(jié)點？是成功否把n的后繼節(jié)點放入OPEN表的末端，提供返回節(jié)點n的指針修改指針方向重排OPEN表第60頁，共110頁，2022年，5月20日，2點19分，星期四3、2 廣度優(yōu)先搜索八數碼問題初始狀態(tài)目標狀態(tài)第61頁，共110頁，2022年，5月20日，2點19分，星期四3、2 廣度優(yōu)先搜索

24、八數碼問題第62頁，共110頁，2022年，5月20日，2點19分，星期四3、2 廣度優(yōu)先搜索解路徑：So 3 8 16 Sg 第63頁，共110頁，2022年，5月20日，2點19分，星期四3、2 廣度優(yōu)先搜索特點只要問題有解，用廣度優(yōu)先搜索總可以得到解，而且得到的是路徑最短的解。廣度優(yōu)先搜索盲目性較大，當目標節(jié)點離初始節(jié)點較遠時將會產生許多無用節(jié)點，搜索效率低。第64頁，共110頁，2022年，5月20日，2點19分，星期四3、3 深度優(yōu)先搜索基本思想從初始節(jié)點開始，一直在節(jié)點的子節(jié)點中查找目標，如果某節(jié)點的子節(jié)點沒有全部擴展前，不對它的兄弟節(jié)點進行擴展?？墒褂靡话闼阉鬟^程，但OPEN表中

25、的節(jié)點進行先進后出排序。第65頁，共110頁，2022年，5月20日，2點19分，星期四3、3 深度優(yōu)先搜索開始把S放入OPEN表OPEN表為空表？是失敗否把第一個節(jié)點（n）從OPEN移至CLOSED表n為目標節(jié)點？是成功否把n的后繼節(jié)點放入OPEN表的前端，提供返回節(jié)點n的指針修改指針方向重排OPEN表第66頁，共110頁，2022年，5月20日，2點19分，星期四3、3 深度優(yōu)先搜索八數碼問題初始狀態(tài)目標狀態(tài)第67頁，共110頁，2022年，5月20日，2點19分，星期四3、3 深度優(yōu)先搜索第68頁，共110頁，2022年，5月20日，2點19分，星期四3、3 深度優(yōu)先搜索特點搜索一旦進入

26、某個分支，就將從該分支一直往下搜索。求得的解不一定是路徑最短的解。如果進入的是無窮分支，則可能得不到解。第69頁，共110頁，2022年，5月20日，2點19分，星期四3、3 深度優(yōu)先搜索八數碼問題進入無窮分支第70頁，共110頁，2022年，5月20日，2點19分，星期四3、4 有界深度優(yōu)先搜索基本思想在深度優(yōu)先搜索的基礎上，引入搜索深度界限(dm)。當搜索深度達到界限，但未出現目標節(jié)點時，就換一個分支搜索。第71頁，共110頁，2022年，5月20日，2點19分，星期四2 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 4

27、7 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 2 37 8 4 6 51 2 38 47 6 52 8 3 6 41 7 52 8 31 67 5 48 32 1 47 6 52 8 37 1 46 52 81 4 37 6 52 8 31 4 57 6123456789abcd1 2 3 8 47 6 5目標ef第72頁，共110頁，2022年，5月20日，2點19分，星期四3、4 有界深度優(yōu)先搜索特點若問題

28、有解，則其路徑長度 dm ，則一定可求得解。若其路徑長度 dm ，則一定求不出解。dm 較難確定?？蛇M行改進，使dm在搜索過程中能夠動態(tài)變化。第73頁，共110頁，2022年，5月20日，2點19分，星期四3、5 代價樹邊上標有代價的樹，稱為代價樹。代價一般指使用某個算符使從一個狀態(tài)變?yōu)榱硪粋€狀態(tài)的付出，例如時間、費用等。第74頁，共110頁，2022年，5月20日，2點19分，星期四3、5 代價樹代價的計算g(x)表示從初始節(jié)點So到節(jié)點x的代價用c(xi,xj)表示父節(jié)點xi到子節(jié)點xj的代價,即邊(xi,xj)的代價。從而有 g(xj)g(xi)c(xi, xj) 而 g(So)0 第7

29、5頁，共110頁，2022年，5月20日，2點19分，星期四3、5 代價樹的廣度優(yōu)先搜索基本思想在廣度優(yōu)先搜索的基礎上，每次都從OPEN表中取出代價最小的節(jié)點放入CLOSED表。第76頁，共110頁，2022年，5月20日，2點19分，星期四3、5 代價樹的廣度優(yōu)先搜索旅行問題設A城是出發(fā)地,E城是目的地, 邊上的數字代表兩城之間的交通費。試求從A到E最小費用的旅行路線。 ABCDE432345交通圖第77頁，共110頁，2022年，5月20日，2點19分，星期四3、5 代價樹的廣度優(yōu)先搜索旅行問題最佳解路徑：A C1 D1 E2 最小費用路線：A C D E第78頁，共110頁，2022年，

30、5月20日，2點19分，星期四3、5 代價樹的深度優(yōu)先搜索基本思想在深度優(yōu)先搜索的基礎上，每次都從剛擴展的子節(jié)點中取出代價最小的節(jié)點放入CLOSED表。第79頁，共110頁，2022年，5月20日，2點19分，星期四3、5 代價樹的深度優(yōu)先搜索旅行問題最佳解路徑：A C1 D1 E2 最小費用路線：A C D E第80頁，共110頁，2022年，5月20日，2點19分，星期四3、6 啟發(fā)式搜索搜索過程中用到問題自身的某些特征信息，指導搜索朝著最有希望的方向進行。用于指導搜索過程的信息稱為啟發(fā)信息。啟發(fā)信息的強度強，降低搜索工作量，可能導致找不到最優(yōu)解弱，極限情況下變?yōu)槊つ克阉鞯?1頁，共110

31、頁，2022年，5月20日，2點19分，星期四3、6 啟發(fā)式搜索基本思想定義一個估價函數f，對當前的搜索狀態(tài)進行評估，找出一個最有希望的節(jié)點來進行擴展。 f(x)=g(x)+h(x)g(x)是從初始節(jié)點到節(jié)點x已經實際付出的代價h(x)是從節(jié)點x到目標節(jié)點的最優(yōu)路徑的估計代價（啟發(fā)信息）第82頁，共110頁，2022年，5月20日，2點19分，星期四3、6 啟發(fā)式搜索例子設有如下結構的移動將牌游戲：DDDWWWE其中，E代表該位置為空。該游戲規(guī)則：1、當一個牌移入相鄰的空位置時，費用為一個單位。2、一個牌至多可跳過兩個牌進入空位置，其費用等于跳過的牌數加1。要求把所有的都移至W的右邊。第83頁

32、，共110頁，2022年，5月20日，2點19分，星期四3、6 啟發(fā)式搜索例子解：根據要求可知，W左邊的越少越接近目標，因此可用W左邊的個數作為h(x),即h(x)=3(每個W左邊個數的總和)這里乘以系數3是為了擴大h(x)在f(x)中的比重。第84頁，共110頁，2022年，5月20日，2點19分，星期四3、6、1 局部擇優(yōu)搜索基本思想 當一個節(jié)點x被擴展以后，按f(x)對x的每個子節(jié)點計算估計值，并從擴展的子節(jié)點中選擇估計值最小的節(jié)點作為下一個考察對象。 深度優(yōu)先搜索、代價樹的深度優(yōu)先搜索以及局部擇優(yōu)搜索都是以子節(jié)點作為考察范圍的。但是前二者可以看作局部擇優(yōu)搜索的特例。第85頁，共110頁

33、，2022年，5月20日，2點19分，星期四3、6、2 全局擇優(yōu)搜索基本思想 每次總是從OPEN表的全體節(jié)點中選取一個估計值最小的節(jié)點。 廣度優(yōu)先搜索、代價樹的廣度優(yōu)先搜索以及全局擇優(yōu)搜索都是以當前所有節(jié)點作為考察范圍的。但是前二者可以看作全局擇優(yōu)搜索的特例。第86頁，共110頁，2022年，5月20日，2點19分，星期四3、6、2 全局擇優(yōu)搜索例子 用全局擇優(yōu)搜索求八數碼問題。2 8 31 6 47 51 2 3457 6 81 2 38 47 6 51 2 3457 6 8g(x)表示節(jié)點x的深度h(x)表示節(jié)點x的格局與目標節(jié)點的格局不同的牌數。第87頁，共110頁，2022年，5月20

34、日，2點19分，星期四2 8 31 6 47 52 8 31 47 6 52 8 31 6 4 7 52 8 31 6 47 52 31 8 47 6 52 8 3 1 47 6 52 8 31 47 6 52 8 37 1 4 6 5 8 32 1 47 6 5 2 31 8 47 6 52 31 8 47 6 51 2 3 8 47 6 51 2 38 47 6 51 2 37 8 4 6 5s(4)A(6)B(4)C(6)D(5)E(5)F(6)G(6)H(7)I(5)J(7)K(5)L(5)M(7)123456目標第88頁，共110頁，2022年，5月20日，2點19分，星期四4、 與

35、/或樹的搜索策略基本思想用分解或等價變換算符通過搜索生成與或樹，最終應能標識出初始節(jié)點（對應于原問題）為可解節(jié)點（原問題有解）或不可解節(jié)點（原問題無解）。與/或樹搜索的目標是尋找解樹，從而求得原問題的解。第89頁，共110頁，2022年，5月20日，2點19分，星期四4、1 與/或樹的一般搜索過程可解標識過程：由可解子節(jié)點來確定其父節(jié)點、祖父節(jié)點等為可解節(jié)點的過程。不可解標識過程：由不可解子節(jié)點來確定其父節(jié)點、祖父節(jié)點等為不可解節(jié)點的過程。與/或樹的搜索過程將反復使用上述兩個過程，直到初始節(jié)點被標示為可解或不可解節(jié)點為止。搜索形成的節(jié)點和指針結構稱為搜索樹。第90頁，共110頁，2022年，5

36、月20日，2點19分，星期四4、1 與/或樹的一般搜索過程一般過程(1)把原始問題作為初始節(jié)點S0，并把它作為當前節(jié)點。(2)應用分解或等價變換算符對當前節(jié)點進行擴充。(3)為每個子節(jié)點設置指向父節(jié)點的指針。(4)選擇合適的子節(jié)點作為當前節(jié)點，反復執(zhí)行第（2）、（3）步。在此其間要多次調用可解標識過程和不可解標識過程，直到初始節(jié)點被標識為可解或不可解節(jié)點為止。第91頁，共110頁，2022年，5月20日，2點19分，星期四4、1 與/或樹的一般搜索過程搜索過程中的注意點某個節(jié)點不能擴展，也不是終止節(jié)點，則該節(jié)點是不可解節(jié)點。如果已經確定某個節(jié)點為可解節(jié)點，則其不可解的子節(jié)點就不再有用，可從搜索

37、樹中刪去。如果已經確定某個節(jié)點為不可解節(jié)點，則其全部子節(jié)點就不再有用，可從搜索樹中刪去；但當前這個不可解節(jié)點還不能刪去，以后它還要用來判斷其先輩節(jié)點的可解性。第92頁，共110頁，2022年，5月20日，2點19分，星期四4、2 與/或樹的廣度優(yōu)先搜索基本思想跟狀態(tài)空間的廣度優(yōu)先搜索類似，但在搜索過程中要多次調用可解標示過程和不可解標示過程。第93頁，共110頁，2022年，5月20日，2點19分，星期四開始把S放入OPEN表OPEN表為空表？是失敗否把第一個節(jié)點（n）從OPEN移至CLOSED表節(jié)點n可擴展？是成功否標示節(jié)點n為不可解節(jié)點，應用不可解標示過程從OPEN表中刪除具有不可解先輩的

38、節(jié)點S為不可解節(jié)點？是失敗否將節(jié)點n的子節(jié)點放入OPEN表，并為子節(jié)點配置指針子節(jié)點有終止節(jié)點？否標示節(jié)點n為可解節(jié)點，應用可解標示過程是S為可解節(jié)點？是從OPEN表中刪除具有可解先輩的節(jié)點否第94頁，共110頁，2022年，5月20日，2點19分，星期四4、2 與/或樹的廣度優(yōu)先搜索例子設有如圖所示的與/或樹，節(jié)點按圖中所標注的順序進行擴展。其中，t1,t2,t3,t4為終止節(jié)點，A和B為不可解節(jié)點。12345ABt1t2t3t4第95頁，共110頁，2022年，5月20日，2點19分，星期四4、2 與/或樹的廣度優(yōu)先搜索12345ABt1t2t3t412345ABt1t2t3t4擴展順序為

39、：1，2，3，4，5第96頁，共110頁，2022年，5月20日，2點19分，星期四4、3 與/或樹的深度優(yōu)先搜索基本思想跟狀態(tài)空間的深度優(yōu)先搜索類似，但在搜索過程中要多次調用可解標示過程和不可解標示過程。第97頁，共110頁，2022年，5月20日，2點19分，星期四4、3 與/或樹的深度優(yōu)先搜索12345ABt1t2t3t412345ABt1t2t3t4擴展順序為：1 ，2，4 ，3，5第98頁，共110頁，2022年，5月20日，2點19分，星期四4、4 與/或樹的有序搜索基本思想是用來求代價最小的解樹的一種搜索方法。在確定下一個要擴展的節(jié)點時，先計算需要付出的代價，選擇代價最小的節(jié)點進

40、行擴展。第99頁，共110頁，2022年，5月20日，2點19分，星期四4、4 與/或樹的有序搜索解樹的代價C(x,y)表示節(jié)點x到其子節(jié)點y的代價。(1) 如果x是終止節(jié)點，h(x)=0(2)如果x是“或”節(jié)點，h(x)=(3)如果x是“與”節(jié)點， h(x)= (4)如果x不可擴展，且又不是終止節(jié)點，h(x)=第100頁，共110頁，2022年，5月20日，2點19分，星期四4、4 與/或樹的有序搜索解樹的代價(例子)如圖是一棵與/或解樹，求該樹的代價。h(A)= 11， h(S0)=13h(B)= 6， h(S0)=8S0ABFt2Ct3t4t5DEt1226521212113G第101頁，共110頁，2022年，5月20日，2點19分，星期四4、4 與/或樹的有序搜索解樹的代價當計算某一節(jié)點x的代價h(x)時，都要求已知它的子節(jié)點yi代價，但搜索是從上到下進行的，因此一般使用啟發(fā)函數估算yi 。當yi