機(jī)器人第六章 迷宮比賽與搜索算法

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

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

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

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

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

6、，星期四2、2 狀態(tài)空間表示法算符使問題從一種狀態(tài)變化為另一種狀態(tài)的操作。狀態(tài)空間由問題的全部狀態(tài)及一切可用算符所構(gòu)成的集合。狀態(tài)空間圖狀態(tài)空間的圖示形式。是一個(gè)有向圖，節(jié)點(diǎn)表示狀態(tài)，有向邊表示算符。第19頁，共110頁，2022年，5月20日，2點(diǎn)19分，星期四2、2 狀態(tài)空間表示法(舉例)二階漢諾塔問題 要求把A、B兩塊金片全部移到另一個(gè)鋼針上。規(guī)定每次只能移動(dòng)一片，并且任何時(shí)刻不能出現(xiàn)B在A的上面。第20頁，共110頁，2022年，5月20日，2點(diǎn)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,目標(biāo)狀態(tài)集合為G=S4,S8。第21頁，共110頁，2022年，5月20日，2點(diǎn)19分，星期四2、2 狀態(tài)空間表示法(舉例)二階漢諾塔問題9種狀態(tài)第22頁，共110頁，2022年，5月20日，2點(diǎn)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個(gè)。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點(diǎn)19分，星期四2、2 狀態(tài)空間表示法(舉例)二階漢諾塔問題 由9種可能的狀態(tài)和12個(gè)算符, 二階漢諾塔問題的狀態(tài)空間圖如下：從(1,1)到(2,2)或(3,3)的任何一條通路都是問題的一個(gè)解。第24頁，共110頁，2022年，5月20日，2點(diǎn)19分，星期四2、2 狀態(tài)空間表示法(舉例)猴子和香蕉在一個(gè)房間內(nèi)

9、有一只猴子、一個(gè)箱子和一束香蕉。香蕉掛在天花板下方，但猴子的高度不足以碰到它。那么這只猴子怎樣才能摘到香蕉呢? 第25頁，共110頁，2022年，5月20日，2點(diǎn)19分，星期四2、2 狀態(tài)空間表示法(舉例)猴子和香蕉用一個(gè)四元表列(W,x,Y,z)來表示這個(gè)問題的狀態(tài)， 其中W猴子的水平位置x當(dāng)猴子在箱子頂上時(shí)取x=1；否則取x=0Y箱子的水平位置z當(dāng)猴子摘到香蕉時(shí)取z=1；否則取z=0 。 第26頁，共110頁，2022年，5月20日，2點(diǎn)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,目標(biāo)狀態(tài)集合為G=S12。第27頁，共110頁，2022年，5月20日，2點(diǎn)19分，星期四2、2 狀態(tài)空間表示法(舉例)猴子和香蕉算符用下面的表示： (1) goto(U)猴子走到相鄰的水平位置U (2) pushbox(V)猴子把箱子推到相鄰的水平位置V (

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

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

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

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

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

16、B盤從2號桿移到3號桿。其中子問題(1)、(3)又分別可分解為三個(gè)子問題。 第42頁，共110頁，2022年，5月20日，2點(diǎn)19分，星期四2、3 與/或樹表示法(舉例)三階漢諾塔問題用三元組表示問題在任一時(shí)刻的狀態(tài)：(i, j, k)其中，i,j,k分別表示金片A、B、C所在的桿號。第43頁，共110頁，2022年，5月20日，2點(diǎn)19分，星期四2、3 與/或樹表示法(舉例)三階漢諾塔問題三階漢諾塔問題的與/或樹 第44頁，共110頁，2022年，5月20日，2點(diǎn)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點(diǎn)19分，星期四3、 狀態(tài)空間的搜索策略使用搜索求解問題時(shí)的狀態(tài)關(guān)系圖。第46頁，共110頁，2022年，5月20日，2點(diǎn)19分，星期四3、 狀態(tài)空間的搜索策略基本思想：通過搜索尋找一個(gè)操作算符的調(diào)用序列，使問題從初始狀態(tài)變遷到目標(biāo)狀態(tài)。變遷過程中的狀態(tài)序列，或相應(yīng)的操作算符調(diào)用序列稱為從初始狀態(tài)到目標(biāo)狀態(tài)的解答路徑。搜索空間的壓縮程度取決于采用的搜索算法

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

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

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

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

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

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

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

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

26、某個(gè)分支，就將從該分支一直往下搜索。求得的解不一定是路徑最短的解。如果進(jìn)入的是無窮分支，則可能得不到解。第69頁，共110頁，2022年，5月20日，2點(diǎn)19分，星期四3、3 深度優(yōu)先搜索八數(shù)碼問題進(jìn)入無窮分支第70頁，共110頁，2022年，5月20日，2點(diǎn)19分，星期四3、4 有界深度優(yōu)先搜索基本思想在深度優(yōu)先搜索的基礎(chǔ)上，引入搜索深度界限(dm)。當(dāng)搜索深度達(dá)到界限，但未出現(xiàn)目標(biāo)節(jié)點(diǎn)時(shí)，就換一個(gè)分支搜索。第71頁，共110頁，2022年，5月20日，2點(diǎn)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目標(biāo)ef第72頁，共110頁，2022年，5月20日，2點(diǎn)19分，星期四3、4 有界深度優(yōu)先搜索特點(diǎn)若問題

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

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

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

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

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

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

34、日，2點(diǎn)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目標(biāo)第88頁，共110頁，2022年，5月20日，2點(diǎn)19分，星期四4、 與

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

36、月20日，2點(diǎn)19分，星期四4、1 與/或樹的一般搜索過程一般過程(1)把原始問題作為初始節(jié)點(diǎn)S0，并把它作為當(dāng)前節(jié)點(diǎn)。(2)應(yīng)用分解或等價(jià)變換算符對當(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)識過程和不可解標(biāo)識過程，直到初始節(jié)點(diǎn)被標(biāo)識為可解或不可解節(jié)點(diǎn)為止。第91頁，共110頁，2022年，5月20日，2點(diǎn)19分，星期四4、1 與/或樹的一般搜索過程搜索過程中的注意點(diǎn)某個(gè)節(jié)點(diǎn)不能擴(kuò)展，也不是終止節(jié)點(diǎn)，則該節(jié)點(diǎn)是不可解節(jié)點(diǎn)。如果已經(jīng)確定某個(gè)節(jié)點(diǎn)為可解節(jié)點(diǎn)，則其不可解的子節(jié)點(diǎn)就不再有用，可從搜索

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

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

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

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