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

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

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

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

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

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

要求把A、B兩塊金片全部移到另一個鋼針上。規(guī)定每次只能移動一片，并且任何時刻不能出現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},目標狀態(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個。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個算符,二階漢諾塔問題的狀態(tài)空間圖如下：從(1,1)到(2,2)或(3,3)的任何一條通路都是問題的一個解。第二十四頁，共一百一十頁，2022年，8月28日2、2狀態(tài)空間表示法(舉例)猴子和香蕉在一個房間內有一只猴子、一個箱子和一束香蕉。香蕉掛在天花板下方，但猴子的高度不足以碰到它。那么這只猴子怎樣才能摘到香蕉呢?第二十五頁，共一百一十頁，2022年，8月28日2、2狀態(tài)空間表示法(舉例)猴子和香蕉

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

W－猴子的水平位置

x－當猴子在箱子頂上時取x=1；否則取x=0

Y－箱子的水平位置

z－當猴子摘到香蕉時取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},目標狀態(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個，包括猴子移動的4個，箱子移動的4個，猴子爬上箱子1個、爬下箱子1個，猴子摘到香蕉1個。第二十八頁，共一百一十頁，2022年，8月28日2、2狀態(tài)空間表示法(舉例)猴子和香蕉

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

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

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

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

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

第四十二頁，共一百一十頁，2022年，8月28日2、3與/或樹表示法(舉例)三階漢諾塔問題用三元組表示問題在任一時刻的狀態(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)空間的搜索策略使用搜索求解問題時的狀態(tài)關系圖。第四十六頁，共一百一十頁，2022年，8月28日3、狀態(tài)空間的搜索策略基本思想：通過搜索尋找一個操作算符的調用序列，使問題從初始狀態(tài)變遷到目標狀態(tài)。變遷過程中的狀態(tài)序列，或相應的操作算符調用序列稱為從初始狀態(tài)到目標狀態(tài)的解答路徑。搜索空間的壓縮程度取決于采用的搜索算法。第四十七頁，共一百一十頁，2022年，8月28日3、狀態(tài)空間的搜索策略分類第四十八頁，共一百一十頁，2022年，8月28日3、1狀態(tài)空間的一般搜索過程搜索過程要使用的兩個表OPEN表--存放待擴展節(jié)點CLOSED表--存放已被擴展節(jié)點s--指示初始狀態(tài)節(jié)點G--指示搜索圖，其中的節(jié)點存放在OPEN表或CLOSED表中第四十九頁，共一百一十頁，2022年，8月28日3、1狀態(tài)空間的一般搜索過程一般搜索過程

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

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

3)若OPEN是空表，則搜索失敗，結束；//因為此時并未搜索到解答（目標狀態(tài)），但又無法繼續(xù)搜索；

第五十頁，共一百一十頁，2022年，8月28日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中；第五十一頁，共一百一十頁，2022年，8月28日3、1狀態(tài)空間的一般搜索過程7)標記和修改指針：全新節(jié)點——未曾在G中出現過（加入OPEN表，并建立從子節(jié)點到父節(jié)點n的指針）已在OPEN表的節(jié)點（比較子節(jié)點經由新、老父節(jié)點到達初始狀態(tài)節(jié)點s的路徑代價，若經由新父節(jié)點的代價較小，則修改子節(jié)點的指針，指向新父節(jié)點）已在CLOSED表的節(jié)點（與第2類同樣的處理，并把這些子節(jié)點從CLOSED表中移出，重新加入OPEN表）第五十二頁，共一百一十頁，2022年，8月28日3、1狀態(tài)空間的一般搜索過程8)按某種原則重新排序OPEN表中的節(jié)點；9）返回3）第五十三頁，共一百一十頁，2022年，8月28日3、1狀態(tài)空間的一般搜索過程開始把S放入OPEN表OPEN表為空表？是失敗否把第一個節(jié)點（n）從OPEN移至CLOSED表n為目標節(jié)點？是成功否把n的后繼節(jié)點放入OPEN表，提供返回節(jié)點n的指針修改指針方向重排OPEN表第五十四頁，共一百一十頁，2022年，8月28日3、1狀態(tài)空間的一般搜索過程二階漢諾塔的一般搜索過程第五十五頁，共一百一十頁，2022年，8月28日3、1狀態(tài)空間的一般搜索過程一些說明上述是一個通用過程，各種搜索策略的主要區(qū)別是對OPEN表中節(jié)點排序的準則不同。如果子節(jié)點的算符有多個，則擴展時會生成一組子節(jié)點。但不能把該節(jié)點的先輩節(jié)點作為它當前擴展的子節(jié)點。一個新生成的節(jié)點，它可能是第一次被生成，也可能是被再次生成的。此時，一般由原始節(jié)點到該節(jié)點的代價來決定其父節(jié)點，代價小的相應節(jié)點就作為父節(jié)點。(例)第五十六頁，共一百一十頁，2022年，8月28日3、1狀態(tài)空間的一般搜索過程一些說明在搜索過程中，一旦某個被考察的節(jié)點是目標節(jié)點，就得到了一個解。該解由從初始節(jié)點到該目標節(jié)點路徑上的算符構成。如果在搜索中一直找不到目標節(jié)點，而且OPEN表中不再有可供擴展的節(jié)點，則搜索失敗。第五十七頁，共一百一十頁，2022年，8月28日3、1狀態(tài)空間的一般搜索過程修改父節(jié)點指針示例

返回第五十八頁，共一百一十頁，2022年，8月28日3、2廣度優(yōu)先搜索基本思想從初始節(jié)點開始，逐層對節(jié)點進行擴展并考察是否為目標節(jié)點，在第n層的節(jié)點沒有全部擴展前，不對第n+1層的節(jié)點進行擴展?？墒褂靡话闼阉鬟^程，但OPEN表中的節(jié)點進行先進先出排序。第五十九頁，共一百一十頁，2022年，8月28日3、2廣度優(yōu)先搜索開始把S放入OPEN表OPEN表為空表？是失敗否把第一個節(jié)點（n）從OPEN移至CLOSED表n為目標節(jié)點？是成功否把n的后繼節(jié)點放入OPEN表的末端，提供返回節(jié)點n的指針修改指針方向重排OPEN表第六十頁，共一百一十頁，2022年，8月28日3、2廣度優(yōu)先搜索八數碼問題初始狀態(tài)目標狀態(tài)第六十一頁，共一百一十頁，2022年，8月28日3、2廣度優(yōu)先搜索八數碼問題第六十二頁，共一百一十頁，2022年，8月28日3、2廣度優(yōu)先搜索解路徑：So→3→8→16→Sg第六十三頁，共一百一十頁，2022年，8月28日3、2廣度優(yōu)先搜索特點只要問題有解，用廣度優(yōu)先搜索總可以得到解，而且得到的是路徑最短的解。廣度優(yōu)先搜索盲目性較大，當目標節(jié)點離初始節(jié)點較遠時將會產生許多無用節(jié)點，搜索效率低。第六十四頁，共一百一十頁，2022年，8月28日3、3深度優(yōu)先搜索基本思想從初始節(jié)點開始，一直在節(jié)點的子節(jié)點中查找目標，如果某節(jié)點的子節(jié)點沒有全部擴展前，不對它的兄弟節(jié)點進行擴展?？墒褂靡话闼阉鬟^程，但OPEN表中的節(jié)點進行先進后出排序。第六十五頁，共一百一十頁，2022年，8月28日3、3深度優(yōu)先搜索開始把S放入OPEN表OPEN表為空表？是失敗否把第一個節(jié)點（n）從OPEN移至CLOSED表n為目標節(jié)點？是成功否把n的后繼節(jié)點放入OPEN表的前端，提供返回節(jié)點n的指針修改指針方向重排OPEN表第六十六頁，共一百一十頁，2022年，8月28日3、3深度優(yōu)先搜索八數碼問題初始狀態(tài)目標狀態(tài)第六十七頁，共一百一十頁，2022年，8月28日3、3深度優(yōu)先搜索第六十八頁，共一百一十頁，2022年，8月28日3、3深度優(yōu)先搜索特點搜索一旦進入某個分支，就將從該分支一直往下搜索。求得的解不一定是路徑最短的解。如果進入的是無窮分支，則可能得不到解。第六十九頁，共一百一十頁，2022年，8月28日3、3深度優(yōu)先搜索八數碼問題進入無窮分支第七十頁，共一百一十頁，2022年，8月28日3、4有界深度優(yōu)先搜索基本思想在深度優(yōu)先搜索的基礎上，引入搜索深度界限(dm)。當搜索深度達到界限，但未出現目標節(jié)點時，就換一個分支搜索。第七十一頁，共一百一十頁，2022年，8月28日23184765

231847652831476523184765283147652831647528314765283164752831647528371465

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

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

，則一定求不出解。dm

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

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

ABCDE432345交通圖第七十七頁，共一百一十頁，2022年，8月28日3、5代價樹的廣度優(yōu)先搜索旅行問題最佳解路徑：A→C1→D1→E2最小費用路線：A→C→D→E第七十八頁，共一百一十頁，2022年，8月28日3、5代價樹的深度優(yōu)先搜索基本思想在深度優(yōu)先搜索的基礎上，每次都從剛擴展的子節(jié)點中取出代價最小的節(jié)點放入CLOSED表。第七十九頁，共一百一十頁，2022年，8月28日3、5代價樹的深度優(yōu)先搜索旅行問題最佳解路徑：A→C1→D1→E2最小費用路線：A→C→D→E第八十頁，共一百一十頁，2022年，8月28日3、6啟發(fā)式搜索搜索過程中用到問題自身的某些特征信息，指導搜索朝著最有希望的方向進行。用于指導搜索過程的信息稱為啟發(fā)信息。啟發(fā)信息的強度強，降低搜索工作量，可能導致找不到最優(yōu)解弱，極限情況下變?yōu)槊つ克阉鞯诎耸豁?，共一百一十頁?022年，8月28日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ā)信息）第八十二頁，共一百一十頁，2022年，8月28日3、6啟發(fā)式搜索例子設有如下結構的移動將牌游戲：DDDWWWE其中，E代表該位置為空。該游戲規(guī)則：1、當一個牌移入相鄰的空位置時，費用為一個單位。2、一個牌至多可跳過兩個牌進入空位置，其費用等于跳過的牌數加1。要求把所有的Ｄ都移至W的右邊。第八十三頁，共一百一十頁，2022年，8月28日3、6啟發(fā)式搜索例子解：根據要求可知，W左邊的Ｄ越少越接近目標，因此可用W左邊Ｄ的個數作為h(x),即h(x)=3×(每個W左邊Ｄ個數的總和)這里乘以系數3是為了擴大h(x)在f(x)中的比重。第八十四頁，共一百一十頁，2022年，8月28日3、6、1局部擇優(yōu)搜索基本思想當一個節(jié)點x被擴展以后，按f(x)對x的每個子節(jié)點計算估計值，并從擴展的子節(jié)點中選擇估計值最小的節(jié)點作為下一個考察對象。

深度優(yōu)先搜索、代價樹的深度優(yōu)先搜索以及局部擇優(yōu)搜索都是以子節(jié)點作為考察范圍的。但是前二者可以看作局部擇優(yōu)搜索的特例。第八十五頁，共一百一十頁，2022年，8月28日3、6、2全局擇優(yōu)搜索基本思想每次總是從OPEN表的全體節(jié)點中選取一個估計值最小的節(jié)點。廣度優(yōu)先搜索、代價樹的廣度優(yōu)先搜索以及全局擇優(yōu)搜索都是以當前所有節(jié)點作為考察范圍的。但是前二者可以看作全局擇優(yōu)搜索的特例。第八十六頁，共一百一十頁，2022年，8月28日3、6、2全局擇優(yōu)搜索例子用全局擇優(yōu)搜索求八數碼問題。28316475123457681238

476512345768g(x)表示節(jié)點x的深度h(x)表示節(jié)點x的格局與目標節(jié)點的格局不同的牌數。第八十七頁，共一百一十頁，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目標第八十八頁，共一百一十頁，2022年，8月28日4、與/或樹的搜索策略基本思想用分解或等價變換算符通過搜索生成與或樹，最終應能標識出初始節(jié)點（對應于原問題）為可解節(jié)點（原問題有解）或不可解節(jié)點（原問題無解）。與/或樹搜索的目標是尋找解樹，從而求得原問題的解。第八十九頁，共一百一十頁，2022年，8月28日4、1與/或樹的一般搜索過程可解標識過程：由可解子節(jié)點來確定其父節(jié)點、祖父節(jié)點等為可解節(jié)點的過程。不可解標識過程：由不可解子節(jié)點來確定其父節(jié)點、祖父節(jié)點等為不可解節(jié)點的過程。與/或樹的搜索過程將反復使用上述兩個過程，直到初始節(jié)點被標示為可解或不可解節(jié)點為止。搜索形成的節(jié)點和指針結構稱為搜索樹。第九十頁，共一百一十頁，2022年，8月28日4、1與/或樹的一般搜索過程一般過程(1)把原始問題作為初始節(jié)點S0，并把它作為當前節(jié)點。(2)應用分解或等價變換算符對當前節(jié)點進行擴充。(3)為每個子節(jié)點設置指向父節(jié)點的指針。(4)選擇合適的子節(jié)點作為當前節(jié)點，反復執(zhí)行第（2）、（3）步。在此其間要多次調用可解標識過程和不可解標識過程，直到初始節(jié)點被標識為可解或不可解節(jié)點為止。第九十一頁，共一百一十頁，2022年，8月28日4、1與/或樹的一般搜索過程搜索過程中的注意點某個節(jié)點不能擴展，也不是終止節(jié)點，則該節(jié)點是不可解節(jié)點。如果已經確定某個節(jié)點為可解節(jié)點，則其不可解的子節(jié)點就不再有用，可從搜索樹中刪去。如果已經確定某個節(jié)點為不可解節(jié)點，則其全部子節(jié)點就不再有用，可從搜索樹中刪去；但當前這個不可解節(jié)點還不能刪去，以后它還要用來判斷其先輩節(jié)點的可解性。第九十二頁，共一百一十頁，2022年，8月28日4、2與/或樹的廣度優(yōu)先搜索基本思想跟狀態(tài)空間的廣度優(yōu)先搜索類似，但在搜索過程中要多次調用可解標示過程和不可解標示過程。第九十三頁，共一百一十頁，2022年，8月28日開始把S放入OPEN表OPEN表為空表？是失敗否把第一個節(jié)點（n）從OPEN移至CLOSED表節(jié)點n可擴展？是成功否標示節(jié)點n為不可解節(jié)點，應用不可解標示過程從OPEN表中刪除具有不可解先輩的節(jié)點S為不可解節(jié)點？是失敗否將節(jié)點n的子節(jié)點放入OPEN表，并為子節(jié)點配置指針子節(jié)點有終止節(jié)點？否標示節(jié)點n為可解節(jié)點，應用可解標示過程是S為可解節(jié)點？是從OPEN表中刪除具有可解先輩的節(jié)點否第九十四頁，共一百一十頁，2022年，8月28日4、2與/或樹的廣度優(yōu)先搜索例子設有如圖所示的與/或樹，節(jié)點按圖中所標注的順序進行擴展。其中，t1,t2,t3,t4為終止節(jié)點，A和B為不可解節(jié)點。12345ABt1t2t3t4第九十五頁，共一百一十頁，2022年，8月28日4、2與/或樹的廣度優(yōu)先搜索12345ABt1t2t3t412345ABt1t2t3t4擴展順序為：1，2，3，4，5第九十六頁，共一百一十頁，2022年，8月28日4、3與/或樹的深度優(yōu)先搜索基本思想跟狀態(tài)空間的深度優(yōu)先搜索類似，但在搜索過程中要多次調用可解標示過程和不可解標示過程。第九十七頁，共一百一十頁，2022年，8月28日4、3與/或樹的深度優(yōu)先搜索12345ABt1t2t3t412345ABt1t2t3t4擴展順序為：1，2，4，3，5第九十八頁，共一百一十頁，2022年，8月28日4、4與/或樹的有序搜索基本思想是用來求代價最小的解樹的一種搜索方法。在確定下一個要擴展的節(jié)點時，先計算需要付出的代價，選擇代價最小的節(jié)點進行擴展。第九十九頁，共一百一十頁，2022年，8月28日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)=∞第一百頁，共一百一十頁，2022年，8月28日4、4與/或樹的有序搜索解樹的代價(例子)如圖是一棵與/或解樹，求該樹的代價。h(A)=11，h(S0)=13h(B)=6，h(S0)=8S0ABFt2Ct3t4t5DEt1226521212113G第一百零一頁，共一百一十頁，2022年，8月28日4、4與/或樹的有序搜索解樹的代價當計算某一節(jié)點x的代價h(x)時，都要求已知它的子節(jié)點yi代價，但搜索是從上到下進行的，因此一般使用啟發(fā)函數估算yi

。當yi在往后的搜索過程中被擴展后，還要重新計算先輩節(jié)點x的代價。第一百零二頁，共一百一十頁，2022年，8月28日開始把S放入OP