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

機(jī)器人第六章迷宮比賽與搜索算法第1頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月本章內(nèi)容1.迷宮比賽簡(jiǎn)介2.搜索的基本知識(shí)3.狀態(tài)空間的搜索策略4.與/或樹(shù)的搜索策略5.搜索策略性能的評(píng)價(jià)第2頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月1、迷宮比賽簡(jiǎn)介比賽內(nèi)容

制造一個(gè)自主控制的機(jī)器人，能在迷宮模型中運(yùn)動(dòng)，并盡快找到出口離開(kāi)迷宮。第3頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月場(chǎng)地1、迷宮比賽簡(jiǎn)介起始區(qū)終止區(qū)

（迷宮場(chǎng)地參考圖）第4頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月場(chǎng)地1、迷宮比賽簡(jiǎn)介起始區(qū)終止區(qū)紅色色塊黃色色塊黑色色塊

（機(jī)器人經(jīng)過(guò)相應(yīng)的色塊將被加時(shí)間）第5頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月簡(jiǎn)單的行走策略左手規(guī)則（障礙在機(jī)器人的左邊）1、前方?jīng)]有發(fā)現(xiàn)障礙，左邊發(fā)現(xiàn)障礙，機(jī)器人繼續(xù)前進(jìn)2、如果機(jī)器人前方發(fā)現(xiàn)障礙，則原地右轉(zhuǎn)避開(kāi)障礙3、如果機(jī)器人前方和左邊都沒(méi)有發(fā)現(xiàn)障礙，左轉(zhuǎn)，尋找左側(cè)障礙1、迷宮比賽簡(jiǎn)介第6頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月簡(jiǎn)單的行走策略左手規(guī)則1、迷宮比賽簡(jiǎn)介第7頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月簡(jiǎn)單的行走策略右手規(guī)則（障礙在機(jī)器人的右邊）1、前方?jīng)]有發(fā)現(xiàn)障礙，右邊發(fā)現(xiàn)障礙，機(jī)器人繼續(xù)前進(jìn)2、如果機(jī)器人前方發(fā)現(xiàn)障礙，則原地左轉(zhuǎn)避開(kāi)障礙3、如果機(jī)器人前方和右邊都沒(méi)有發(fā)現(xiàn)障礙，右轉(zhuǎn)，尋找右側(cè)障礙1、迷宮比賽簡(jiǎn)介第8頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月簡(jiǎn)單的行走策略1、迷宮比賽簡(jiǎn)介第9頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月簡(jiǎn)單的行走策略1、迷宮比賽簡(jiǎn)介怎樣找到路徑和最佳路徑？第10頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月2、搜索的基本知識(shí)搜索的概念根據(jù)問(wèn)題的實(shí)際情況，不斷尋找可利用的知識(shí)，從而構(gòu)造一條可行的推理路線，使問(wèn)題得到解決的過(guò)程。第11頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月2、搜索的基本知識(shí)搜索的使用場(chǎng)合1、在知識(shí)不完全，沒(méi)有成熟的算法可使用。2、理論上有算法，但問(wèn)題的復(fù)雜度高，用計(jì)算機(jī)求解有時(shí)間、空間的局限性。第12頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月2、搜索的基本知識(shí)搜索的分類(lèi)盲目搜索啟發(fā)式搜索第13頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月2、1搜索的分類(lèi)盲目搜索按預(yù)定的控制策略進(jìn)行搜索，在搜索過(guò)程中獲得的中間信息不用來(lái)改進(jìn)控制策略。通用，效率低，不便于復(fù)雜問(wèn)題的求解。是一種不得已而采取的方法第14頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月2、1搜索的分類(lèi)啟發(fā)式搜索在搜索過(guò)程中，根據(jù)問(wèn)題本身的特性或搜索過(guò)程中產(chǎn)生的一些與問(wèn)題有關(guān)的啟發(fā)信息，指導(dǎo)搜索朝著最有希望的推理方向前進(jìn)，加速問(wèn)題的求解過(guò)程，并找到最優(yōu)解。

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

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

用二元組SK=(SA,SB)表示問(wèn)題的狀態(tài),SA表示金盤(pán)A所在的桿號(hào),SB表示金盤(pán)B所在的桿號(hào)。全部可能的狀態(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)問(wèn)題的初始狀態(tài)集合為S={S0},目標(biāo)狀態(tài)集合為G={S4,S8}。第21頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月2、2狀態(tài)空間表示法(舉例)二階漢諾塔問(wèn)題9種狀態(tài)第22頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月2、2狀態(tài)空間表示法(舉例)二階漢諾塔問(wèn)題算符分別用A(i,j)及B(i,j)表示：A(i,j)表示把A盤(pán)從第i號(hào)桿移到第j號(hào)桿上;B(i,j)表示把B盤(pán)從第i號(hào)桿移到第j號(hào)桿上。則，算符共有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頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月2、2狀態(tài)空間表示法(舉例)二階漢諾塔問(wèn)題

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

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

W－猴子的水平位置

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

Y－箱子的水平位置

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

第26頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月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)問(wèn)題的初始狀態(tài)集合為S={S0},目標(biāo)狀態(tài)集合為G={S12}。第27頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月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è)。第28頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月2、2狀態(tài)空間表示法(舉例)猴子和香蕉

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

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

(1)把A、B盤(pán)從1號(hào)桿移到2號(hào)桿。

(2)把C盤(pán)從1號(hào)桿移到3號(hào)桿。

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

第42頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月2、3與/或樹(shù)表示法(舉例)三階漢諾塔問(wèn)題用三元組表示問(wèn)題在任一時(shí)刻的狀態(tài)：

(i,j,k)其中，i,j,k分別表示金片A、B、C所在的桿號(hào)。第43頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月2、3與/或樹(shù)表示法(舉例)三階漢諾塔問(wèn)題三階漢諾塔問(wèn)題的與/或樹(shù)

第44頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月2、3與/或樹(shù)表示法(舉例)三階漢諾塔問(wèn)題問(wèn)題的解：(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)

第45頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月3、狀態(tài)空間的搜索策略使用搜索求解問(wèn)題時(shí)的狀態(tài)關(guān)系圖。第46頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月3、狀態(tài)空間的搜索策略基本思想：通過(guò)搜索尋找一個(gè)操作算符的調(diào)用序列，使問(wèn)題從初始狀態(tài)變遷到目標(biāo)狀態(tài)。變遷過(guò)程中的狀態(tài)序列，或相應(yīng)的操作算符調(diào)用序列稱(chēng)為從初始狀態(tài)到目標(biāo)狀態(tài)的解答路徑。搜索空間的壓縮程度取決于采用的搜索算法。第47頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月3、狀態(tài)空間的搜索策略分類(lèi)第48頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月3、1狀態(tài)空間的一般搜索過(guò)程搜索過(guò)程要使用的兩個(gè)表OPEN表--存放待擴(kuò)展節(jié)點(diǎn)CLOSED表--存放已被擴(kuò)展節(jié)點(diǎn)s--指示初始狀態(tài)節(jié)點(diǎn)G--指示搜索圖，其中的節(jié)點(diǎn)存放在OPEN表或CLOSED表中第49頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月3、1狀態(tài)空間的一般搜索過(guò)程一般搜索過(guò)程

1)G:=s;//算法開(kāi)始時(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)），但又無(wú)法繼續(xù)搜索；

第50頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月3、1狀態(tài)空間的一般搜索過(guò)程一般搜索過(guò)程

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頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月3、1狀態(tài)空間的一般搜索過(guò)程7)標(biāo)記和修改指針：全新節(jié)點(diǎn)——未曾在G中出現(xiàn)過(guò)（加入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類(lèi)同樣的處理，并把這些子節(jié)點(diǎn)從CLOSED表中移出，重新加入OPEN表）第52頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月3、1狀態(tài)空間的一般搜索過(guò)程8)按某種原則重新排序OPEN表中的節(jié)點(diǎn)；9）返回3）第53頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月3、1狀態(tài)空間的一般搜索過(guò)程開(kā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的指針修改指針?lè)较蛑嘏臤PEN表第54頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月3、1狀態(tài)空間的一般搜索過(guò)程二階漢諾塔的一般搜索過(guò)程第55頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月3、1狀態(tài)空間的一般搜索過(guò)程一些說(shuō)明上述是一個(gè)通用過(guò)程，各種搜索策略的主要區(qū)別是對(duì)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à)來(lái)決定其父節(jié)點(diǎn)，代價(jià)小的相應(yīng)節(jié)點(diǎn)就作為父節(jié)點(diǎn)。(例)第56頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月3、1狀態(tài)空間的一般搜索過(guò)程一些說(shuō)明在搜索過(guò)程中，一旦某個(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頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月3、1狀態(tài)空間的一般搜索過(guò)程修改父節(jié)點(diǎn)指針示例

返回第58頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月3、2廣度優(yōu)先搜索基本思想從初始節(jié)點(diǎn)開(kāi)始，逐層對(duì)節(jié)點(diǎn)進(jìn)行擴(kuò)展并考察是否為目標(biāo)節(jié)點(diǎn)，在第n層的節(jié)點(diǎn)沒(méi)有全部擴(kuò)展前，不對(duì)第n+1層的節(jié)點(diǎn)進(jìn)行擴(kuò)展。可使用一般搜索過(guò)程，但OPEN表中的節(jié)點(diǎn)進(jìn)行先進(jìn)先出排序。第59頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月3、2廣度優(yōu)先搜索開(kā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的指針修改指針?lè)较蛑嘏臤PEN表第60頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月3、2廣度優(yōu)先搜索八數(shù)碼問(wèn)題初始狀態(tài)目標(biāo)狀態(tài)第61頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月3、2廣度優(yōu)先搜索八數(shù)碼問(wèn)題第62頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月3、2廣度優(yōu)先搜索解路徑：So→3→8→16→Sg第63頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月3、2廣度優(yōu)先搜索特點(diǎn)只要問(wèn)題有解，用廣度優(yōu)先搜索總可以得到解，而且得到的是路徑最短的解。廣度優(yōu)先搜索盲目性較大，當(dāng)目標(biāo)節(jié)點(diǎn)離初始節(jié)點(diǎn)較遠(yuǎn)時(shí)將會(huì)產(chǎn)生許多無(wú)用節(jié)點(diǎn)，搜索效率低。第64頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月3、3深度優(yōu)先搜索基本思想從初始節(jié)點(diǎn)開(kāi)始，一直在節(jié)點(diǎn)的子節(jié)點(diǎn)中查找目標(biāo)，如果某節(jié)點(diǎn)的子節(jié)點(diǎn)沒(méi)有全部擴(kuò)展前，不對(duì)它的兄弟節(jié)點(diǎn)進(jìn)行擴(kuò)展?？墒褂靡话闼阉鬟^(guò)程，但OPEN表中的節(jié)點(diǎn)進(jìn)行先進(jìn)后出排序。第65頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月3、3深度優(yōu)先搜索開(kā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的指針修改指針?lè)较蛑嘏臤PEN表第66頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月3、3深度優(yōu)先搜索八數(shù)碼問(wèn)題初始狀態(tài)目標(biāo)狀態(tài)第67頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月3、3深度優(yōu)先搜索第68頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月3、3深度優(yōu)先搜索特點(diǎn)搜索一旦進(jìn)入某個(gè)分支，就將從該分支一直往下搜索。求得的解不一定是路徑最短的解。如果進(jìn)入的是無(wú)窮分支，則可能得不到解。第69頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月3、3深度優(yōu)先搜索八數(shù)碼問(wèn)題進(jìn)入無(wú)窮分支第70頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月3、4有界深度優(yōu)先搜索基本思想在深度優(yōu)先搜索的基礎(chǔ)上，引入搜索深度界限(dm)。當(dāng)搜索深度達(dá)到界限，但未出現(xiàn)目標(biāo)節(jié)點(diǎn)時(shí)，就換一個(gè)分支搜索。第71頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月23184765

231847652831476523184765283147652831647528314765283164752831647528371465

8321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123456789abcd12384765目標(biāo)ef第72頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月3、4有界深度優(yōu)先搜索特點(diǎn)若問(wèn)題有解，則其路徑長(zhǎng)度≤dm

，則一定可求得解。若其路徑長(zhǎng)度＞dm

，則一定求不出解。dm

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

第75頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月3、5代價(jià)樹(shù)的廣度優(yōu)先搜索基本思想在廣度優(yōu)先搜索的基礎(chǔ)上，每次都從OPEN表中取出代價(jià)最小的節(jié)點(diǎn)放入CLOSED表。第76頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月3、5代價(jià)樹(shù)的廣度優(yōu)先搜索旅行問(wèn)題設(shè)A城是出發(fā)地,E城是目的地,邊上的數(shù)字代表兩城之間的交通費(fèi)。試求從A到E最小費(fèi)用的旅行路線。

ABCDE432345交通圖第77頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月3、5代價(jià)樹(shù)的廣度優(yōu)先搜索旅行問(wèn)題最佳解路徑：A→C1→D1→E2最小費(fèi)用路線：A→C→D→E第78頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月3、5代價(jià)樹(shù)的深度優(yōu)先搜索基本思想在深度優(yōu)先搜索的基礎(chǔ)上，每次都從剛擴(kuò)展的子節(jié)點(diǎn)中取出代價(jià)最小的節(jié)點(diǎn)放入CLOSED表。第79頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月3、5代價(jià)樹(shù)的深度優(yōu)先搜索旅行問(wèn)題最佳解路徑：A→C1→D1→E2最小費(fèi)用路線：A→C→D→E第80頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月3、6啟發(fā)式搜索搜索過(guò)程中用到問(wèn)題自身的某些特征信息，指導(dǎo)搜索朝著最有希望的方向進(jìn)行。用于指導(dǎo)搜索過(guò)程的信息稱(chēng)為啟發(fā)信息。啟發(fā)信息的強(qiáng)度強(qiáng)，降低搜索工作量，可能導(dǎo)致找不到最優(yōu)解弱，極限情況下變?yōu)槊つ克阉鞯?1頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月3、6啟發(fā)式搜索基本思想定義一個(gè)估價(jià)函數(shù)f，對(duì)當(dāng)前的搜索狀態(tài)進(jìn)行評(píng)估，找出一個(gè)最有希望的節(jié)點(diǎn)來(lái)進(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頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月3、6啟發(fā)式搜索例子設(shè)有如下結(jié)構(gòu)的移動(dòng)將牌游戲：DDDWWWE其中，E代表該位置為空。該游戲規(guī)則：1、當(dāng)一個(gè)牌移入相鄰的空位置時(shí)，費(fèi)用為一個(gè)單位。2、一個(gè)牌至多可跳過(guò)兩個(gè)牌進(jìn)入空位置，其費(fèi)用等于跳過(guò)的牌數(shù)加1。要求把所有的Ｄ都移至W的右邊。第83頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月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頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月3、6、1局部擇優(yōu)搜索基本思想當(dāng)一個(gè)節(jié)點(diǎn)x被擴(kuò)展以后，按f(x)對(duì)x的每個(gè)子節(jié)點(diǎn)計(jì)算估計(jì)值，并從擴(kuò)展的子節(jié)點(diǎn)中選擇估計(jì)值最小的節(jié)點(diǎn)作為下一個(gè)考察對(duì)象。

深度優(yōu)先搜索、代價(jià)樹(shù)的深度優(yōu)先搜索以及局部擇優(yōu)搜索都是以子節(jié)點(diǎn)作為考察范圍的。但是前二者可以看作局部擇優(yōu)搜索的特例。第85頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月3、6、2全局擇優(yōu)搜索基本思想每次總是從OPEN表的全體節(jié)點(diǎn)中選取一個(gè)估計(jì)值最小的節(jié)點(diǎn)。廣度優(yōu)先搜索、代價(jià)樹(shù)的廣度優(yōu)先搜索以及全局擇優(yōu)搜索都是以當(dāng)前所有節(jié)點(diǎn)作為考察范圍的。但是前二者可以看作全局擇優(yōu)搜索的特例。第86頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月3、6、2全局擇優(yōu)搜索例子用全局擇優(yōu)搜索求八數(shù)碼問(wèn)題。28316475123457681238

476512345768g(x)表示節(jié)點(diǎn)x的深度h(x)表示節(jié)點(diǎn)x的格局與目標(biāo)節(jié)點(diǎn)的格局不同的牌數(shù)。第87頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月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)第88頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月4、與/或樹(shù)的搜索策略基本思想用分解或等價(jià)變換算符通過(guò)搜索生成與或樹(shù)，最終應(yīng)能標(biāo)識(shí)出初始節(jié)點(diǎn)（對(duì)應(yīng)于原問(wèn)題）為可解節(jié)點(diǎn)（原問(wèn)題有解）或不可解節(jié)點(diǎn)（原問(wèn)題無(wú)解）。與/或樹(shù)搜索的目標(biāo)是尋找解樹(shù)，從而求得原問(wèn)題的解。第89頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月4、1與/或樹(shù)的一般搜索過(guò)程可解標(biāo)識(shí)過(guò)程：由可解子節(jié)點(diǎn)來(lái)確定其父節(jié)點(diǎn)、祖父節(jié)點(diǎn)等為可解節(jié)點(diǎn)的過(guò)程。不可解標(biāo)識(shí)過(guò)程：由不可解子節(jié)點(diǎn)來(lái)確定其父節(jié)點(diǎn)、祖父節(jié)點(diǎn)等為不可解節(jié)點(diǎn)的過(guò)程。與/或樹(shù)的搜索過(guò)程將反復(fù)使用上述兩個(gè)過(guò)程，直到初始節(jié)點(diǎn)被標(biāo)示為可解或不可解節(jié)點(diǎn)為止。搜索形成的節(jié)點(diǎn)和指針結(jié)構(gòu)稱(chēng)為搜索樹(shù)。第90頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月4、1與/或樹(shù)的一般搜索過(guò)程一般過(guò)程(1)把原始問(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)識(shí)過(guò)程和不可解標(biāo)識(shí)過(guò)程，直到初始節(jié)點(diǎn)被標(biāo)識(shí)為可解或不可解節(jié)點(diǎn)為止。第91頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月4、1與/或樹(shù)的一般搜索過(guò)程搜索過(guò)程中的注意點(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)就不再有用，可從搜索樹(shù)中刪去。如果已經(jīng)確定某個(gè)節(jié)點(diǎn)為不可解節(jié)點(diǎn)，則其全部子節(jié)點(diǎn)就不再有用，可從搜索樹(shù)中刪去；但當(dāng)前這個(gè)不可解節(jié)點(diǎn)還不能刪去，以后它還要用來(lái)判斷其先輩節(jié)點(diǎn)的可解性。第92頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月4、2與/或樹(shù)的廣度優(yōu)先搜索基本思想跟狀態(tài)空間的廣度優(yōu)先搜索類(lèi)似，但在搜索過(guò)程中要多次調(diào)用可解標(biāo)示過(guò)程和不可解標(biāo)示過(guò)程。第93頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月開(kāi)始把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)示過(guò)程從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)示過(guò)程是S為可解節(jié)點(diǎn)？是從OPEN表中刪除具有可解先輩的節(jié)點(diǎn)否第94頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月4、2與/或樹(shù)的廣度優(yōu)先搜索例子設(shè)有如圖所示的與/或樹(shù)，節(jié)點(diǎn)按圖中所標(biāo)注的順序進(jìn)行擴(kuò)展。其中，t1,t2,t3,t4為終止節(jié)點(diǎn)，A和B為不可解節(jié)點(diǎn)。12345ABt1t2t3t4第95頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月4、2與/或樹(shù)的廣度優(yōu)先搜索12345ABt1t2t3t412345ABt1t2t3t4擴(kuò)展順序?yàn)椋?，2，3，4，5第96頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月4、3與/或樹(shù)的深度優(yōu)先搜索基本思想跟狀態(tài)空間的深度優(yōu)先搜索類(lèi)似，但在搜索過(guò)程中要多次調(diào)用可解標(biāo)示過(guò)程和不可解標(biāo)示過(guò)程。第97頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月4、3與/或樹(shù)的深度優(yōu)先搜索12345ABt1t2t3t412345ABt1t2t3t4擴(kuò)展順序?yàn)椋?，2，4，3，5第98頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月4、4與/或樹(shù)的有序搜索基本思想是用來(lái)求代價(jià)最小的解樹(shù)的一種搜索方法。在確定下一個(gè)要擴(kuò)展的節(jié)點(diǎn)時(shí)，先計(jì)算需要付出的代價(jià)，選擇代價(jià)最小的節(jié)點(diǎn)進(jìn)行擴(kuò)展。第99頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月4、4與/或樹(shù)的有序搜索解樹(shù)的代價(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頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月4、4與/或樹(shù)的有序搜索解樹(shù)的代價(jià)(例子)如圖是一棵與/或解樹(shù)，求該樹(shù)的代價(jià)。h(A)=11，h(S0)=13h(B)=6，h(S0)=8S0ABFt2Ct3t4t5DEt1226521212113G第101頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月4、4與/或樹(shù)的有序搜索解樹(shù)的代價(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在往后的搜索過(guò)程中被擴(kuò)展后，還要重新計(jì)算先輩節(jié)點(diǎn)x的代價(jià)。第102頁(yè)，課件共110頁(yè)，創(chuàng)作于2023年2月開(kāi)始把S放入OPEN