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

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

2、，遍歷一般分為深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷。本實(shí)驗(yàn)中用到的是廣度優(yōu)先搜索遍歷。即首先訪問(wèn)初始點(diǎn)vi，并將其標(biāo)記為已訪問(wèn)過(guò)，接著訪問(wèn)vi的所有未被訪問(wèn)過(guò)的鄰接點(diǎn)，順序任意，并均標(biāo)記為已訪問(wèn)過(guò)，以此類推，直到圖中所有和初始點(diǎn)vi有路徑相通的頂點(diǎn)都被訪問(wèn)過(guò)為止。鑒于廣度優(yōu)先搜索是將所有路徑同時(shí)按照順序遍歷，直到遍歷出迷宮出口，生成的路徑為最短路徑。因此我們采用了廣度優(yōu)先搜索。無(wú)論是深度優(yōu)先搜索還是廣度優(yōu)先搜索，其本質(zhì)都是將圖的二維頂點(diǎn)結(jié)構(gòu)線性化的過(guò)程，并將當(dāng)前頂點(diǎn)相鄰的未被訪問(wè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è)n

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

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

5、 /將開(kāi)始和結(jié)束位置強(qiáng)制為0，保證有可能出來(lái)迷宮mazem-1n-1=0;2、迷宮路徑的搜索在生成的0、1矩陣迷宮中，首先從迷宮的入口開(kāi)始，如果該位置就是迷宮出口，則已經(jīng)找到了一條路徑，搜索工作結(jié)束。否則搜索其北（-1，0），東北（-1，1），東（0,1），東南（1,1），南（1,0），西南（1，-1），西（0，-1），西北（-1，-1）8個(gè)方向位，是否是障礙，若不是障礙，就移動(dòng)到該位置，然后再?gòu)脑撐恢瞄_(kāi)始搜索通往出口的路徑；若是障礙就選擇另一個(gè)相鄰的位置，并從它開(kāi)始搜索路徑。為防止搜索重復(fù)出現(xiàn)，則將已搜索過(guò)的位置標(biāo)記為2，同時(shí)保留搜索痕跡，在考慮進(jìn)入下一個(gè)位置搜索之前，將當(dāng)前位置保存在一個(gè)隊(duì)

6、列中，如果所有相鄰的非障礙位置均被搜索過(guò)，且未找到通往出口的路徑，則表明不存在從入口到出口的路徑。這實(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測(cè)試結(jié)果 圖1 圖2 圖3 圖4 圖 5 圖6 圖7 4分析與探討首先明確題目中的已知條件：（1） 迷宮是一個(gè)8*8大小的矩陣。（2） 從迷宮的左上角進(jìn)入，右下角為迷宮的終點(diǎn)。（3） mazeij=0代表第i

7、+1行第j+1列的點(diǎn)是通路；mazeij=1代表該點(diǎn)是墻，無(wú)法通行。（4） 迷宮有兩種生成方式：手工設(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來(lái)表示這個(gè)迷宮，其中N為迷宮的行、列數(shù)。當(dāng)值為“0”時(shí)表示該點(diǎn)是通路，當(dāng)值為“1”時(shí)表示該點(diǎn)是墻。老鼠在迷宮的位置在任何時(shí)候都可以由行號(hào)row和列號(hào)cool表示。（7） 為什么指定: mazeN+2N+2來(lái)表示迷宮，而不是使用mazeNN來(lái)表示迷宮？原因是當(dāng)老鼠跑到

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

9、可以用深度優(yōu)先搜索方法實(shí)現(xiàn)。當(dāng)老鼠在迷宮中移動(dòng)的時(shí)候，可能會(huì)有許多種移動(dòng)選擇方向。程序需要記錄并用棧來(lái)保存當(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)用于存儲(chǔ)每一步的橫縱坐標(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)的方向是di

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

11、己的圖形庫(kù)，所以使用VC+編譯提示錯(cuò)誤）。針對(duì)圖3.5，可使用circle（）函數(shù)畫(huà)圓，outtexttxy（）函數(shù)標(biāo)記文字，并用line（）函數(shù)來(lái)劃線。 程序的主要函數(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中對(duì)應(yīng)的值改為1，表示

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

13、出發(fā)進(jìn)行深度優(yōu)先搜索遍歷。如此執(zhí)行，當(dāng)Vi的所有鄰接點(diǎn)均被訪問(wèn)過(guò)時(shí)，則退回到上一個(gè)頂點(diǎn)Vk，從Vk的另一未被訪問(wèn)過(guò)的鄰接點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索遍歷。如此執(zhí)行，直到退回到初始點(diǎn)并且沒(méi)有未被訪問(wèn)過(guò)的鄰接點(diǎn)為止。 （2）廣度優(yōu)先搜索遍歷：廣度優(yōu)先搜索過(guò)程為：首先訪問(wèn)初始點(diǎn)Vi，并將其標(biāo)記為已訪問(wèn)過(guò)，接著訪問(wèn)Vi的所有未被訪問(wèn)過(guò)的鄰接點(diǎn)，其訪問(wèn)順序可以任意，假定依次為Vi1、Vi2，Vin，并標(biāo)記為已訪問(wèn)過(guò)，然后按照Vi1、Vi2，Vin的次序訪問(wèn)每一個(gè)頂點(diǎn)的所有未被訪問(wèn)過(guò)的鄰接點(diǎn)，并均標(biāo)記為已訪問(wèn)過(guò)，依次類推，直到圖中所有和初始點(diǎn)Vi有路徑相通的頂點(diǎn)都被訪問(wèn)過(guò)為止。在設(shè)計(jì)迷宮問(wèn)題時(shí)要考慮使用二維數(shù)組

14、，在數(shù)組中我們選擇mazeN+2N+2來(lái)表示迷宮，而不是用mazeNN來(lái)表示，這樣就可以避免老鼠走迷宮會(huì)出格。 通過(guò)這一個(gè)星期的學(xué)習(xí)實(shí)踐，我更加深層次的了解了關(guān)于數(shù)據(jù)結(jié)構(gòu)的相關(guān)知識(shí)，也越來(lái)越發(fā)現(xiàn)自己對(duì)數(shù)據(jù)結(jié)構(gòu)方面知識(shí)的欠缺，使我對(duì)自己所學(xué)得的知識(shí)有了一個(gè)深刻的理解，對(duì)于這方面的知識(shí)，我還缺少很多，紙上得來(lái)終覺(jué)淺，再?gòu)?qiáng)大的理論也要通過(guò)實(shí)踐來(lái)證明。在今后的學(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語(yǔ)言版）.清華大學(xué)出版

15、社,1997年4月4 李志球?qū)嵱肅語(yǔ)言程序設(shè)計(jì)教程 北京：電子工業(yè)出版社，19995 王立柱：C/C+與數(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<stdlib.h> /庫(kù)中包含system("pause")和rand()函數(shù)#include<stdio.h> /c語(yǔ)言里的庫(kù)#include<iostream>u

16、sing namespace std;#define N 49 /定義為全局變量,這是迷宮數(shù)組的上線，可以自行修改#define M 49int X; int mazeN+2M+2;int head=0,tail=0; /隊(duì)列的頭尾指針，初始值設(shè)為0struct point /存放迷宮訪問(wèn)到點(diǎn)的隊(duì)列結(jié)構(gòu)體，包含列，行，序號(hào) int row,col,predecessor; queue1200;void hand_maze(int m,int n) /手動(dòng)生成迷宮int i,j;cout<<endl; cout<<"請(qǐng)按行輸入迷宮，0表示通路，1表示障礙:&qu

17、ot;<<endl; for(i=0;i<m;i+) for(j=0;j<n;j+)cin>>mazeij; void automatic_maze(int m,int n) /自動(dòng)生成迷宮int i,j;cout<<"n迷宮生成中nn"system("pause");for(i=0;i<m;i+)for(j=0;j<n;j+)mazeij=rand()%2; /隨機(jī)生成0、1maze00=0; /將開(kāi)始和結(jié)束位置強(qiáng)制為0，保證有可能出來(lái)迷宮mazem-1n-1=0;void data(int

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

19、t;"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字符迷宮生成結(jié)果如下:nn"cout<<"迷宮入口n"cout<

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

21、ot;" /生成右外殼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) /這個(gè)是打印輸出迷宮的星號(hào)路徑 int

22、 i,j;cout<<"迷宮通路(用表示)如下所示：nt"for(i=0;i<m;i+)cout<<"n"for(j=0;j<n;j+)if(mazeij=0|mazeij=2) /2是隊(duì)列中訪問(wèn)過(guò)的點(diǎn) cout<<""if(mazeij=1) cout<<""if(mazeij=3) /3是標(biāo)記的可以走通的路徑cout<<""void enqueue(struct point p) /迷宮中隊(duì)列入隊(duì)操作queuetail=

23、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) /訪問(wèn)迷宮矩陣中的節(jié)點(diǎn)struct point visit_point=row,col,head-1; /head-1的作用是正在訪問(wèn)的這個(gè)點(diǎn)的序號(hào)為之前的點(diǎn)序號(hào)mazerowcol=2; /將訪問(wèn)過(guò)的點(diǎn)位標(biāo)記為2enqueue(visit_poi

24、nt);/入隊(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í)，迷宮不可解 cout<<"n=n" cout<<"此迷宮無(wú)解nn" X=0; return 0; mazep.rowp.col=2; /標(biāo)記為已訪問(wèn) enqueue(p); /將p入隊(duì)列while(!is_empty() p=dequeue(); if(p.row=m-1)&&(p.c

25、ol=n-1) /當(dāng)行和列為出口時(shí)跳出 break; /定義8個(gè)走位方向 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.col+1,maze);

26、/東北 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.col+0=0) visit(

27、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,maze); /西 if(p.ro

28、w-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) /如果當(dāng)前矩陣點(diǎn)是出口點(diǎn)，輸出路徑cout<<"n=n" cout<<"迷宮路徑為：n" cout<<"出口"<<endl

29、; cout<<" "<<""<<endl; printf("(%d,%d)n",p.row+1,p.col+1); cout<<" "<<""<<endl; mazep.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<<

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

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