實(shí)驗(yàn)5樹(shù)的深度搜索

1、實(shí)驗(yàn)5樹(shù)的深度搜索一實(shí)驗(yàn)原理1、定義在此搜索中，首先擴(kuò)展最新產(chǎn)生的（即最深的）節(jié)點(diǎn)。深度相等的節(jié)點(diǎn)可以任 意排列。這種盲目（無(wú)信息）搜索叫做深度優(yōu)先搜索（depth-first search）。2、特點(diǎn)首先，擴(kuò)展最深的節(jié)點(diǎn)的結(jié)果使得搜索沿著狀態(tài)空間某條單一的路徑從起始 節(jié)點(diǎn)向下進(jìn)行下去；只有當(dāng)搜索到達(dá)一個(gè)沒(méi)有后裔的狀態(tài)時(shí)，它才考慮另一條替 代的路徑。3、深度界限為了避免考慮太長(zhǎng)的路徑（防止搜索過(guò)程沿著無(wú)益的路徑擴(kuò)展下去），往往給 出一個(gè)節(jié)點(diǎn)擴(kuò)展的最大深度橐深度界限。任何節(jié)點(diǎn)如果達(dá)到了深度界限，那么都 將把它們作為沒(méi)有后繼節(jié)點(diǎn)處理。二實(shí)驗(yàn)?zāi)康恼莆沼嘘P(guān)樹(shù)的深度優(yōu)先搜索和圖的搜索算法三實(shí)驗(yàn)內(nèi)容與結(jié)果

2、 四實(shí)驗(yàn)心得5.1樹(shù)的深度搜索深度搜索在人工智能領(lǐng)域，經(jīng)常使用到搜索技術(shù)。常見(jiàn)的搜索方式有深度優(yōu)先搜索與寬度 優(yōu)先搜索兩種。問(wèn)題：樹(shù)的搜索樹(shù)在計(jì)算機(jī)科學(xué)領(lǐng)域是一種數(shù)據(jù)結(jié)構(gòu)的概念。例如下圖就表示一棵樹(shù)：樹(shù)中的字母表示樹(shù)的節(jié)點(diǎn)，節(jié)點(diǎn)a叫做樹(shù)的根，節(jié)點(diǎn)b、c、d叫做節(jié)點(diǎn)a的子節(jié) 點(diǎn)。b、c、d又分別有它們的子節(jié)點(diǎn)。樹(shù)的搜索的意思就是要找到一條連接兩個(gè) 節(jié)點(diǎn)的路徑，例如連接節(jié)點(diǎn)a與g的路徑是a-c-g。上面的例子是顯而易見(jiàn)的，不過(guò)要想讓計(jì)算機(jī)也能夠找到這條路徑，就必須編程 解決。下面介紹它的Prolog程序的編法。樹(shù)的表達(dá) 首先我們需要把上面的樹(shù)翻譯為Prolog的語(yǔ)言，這不難辦到，只要使用事實(shí)就可以

3、輕易地搞定：FILE18.PRO15:1InsertIndentsub(a,b). sub(a,c). sub (a, d). sub (b, e). sub(c,f). sub (c, g). sub(d,i). sub (d,h).上面的每一條事實(shí)對(duì)應(yīng)樹(shù)中的一條樹(shù)枝。樹(shù)的搜索先給出搜索程序：(事實(shí)框中輸入)route(X,X,).route(X,Y,L):-sub (X, Z) , 4首先找到工的一個(gè)子節(jié)點(diǎn)碼route (Z,Y,L1),板在尋找從Z到目的節(jié)點(diǎn)Y的路由L1,L = Z| L1.專最終的路由表為Z加上L1.樹(shù)的深度搜索完整源程序:測(cè)試用例及結(jié)果(目標(biāo)框中輸入): route(

4、a,f,L).L = c,f;1 Solution route(a,h,L)L= d,h1 Solution我們可以看出，上面的route/3是使用遞歸的方法書(shū)寫(xiě)的。前兩個(gè)參數(shù)為要 考慮的節(jié)點(diǎn)，第三個(gè)參數(shù)儲(chǔ)存找出來(lái)的路由表。route的第一個(gè)子句為邊界條件； 第二個(gè)子句遞歸調(diào)用route/3本身。在這個(gè)程序中，當(dāng)找到X的一個(gè)子節(jié)點(diǎn)后，系統(tǒng)就開(kāi)始尋找這個(gè)子節(jié)點(diǎn)的子 節(jié)點(diǎn)，一直到找到目標(biāo)，搜索就成功地結(jié)束，而如果某個(gè)節(jié)點(diǎn)沒(méi)有子節(jié)點(diǎn)，就會(huì) 引起回溯，去尋找它的父節(jié)點(diǎn)的另一個(gè)子節(jié)點(diǎn)。這種搜索方式就叫做深度優(yōu)先搜 索。由于Prolog內(nèi)建的自動(dòng)回溯功能，使得我們可以非常容易地實(shí)現(xiàn)深度搜索。 所以在一般情

5、況下，通常使用深度搜索，而只在特殊的情況下才使用寬度搜索。5.2圖的搜索-樹(shù)的搜索拓展有向圖如果在前面的事實(shí)中增加一條sub(d,g)，那么g既是d的子節(jié)點(diǎn)，又是c 得子節(jié)點(diǎn)。我們把這樣的樹(shù)叫做有向圖。有向圖的搜索與樹(shù)的搜索過(guò)程是相同的。圖的搜索圖是最復(fù)雜的數(shù)據(jù)結(jié)構(gòu)了。在圖中不分什么父節(jié)點(diǎn)與子節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)都與 一定數(shù)量的其它節(jié)點(diǎn)相連，一條連接叫做一條路經(jīng)。每條路徑都有不同的權(quán)值， 從某個(gè)節(jié)點(diǎn)到另外的節(jié)點(diǎn)所走過(guò)的路徑就叫做這兩個(gè)節(jié)點(diǎn)之間的通路。圖的搜索 的目的就是要找出這些通路，有時(shí)還需要所有的權(quán)值加起來(lái)最小(后面實(shí)驗(yàn)將會(huì) 涉及)。圖的最典型的例子就是地理上的地圖了，每個(gè)城市相當(dāng)于一個(gè)節(jié)點(diǎn)，城

6、 市之間的道路就是路徑了。搜索工作就是一個(gè)旅游向?qū)?，它能夠幫助你決定到達(dá) 另外一個(gè)城市所需的路徑。圖的搜索和樹(shù)的搜索是類似的，不過(guò)由于圖中存在著環(huán)路，所以如果不加以 控制，而直接使用前面的程序就會(huì)導(dǎo)致永遠(yuǎn)不會(huì)結(jié)束。（此處及以下的解決搜索 主要是針對(duì)無(wú)向圖解決環(huán)路的辦法也很簡(jiǎn)單：使用一個(gè)列表儲(chǔ)存已經(jīng)考慮過(guò)的節(jié)點(diǎn)，如果正在 考慮的節(jié)點(diǎn)已經(jīng)在此列表中就表明沒(méi)有必要再搜索此節(jié)點(diǎn)了。卜面是完整的Prolog程序。上圖為源程序及程序注解說(shuō)明。源程序備注說(shuō)明：謂詞c/2定義了圖的信息，你也可以自己根據(jù)事實(shí)給出的信息在紙上畫(huà)畫(huà)此有向 圖。findroad/4findroad/4為尋找路由的謂詞，它的調(diào)用方式為

7、findroad(a,e,X)。findroad(X,X,L,L).第一個(gè)子句定義了邊界條件，它用來(lái)把第三個(gè)參數(shù)傳給第四個(gè)參數(shù)，第 三個(gè)參數(shù)為臨時(shí)的路由表，第四個(gè)參數(shù)為最終的路由表。findroad(X,Y,L,L1)：- % L 為儲(chǔ)存的路由表。connect(X,Z),not(member(Z,L),% X所連接的節(jié)點(diǎn)Z不在已經(jīng)儲(chǔ)存的路由表中。findroad(Z,Y,Z|L,L1).第二個(gè)子句先找出與X相連的節(jié)點(diǎn)Z，然后判斷Z是否在臨時(shí)的路由表 中，如果不在，就把Z加入到臨時(shí)路由表中，并且尋找從Z到Y(jié)的路由。下面是運(yùn)行結(jié)果：findroad(a,e,L),write(L),nl,fail

8、e,be,f,b e,b,ce,b,a,ce,f,b,a,ce,b,d,a,ce,f,b,d,a,ce,b,a,de,f,b,a,de,b,c,a,de,f,b,c,a,de,b,de,f,b,dNo solutionsfindroad(a,f, 口，L),write(L),nl,failf,e,bf,bf,e,b,cf,b,cf,e,b,a,cf,b,a,cf,e,b,d,a,cf,b,d,a,cf,e,b,a,df,b,a,df,e,b,c,a,df,b,c,a,df,e,b,df,b,dNo solutions 對(duì)于結(jié)果正確與否，同學(xué)們可以通過(guò)參照下圖自己來(lái)驗(yàn)證。這里有兩點(diǎn)需要說(shuō)明:第一，我們找出來(lái)的路由表是倒過(guò)來(lái)的，不過(guò)這并不影響結(jié)果；第二，這個(gè)程序找出了所有的通路，但是并不能判斷哪條通路是最短通路，另 外我們還沒(méi)有加入路徑的權(quán)值。作業(yè)要求：實(shí)驗(yàn)結(jié)果均要求保存在