深度與廣度優(yōu)先搜索：迷宮問題

1、程序實踐報告（2010）數(shù)據結構課程設計報告題目：深度與廣度優(yōu)先搜索-迷宮問題 專業(yè)計算機科學與技術學生姓名李柏班級B計算機115學號1110704512指導教師鞏 永 旺完成日期2013年1月11日1目 錄1 簡介12算法說明13測試結果34分析與探討65小結8附 錄10附錄1 源程序清單101 迷宮問題1 簡介1、圖的存儲結構 圖的存儲結構又稱圖的表示，其最常用的方法是鄰接矩陣和鄰接表。無論采用什么存儲方式，其目標總是相同的，既不僅要存儲圖中各個頂點的信息，同時還要存儲頂點之間的所有關系。2、圖的遍歷圖的遍歷就是從指定的某個頂點（稱其為初始點）出發(fā)，按照一定的搜索方法對圖中的所有頂點各做一

2、次訪問過程。根據搜索方法不同，遍歷一般分為深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷。本實驗中用到的是廣度優(yōu)先搜索遍歷。即首先訪問初始點vi，并將其標記為已訪問過，接著訪問vi的所有未被訪問過的鄰接點，順序任意，并均標記為已訪問過，以此類推，直到圖中所有和初始點vi有路徑相通的頂點都被訪問過為止。鑒于廣度優(yōu)先搜索是將所有路徑同時按照順序遍歷，直到遍歷出迷宮出口，生成的路徑為最短路徑。因此我們采用了廣度優(yōu)先搜索。無論是深度優(yōu)先搜索還是廣度優(yōu)先搜索，其本質都是將圖的二維頂點結構線性化的過程，并將當前頂點相鄰的未被訪問的頂點作為下一個頂點。廣度優(yōu)先搜索采用隊列作為數(shù)據結構。本實驗的目的是設計一個程序，實現(xiàn)手

3、動或者自動生成一個n×m矩陣的迷宮，尋找一條從入口點到出口點的通路。具體實驗內容如下：選擇手動或者自動生成一個n×m的迷宮，將迷宮的左上角作入口，右下角作出口，設“0”為通路，“1”為墻，即無法穿越。假設一只老鼠從起點出發(fā)，目的為右下角終點，可向“上、下、左、右、左上、左下、右上、右下”8個方向行走。如果迷宮可以走通，則用“”代表“1”，用“”代表“0”，用“”代表行走迷宮的路徑。輸出迷宮原型圖、迷宮路線圖以及迷宮行走路徑。如果迷宮為死迷宮，則只輸出迷宮原型圖。2算法說明 迷宮中存在通路和障礙，為了方便迷宮的創(chuàng)建，可用0表示通路，用1表示障礙，這樣迷宮就可以用0、1矩陣來描

4、述。設置迷宮的長為n、寬為m，范圍為49×49，用int mazeN+2M+2來表示，這樣相當于在迷宮外層包了一層1，即防止搜索路徑時跳出迷宮。（1）手動生成迷宮void hand_maze(int m,int n) /手動生成迷宮int i,j; for(i=0;i<m;i+) for(j=0;j<n;j+)cin>>mazeij; （2） 自動生成迷宮void automatic_maze(int m,int n) /自動生成迷宮int i,j;for(i=0;i<m;i+)for(j=0;j<n;j+)mazeij=rand()%2; /隨機

5、生成0、1maze00=0; /將開始和結束位置強制為0，保證有可能出來迷宮mazem-1n-1=0;2、迷宮路徑的搜索在生成的0、1矩陣迷宮中，首先從迷宮的入口開始，如果該位置就是迷宮出口，則已經找到了一條路徑，搜索工作結束。否則搜索其北（-1，0），東北（-1，1），東（0,1），東南（1,1），南（1,0），西南（1，-1），西（0，-1），西北（-1，-1）8個方向位，是否是障礙，若不是障礙，就移動到該位置，然后再從該位置開始搜索通往出口的路徑；若是障礙就選擇另一個相鄰的位置，并從它開始搜索路徑。為防止搜索重復出現(xiàn)，則將已搜索過的位置標記為2，同時保留搜索痕跡，在考慮進入下一個位置搜索

6、之前，將當前位置保存在一個隊列中，如果所有相鄰的非障礙位置均被搜索過，且未找到通往出口的路徑，則表明不存在從入口到出口的路徑。這實現(xiàn)的是廣度優(yōu)先遍歷的算法，如果找到路徑，則為最短路徑。逆序輸出路徑，將已輸出的路徑標記為3。 實驗數(shù)據如下： 表3.1 方向move的偏移量Name dirMovedir.vertMovedir.horizN0-10NE1-11E201SE311S410SW51-1W60-1NW60-13測試結果 圖1 圖2 圖3 圖4 圖 5 圖6 圖7 4分析與探討首先明確題目中的已知條件：（1） 迷宮是一個8*8大小的矩陣。（2） 從迷宮的左上角進入，右下角為迷宮的終點。（3

7、） mazeij=0代表第i+1行第j+1列的點是通路；mazeij=1代表該點是墻，無法通行。（4） 迷宮有兩種生成方式：手工設定和自動生成。（5） 當老鼠處于迷宮中某一點的位置上，它可以向8個方向前進，分別是：“上、下、左、右、左上、左下、右上、右下”8個方向。（6） 要實現(xiàn)這個程序，首先要考慮如何表示這個迷宮。在實例程序中使用二維數(shù)組mazeN+2N+2來表示這個迷宮，其中N為迷宮的行、列數(shù)。當值為“0”時表示該點是通路，當值為“1”時表示該點是墻。老鼠在迷宮的位置在任何時候都可以由行號row和列號cool表示。（7） 為什么指定: mazeN+2N+2來表示迷宮，而不是使用mazeNN

8、來表示迷宮？原因是當老鼠跑到了迷宮的邊界點時就有可能跳出迷宮，而使用mazeN+2N+2就可以把迷宮的外邊再包一層“1”，這樣就能阻止老鼠走出格。（8） 老鼠在每一點都有8種方向可以走，分別是：North，NorthEast，East，SouthEast,South,SouthWest,West，NorthWest?？梢杂脭?shù)組move8來表示每一個方向上的橫縱坐標的偏移量，見表3.1。根據這個數(shù)組，就很容易計算出沿某個方向行走后的下一個點的坐標。 方向move的偏移量Name dirMovedir.vertMovedir.horizN0-10NE1-11E201SE311S410SW51-1W

9、60-1NW60-1迷宮問題可以用深度優(yōu)先搜索方法實現(xiàn)。當老鼠在迷宮中移動的時候，可能會有許多種移動選擇方向。程序需要記錄并用棧來保存當前點的坐標，然后任意選擇一個方向進行移動。由于應用棧保存了當前通道上各點的坐標，所以當在當前各方向上都走不通時可以返回上一個點，然后選擇另一個方向前進。 可定義element結構用于存儲每一步的橫縱坐標和方向。 typedef struct short int row; short int col; short int dir;element;Element stackMAX _STACK_SIZE;根據表3.1可推算出每次移動后的坐標。設當前的坐標是（row

10、,col）,移動的方向是dir，移動后的點是next,則有next_row=row+movedir.vert;next_col=col+movedir.horiz; 可用另一個二維數(shù)組markN+2來記錄哪些點已經被訪問過。當經過點mazerowcol時，相應地將markrowcol的值從0置為1。 本程序支持自動生成迷宮。利用random（2）函數(shù)可隨機產生0或1，來支持迷宮的自動生成。注意mazeNN和maze11一定要等于0，因為他們分別是起點和終點。 如果找到了一條走出迷宮的路徑，則需要在屏幕中打印出如圖3.5所示格式的信息。這里要用到graphics.h即TC中的圖形庫（注意：本程序

11、是TC上的實現(xiàn)，而VC+有自己的圖形庫，所以使用VC+編譯提示錯誤）。針對圖3.5，可使用circle（）函數(shù)畫圓，outtexttxy（）函數(shù)標記文字，并用line（）函數(shù)來劃線。 程序的主要函數(shù)如下： 函數(shù)void add（int*top,element item），將當前步的信息item壓入到作為全局變量的棧stack（棧頂為top）中。 函數(shù)element delete（int * top），返回stack中棧頂?shù)脑亍?函數(shù)void path（void），采用深度優(yōu)先搜索算法，首先取出棧頂元素作為當前點選擇一個方向前進到下一個點（如果能走得話）；然后，將下一個點壓入棧，并將二維數(shù)組m

12、ark中對應的值改為1，表示該點已經走到了。反復執(zhí)行上面兩步，當走到一個點不能再走下去了（已經嘗試了各個方向并失?。⑶疫@個點不是終點，則這個點的上一個點會從棧中被跑拋出，從而“回朔”到上一點；當遇到終點時，程序結束，找到一條路徑；當在程序循環(huán)過程中遇到棧為空，則說明該迷宮根本無法走到終點。5小結為期一個星期的數(shù)據結構課程設計快結束了，這使我對深度和廣度優(yōu)先搜索有了更加深刻的理解和認識。我們團隊負責的迷宮問題的課程設計就是充分的利用深度和廣度優(yōu)先搜索的有關知識，主要運用的是廣度優(yōu)先搜索遍歷。（1）深度優(yōu)先搜索遍歷：深度優(yōu)先搜索是一個遞歸過程。首先訪問一個頂點Vi并將其標記為已訪問過，然后從V

13、i的任意一個未被訪問的鄰接點出發(fā)進行深度優(yōu)先搜索遍歷。如此執(zhí)行，當Vi的所有鄰接點均被訪問過時，則退回到上一個頂點Vk，從Vk的另一未被訪問過的鄰接點出發(fā)進行深度優(yōu)先搜索遍歷。如此執(zhí)行，直到退回到初始點并且沒有未被訪問過的鄰接點為止。 （2）廣度優(yōu)先搜索遍歷：廣度優(yōu)先搜索過程為：首先訪問初始點Vi，并將其標記為已訪問過，接著訪問Vi的所有未被訪問過的鄰接點，其訪問順序可以任意，假定依次為Vi1、Vi2，Vin，并標記為已訪問過，然后按照Vi1、Vi2，Vin的次序訪問每一個頂點的所有未被訪問過的鄰接點，并均標記為已訪問過，依次類推，直到圖中所有和初始點Vi有路徑相通的頂點都被訪問過為止。在設計

14、迷宮問題時要考慮使用二維數(shù)組，在數(shù)組中我們選擇mazeN+2N+2來表示迷宮，而不是用mazeNN來表示，這樣就可以避免老鼠走迷宮會出格。 通過這一個星期的學習實踐，我更加深層次的了解了關于數(shù)據結構的相關知識，也越來越發(fā)現(xiàn)自己對數(shù)據結構方面知識的欠缺，使我對自己所學得的知識有了一個深刻的理解，對于這方面的知識，我還缺少很多，紙上得來終覺淺，再強大的理論也要通過實踐來證明。在今后的學習中我要多練習，做一個專業(yè)的計算機學生。 參考文獻1 劉振安,劉燕君.C程序設計課程設計M.北京機械工業(yè)出版社,2004年9月2 譚浩強.C程序設計（第三版）.清華大學出版社,2005年7月3 嚴蔚敏,吳偉民.數(shù)據結

15、構（C語言版）.清華大學出版社,1997年4月4 李志球實用C語言程序設計教程 北京：電子工業(yè)出版社，19995 王立柱：C/C+與數(shù)據結構 北京：清華大學出版社，20026 吳文虎 程序設計基礎 北京：清華大學出版社，20037 郭福順，王曉芬，李蓮治 數(shù)據結構（修訂本），大連理工大學出版社，19978 潘道才，陳一華 數(shù)據結構，電子科技大學出版社，1994附 錄附錄1 源程序清單 #include<stdlib.h> /庫中包含system("pause")和rand()函數(shù)#include<stdio.h> /c語言里的庫#include<

16、;iostream>using namespace std;#define N 49 /定義為全局變量,這是迷宮數(shù)組的上線，可以自行修改#define M 49int X; int mazeN+2M+2;int head=0,tail=0; /隊列的頭尾指針，初始值設為0struct point /存放迷宮訪問到點的隊列結構體，包含列，行，序號 int row,col,predecessor; queue1200;void hand_maze(int m,int n) /手動生成迷宮int i,j;cout<<endl; cout<<"請按行輸入迷宮，0

17、表示通路，1表示障礙:"<<endl; for(i=0;i<m;i+) for(j=0;j<n;j+)cin>>mazeij; void automatic_maze(int m,int n) /自動生成迷宮int i,j;cout<<"n迷宮生成中nn"system("pause");for(i=0;i<m;i+)for(j=0;j<n;j+)mazeij=rand()%2; /隨機生成0、1maze00=0; /將開始和結束位置強制為0，保證有可能出來迷宮mazem-1n-1=0;

18、void data(int m,int n) /當用戶輸入的不是規(guī)整的m行n列的迷宮，用來生成規(guī)則的數(shù)字迷宮int i,j; cout<<endl;cout<<"根據您先前設定的迷宮范圍"<<endl;cout<<endl;cout<<" 我們將取所輸入的前"<<m*n<<"個數(shù)生成迷宮"<<endl;cout<<"n數(shù)字迷宮生成結果如下:nn"cout<<"迷宮入口n" co

19、ut<<""for(i=0;i<m;i+) cout<<"n"for(j=0;j<n;j+) if(mazeij=0) cout<<" 0"if(mazeij=1) cout<<" 1" cout<<"迷宮出口n"void print_maze(int m,int n) /打印迷宮外殼int i,j,k;cout<<"n字符迷宮生成結果如下:nn"cout<<"迷宮入口n

20、"cout<<" "cout<<endl;cout<<" " /生成上外殼for(k=0;k<n;k+)cout<<"" /這兩個黑三角用來生成頂部外殼for(i=0;i<m;i+)cout<<"n" /生成左外殼cout<<""for(j=0;j<n;j+) if(mazeij=0) printf("");if(mazeij=1) printf("");c

21、out<<"" /生成右外殼cout<<endl;for(k=0;k<n;k+)cout<<""cout<<" n" /生成底部外殼 for(i=0;i<n;i+)cout<<" " cout<<"n"for(i=0;i<n;i+)cout<<" "cout<<"迷宮出口n"void result_maze(int m,int n) /這個是打

22、印輸出迷宮的星號路徑 int i,j;cout<<"迷宮通路(用表示)如下所示：nt"for(i=0;i<m;i+)cout<<"n"for(j=0;j<n;j+)if(mazeij=0|mazeij=2) /2是隊列中訪問過的點 cout<<""if(mazeij=1) cout<<""if(mazeij=3) /3是標記的可以走通的路徑cout<<""void enqueue(struct point p) /迷宮中隊列

23、入隊操作queuetail=p;tail+; /先用再加，隊列尾部加1struct point dequeue() /迷宮中隊列出隊操作，不需要形參，因此用結構體定義head+;return queuehead-1;int is_empty() /判斷隊列是否為空return head=tail;void visit(int row,int col,int maze5151) /訪問迷宮矩陣中的節(jié)點struct point visit_point=row,col,head-1; /head-1的作用是正在訪問的這個點的序號為之前的點序號mazerowcol=2; /將訪問過的點位標記為2enq

24、ueue(visit_point);/入隊int path(int maze5151,int m,int n) /路徑求解X=1; /初始值定為1struct point p=0,0,-1; /定義入口節(jié)點if(mazep.rowp.col=1) /入口為1時，迷宮不可解 cout<<"n=n" cout<<"此迷宮無解nn" X=0; return 0; mazep.rowp.col=2; /標記為已訪問 enqueue(p); /將p入隊列while(!is_empty() p=dequeue(); if(p.row=m-1)

25、&&(p.col=n-1) /當行和列為出口時跳出 break; /定義8個走位方向 if(p.row-1)>=0)&&(p.row-1)<m)&&(p.col+0)<n)&&(mazep.row-1p.col+0=0) visit(p.row-1,p.col+0,maze); /北 if(p.row-1)>=0)&&(p.row-1)<m)&&(p.col+1)<n)&&(mazep.row-1p.col+1=0) visit(p.row-1,p

26、.col+1,maze); /東北 if(p.row+0)<m)&&(p.col+1)<n)&&(mazep.row+0p.col+1=0) visit(p.row+0,p.col+1,maze); /東 if(p.row+1)<m)&&(p.col+1)<n)&&(mazep.row+1p.col+1=0) visit(p.row+1,p.col+1,maze); /東南 if(p.row+1)<m)&&(p.col+0)<n)&&(mazep.row+1p.c

27、ol+0=0) visit(p.row+1,p.col+0,maze); /南 if(p.row+1)<m)&&(p.col-1)<n)&&(p.col-1)>=0)&&(mazep.row+1p.col-1=0) visit(p.row+1,p.col-1,maze); /西南 if(p.row+0)<m)&&(p.col-1)<n)&&(p.col-1)>=0)&&(mazep.row+0p.col-1=0) visit(p.row+0,p.col-1,maz

28、e); /西 if(p.row-1)>=0)&&(p.row-1)<m)&&(p.col-1)<n)&&(p.col-1)>=0)&&(mazep.row-1p.col-1=0) visit(p.row-1,p.col-1,maze); /西北if(p.row=m-1&&p.col=n-1) /如果當前矩陣點是出口點，輸出路徑cout<<"n=n" cout<<"迷宮路徑為：n" cout<<"出口&quo

29、t;<<endl; cout<<" "<<""<<endl; printf("(%d,%d)n",p.row+1,p.col+1); cout<<" "<<""<<endl; mazep.rowp.col=3; /逆序將路徑標記為3 while(p.predecessor!=-1) p=queuep.predecessor; printf("(%d,%d)n",p.row+1,p.col+1)

30、; cout<<" "<<""<<endl; mazep.rowp.col=3; cout<<"入口"<<endl;else cout<<"n=n" cout<<"此迷宮無解！nn" X=0;return 0;void main() int i,m,n,cycle=0; while(cycle!=(-1) cout<<"*n" cout<<" 歡迎進入迷宮求解

31、系統(tǒng)n" cout<<endl; cout<<" 設計者:李柏（B計算機115班）n" cout<<"*n" cout<<" 手動生成迷宮 請按：1n" cout<<" 自動生成迷宮 請按：2n" cout<<" 退出 請按：3nn" cout<<"*n" cout<<"n" cout<<"請選擇你的操作：n" cin>>i; switch(i) case 1: cout<<"n請輸入行數(shù)：" cin>>m; cout<<"n" cout<<"請輸入列數(shù)：" cin>>n; while(m<0|m>49)|(n<0|n>49) cout<<"n抱歉，你輸入的行列數(shù)超出預設范圍(0-49,0-49),請重新輸入：nn" cout<<&quo