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

機(jī)器人第六章迷宮比賽與搜索算法第一頁，共一百一十頁，2022年，8月28日本章內(nèi)容1.迷宮比賽簡介2.搜索的基本知識3.狀態(tài)空間的搜索策略4.與/或樹的搜索策略5.搜索策略性能的評價(jià)第二頁，共一百一十頁，2022年，8月28日1、迷宮比賽簡介比賽內(nèi)容

制造一個(gè)自主控制的機(jī)器人，能在迷宮模型中運(yùn)動(dòng)，并盡快找到出口離開迷宮。第三頁，共一百一十頁，2022年，8月28日場地1、迷宮比賽簡介起始區(qū)終止區(qū)

（迷宮場地參考圖）第四頁，共一百一十頁，2022年，8月28日場地1、迷宮比賽簡介起始區(qū)終止區(qū)紅色色塊黃色色塊黑色色塊

（機(jī)器人經(jīng)過相應(yīng)的色塊將被加時(shí)間）第五頁，共一百一十頁，2022年，8月28日簡單的行走策略左手規(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、迷宮比賽簡介第六頁，共一百一十頁，2022年，8月28日簡單的行走策略左手規(guī)則1、迷宮比賽簡介第七頁，共一百一十頁，2022年，8月28日簡單的行走策略右手規(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、迷宮比賽簡介第八頁，共一百一十頁，2022年，8月28日簡單的行走策略1、迷宮比賽簡介第九頁，共一百一十頁，2022年，8月28日簡單的行走策略1、迷宮比賽簡介怎樣找到路徑和最佳路徑？第十頁，共一百一十頁，2022年，8月28日2、搜索的基本知識搜索的概念根據(jù)問題的實(shí)際情況，不斷尋找可利用的知識，從而構(gòu)造一條可行的推理路線，使問題得到解決的過程。第十一頁，共一百一十頁，2022年，8月28日2、搜索的基本知識搜索的使用場合1、在知識不完全，沒有成熟的算法可使用。2、理論上有算法，但問題的復(fù)雜度高，用計(jì)算機(jī)求解有時(shí)間、空間的局限性。第十二頁，共一百一十頁，2022年，8月28日2、搜索的基本知識搜索的分類盲目搜索啟發(fā)式搜索第十三頁，共一百一十頁，2022年，8月28日2、1搜索的分類盲目搜索按預(yù)定的控制策略進(jìn)行搜索，在搜索過程中獲得的中間信息不用來改進(jìn)控制策略。通用，效率低，不便于復(fù)雜問題的求解。是一種不得已而采取的方法第十四頁，共一百一十頁，2022年，8月28日2、1搜索的分類啟發(fā)式搜索在搜索過程中，根據(jù)問題本身的特性或搜索過程中產(chǎn)生的一些與問題有關(guān)的啟發(fā)信息，指導(dǎo)搜索朝著最有希望的推理方向前進(jìn)，加速問題的求解過程，并找到最優(yōu)解。

第十五頁，共一百一十頁，2022年，8月28日2、1搜索的分類查找第十六頁，共一百一十頁，2022年，8月28日2、2狀態(tài)空間表示法狀態(tài)空間表示法用來表示問題及其搜索過程的一種方法。包含三個(gè)元素：狀態(tài)、算符、狀態(tài)空間。第十七頁，共一百一十頁，2022年，8月28日2、2狀態(tài)空間表示法狀態(tài)描述問題求解過程中不同時(shí)刻的狀況。Sk=(Sk0,Sk1,…,Skn)Skn：代表每個(gè)具體的狀態(tài)。其中還包括初始狀態(tài)、目標(biāo)狀態(tài)。第十八頁，共一百一十頁，2022年，8月28日2、2狀態(tài)空間表示法算符使問題從一種狀態(tài)變化為另一種狀態(tài)的操作。狀態(tài)空間由問題的全部狀態(tài)及一切可用算符所構(gòu)成的集合。狀態(tài)空間圖狀態(tài)空間的圖示形式。是一個(gè)有向圖，節(jié)點(diǎn)表示狀態(tài)，有向邊表示算符。第十九頁，共一百一十頁，2022年，8月28日2、2狀態(tài)空間表示法(舉例)二階漢諾塔問題

要求把A、B兩塊金片全部移到另一個(gè)鋼針上。規(guī)定每次只能移動(dòng)一片，并且任何時(shí)刻不能出現(xiàn)B在A的上面。第二十頁，共一百一十頁，2022年，8月28日2、2狀態(tài)空間表示法(舉例)二階漢諾塔問題

用二元組SK=(SA,SB)表示問題的狀態(tài),SA表示金盤A所在的桿號,SB表示金盤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}。第二十一頁，共一百一十頁，2022年，8月28日2、2狀態(tài)空間表示法(舉例)二階漢諾塔問題9種狀態(tài)第二十二頁，共一百一十頁，2022年，8月28日2、2狀態(tài)空間表示法(舉例)二階漢諾塔問題算符分別用A(i,j)及B(i,j)表示：A(i,j)表示把A盤從第i號桿移到第j號桿上;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)第二十三頁，共一百一十頁，2022年，8月28日2、2狀態(tài)空間表示法(舉例)二階漢諾塔問題

由9種可能的狀態(tài)和12個(gè)算符,二階漢諾塔問題的狀態(tài)空間圖如下：從(1,1)到(2,2)或(3,3)的任何一條通路都是問題的一個(gè)解。第二十四頁，共一百一十頁，2022年，8月28日2、2狀態(tài)空間表示法(舉例)猴子和香蕉在一個(gè)房間內(nèi)有一只猴子、一個(gè)箱子和一束香蕉。香蕉掛在天花板下方，但猴子的高度不足以碰到它。那么這只猴子怎樣才能摘到香蕉呢?第二十五頁，共一百一十頁，2022年，8月28日2、2狀態(tài)空間表示法(舉例)猴子和香蕉

用一個(gè)四元表列(W,x,Y,z)來表示這個(gè)問題的狀態(tài)，其中

W－猴子的水平位置

x－當(dāng)猴子在箱子頂上時(shí)取x=1；否則取x=0

Y－箱子的水平位置

z－當(dāng)猴子摘到香蕉時(shí)取z=1；否則取z=0。

第二十六頁，共一百一十頁，2022年，8月28日2、2狀態(tài)空間表示法(舉例)猴子和香蕉

全部可能的狀態(tài)有13種,可表示如下：

S0=(a,0,b,0),S1=(a,0,c,0),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}。第二十七頁，共一百一十頁，2022年，8月28日2、2狀態(tài)空間表示法(舉例)猴子和香蕉算符用下面的表示：(1)goto(U)猴子走到相鄰的水平位置U(2)pushbox(V)猴子把箱子推到相鄰的水平位置V

(3)climbbox猴子爬上箱頂

(4)godownbox猴子爬下箱子(5)grasp猴子摘到香蕉則，算符共有11個(gè)，包括猴子移動(dòng)的4個(gè)，箱子移動(dòng)的4個(gè)，猴子爬上箱子1個(gè)、爬下箱子1個(gè)，猴子摘到香蕉1個(gè)。第二十八頁，共一百一十頁，2022年，8月28日2、2狀態(tài)空間表示法(舉例)猴子和香蕉

由13種可能的狀態(tài)和11個(gè)算符,猴子和香蕉問題的狀態(tài)空間圖如下：第二十九頁，共一百一十頁，2022年，8月28日2、2狀態(tài)空間表示法需要定義狀態(tài)、算符。問題的求解過程，是一個(gè)不斷把算符作用于狀態(tài)的過程。問題的解是從初始狀態(tài)到目標(biāo)狀態(tài)所用算符構(gòu)成的序列。使用算符最少的解是最優(yōu)解。對一個(gè)狀態(tài)選取哪個(gè)算符操作，取決于搜索策略。不同的搜索策略，操作順序不一定相同。(重點(diǎn)討論的問題)第三十頁，共一百一十頁，2022年，8月28日2、3與/或樹表示法與/或樹表示法用于表示問題及其求解過程的一種方法，通常用于表示比較復(fù)雜問題的求解。對于一個(gè)復(fù)雜問題，直接求解往往比較困難，可以對其進(jìn)行簡化。簡化使用的兩個(gè)操作：分解、等價(jià)變換第三十一頁，共一百一十頁，2022年，8月28日2、3與/或樹表示法分解把一個(gè)復(fù)雜問題分解為若干個(gè)較為容易求解的子問題。每個(gè)子問題又可繼續(xù)分解。不斷重復(fù)，直到不需要或者不能再分解為止。復(fù)合各子問題的解就得到原問題的解。第三十二頁，共一百一十頁，2022年，8月28日2、3與/或樹表示法分解PP1P2P3與樹分解形成“與”樹第三十三頁，共一百一十頁，2022年，8月28日2、3與/或樹表示法等價(jià)變換把一個(gè)原問題變換為若干個(gè)較為容易求解的新問題。若新問題中有一個(gè)可求解，則就得到了原問題的解。第三十四頁，共一百一十頁，2022年，8月28日2、3與/或樹表示法等價(jià)變換等價(jià)變換形成“或”樹PP1P2P3或樹第三十五頁，共一百一十頁，2022年，8月28日2、3與/或樹表示法分解、等價(jià)變換結(jié)合使用兩種方法結(jié)合使用形成“與/或”樹第三十六頁，共一百一十頁，2022年，8月28日2、3與/或樹表示法本原問題不能再分解或變換，而且是直接可解的子問題。端節(jié)點(diǎn)沒有子節(jié)點(diǎn)的節(jié)點(diǎn)終止節(jié)點(diǎn)本原問題對應(yīng)的節(jié)點(diǎn)Pttt第三十七頁，共一百一十頁，2022年，8月28日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)。第三十八頁，共一百一十頁，2022年，8月28日2、3與/或樹表示法解樹要判斷原問題是否可解，就必須要找出一棵解樹。解樹：由可解節(jié)點(diǎn)構(gòu)成，并且由這些可解節(jié)點(diǎn)能夠推出初始節(jié)點(diǎn)為可解節(jié)點(diǎn)的子樹。第三十九頁，共一百一十頁，2022年，8月28日2、3與/或樹表示法PtttPttt解樹第四十頁，共一百一十頁，2022年，8月28日2、3與/或樹表示法(舉例)三階漢諾塔問題

要求把A、B、C三塊金片全部移到另一個(gè)鋼針上。規(guī)定每次只能移動(dòng)一片，并且任何時(shí)刻不能出現(xiàn)大的金片在小的金片上面。第四十一頁，共一百一十頁，2022年，8月28日2、3與/或樹表示法(舉例)三階漢諾塔問題可把三階梵塔問題分解為下面的三個(gè)子問題：

(1)把A、B盤從1號桿移到2號桿。

(2)把C盤從1號桿移到3號桿。

(3)把A、B盤從2號桿移到3號桿。其中子問題(1)、(3)又分別可分解為三個(gè)子問題。

第四十二頁，共一百一十頁，2022年，8月28日2、3與/或樹表示法(舉例)三階漢諾塔問題用三元組表示問題在任一時(shí)刻的狀態(tài)：

(i,j,k)其中，i,j,k分別表示金片A、B、C所在的桿號。第四十三頁，共一百一十頁，2022年，8月28日2、3與/或樹表示法(舉例)三階漢諾塔問題三階漢諾塔問題的與/或樹

第四十四頁，共一百一十頁，2022年，8月28日2、3與/或樹表示法(舉例)三階漢諾塔問題問題的解：(1,1,1)

(3,1,1)(3,1,1)

(3,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)

第四十五頁，共一百一十頁，2022年，8月28日3、狀態(tài)空間的搜索策略使用搜索求解問題時(shí)的狀態(tài)關(guān)系圖。第四十六頁，共一百一十頁，2022年，8月28日3、狀態(tài)空間的搜索策略基本思想：通過搜索尋找一個(gè)操作算符的調(diào)用序列，使問題從初始狀態(tài)變遷到目標(biāo)狀態(tài)。變遷過程中的狀態(tài)序列，或相應(yīng)的操作算符調(diào)用序列稱為從初始狀態(tài)到目標(biāo)狀態(tài)的解答路徑。搜索空間的壓縮程度取決于采用的搜索算法。第四十七頁，共一百一十頁，2022年，8月28日3、狀態(tài)空間的搜索策略分類第四十八頁，共一百一十頁，2022年，8月28日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表中第四十九頁，共一百一十頁，2022年，8月28日3、1狀態(tài)空間的一般搜索過程一般搜索過程

1)G:=s;//算法開始時(shí)搜索圖只包括初始狀態(tài)節(jié)點(diǎn)；

2)OPEN:=(s),CLOSED:=();//此時(shí)僅有ｓ作為待擴(kuò)展節(jié)點(diǎn)，而CLOSED表為空；

3)若OPEN是空表，則搜索失敗，結(jié)束；//因?yàn)榇藭r(shí)并未搜索到解答（目標(biāo)狀態(tài)），但又無法繼續(xù)搜索；

第五十頁，共一百一十頁，2022年，8月28日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中；第五十一頁，共一百一十頁，2022年，8月28日3、1狀態(tài)空間的一般搜索過程7)標(biāo)記和修改指針：全新節(jié)點(diǎn)——未曾在G中出現(xiàn)過（加入OPEN表，并建立從子節(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表）第五十二頁，共一百一十頁，2022年，8月28日3、1狀態(tài)空間的一般搜索過程8)按某種原則重新排序OPEN表中的節(jié)點(diǎn)；9）返回3）第五十三頁，共一百一十頁，2022年，8月28日3、1狀態(tài)空間的一般搜索過程開始把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表第五十四頁，共一百一十頁，2022年，8月28日3、1狀態(tài)空間的一般搜索過程二階漢諾塔的一般搜索過程第五十五頁，共一百一十頁，2022年，8月28日3、1狀態(tài)空間的一般搜索過程一些說明上述是一個(gè)通用過程，各種搜索策略的主要區(qū)別是對OPEN表中節(jié)點(diǎn)排序的準(zhǔn)則不同。如果子節(jié)點(diǎn)的算符有多個(gè)，則擴(kuò)展時(shí)會(huì)生成一組子節(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à)來決定其父節(jié)點(diǎn)，代價(jià)小的相應(yīng)節(jié)點(diǎn)就作為父節(jié)點(diǎn)。(例)第五十六頁，共一百一十頁，2022年，8月28日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)，則搜索失敗。第五十七頁，共一百一十頁，2022年，8月28日3、1狀態(tài)空間的一般搜索過程修改父節(jié)點(diǎn)指針示例

返回第五十八頁，共一百一十頁，2022年，8月28日3、2廣度優(yōu)先搜索基本思想從初始節(jié)點(diǎn)開始，逐層對節(jié)點(diǎn)進(jìn)行擴(kuò)展并考察是否為目標(biāo)節(jié)點(diǎn)，在第n層的節(jié)點(diǎn)沒有全部擴(kuò)展前，不對第n+1層的節(jié)點(diǎn)進(jìn)行擴(kuò)展?？墒褂靡话闼阉鬟^程，但OPEN表中的節(jié)點(diǎn)進(jìn)行先進(jìn)先出排序。第五十九頁，共一百一十頁，2022年，8月28日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表第六十頁，共一百一十頁，2022年，8月28日3、2廣度優(yōu)先搜索八數(shù)碼問題初始狀態(tài)目標(biāo)狀態(tài)第六十一頁，共一百一十頁，2022年，8月28日3、2廣度優(yōu)先搜索八數(shù)碼問題第六十二頁，共一百一十頁，2022年，8月28日3、2廣度優(yōu)先搜索解路徑：So→3→8→16→Sg第六十三頁，共一百一十頁，2022年，8月28日3、2廣度優(yōu)先搜索特點(diǎn)只要問題有解，用廣度優(yōu)先搜索總可以得到解，而且得到的是路徑最短的解。廣度優(yōu)先搜索盲目性較大，當(dāng)目標(biāo)節(jié)點(diǎn)離初始節(jié)點(diǎn)較遠(yuǎn)時(shí)將會(huì)產(chǎn)生許多無用節(jié)點(diǎn)，搜索效率低。第六十四頁，共一百一十頁，2022年，8月28日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表中的節(jié)點(diǎn)進(jìn)行先進(jìn)后出排序。第六十五頁，共一百一十頁，2022年，8月28日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表第六十六頁，共一百一十頁，2022年，8月28日3、3深度優(yōu)先搜索八數(shù)碼問題初始狀態(tài)目標(biāo)狀態(tài)第六十七頁，共一百一十頁，2022年，8月28日3、3深度優(yōu)先搜索第六十八頁，共一百一十頁，2022年，8月28日3、3深度優(yōu)先搜索特點(diǎn)搜索一旦進(jìn)入某個(gè)分支，就將從該分支一直往下搜索。求得的解不一定是路徑最短的解。如果進(jìn)入的是無窮分支，則可能得不到解。第六十九頁，共一百一十頁，2022年，8月28日3、3深度優(yōu)先搜索八數(shù)碼問題進(jìn)入無窮分支第七十頁，共一百一十頁，2022年，8月28日3、4有界深度優(yōu)先搜索基本思想在深度優(yōu)先搜索的基礎(chǔ)上，引入搜索深度界限(dm)。當(dāng)搜索深度達(dá)到界限，但未出現(xiàn)目標(biāo)節(jié)點(diǎn)時(shí)，就換一個(gè)分支搜索。第七十一頁，共一百一十頁，2022年，8月28日23184765

231847652831476523184765283147652831647528314765283164752831647528371465

8321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123456789abcd12384765目標(biāo)ef第七十二頁，共一百一十頁，2022年，8月28日3、4有界深度優(yōu)先搜索特點(diǎn)若問題有解，則其路徑長度≤dm

，則一定可求得解。若其路徑長度＞dm

，則一定求不出解。dm

較難確定?？蛇M(jìn)行改進(jìn)，使dm在搜索過程中能夠動(dòng)態(tài)變化。第七十三頁，共一百一十頁，2022年，8月28日3、5代價(jià)樹邊上標(biāo)有代價(jià)的樹，稱為代價(jià)樹。代價(jià)一般指使用某個(gè)算符使從一個(gè)狀態(tài)變?yōu)榱硪粋€(gè)狀態(tài)的付出，例如時(shí)間、費(fèi)用等。第七十四頁，共一百一十頁，2022年，8月28日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

第七十五頁，共一百一十頁，2022年，8月28日3、5代價(jià)樹的廣度優(yōu)先搜索基本思想在廣度優(yōu)先搜索的基礎(chǔ)上，每次都從OPEN表中取出代價(jià)最小的節(jié)點(diǎn)放入CLOSED表。第七十六頁，共一百一十頁，2022年，8月28日3、5代價(jià)樹的廣度優(yōu)先搜索旅行問題設(shè)A城是出發(fā)地,E城是目的地,邊上的數(shù)字代表兩城之間的交通費(fèi)。試求從A到E最小費(fèi)用的旅行路線。

ABCDE432345交通圖第七十七頁，共一百一十頁，2022年，8月28日3、5代價(jià)樹的廣度優(yōu)先搜索旅行問題最佳解路徑：A→C1→D1→E2最小費(fèi)用路線：A→C→D→E第七十八頁，共一百一十頁，2022年，8月28日3、5代價(jià)樹的深度優(yōu)先搜索基本思想在深度優(yōu)先搜索的基礎(chǔ)上，每次都從剛擴(kuò)展的子節(jié)點(diǎn)中取出代價(jià)最小的節(jié)點(diǎn)放入CLOSED表。第七十九頁，共一百一十頁，2022年，8月28日3、5代價(jià)樹的深度優(yōu)先搜索旅行問題最佳解路徑：A→C1→D1→E2最小費(fèi)用路線：A→C→D→E第八十頁，共一百一十頁，2022年，8月28日3、6啟發(fā)式搜索搜索過程中用到問題自身的某些特征信息，指導(dǎo)搜索朝著最有希望的方向進(jìn)行。用于指導(dǎo)搜索過程的信息稱為啟發(fā)信息。啟發(fā)信息的強(qiáng)度強(qiáng)，降低搜索工作量，可能導(dǎo)致找不到最優(yōu)解弱，極限情況下變?yōu)槊つ克阉鞯诎耸豁?，共一百一十頁?022年，8月28日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ā)信息）第八十二頁，共一百一十頁，2022年，8月28日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的右邊。第八十三頁，共一百一十頁，2022年，8月28日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)中的比重。第八十四頁，共一百一十頁，2022年，8月28日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)搜索的特例。第八十五頁，共一百一十頁，2022年，8月28日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)搜索的特例。第八十六頁，共一百一十頁，2022年，8月28日3、6、2全局擇優(yōu)搜索例子用全局擇優(yōu)搜索求八數(shù)碼問題。28316475123457681238

476512345768g(x)表示節(jié)點(diǎn)x的深度h(x)表示節(jié)點(diǎn)x的格局與目標(biāo)節(jié)點(diǎn)的格局不同的牌數(shù)。第八十七頁，共一百一十頁，2022年，8月28日2831647528314765283164752831647523184765283147652831476528371465

83214765

2318476523184765123847651238476512378465s(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)第八十八頁，共一百一十頁，2022年，8月28日4、與/或樹的搜索策略基本思想用分解或等價(jià)變換算符通過搜索生成與或樹，最終應(yīng)能標(biāo)識出初始節(jié)點(diǎn)（對應(yīng)于原問題）為可解節(jié)點(diǎn)（原問題有解）或不可解節(jié)點(diǎn)（原問題無解）。與/或樹搜索的目標(biāo)是尋找解樹，從而求得原問題的解。第八十九頁，共一百一十頁，2022年，8月28日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)稱為搜索樹。第九十頁，共一百一十頁，2022年，8月28日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)為止。第九十一頁，共一百一十頁，2022年，8月28日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)就不再有用，可從搜索樹中刪去。如果已經(jīng)確定某個(gè)節(jié)點(diǎn)為不可解節(jié)點(diǎn)，則其全部子節(jié)點(diǎn)就不再有用，可從搜索樹中刪去；但當(dāng)前這個(gè)不可解節(jié)點(diǎn)還不能刪去，以后它還要用來判斷其先輩節(jié)點(diǎn)的可解性。第九十二頁，共一百一十頁，2022年，8月28日4、2與/或樹的廣度優(yōu)先搜索基本思想跟狀態(tài)空間的廣度優(yōu)先搜索類似，但在搜索過程中要多次調(diào)用可解標(biāo)示過程和不可解標(biāo)示過程。第九十三頁，共一百一十頁，2022年，8月28日開始把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表中刪除具有不可解先輩的節(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)否第九十四頁，共一百一十頁，2022年，8月28日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第九十五頁，共一百一十頁，2022年，8月28日4、2與/或樹的廣度優(yōu)先搜索12345ABt1t2t3t412345ABt1t2t3t4擴(kuò)展順序?yàn)椋?，2，3，4，5第九十六頁，共一百一十頁，2022年，8月28日4、3與/或樹的深度優(yōu)先搜索基本思想跟狀態(tài)空間的深度優(yōu)先搜索類似，但在搜索過程中要多次調(diào)用可解標(biāo)示過程和不可解標(biāo)示過程。第九十七頁，共一百一十頁，2022年，8月28日4、3與/或樹的深度優(yōu)先搜索12345ABt1t2t3t412345ABt1t2t3t4擴(kuò)展順序?yàn)椋?，2，4，3，5第九十八頁，共一百一十頁，2022年，8月28日4、4與/或樹的有序搜索基本思想是用來求代價(jià)最小的解樹的一種搜索方法。在確定下一個(gè)要擴(kuò)展的節(jié)點(diǎn)時(shí)，先計(jì)算需要付出的代價(jià)，選擇代價(jià)最小的節(jié)點(diǎn)進(jìn)行擴(kuò)展。第九十九頁，共一百一十頁，2022年，8月28日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)=∞第一百頁，共一百一十頁，2022年，8月28日4、4與/或樹的有序搜索解樹的代價(jià)(例子)如圖是一棵與/或解樹，求該樹的代價(jià)。h(A)=11，h(S0)=13h(B)=6，h(S0)=8S0ABFt2Ct3t4t5DEt1226521212113G第一百零一頁，共一百一十頁，2022年，8月28日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在往后的搜索過程中被擴(kuò)展后，還要重新計(jì)算先輩節(jié)點(diǎn)x的代價(jià)。第一百零二頁，共一百一十頁，2022年，8月28日開始把S放入OP