第3章圖搜索與問題求解

3.1概述3.2狀態(tài)圖與狀態(tài)圖搜索3.3狀態(tài)圖搜索問題求解延伸學(xué)習(xí)導(dǎo)引

3.1概述搜索是人工智能技術(shù)中進(jìn)行問題求解的基本技術(shù)，不管是符號智能還是計算智能以及統(tǒng)計智能和交互智能，不管是解決具體應(yīng)用問題（如：證明、診斷、規(guī)劃、調(diào)度、配置、優(yōu)化），還是智能行為本身（如：學(xué)習(xí)、識別），最終往往都?xì)w結(jié)為某種搜索，都要用某種搜索算法來實(shí)現(xiàn)。3.2狀態(tài)圖與狀態(tài)圖搜索

3.2.1狀態(tài)圖

迷宮問題圖

3-1迷宮圖

圖

3-2迷宮的有向圖表示

圖

3-3八數(shù)碼問題示例

八數(shù)碼問題

3.2.2狀態(tài)圖搜索

1.搜索方式

樹式搜索形象地講就是以“畫樹”的方式進(jìn)行搜索。即從樹根（初始節(jié)點(diǎn)）出發(fā)，一筆一筆地描出一棵樹來。準(zhǔn)確地講，樹式搜索就是在搜索過程中記錄所經(jīng)過的所有節(jié)點(diǎn)和邊。所以，樹式搜索所記錄的軌跡始終是一棵“樹”，這棵樹也就是搜索過程中所產(chǎn)生的搜索樹。

線式搜索形象地講就是以“畫線”的方式進(jìn)行搜索。準(zhǔn)確地講，線式搜索在搜索過程中只記錄那些當(dāng)前認(rèn)為是處在所找路徑上的節(jié)點(diǎn)和邊。所以，線式搜索所記錄的軌跡始終是一條“線”（折線）。

2.搜索策略

盲目搜索就是無“向?qū)А钡乃阉?。樹式盲目搜索就是窮舉式搜索，即從初始節(jié)點(diǎn)出發(fā)，沿連接邊逐一考察各個節(jié)點(diǎn)（看是否為目標(biāo)節(jié)點(diǎn)），或者反向進(jìn)行；而線式盲目搜索，對于不回溯的就是隨機(jī)碰撞式搜索，對于回溯的則也是窮舉式的搜索。

啟發(fā)式(heuristic)搜索是利用“啟發(fā)性信息”引導(dǎo)的搜索。所謂“啟發(fā)性信息”就是與問題有關(guān)的有利于盡快找到問題解的信息或知識。啟發(fā)式搜索又可分為許多不同的策略，如全局擇優(yōu)、局部擇優(yōu)（瞎子爬山法）、最佳圖搜索等等。

按搜索范圍的擴(kuò)展順序的不同，搜索又可分為廣度優(yōu)先和深度優(yōu)先兩種類型。

圖

3-4OPEN表與CLOSED表示例

3.搜索算法樹式搜索算法：

(1)把初始節(jié)點(diǎn)So放入OPEN表中。

(2)若OPEN表為空,則搜索失敗,退出。

(3)移出OPEN表中第一個節(jié)點(diǎn)N放入CLOSED表中,并冠以順序編號n。

(4)若目標(biāo)節(jié)點(diǎn)Sg=N,則搜索成功,結(jié)束。

(5)若N不可擴(kuò)展,則轉(zhuǎn)步(2)。

(6)擴(kuò)展N,生成一組子節(jié)點(diǎn),對這組子節(jié)點(diǎn)做如下處理：

①刪除N的先輩節(jié)點(diǎn)(如果有的話)。

②對已存在于OPEN表的節(jié)點(diǎn)(如果有的話)也刪除之；但刪除之前要比較其返回初始節(jié)點(diǎn)的新路徑與原路徑,如果新路徑“短”,則修改這些節(jié)點(diǎn)在OPEN表中的原返回指針,使其沿新路返回(如圖3-5所示)。③對已存在于CLOSED表的節(jié)點(diǎn)(如果有的話),做與(2)同樣的處理,并且再將其移出CLOSED表,放入OPEN表重新擴(kuò)展(為了重新計算代價)。④對其余子節(jié)點(diǎn)配上指向N的返回指針后放入OPEN表中某處,或?qū)PEN表進(jìn)行重新排序,轉(zhuǎn)步(2)。

說明：

(1)這里的返回指針也就是父節(jié)點(diǎn)在CLOSED表中的編號。

(2)步(6)中修改返回指針的原因是,因?yàn)檫@些節(jié)點(diǎn)又被第二次生成,所以它們返回初始節(jié)點(diǎn)的路徑已有兩條,但這兩條路徑的“長度”可能不同。那么,當(dāng)新路短時自然要走新路。

(3)這里對路徑的長短是按路徑上的節(jié)點(diǎn)數(shù)來衡量的,后面我們將會看到路徑的長短也可以其“代價”(如距離、費(fèi)用、時間等)衡量。若按其代價衡量,則在需修改返回指針的同時還要修改相應(yīng)的代價值,或者不修改返回指針也要修改代價值(為了實(shí)現(xiàn)代價小者優(yōu)先擴(kuò)展)。線式搜索算法：

不回溯的線式搜索

(1)把初始節(jié)點(diǎn)So放入CLOSED表中。

(2)令N＝So。

(3)若N是目標(biāo)節(jié)點(diǎn),則搜索成功,結(jié)束。

(4)若N不可擴(kuò)展,則搜索失敗,退出。

(5)擴(kuò)展N,選取其一個未在CLOSED表中出現(xiàn)過的子節(jié)點(diǎn)N1放入CLOSED表中,令N＝N1,轉(zhuǎn)步(3)。

可回溯的線式搜索

(1)把初始節(jié)點(diǎn)So放入CLOSED表中。

(2)令N＝So。

(3)若N是目標(biāo)節(jié)點(diǎn),則搜索成功,結(jié)束。

(4)若N不可擴(kuò)展,則移出CLOSED表的末端節(jié)點(diǎn)Ne,若Ne＝So,則搜索失敗,退出。否則,以CLOSED表新的末端節(jié)點(diǎn)Ne作為N,即令N＝Ne,轉(zhuǎn)步(4)。

(5)擴(kuò)展N,選取其一個未在CLOSED表用出現(xiàn)過的子節(jié)點(diǎn)N1放入CLOSED表中,令N＝N1,轉(zhuǎn)步(3)。

3.2.3窮舉式搜索

1.廣度優(yōu)先搜索廣度優(yōu)先搜索就是始終先在同一級節(jié)點(diǎn)中考察，只有當(dāng)同一級節(jié)點(diǎn)考察完之后，才考察下一級節(jié)點(diǎn)?；蛘哒f，是以初始節(jié)點(diǎn)為根節(jié)點(diǎn)，向下逐級擴(kuò)展搜索樹。所以,廣度優(yōu)先策略的搜索樹是自頂向下一層一層逐漸生成的。

例

3-1用廣度優(yōu)先搜索策略求解八數(shù)碼問題。解設(shè)初始節(jié)點(diǎn)So和目標(biāo)節(jié)點(diǎn)Sg分別如圖3-3的初始棋局和目標(biāo)棋局所示，用廣度優(yōu)先搜索策略，則可得到如圖3-6所示的搜索樹。圖3-6八數(shù)碼問題的廣度優(yōu)先搜索

廣度優(yōu)先搜索算法：

(1)把初始節(jié)點(diǎn)So放入OPEN表中。

(2)若OPEN表為空,則搜索失敗,退出。

(3)取OPEN表中前面第一個節(jié)點(diǎn)N放在CLOSED表中,并冠以順序編號n。

(4)若目標(biāo)節(jié)點(diǎn)Sg=N,則搜索成功,結(jié)束。

(5)若N不可擴(kuò)展,則轉(zhuǎn)步(2)。

(6)擴(kuò)展N,將其所有子節(jié)點(diǎn)配上指向N的指針依次放入OPEN表尾部,轉(zhuǎn)步(2)。

2.深度優(yōu)先搜索深度優(yōu)先搜索就是在搜索樹的每一層始終先只擴(kuò)展一個子節(jié)點(diǎn)，不斷地向縱深前進(jìn)，直到不能再前進(jìn)（到達(dá)葉子節(jié)點(diǎn)或受到深度限制）時，才從當(dāng)前節(jié)點(diǎn)返回到上一級節(jié)點(diǎn)，沿另一方向又繼續(xù)前進(jìn)。這種方法的搜索樹是從樹根開始一枝一枝逐漸形成的。

圖3-7八數(shù)碼問題的深度優(yōu)先搜索

深度優(yōu)先搜索算法：

(1)把初始節(jié)點(diǎn)So放入OPEN表中。

(2)若OPEN表為空,則搜索失敗,退出。

(3)取OPEN表中前面第一個節(jié)點(diǎn)N放入CLOSED表中,并冠以順序編號n。

(4)若目標(biāo)節(jié)點(diǎn)Sg=N,則搜索成功,結(jié)束。

(5)若N不可擴(kuò)展,則轉(zhuǎn)步(2)。

(6)擴(kuò)展N,將其所有子節(jié)點(diǎn)配上指向N的返回指針依次放入OPEN表的首部,轉(zhuǎn)步(2)。

3.2.4啟發(fā)式搜索

1.問題的提出

2.啟發(fā)性信息

按其用途劃分,啟發(fā)性信息可分為以下三類：

(1)用于擴(kuò)展節(jié)點(diǎn)的選擇,即用于決定應(yīng)先擴(kuò)展哪一個節(jié)點(diǎn),以免盲目擴(kuò)展。

(2)用于生成節(jié)點(diǎn)的選擇,即用于決定應(yīng)生成哪些后續(xù)節(jié)點(diǎn),以免盲目地生成過多無用節(jié)點(diǎn)。

(3)用于刪除節(jié)點(diǎn)的選擇,即用于決定應(yīng)刪除哪些無用節(jié)點(diǎn),以免造成進(jìn)一步的時空浪費(fèi)。3.啟發(fā)函數(shù)

啟發(fā)函數(shù)是用來估計搜索樹上節(jié)點(diǎn)x與目標(biāo)節(jié)點(diǎn)Sg接近程度的一種函數(shù),通常記為h(x)。4.啟發(fā)式搜索算法

1)全局擇優(yōu)搜索

2)局部擇優(yōu)搜索

全局擇優(yōu)搜索算法：

(1)把初始節(jié)點(diǎn)So放入OPEN表中,計算h(So)。

(2)若OPEN表為空,則搜索失敗,退出。

(3)移出OPEN表中第一個節(jié)點(diǎn)N放入CLOSED表中,并冠以序號n。

(4)若目標(biāo)節(jié)點(diǎn)Sg=N,則搜索成功,結(jié)束。

(5)若N不可擴(kuò)展,則轉(zhuǎn)步(2)。

(6)擴(kuò)展N,計算每個子節(jié)點(diǎn)x的函數(shù)值h(x),并將所有子節(jié)點(diǎn)配以指向N的返回指針后放入OPEN表中,再對OPEN表中的所有子節(jié)點(diǎn)按其函數(shù)值大小以升序排序,轉(zhuǎn)步(2)。

例3-3

用全局擇優(yōu)搜索法解八數(shù)碼難題。初始棋局和目標(biāo)棋局如下面的圖3-8所示。

解

設(shè)啟發(fā)函數(shù)h(x)為節(jié)點(diǎn)x的格局與目標(biāo)格局相比數(shù)碼不同的位置個數(shù)。以這個函數(shù)制導(dǎo)的搜索樹如圖3-8所示。此八數(shù)問題的解為：So,S1,S2,S3,Sg。

圖

3-8八數(shù)碼問題的全局擇優(yōu)搜索

■教材的微課視頻中有搜索過程的動畫3.3狀態(tài)圖搜索問題求解

3.3.1問題的狀態(tài)圖表示

1.狀態(tài)

狀態(tài)就是問題在任一確定時刻的狀況,它表征了問題特征和結(jié)構(gòu)等。狀態(tài)在狀態(tài)圖中表示為節(jié)點(diǎn)。狀態(tài)一般用一組數(shù)據(jù)表示。在程序中用字符、數(shù)字、記錄、數(shù)組、結(jié)構(gòu)、對象等表示。

2.狀態(tài)轉(zhuǎn)換規(guī)則

狀態(tài)轉(zhuǎn)換規(guī)則就是能使問題狀態(tài)改變的某種操作、規(guī)則、行為、變換、關(guān)系、函數(shù)、算子、過程等等。狀態(tài)轉(zhuǎn)換規(guī)則也稱為操作,問題的狀態(tài)也只能經(jīng)定義在其上的這種操作而改變。狀態(tài)轉(zhuǎn)換規(guī)則在狀態(tài)圖中表示為邊。在程序中狀態(tài)轉(zhuǎn)換規(guī)則可用數(shù)據(jù)對、條件語句、規(guī)則、函數(shù)、過程等表示。3.狀態(tài)圖表示一個問題的狀態(tài)圖是一個三元組

(S,F,G)

其中S是問題的初始狀態(tài)集合,F是問題的狀態(tài)轉(zhuǎn)換規(guī)則集合,G是問題的目標(biāo)狀態(tài)集合。一個問題的全體狀態(tài)及其關(guān)系就構(gòu)成一個空間,稱為狀態(tài)空間。所以,狀態(tài)圖也稱為狀態(tài)空間圖。

例

3-4

迷宮問題的狀態(tài)圖表示。

S：SoF：｛(So,S4),(S4,So),(S4,S1),(S1,S4),(S1,S2),(S2,S1),(S2,S3),(S3,S2),(S4,S7),(S7,S4),(S4,S5),(S5,S4),(S5,S6),(S6,S5),(S5,S8),(S8,S5),(S8,S9),(S9,S8),(S9,Sg)｝G：SgX1X2X3X８X0X4X7X6X5

例

3-5八數(shù)碼難題的狀態(tài)圖表示。

用向量

A＝(X0,X1,X2,X3,X4,X5,X6,X7,X8)表示,Xi為變量,Xi的值就是所在方格內(nèi)的數(shù)字。于是,向量A就是該問題的狀態(tài)表達(dá)式。我們將棋局

設(shè)初始狀態(tài)和目標(biāo)狀態(tài)分別為

So＝(0,2,8,3,4,5,6,7,1)

Sg＝(0,1,2,3,4,5,6,7,8)

0組規(guī)則：

r1:(X0==0)

(X2==n)

(X0=n)

(X2=0)r2:(X0==0)

(X4==n)

(X0=n)

(X4=0)r3:(X0==0)

(X6==n)

(X0=n)

(X6=0)r4:(X0==0)

(X8==n)

(X0=n)

(X8=0)

1組規(guī)則：

r5:(X1==0)

(X2==n)

(X1=n)

(X2=0)r6:(X1==0)

(X8==n)

(X1=n)

(X8=0)

2組規(guī)則：

r7:(X2==0)

(X1==n)

(X2=n)

(X1=0)r8:(X2==0)

(X3==n)

(X2=n)

(X3=0)r9:(X2==0)

(X0==n)

(X2=n)

(X0=0)…8組規(guī)則:

r22:(X8==0)

(X1==n)

(X8=n)

(X1=0)r23:(X8==0)

(X0==n)

(X8=n)

(X0=0)r24:(X8==0)

(X7==n)

(X8=n)

(X7=0)

于是,八數(shù)碼問題的狀態(tài)圖可表示為

({So},{r1,r2,…,r24},{Sg})

例3-6

梵塔問題。傳說在印度的貝那勒斯的圣廟中,主神梵天做了一個由64個大小不同的金盤組成的“梵塔”,并把它穿在一個寶石桿上。另外,旁邊再插上兩個寶石桿。然后,他要求僧侶們把穿在第一個寶石桿上的64個金盤全部搬到第三個寶石桿上。搬動金盤的規(guī)則是：一次只能搬一個；不允許將較大的盤子放在較小的盤子上。于是,梵天預(yù)言：一旦64個盤子都搬到了3號桿上,世界將在一聲霹靂中毀滅。

盤子的搬動次數(shù)：

264-1＝18446744073709511615

二階梵塔問題

設(shè)有三根寶石桿,在1號桿上穿有A、B兩個金盤,A小于B,A位于B的上面。用二元組(SA,SB)表示問題的狀態(tài),SA表示金盤A所在的桿號,SB表示金盤B所在的桿號,這樣,全部可能的狀態(tài)有9種,可表示如下：

(1,1),(1,2),(1,3)(2,1),(2,2),(2,3)(3,1),(3,2),(3,3)如圖3-9所示。

圖

3-9二階梵塔的全部狀態(tài)

這里的狀態(tài)轉(zhuǎn)換規(guī)則就是金盤的搬動規(guī)則，分別用A(i,j)及B(i,j)表示：A(i,j)表示把A盤從第i號桿移到第j號桿上;B(i,j)表示把B盤從第i號桿移到第j號桿上。經(jīng)分析，共有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)規(guī)則的具體形式應(yīng)是：

IF〈條件〉THENA(i,j)IF〈條件〉THENB(i,j)

這樣由題意,問題的初始狀態(tài)為(1,1),目標(biāo)狀態(tài)為(3,3),則二階梵塔問題可用狀態(tài)圖表示為({(1,1)},{A(1,2),…,B(3,2)},{(3,3)})

由這9種可能的狀態(tài)和12種操作,二階梵塔問題的狀態(tài)空間圖如圖3-10所示。

圖

3-10二階梵塔狀態(tài)空間圖

■教材的微課視頻中有盤子移動過程的動畫

例3-7旅行商問題(Traveling-SalesmanProblem,TSP)。設(shè)有n個互相可直達(dá)的城市,某推銷商準(zhǔn)備從其中的A城出發(fā),周游各城市一遍,最后又回到A城。要求為該推銷商規(guī)劃一條最短的旅行路線。

該問題的狀態(tài)為以A打頭的已訪問過的城市序列:A…

So:A。

Sg:A,…,A。其中“…”為其余n-1個城市的一個序列。

狀態(tài)轉(zhuǎn)換規(guī)則：

規(guī)則1

如果當(dāng)前城市的下一個城市還未去過,則去該城市,并把該城市名排在已去過的城市名序列后端。

規(guī)則2

如果所有城市都去過一次,則從當(dāng)前城市返回A城,把A也添在去過的城市名序列后端。

3.3.2狀態(tài)圖問題求解程序舉例

例3-8下面是一個通用的狀態(tài)圖搜索程序。對于求解的具體問題，只需將其狀態(tài)圖的程序表示并入該程序即可。

/*狀態(tài)圖搜索通用程序*/

DOMAINSstate=<領(lǐng)域說明>%例如:state=symbolDATABASE-mydatabase

open(state,integer)

%用動態(tài)數(shù)據(jù)庫實(shí)現(xiàn)OPEN表

closed(integer,state,integer)%和CLOSED表

res(state)

open1(state,integer)

min(state,integer)

mark(state)

fail_PREDICATESsolvesearch(state,state)resultsearchingstep4(integer,state)step56(integer,state)equal(state,state)repeatresulting(integer)rule(state,state)GOALsolve.CLAUSESsolve:-search(<初始狀態(tài)>,<目標(biāo)狀態(tài)>),result./*例如

solve:-search(st(0,1,2,3,4,5,6,7,8),st(0,2,8,3,4,5,6,7,1)),result.*/search(Begin,End):-%搜索

retractall(_,mydatabase),assert(closed(0,Begin,0)),assert(open(Begin,0)),%步1將初始節(jié)點(diǎn)放入OPEN表

assert(mark(End)),repeat,searching,!.result:- %輸出解

not(fail_),retract(closed(0,_,0)),closed(M,_,_),resulting(M),!.result:-beep,write(″sorrydon'tfindaroad!″).searching:-open(State,Pointer),%步2若OPEN表空,則失敗,退出

retract(open(State,Pointer)),%步3取出OPEN表中第一個節(jié)點(diǎn),

closed(No,_,_),No2=No+1,%給其編號

asserta(closed(No2,State,Pointer)),%放入CLOSED表

!,step4(No2,State).searching:-assert(fail_). %步4若當(dāng)前節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn),則成功

step4(_,