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

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

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

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

4、t mazeN+2M+2來表示，這樣相當(dāng)于在迷宮外層包了一層1，即防止搜索路徑時(shí)跳出迷宮。（1）手動(dòng)生成迷宮void hand_maze(int m,int n) /手動(dòng)生成迷宮int i,j; for(i=0;im;i+) for(j=0;jmazeij; （2） 自動(dòng)生成迷宮void automatic_maze(int m,int n) /自動(dòng)生成迷宮int i,j;for(i=0;im;i+)for(j=0;jn;j+)mazeij=rand()%2; /隨機(jī)生成0、1maze00=0; /將開始和結(jié)束位置強(qiáng)制為0，保證有可能出來迷宮mazem-1n-1=0;2、迷宮路徑的搜索在生成的

5、0、1矩陣迷宮中，首先從迷宮的入口開始，如果該位置就是迷宮出口，則已經(jīng)找到了一條路徑，搜索工作結(jié)束。否則搜索其北（-1，0），東北（-1，1），東（0,1），東南（1,1），南（1,0），西南（1，-1），西（0，-1），西北（-1，-1）8個(gè)方向位，是否是障礙，若不是障礙，就移動(dòng)到該位置，然后再從該位置開始搜索通往出口的路徑；若是障礙就選擇另一個(gè)相鄰的位置，并從它開始搜索路徑。為防止搜索重復(fù)出現(xiàn)，則將已搜索過的位置標(biāo)記為2，同時(shí)保留搜索痕跡，在考慮進(jìn)入下一個(gè)位置搜索之前，將當(dāng)前位置保存在一個(gè)隊(duì)列中，如果所有相鄰的非障礙位置均被搜索過，且未找到通往出口的路徑，則表明不存在從入口到出口的路徑。這

6、實(shí)現(xiàn)的是廣度優(yōu)先遍歷的算法，如果找到路徑，則為最短路徑。逆序輸出路徑，將已輸出的路徑標(biāo)記為3。 實(shí)驗(yàn)數(shù)據(jù)如下： 表3.1 方向move的偏移量Name dirMovedir.vertMovedir.horizN0-10NE1-11E201SE311S410SW51-1W60-1NW60-13測試結(jié)果 圖1 圖2 圖3 圖4 圖 5 圖6 圖7 4分析與探討首先明確題目中的已知條件：（1） 迷宮是一個(gè)8*8大小的矩陣。（2） 從迷宮的左上角進(jìn)入，右下角為迷宮的終點(diǎn)。（3） mazeij=0代表第i+1行第j+1列的點(diǎn)是通路；mazeij=1代表該點(diǎn)是墻，無法通行。（4） 迷宮有兩種生成方式：手工

7、設(shè)定和自動(dòng)生成。（5） 當(dāng)老鼠處于迷宮中某一點(diǎn)的位置上，它可以向8個(gè)方向前進(jìn)，分別是：“上、下、左、右、左上、左下、右上、右下”8個(gè)方向。（6） 要實(shí)現(xiàn)這個(gè)程序，首先要考慮如何表示這個(gè)迷宮。在實(shí)例程序中使用二維數(shù)組mazeN+2N+2來表示這個(gè)迷宮，其中N為迷宮的行、列數(shù)。當(dāng)值為“0”時(shí)表示該點(diǎn)是通路，當(dāng)值為“1”時(shí)表示該點(diǎn)是墻。老鼠在迷宮的位置在任何時(shí)候都可以由行號row和列號cool表示。（7） 為什么指定: mazeN+2N+2來表示迷宮，而不是使用mazeNN來表示迷宮？原因是當(dāng)老鼠跑到了迷宮的邊界點(diǎn)時(shí)就有可能跳出迷宮，而使用mazeN+2N+2就可以把迷宮的外邊再包一層“1”，這樣就

8、能阻止老鼠走出格。（8） 老鼠在每一點(diǎn)都有8種方向可以走，分別是：North，NorthEast，East，SouthEast,South,SouthWest,West，NorthWest。可以用數(shù)組move8來表示每一個(gè)方向上的橫縱坐標(biāo)的偏移量，見表3.1。根據(jù)這個(gè)數(shù)組，就很容易計(jì)算出沿某個(gè)方向行走后的下一個(gè)點(diǎn)的坐標(biāo)。 方向move的偏移量Name dirMovedir.vertMovedir.horizN0-10NE1-11E201SE311S410SW51-1W60-1NW60-1迷宮問題可以用深度優(yōu)先搜索方法實(shí)現(xiàn)。當(dāng)老鼠在迷宮中移動(dòng)的時(shí)候，可能會有許多種移動(dòng)選擇方向。程序需要記錄并用棧

9、來保存當(dāng)前點(diǎn)的坐標(biāo)，然后任意選擇一個(gè)方向進(jìn)行移動(dòng)。由于應(yīng)用棧保存了當(dāng)前通道上各點(diǎn)的坐標(biāo)，所以當(dāng)在當(dāng)前各方向上都走不通時(shí)可以返回上一個(gè)點(diǎn)，然后選擇另一個(gè)方向前進(jìn)。 可定義element結(jié)構(gòu)用于存儲每一步的橫縱坐標(biāo)和方向。 typedef struct short int row; short int col; short int dir;element;Element stackMAX _STACK_SIZE;根據(jù)表3.1可推算出每次移動(dòng)后的坐標(biāo)。設(shè)當(dāng)前的坐標(biāo)是（row,col）,移動(dòng)的方向是dir，移動(dòng)后的點(diǎn)是next,則有next_row=row+movedir.vert;next_col=

10、col+movedir.horiz; 可用另一個(gè)二維數(shù)組markN+2來記錄哪些點(diǎn)已經(jīng)被訪問過。當(dāng)經(jīng)過點(diǎn)mazerowcol時(shí)，相應(yīng)地將markrowcol的值從0置為1。 本程序支持自動(dòng)生成迷宮。利用random（2）函數(shù)可隨機(jī)產(chǎn)生0或1，來支持迷宮的自動(dòng)生成。注意mazeNN和maze11一定要等于0，因?yàn)樗麄兎謩e是起點(diǎn)和終點(diǎn)。 如果找到了一條走出迷宮的路徑，則需要在屏幕中打印出如圖3.5所示格式的信息。這里要用到graphics.h即TC中的圖形庫（注意：本程序是TC上的實(shí)現(xiàn)，而VC+有自己的圖形庫，所以使用VC+編譯提示錯(cuò)誤）。針對圖3.5，可使用circle（）函數(shù)畫圓，outtex

11、ttxy（）函數(shù)標(biāo)記文字，并用line（）函數(shù)來劃線。 程序的主要函數(shù)如下： 函數(shù)void add（int*top,element item），將當(dāng)前步的信息item壓入到作為全局變量的棧stack（棧頂為top）中。 函數(shù)element delete（int * top），返回stack中棧頂?shù)脑亍?函數(shù)void path（void），采用深度優(yōu)先搜索算法，首先取出棧頂元素作為當(dāng)前點(diǎn)選擇一個(gè)方向前進(jìn)到下一個(gè)點(diǎn)（如果能走得話）；然后，將下一個(gè)點(diǎn)壓入棧，并將二維數(shù)組mark中對應(yīng)的值改為1，表示該點(diǎn)已經(jīng)走到了。反復(fù)執(zhí)行上面兩步，當(dāng)走到一個(gè)點(diǎn)不能再走下去了（已經(jīng)嘗試了各個(gè)方向并失?。?，并且這個(gè)點(diǎn)

12、不是終點(diǎn)，則這個(gè)點(diǎn)的上一個(gè)點(diǎn)會從棧中被跑拋出，從而“回朔”到上一點(diǎn)；當(dāng)遇到終點(diǎn)時(shí)，程序結(jié)束，找到一條路徑；當(dāng)在程序循環(huán)過程中遇到棧為空，則說明該迷宮根本無法走到終點(diǎn)。5小結(jié)為期一個(gè)星期的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)快結(jié)束了，這使我對深度和廣度優(yōu)先搜索有了更加深刻的理解和認(rèn)識。我們團(tuán)隊(duì)負(fù)責(zé)的迷宮問題的課程設(shè)計(jì)就是充分的利用深度和廣度優(yōu)先搜索的有關(guān)知識，主要運(yùn)用的是廣度優(yōu)先搜索遍歷。（1）深度優(yōu)先搜索遍歷：深度優(yōu)先搜索是一個(gè)遞歸過程。首先訪問一個(gè)頂點(diǎn)Vi并將其標(biāo)記為已訪問過，然后從Vi的任意一個(gè)未被訪問的鄰接點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索遍歷。如此執(zhí)行，當(dāng)Vi的所有鄰接點(diǎn)均被訪問過時(shí)，則退回到上一個(gè)頂點(diǎn)Vk，從Vk的

13、另一未被訪問過的鄰接點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索遍歷。如此執(zhí)行，直到退回到初始點(diǎn)并且沒有未被訪問過的鄰接點(diǎn)為止。 （2）廣度優(yōu)先搜索遍歷：廣度優(yōu)先搜索過程為：首先訪問初始點(diǎn)Vi，并將其標(biāo)記為已訪問過，接著訪問Vi的所有未被訪問過的鄰接點(diǎn)，其訪問順序可以任意，假定依次為Vi1、Vi2，Vin，并標(biāo)記為已訪問過，然后按照Vi1、Vi2，Vin的次序訪問每一個(gè)頂點(diǎn)的所有未被訪問過的鄰接點(diǎn)，并均標(biāo)記為已訪問過，依次類推，直到圖中所有和初始點(diǎn)Vi有路徑相通的頂點(diǎn)都被訪問過為止。在設(shè)計(jì)迷宮問題時(shí)要考慮使用二維數(shù)組，在數(shù)組中我們選擇mazeN+2N+2來表示迷宮，而不是用mazeNN來表示，這樣就可以避免老鼠走迷

14、宮會出格。 通過這一個(gè)星期的學(xué)習(xí)實(shí)踐，我更加深層次的了解了關(guān)于數(shù)據(jù)結(jié)構(gòu)的相關(guān)知識，也越來越發(fā)現(xiàn)自己對數(shù)據(jù)結(jié)構(gòu)方面知識的欠缺，使我對自己所學(xué)得的知識有了一個(gè)深刻的理解，對于這方面的知識，我還缺少很多，紙上得來終覺淺，再強(qiáng)大的理論也要通過實(shí)踐來證明。在今后的學(xué)習(xí)中我要多練習(xí)，做一個(gè)專業(yè)的計(jì)算機(jī)學(xué)生。 參考文獻(xiàn)1 劉振安,劉燕君.C程序設(shè)計(jì)課程設(shè)計(jì)M.北京機(jī)械工業(yè)出版社,2004年9月2 譚浩強(qiáng).C程序設(shè)計(jì)（第三版）.清華大學(xué)出版社,2005年7月3 嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）.清華大學(xué)出版社,1997年4月4 李志球?qū)嵱肅語言程序設(shè)計(jì)教程 北京：電子工業(yè)出版社，19995 王立柱：C/C

15、+與數(shù)據(jù)結(jié)構(gòu) 北京：清華大學(xué)出版社，20026 吳文虎 程序設(shè)計(jì)基礎(chǔ) 北京：清華大學(xué)出版社，20037 郭福順，王曉芬，李蓮治 數(shù)據(jù)結(jié)構(gòu)（修訂本），大連理工大學(xué)出版社，19978 潘道才，陳一華 數(shù)據(jù)結(jié)構(gòu)，電子科技大學(xué)出版社，1994附 錄附錄1 源程序清單 #include /庫中包含system(pause)和rand()函數(shù)#include /c語言里的庫#includeusing namespace std;#define N 49 /定義為全局變量,這是迷宮數(shù)組的上線，可以自行修改#define M 49int X; int mazeN+2M+2;int head=0,tail=0;

16、 /隊(duì)列的頭尾指針，初始值設(shè)為0struct point /存放迷宮訪問到點(diǎn)的隊(duì)列結(jié)構(gòu)體，包含列，行，序號 int row,col,predecessor; queue1200;void hand_maze(int m,int n) /手動(dòng)生成迷宮int i,j;coutendl; cout請按行輸入迷宮，0表示通路，1表示障礙:endl; for(i=0;im;i+) for(j=0;jmazeij; void automatic_maze(int m,int n) /自動(dòng)生成迷宮int i,j;coutn迷宮生成中nn;system(pause);for(i=0;im;i+)for(j=0

17、;jn;j+)mazeij=rand()%2; /隨機(jī)生成0、1maze00=0; /將開始和結(jié)束位置強(qiáng)制為0，保證有可能出來迷宮mazem-1n-1=0;void data(int m,int n) /當(dāng)用戶輸入的不是規(guī)整的m行n列的迷宮，用來生成規(guī)則的數(shù)字迷宮int i,j; coutendl;cout根據(jù)您先前設(shè)定的迷宮范圍endl;coutendl;cout 我們將取所輸入的前m*n個(gè)數(shù)生成迷宮endl;coutn數(shù)字迷宮生成結(jié)果如下:nn;cout迷宮入口n; cout;for(i=0;im;i+) coutn;for(j=0;jn;j+) if(mazeij=0) cout 0;i

18、f(mazeij=1) cout 1; cout迷宮出口n;void print_maze(int m,int n) /打印迷宮外殼int i,j,k;coutn字符迷宮生成結(jié)果如下:nn;cout迷宮入口n;cout ;coutendl;cout ; /生成上外殼for(k=0;kn;k+)cout; /這兩個(gè)黑三角用來生成頂部外殼for(i=0;im;i+)coutn; /生成左外殼cout;for(j=0;jn;j+) if(mazeij=0) printf();if(mazeij=1) printf();cout; /生成右外殼coutendl;for(k=0;kn;k+)cout;c

19、out n; /生成底部外殼 for(i=0;in;i+)cout ; coutn;for(i=0;in;i+)cout ;cout迷宮出口n;void result_maze(int m,int n) /這個(gè)是打印輸出迷宮的星號路徑 int i,j;cout迷宮通路(用表示)如下所示：nt;for(i=0;im;i+)coutn;for(j=0;jn;j+)if(mazeij=0|mazeij=2) /2是隊(duì)列中訪問過的點(diǎn) cout;if(mazeij=1) cout;if(mazeij=3) /3是標(biāo)記的可以走通的路徑cout;void enqueue(struct point p) /迷

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

21、2enqueue(visit_point);/入隊(duì)int path(int maze5151,int m,int n) /路徑求解X=1; /初始值定為1struct point p=0,0,-1; /定義入口節(jié)點(diǎn)if(mazep.rowp.col=1) /入口為1時(shí)，迷宮不可解 coutn=n; cout=0)&(p.row-1)m)&(p.col+0)=0)&(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+0)m)&(p.col+1)n)&(mazep.row+

22、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.col+0=0) visit(p.row+1,p.col+0,maze); /南 if(p.row+1)m)&(p.col-1)=0)&(mazep.row+1p.col-1=0) visit(p.row+1,p.col-1,maze); /西南 if(p.row+0

23、)m)&(p.col-1)=0)&(mazep.row+0p.col-1=0) visit(p.row+0,p.col-1,maze); /西 if(p.row-1)=0)&(p.row-1)m)&(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) /如果當(dāng)前矩陣點(diǎn)是出口點(diǎn)，輸出路徑coutn=n; cout迷宮路徑為：n; cout出口endl; cout endl; printf(%d,%d)n,p.row+1,p.col+1); cout endl; maz

24、ep.rowp.col=3; /逆序?qū)⒙窂綐?biāo)記為3 while(p.predecessor!=-1) p=queuep.predecessor; printf(%d,%d)n,p.row+1,p.col+1); cout endl; mazep.rowp.col=3; cout入口endl;else coutn=n; cout此迷宮無解！nn; X=0;return 0;void main() int i,m,n,cycle=0; while(cycle!=(-1) cout*n; cout 歡迎進(jìn)入迷宮求解系統(tǒng)n; coutendl; cout 設(shè)計(jì)者:李柏（B計(jì)算機(jī)115班）n; cout*