盲目搜索策略及其在實際中的應用研究

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

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

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

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

5、的擺放位置。 若用0來表示空格，則 將初始狀態(tài)為：，目標狀態(tài)為：的八數碼問題轉換為從開始序列：2,8,3,1,0,4,7,6,5 轉換到目標序列 1,2,3,8,0,4,7,6,5 的問題。 1.2 操作符描述 對于八數碼問題中空格的移動問題，我們建立以下操作符: 左移：1；上移：2；下移：3；右移：4 建立下列狀態(tài)轉換： 空格右移了一步，所以用4來表示。 1.3 狀態(tài)空間法的數據結構 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 記錄數碼位置，path2以及int layer。path0表示這個結點記錄是closed表當中的第幾個記錄，path1 是本記錄結點的父結點。Layer表示在已搜索的樹當中是第幾層。 空格移動規(guī)則如表1所示。 2 八數碼游戲問題的盲目搜索技術 2.1 寬度優(yōu)先搜索 2.1.1 寬度優(yōu)

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

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

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

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

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

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

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

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

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

16、點*/struct link *open_head;/*Open表的根節(jié)點*/*/* 函數名稱：output()*/* 功能說明：輸出指針P指向的節(jié)點的數據 */*/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列上的數據*/ printf("n"); /*每輸出一行數據，回車換行*/ printf("-n

17、"); /*輸出一條橫線以區(qū)分屏幕上其他節(jié)點數據*/ p-; /* 函數名稱：compare*/* 功能說明：將指針Operate指向的節(jié)點中的數據與二維數組dest中的數據進行比較*/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列上的數據*/count+; /*計數器加一*/else /*只要發(fā)現有一個數據不相等*/*即返回 fail，宣告比

18、較失敗*/ j=3; /*強制推出for循環(huán)*/ i=3; /*強制推出for循環(huán)*/ return 0; if(count=9)/*相等的數據的個數與維數平方相等*/ return 1; /*表示數據都對應相等，返回true */* 函數名稱：eight()*/ /* 功能說明：通過深度擴展的方式找出八數碼問題從初始狀態(tài)到目標狀態(tài)的路徑 */ int eight(struct link *open_head,int dest33) int i,j,zero_x,zero_y; /*0的橫坐標，0的縱坐標*/ 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的坐標*/ for(j=0;j<3;j+) if(close_point->dataij=0) /*data or dest*/ zero_x=i;/*橫坐標*/ zero_y=j;/*縱坐標*/ j=3; /*強制退出循環(huán)*/ i=3; /*強制退出循環(huán)*/ if(zero_x-1)>=0)/*往上移*/ /*申請內存空間*/ new_point=(struct link *)mal

21、loc(sizeof(struct link); for(i=0;i<3;i+)/*對新擴展的節(jié)點賦值*/ 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)/*往下移*/ /*申請內存空

22、間*/ new_point=(struct link *)malloc(sizeof(struct link); for(i=0;i<3;i+)/*對新擴展的節(jié)點賦值*/ 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往右移*/ /*申請內存空間*/ new_point=(struct link *)malloc(sizeof(struct link); for(i=0;i<3;i+)/*對新擴展的節(jié)點賦值*/ 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往左移*/ /*申請內存空間*/ new_point=(struct link *)malloc(sizeof(struct link); for(i=0;i<3;i+)/*對新擴展的節(jié)點賦值*/ 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"); /* 函數名稱：main*/ void main() int i,j; int destination33; /*二維數組，用以存放目標狀態(tài)*/ struct link *open_head=(struct link *)malloc(sizeof(struct link); /*申請一個節(jié)點空間* printf("The max dimention is 3"); /*提醒用戶八數碼的維數大小*/ printf("Please input the initial state of <eight