盲目搜索策略及其在實(shí)際中的應(yīng)用研究

1、 商務(wù)學(xué)院課 程 論 文論 文 題 目盲目搜索策略及其在實(shí)際中的應(yīng)用研究專 業(yè) 年 級 08計科24班 課 程 名 稱 人工智能 指 導(dǎo) 教 師 劉文江 學(xué) 生 姓 名 伍鋮煌 學(xué) 號 200818131023 成 績 教務(wù)處制二O一一 年 十 月 十日 盲目搜索策略及其在實(shí)際中的應(yīng)用研究摘要：搜索策略是人工智能研究的主攻方向之一,采用不同的搜索策略在求解問題的過程中也會存在差異.通過對于八數(shù)碼的搜索求解分析,采用盲目搜索中的廣度優(yōu)先搜索算法和寬度搜索算法進(jìn)行實(shí)現(xiàn),將廣度優(yōu)先搜索算法與寬度搜索算法進(jìn)行比較,從而評價這兩種搜索算法的優(yōu)劣性.關(guān)鍵字：搜索策略；深度優(yōu)先；寬度優(yōu)先；八數(shù)碼1 盲目的圖

2、搜索策略圖搜索策略可分為兩種：一種稱為盲目的圖搜索策略，或稱無信息圖搜索策略； 而另一種稱為啟發(fā)式搜索策略，又稱為有信息的圖搜索策略。盲目搜索是不利用問題的有關(guān)信息, 而根據(jù)事先確定好的某種固定的搜索方法進(jìn)行搜索1。最常用的兩種無信息圖搜索策略是寬度優(yōu)先搜索和深度優(yōu)先搜索。1.1 寬度優(yōu)先搜索2它是從根節(jié)點(diǎn)（起始節(jié)點(diǎn)）開始，按層進(jìn)行搜索，也就是按層來擴(kuò)展節(jié)點(diǎn)。所謂按層擴(kuò)展，就是前一層的節(jié)點(diǎn)擴(kuò)展完畢后才進(jìn)行下一層節(jié)點(diǎn)的擴(kuò)展，直到得到目標(biāo)節(jié)點(diǎn)為止。這種搜索方式的優(yōu)點(diǎn)是，只要存在有任何解答的話，它能保證最終找到由起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最短路徑的解，但它的缺點(diǎn)是往往搜索過程很長。1.2 深度優(yōu)

3、先搜索3它是從根節(jié)點(diǎn)開始，首先擴(kuò)展最新產(chǎn)生的節(jié)點(diǎn)，即沿著搜索樹的深度發(fā)展下去，一直到?jīng)]有后繼結(jié)點(diǎn)處時再返回，換一條路徑走下去。就是在搜索樹的每一層始終先只擴(kuò)展一個子節(jié)點(diǎn)，不斷地向縱深前進(jìn)直到不能再前進(jìn)（到達(dá)葉子節(jié)點(diǎn)或受到深度限制）時，才從當(dāng)前節(jié)點(diǎn)返回到上一級節(jié)點(diǎn)，沿另一方向又繼續(xù)前進(jìn)。這種方法的搜索樹是從樹根開始一枝一枝逐漸形成的。由于一個有解的問題樹可能含有無窮分枝，深度優(yōu)先搜索如果誤入無窮分枝（即深度無限），則不可能找到目標(biāo)節(jié)點(diǎn)。為了避免這種情況的出現(xiàn)，在實(shí)施這一方法時，定出一個深度界限，在搜索達(dá)到這一深度界限而且尚未找到目標(biāo)時，即返回重找，所以，深度優(yōu)先搜索策略是不完備的4。另外，應(yīng)用此

4、策略得到的解不一定是最佳解（最短路徑）。2用深度優(yōu)先或?qū)挾葍?yōu)先解決8數(shù)碼(見附錄)【八數(shù)碼問題】5 所謂八數(shù)碼問題是指這樣一種游戲：將分別標(biāo)有數(shù)字1，2，3，8的八塊正方形數(shù)碼牌任意地放在一塊3×3的數(shù)碼盤上。放牌時要求不能重疊。于是，在3×3的數(shù)碼盤上出現(xiàn)了一個空格。現(xiàn)在要求按照每次只能將與空格相鄰的數(shù)碼牌與空格交換的原則，將任意擺放的數(shù)碼盤逐步擺成某種特殊的排列。 解決八數(shù)碼問題的算法很多，盲目是搜索算法如深度優(yōu)先搜索、寬度優(yōu)先搜索等7。 1 八數(shù)碼游戲問題的狀態(tài)空間法表示 1.1 狀態(tài)描述 我們在八數(shù)碼問題中，將號碼牌擺放的位置抽象成一個序列，用來記錄不同碼值的號碼牌

5、的擺放位置。 若用0來表示空格，則 將初始狀態(tài)為：，目標(biāo)狀態(tài)為：的八數(shù)碼問題轉(zhuǎn)換為從開始序列：2,8,3,1,0,4,7,6,5 轉(zhuǎn)換到目標(biāo)序列 1,2,3,8,0,4,7,6,5 的問題。 1.2 操作符描述 對于八數(shù)碼問題中空格的移動問題，我們建立以下操作符: 左移：1；上移：2；下移：3；右移：4 建立下列狀態(tài)轉(zhuǎn)換： 空格右移了一步，所以用4來表示。 1.3 狀態(tài)空間法的數(shù)據(jù)結(jié)構(gòu) struct Node public: int path2;/path0 is the line of the closed box path1 is the direction of /the father

6、node move to this node int layer;/layer is the deep nums of the node in the whole graph string seq; / using the string to achieve the sequence ; 其中string seq 記錄數(shù)碼位置，path2以及int layer。path0表示這個結(jié)點(diǎn)記錄是closed表當(dāng)中的第幾個記錄，path1 是本記錄結(jié)點(diǎn)的父結(jié)點(diǎn)。Layer表示在已搜索的樹當(dāng)中是第幾層。 空格移動規(guī)則如表1所示。 2 八數(shù)碼游戲問題的盲目搜索技術(shù) 2.1 寬度優(yōu)先搜索 2.1.1 寬度優(yōu)

7、先搜索的搜索步驟 把起始節(jié)點(diǎn)放到 OPEN 表中(如果該起始節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn)，則得到解) 如果 OPEN 是個空表，則無解，失敗退出；否則繼續(xù)下一步 把第一個節(jié)點(diǎn)(記作節(jié)點(diǎn) n )從 OPEN 表移出，并把它放入 CLOSED 的已擴(kuò)展節(jié)點(diǎn)表中 擴(kuò)展節(jié)點(diǎn) n 。如果沒有后繼節(jié)點(diǎn)，則轉(zhuǎn)向第步 把 n 的所有后繼節(jié)點(diǎn)放到OPEN表的末端，并提供從這些后繼節(jié)點(diǎn)回到 n 的指針 如果 n 的任一個后繼節(jié)點(diǎn)是個目標(biāo)節(jié)點(diǎn)，則找到一個解（反向追蹤得到從目標(biāo)節(jié)點(diǎn)到起始節(jié)點(diǎn)的路徑），成功退出，否則轉(zhuǎn)向第步 2.1.2 寬度優(yōu)先的成員數(shù)據(jù)結(jié)構(gòu) string InitialString,ResultString;

8、初始序列以及結(jié)果序列 OPEN表：SeqQueue ws_open (特別說明，這里的SeqQueue 是我自己實(shí)現(xiàn)的隊列模板，因為想試下有沒有用，就放到程序里試了一下) 存放待擴(kuò)展的節(jié)點(diǎn)，從數(shù)據(jù)結(jié)構(gòu)上來說，它是一個先進(jìn)先出的隊列 CLOSED 表：vector ws_closed; （堆棧用vector實(shí)現(xiàn)） 是存放已被擴(kuò)展過的節(jié)點(diǎn)（包括有后繼節(jié)點(diǎn)的非端節(jié)點(diǎn)和無后繼節(jié)點(diǎn)的端節(jié)點(diǎn)） int WsExpand(Node node,int No) 寬度優(yōu)先搜索的擴(kuò)展結(jié)點(diǎn)函數(shù) 輸入：待擴(kuò)展結(jié)點(diǎn) node；父結(jié)點(diǎn)（即node結(jié)點(diǎn)）在closed表的編號No 結(jié)果：擴(kuò)展上下左右四個方向的結(jié)點(diǎn)，并存入op

9、en表。如果生成結(jié)點(diǎn)中有目標(biāo)結(jié)點(diǎn)，則返回最后一步移動的方向。 void swap(char &a,char &b ) 字符交換函數(shù) 輸入：字符a，字符b 結(jié)果：在序列中，將a和b的位置交換 （深度和寬度合用） void WideSearch() 輸入：無 結(jié)果：對成員初始序列到結(jié)果序列進(jìn)行寬度優(yōu)先搜索，得出搜索過程。 bool isInOpenOrClosed(Node s) 輸入：待測結(jié)點(diǎn)s 結(jié)果：返回帶測結(jié)點(diǎn)在open或closed表中的真值 2.2 深度優(yōu)先搜索 2.2.1 深度優(yōu)先搜索的搜索過程 把起始節(jié)點(diǎn) S 放到未擴(kuò)展節(jié)點(diǎn)的 OPEN 表（此時OPEN表是一個堆棧，

10、后進(jìn)先出）中。如果此節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn)，則得到解 如果 OPEN 為一空表，則無解、失敗退出 把第一個節(jié)點(diǎn)(記作節(jié)點(diǎn) n )從 OPEN 表移到 CLOSED 表 如果節(jié)點(diǎn) n 的深度等于最大深度，則轉(zhuǎn)向 擴(kuò)展節(jié)點(diǎn) n ，產(chǎn)生其全部后繼節(jié)點(diǎn)，并把它們放入 OPEN 表的前頭。如果沒有后繼節(jié)點(diǎn)，則轉(zhuǎn)向 如果后繼節(jié)點(diǎn)中有任一個節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)，則求得一個解（反向追蹤從目標(biāo)節(jié)點(diǎn)到起始節(jié)點(diǎn)的路徑），成功退出；否則，轉(zhuǎn)向 2.2.2 深度優(yōu)先搜索的成員數(shù)據(jù)結(jié)構(gòu) string InitialString,ResultString; 初始序列以及結(jié)果序列 OPEN表： vector ds_open 在深度優(yōu)先搜

11、索中，open表式一個后進(jìn)先出的堆棧，這里用vector來實(shí)現(xiàn)。 CLOSED 表：vector ds_closed 在寬度優(yōu)先搜索中，closed表用vector來實(shí)現(xiàn)，是存放已被擴(kuò)展過的節(jié)點(diǎn)（包括有后繼節(jié)點(diǎn)的非端節(jié)點(diǎn)和無后繼節(jié)點(diǎn)的端節(jié)點(diǎn)） int DsExpand(Node node,int No) 深度優(yōu)先搜索的擴(kuò)展結(jié)點(diǎn)函數(shù) 輸入：待擴(kuò)展結(jié)點(diǎn) node；父結(jié)點(diǎn)（即node結(jié)點(diǎn)）在closed表的編號No 結(jié)果：擴(kuò)展上下左右四個方向的結(jié)點(diǎn)，并存入open表。如果生成結(jié)點(diǎn)中有目標(biāo)結(jié)點(diǎn)，則返回最后一步移動的方向 void swap(char &a,char &b ) 字符交換函

12、數(shù) 輸入：字符a，字符b 結(jié)果：在序列中，將a和b的位置交換 （深度和寬度合用） void DeepSearch() 輸入：無 結(jié)果：對成員初始序列到結(jié)果序列進(jìn)行深度優(yōu)先搜索，得出搜索過程。 bool isInDSOpenOrClosed(Node s) 輸入：待測結(jié)點(diǎn)s 結(jié)果：返回帶測結(jié)點(diǎn)在open或closed表中的真值 3 例子及分析 初始狀態(tài)通過目標(biāo)狀態(tài)倒推 3.1.1 寬度優(yōu)先搜索 程序運(yùn)行如圖所示。 如圖所示，寬度優(yōu)先搜索共走了4步，所用時間約為0.65秒，獲得的解為全局最優(yōu)解。 3.1.2 深度優(yōu)先搜索 而深度優(yōu)先搜索結(jié)果和深度界限有關(guān)，所以當(dāng)深度界限分別為3,5,20時，結(jié)果如

13、下： 當(dāng)深度界限為3時，如圖所示。 圖當(dāng)深度界限為5時，如圖所示。 圖走了4步，耗費(fèi)時間0.027s 當(dāng)深度界限為20時如圖所示。 走了20步，所用時間為4.65s 4 結(jié)束語 從例子的結(jié)果來看，寬度優(yōu)先搜索方法能夠保證在搜索樹中找到一條通向目標(biāo)節(jié)點(diǎn)的最短途徑（所用操作符最少），只要結(jié)點(diǎn)間可以到達(dá)，就一定可以找到一個最優(yōu)解。深度優(yōu)先搜索具有深度界限，當(dāng)搜索深度達(dá)到深度界限時，停止搜索。所以，深度優(yōu)先搜索有可能會得不到結(jié)果，是一種不安全的搜索方法。但是當(dāng)結(jié)果在搜索界限內(nèi)時，可以快速的得到結(jié)果，時間效率高。故對于深度優(yōu)先搜索，如何去定義一個較好的搜索界限，是下一步需要繼續(xù)改進(jìn)的方面。3深度優(yōu)先搜索

14、和寬度優(yōu)先搜索的優(yōu)缺點(diǎn)6(1)寬度優(yōu)先搜索在有解的情況下可以找到最優(yōu)解，但深度優(yōu)先搜索不同，它不保證第一次碰到某個狀態(tài)時，找到的就是到這個狀態(tài)的最短路徑，而且也不保證一定能找到解。(2)寬度優(yōu)先可以保證找到解，但是如果存在一個不利的分支（各個狀態(tài)相對很多的情況），那么會非常耗時。(3) 如果要搜索具有很多分支的空間，那么深度優(yōu)先搜索的效率更高，因為它不必把給定層的所有結(jié)點(diǎn)保存到open列表中(4)選擇深度優(yōu)先搜索還是寬度優(yōu)先搜索的最佳答案是仔細(xì)分析問題空間并向這個領(lǐng)域的專家咨詢。例如，對于國際象棋來說，寬度優(yōu)先搜索就是不可能的。在更簡單的游戲中，寬度優(yōu)先搜索不僅是可能的，而且可能是避免迷失的惟

15、一方法。附錄：利用寬度優(yōu)先算法解決8數(shù)碼（源代碼）#include<stdio.h>#include<math.h>#include<stdlib.h>#define max_layer 5 /*最大擴(kuò)展層數(shù)宏定義*/#define true 1#define fail 0#define null 0struct link int data33;/*八數(shù)碼狀態(tài)*/ int layer; /*該節(jié)點(diǎn)的層數(shù)*/ struct link *next; struct link *prior; ;struct link *close_head; /*Close表的根節(jié)

16、點(diǎn)*/struct link *open_head;/*Open表的根節(jié)點(diǎn)*/*/* 函數(shù)名稱：output()*/* 功能說明：輸出指針P指向的節(jié)點(diǎn)的數(shù)據(jù) */*/void output(struct link *p) int i,j; while(p!=NULL) for(i=0;i<3;i+) /*行輸出控制*/ for(j=0;j<3;j+) /*列輸出控制*/ printf("%d ",p->dataij);/*輸出i行j列上的數(shù)據(jù)*/ printf("n"); /*每輸出一行數(shù)據(jù)，回車換行*/ printf("-n

17、"); /*輸出一條橫線以區(qū)分屏幕上其他節(jié)點(diǎn)數(shù)據(jù)*/ p-; /* 函數(shù)名稱：compare*/* 功能說明：將指針Operate指向的節(jié)點(diǎn)中的數(shù)據(jù)與二維數(shù)組dest中的數(shù)據(jù)進(jìn)行比較*/int compare(struct link *q,int dest33) int i,j,count=0; for(i=0;i<3;i+) /*行比較控制*/ for(j=0;j<3;j+) /*列比較控制*/if(q->dataij=destij) /*比較i行j列上的數(shù)據(jù)*/count+; /*計數(shù)器加一*/else /*只要發(fā)現(xiàn)有一個數(shù)據(jù)不相等*/*即返回 fail，宣告比

18、較失敗*/ j=3; /*強(qiáng)制推出for循環(huán)*/ i=3; /*強(qiáng)制推出for循環(huán)*/ return 0; if(count=9)/*相等的數(shù)據(jù)的個數(shù)與維數(shù)平方相等*/ return 1; /*表示數(shù)據(jù)都對應(yīng)相等，返回true */* 函數(shù)名稱：eight()*/ /* 功能說明：通過深度擴(kuò)展的方式找出八數(shù)碼問題從初始狀態(tài)到目標(biāo)狀態(tài)的路徑 */ int eight(struct link *open_head,int dest33) int i,j,zero_x,zero_y; /*0的橫坐標(biāo)，0的縱坐標(biāo)*/ struct link *new_point; /*處理open表的一個臨時指針*/

19、 struct link *open_point=*open_head;/*open表操作指針1*/ struct link *close_point; while(open_link_point!=NULL) close_point=open_point; open_point->prior->next=NULL; open_point-; if(compare(close_point,dest)=1) printf("find solution"); output(close_point); return 1; else if(close_point->

20、;layer>max_layer) close_point->next=*open_point; close_point+; else for(i=0;i<3;i+)/*獲取0的坐標(biāo)*/ for(j=0;j<3;j+) if(close_point->dataij=0) /*data or dest*/ zero_x=i;/*橫坐標(biāo)*/ zero_y=j;/*縱坐標(biāo)*/ j=3; /*強(qiáng)制退出循環(huán)*/ i=3; /*強(qiáng)制退出循環(huán)*/ if(zero_x-1)>=0)/*往上移*/ /*申請內(nèi)存空間*/ new_point=(struct link *)mal

21、loc(sizeof(struct link); for(i=0;i<3;i+)/*對新擴(kuò)展的節(jié)點(diǎn)賦值*/ for(j=0;j<3;j+) new_point->dataij=close_point->dataij; new_point->datazero_xzero_y=new_point->datazero_x-1zero_y; new_point->datazero_x-1zero_y=0; open_point->next=*new_point; open_point+; if(zero_x+1)<3)/*往下移*/ /*申請內(nèi)存空

22、間*/ new_point=(struct link *)malloc(sizeof(struct link); for(i=0;i<3;i+)/*對新擴(kuò)展的節(jié)點(diǎn)賦值*/ for(j=0;j<3;j+) new_point->dataij=close_point->dataij; new_point->datazero_xzero_y=new_point->datazero_x+1zero_y; new_point->datazero_x+1zero_y=0; open_point->next=*new_point; open_point+; i

23、f(zero_y-1)>=0)/*0往右移*/ /*申請內(nèi)存空間*/ new_point=(struct link *)malloc(sizeof(struct link); for(i=0;i<3;i+)/*對新擴(kuò)展的節(jié)點(diǎn)賦值*/ for(j=0;j<3;j+) new_point->dataij=close_point->dataij; new_point->datazero_xzero_y=new_point->datazero_xzero_y-1; new_point->datazero_xzero_y-1=0; open_point-&

24、gt;next=*new_point; open_point+; if(zero_y+1)<3)/*0往左移*/ /*申請內(nèi)存空間*/ new_point=(struct link *)malloc(sizeof(struct link); for(i=0;i<3;i+)/*對新擴(kuò)展的節(jié)點(diǎn)賦值*/ for(j=0;j<3;j+) new_point->dataij=close_point->dataij; new_point->datazero_xzero_y=new_point->datazero_xzero_y+1; new_point->d

25、atazero_xzero_y+1=0; open_point->next=*new_point; open_point+; if(open_point=NULL) printf("no solution"); /* 函數(shù)名稱：main*/ void main() int i,j; int destination33; /*二維數(shù)組，用以存放目標(biāo)狀態(tài)*/ struct link *open_head=(struct link *)malloc(sizeof(struct link); /*申請一個節(jié)點(diǎn)空間* printf("The max dimention is 3"); /*提醒用戶八數(shù)碼的維數(shù)大小*/ printf("Please input the initial state of <eight