深度與廣度優(yōu)先搜索：迷宮問題的設(shè)計

1、數(shù)數(shù)據(jù)據(jù)結(jié)結(jié)構(gòu)構(gòu)課課程程設(shè)設(shè)計計報報告告深度與廣度優(yōu)先搜索：迷宮問深度與廣度優(yōu)先搜索：迷宮問題題的設(shè)計的設(shè)計目目 錄錄1 設(shè)計內(nèi)容.12 設(shè)計分析.13 設(shè)計實踐.34 測試方法.45 程序運行效果.66 設(shè)計心得.87 附錄.9數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告（2017）1深度與廣度優(yōu)先搜索：迷宮問題的設(shè)計深度與廣度優(yōu)先搜索：迷宮問題的設(shè)計1 設(shè)計內(nèi)容 一般的迷宮可表示為一個二維平面圖形，將迷宮的左上角作入口，右下角作出口。迷宮問題求解的目標是尋找一條從入口點到出口點的通路。例如，可以設(shè)計一個8*8矩陣maze88來表示迷宮，如下所示：0 1 0 0 0 0 1 10 0 0 1 0 0 1 01 0

2、1 0 1 0 1 11 0 1 0 1 1 0 10 1 1 1 1 1 1 01 0 0 1 1 0 0 0 1 0 1 0 0 0 1 1 1 0 1 1 0 1 0 0 左上角maze00為起點，右下角maze77為終點；設(shè)“0”為通路， “1”為墻，即無法穿越。假設(shè)一只老鼠從起點出發(fā)，目的為右下角終點，可向“上，下，左，右，左上，左下，右上，右下”8個方向行走。 設(shè)計一個程序，能自動生存或者手動生成這樣一個8*8矩陣，針對這個矩陣，程序判斷是否能從起點經(jīng)過迷宮走到終點。如果不能，指出；如果能，用圖形界面標出走出迷宮的路徑。2 設(shè)計分析首先明確題目中的已知條件：（1） 迷宮是一個 8*

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

4、 表示。 為什么指定 mazeN+2N+2來表示迷宮，而不是使用 mazeNN來表示迷宮？原因是當老鼠跑到迷宮的邊界點時就有可能跳出迷宮，而使用 mazeN+2N+2就可以把迷宮的外面再包一層“1” ，這樣就能阻止老鼠走出格。 老鼠在每一點都有 8 種方向可以走，分別是：North，NorthEast，East，SouthEast，South，SouthWest，West，NorthWest?？梢杂脭?shù)組 move8來表示在每一個方向上的橫縱坐標的偏移量，見表 3.1。根據(jù)這個數(shù)組，就很容易計算出沿某個方向行走的下一點的坐標。深度與廣度優(yōu)先搜索：迷宮問題的設(shè)計2表 3.1 8 種方向 move

5、的偏移量NameDirMovedir.vertMovedir.horizN0-10NE1-11E201SE311S410SW51-1W60-1NW7-1-1迷宮問題可以用深度優(yōu)先搜索方法實現(xiàn)。當老鼠在迷宮中移動的時候，可能會有多種移動方向。程序需要記錄并用棧來保存當前點的坐標，然后任意任取一個方向進行移動。由于應(yīng)用棧保存了當前通道上各點的坐標，所以當在當前各方向上走不通時可以返回上一個點，然后選擇另一個方向前進?？啥xelement結(jié)構(gòu)用于存儲每一步的橫縱坐標和方向。Typedef struct short int row; short int col; short int dir;eleme

6、nt;element stackMAX_STACK_SIZE；根據(jù)表3.1 可推算出每次移動后的坐標。設(shè)當前點的坐標是（row,col） ，移動方向是dir,移動后的點是next,則有next_row=-row+movedir.vert;next_col=col+movedir.horiz;可用另一個二維數(shù)組markN+2N+2來記錄哪些點已經(jīng)被訪問過。當經(jīng)過點mazerowcol時，相應(yīng)地將markrowcol的值從0置1。本程序支持自動生存迷宮。利用random（2）函數(shù)可隨機產(chǎn)生0或1，來支持迷宮的自動生存。注意mazeNN和maze11一定要等于0，因為它們分別是起點和終點。如果找到了

7、一條走出迷宮的路徑，則需要在屏幕中打印出如圖3.5所示格式的信息。這里要用到graphices.h，即TC中的圖形庫。程序的主要函數(shù)如下：函數(shù)void add(int *top,element item)，將當前步的信息item壓入到作為全局變量的棧stack(棧頂為top)中。函數(shù)elemrnt delete(int *top)，返回stack中棧頂?shù)脑?。?shù)據(jù)結(jié)構(gòu)課程設(shè)計報告（2017）3函數(shù)void path(void)，采用深度優(yōu)先搜索算法，首先取出棧頂元素作為當前點，并從當前點選擇一個方向前進到下一個點（如果能走得話） ；然后，將下一個點壓入棧，并將二維數(shù)組mark中對應(yīng)的值改為1，

8、表示該點已經(jīng)走到了。反復執(zhí)行上面兩步，當走到一個點不能再走下去了，并且這個點不是終點，則這個點的上一個點會從棧中被拋出，從而“回溯”到上一個點；當遇到終點時，程序結(jié)束，找到一條路徑；當在程序循環(huán)過程中遇到棧為空，則說明該迷宮根本無法走到終點。3 設(shè)計實踐3.1 結(jié)構(gòu)體記錄水平和垂直的偏移量typedef struct short int vert;short int horiz;offsets;offsets move8; /* 8 個方向的 move*/int mazeN+2N+2;/*二維數(shù)組記錄迷宮*/int markN+2N+2;/*記錄迷宮中每點是否可到達*/int EXIT_ROW

9、 = N, EXIT_COL = N;3.2 輸出走出迷宮的路徑void path(void) int i, j, k, row, col, next_row, next_col, dir, found = FALSE; int gd=VGA; int gm=VGAHI;/*-*|i - 用來循環(huán)計數(shù) |row , col - 當前位置的坐標 |next_row - 移動后的位置的橫坐標 |next_col - 移動后的位置的縱坐標|dir - 移動的方向 |found - 標志路徑是否發(fā)現(xiàn) |*-*/ element position; int top = 0; mark11 = 1; /*

10、 maze11已經(jīng)被走過了*/ stack0.row = 1; stack0.col = 1; stack0.dir = 1; /*第一步的狀態(tài)*/ move0.vert = -1; move0.horiz = 0 ; move1.vert = -1; move1.horiz = 1 ;深度與廣度優(yōu)先搜索：迷宮問題的設(shè)計4 move2.vert = 0 ; move2.horiz = 1 ; move3.vert = 1 ; move3.horiz = 1 ; move4.vert = 1 ; move4.horiz = 0 ; move5.vert = 1 ; move5.horiz = -

11、1; move6.vert = 0 ; move6.horiz = -1; move7.vert = -1; move7.horiz = -1; initgraph(&gd,&gm,); /* 指定了八個方向*/ /*-* | 主要算法描述: | | 當 stack 不為空,移動到 stack 頂部的位置 | | 試著向各個方向移動，如果可以移動就移動到 | 下一個位置并把它標志成 1。 | | 然后保存狀態(tài)并加入到 stack 中 | | 如果路徑被破壞，或者不存在，就將其刪除 | | 并返回到上一點繼續(xù)遍歷其他方向的點 | | 直到一條路徑被發(fā)現(xiàn)。 | *-*/4 測試方法

12、 針對迷宮生成方式不同，本程序的測試分為兩類：手動輸入迷宮測試和計算機自動生成迷宮測試。另外，根據(jù)測試用例類型不同也可分為兩類：有解迷宮測試和無解迷宮測試。 下面給出兩個測試用例。測試用例 1（有解迷宮）：0 1 1 1 1 0 1 00 0 0 1 0 1 0 11 0 1 0 0 1 1 01 0 1 1 0 1 0 01 0 0 1 0 1 1 00 1 1 0 1 1 1 10 1 0 1 0 1 1 11 1 1 1 0 0 0 0數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告（2017）5其期望輸出結(jié)果如圖所示。測試用例 2;（無解迷宮）0 1 0 0 0 1 1 11 0 0 1 1 0 1 00 0 1

13、 0 1 1 0 11 0 1 0 0 1 0 00 0 0 1 0 1 1 10 0 1 0 1 1 0 00 0 0 0 0 1 0 00 1 0 1 1 1 1 0深度與廣度優(yōu)先搜索：迷宮問題的設(shè)計6其期望輸出結(jié)果如圖所示。5 程序運行效果測試用例 1（有解迷宮）：0 1 1 1 1 0 1 00 0 0 1 1 1 0 11 0 1 0 0 1 1 01 0 1 1 0 1 0 01 0 0 1 0 1 1 00 1 1 0 1 1 1 10 1 0 1 0 1 1 11 1 1 1 0 0 0 0數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告（2017）7其期望輸出結(jié)果如圖所示。測試用例 2;（無解迷宮）0

14、1 0 0 0 1 1 11 0 1 1 0 0 1 00 1 1 0 0 1 1 11 0 1 1 0 0 0 00 1 0 1 0 1 1 00 1 1 0 1 0 0 00 0 1 1 0 0 1 11 1 0 1 0 1 1 0深度與廣度優(yōu)先搜索：迷宮問題的設(shè)計8其期望輸出結(jié)果如圖所示。6 設(shè)計心得通過這五天的課程設(shè)計里，也讓我從中有所獲，此次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計使我對深度和廣度優(yōu)先搜索有了更加深刻的了解，迷宮問題的課程設(shè)計就是充分的利用深度和廣度優(yōu)先搜索的有關(guān)知識。剛開始用 C 語言編寫，碰到了一個很大的問題，調(diào)試了很多次，在 VC 里執(zhí)行不出來。 “#include” ，這其實是 TC

15、 里的一個圖形庫，在 VC 里編譯時不行的，會顯示有一個錯誤。但在 TC 里也碰到問題了，代碼不能完全輸入到編輯器中，導致最后還是無法運行。最后找了相關(guān)的代碼，安裝了相關(guān)圖形文件進去，試了試，終于運行成功。這次課程設(shè)計讓我受益匪淺，對數(shù)據(jù)結(jié)構(gòu)也有進一步的理解和認識。但也讓我認識到我還有很多的不足，今后需要多實踐和學習，提高能力和熟練應(yīng)用。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告（2017）97 附錄附錄#include #include #include #define N8#define MAX_STACK_SIZEN*N/*最大棧容量 */#define TRUE1#define FALSE0#define

16、LEN(300/N)/*結(jié)構(gòu)體記錄每一步的橫坐標，縱坐標和方向*/typedef struct short int row;short int col;short int dir;element;element stackMAX_STACK_SIZE;/*結(jié)構(gòu)體記錄水平和垂直的偏移量*/typedef struct short int vert;short int horiz;offsets;offsets move8; /* 8 個方向的 move*/int mazeN+2N+2;/*二維數(shù)組記錄迷宮*/int markN+2N+2;/*記錄迷宮中每點是否可到達*/int EXIT_ROW

17、= N, EXIT_COL = N;/*在棧中加入一個元素*/void add(int *top, element item)if (*top = MAX_STACK_SIZE - 1)printf(The stack is full!n);return; stack+*top = item;/*返回棧中頂部的元素*/element delete(int *top)if (*top = -1)printf(The stack is empty ! n);exit(1); return stack(*top)-;深度與廣度優(yōu)先搜索：迷宮問題的設(shè)計10/*輸出走出迷宮的路徑*/void path(

18、void) int i, j, k, row, col, next_row, next_col, dir, found = FALSE; int gd=VGA; int gm=VGAHI;/*-*|i - 用來循環(huán)計數(shù) |row , col - 當前位置的坐標 |next_row - 移動后的位置的橫坐標 |next_col - 移動后的位置的縱坐標|dir - 移動的方向 |found - 標志路徑是否發(fā)現(xiàn) |*-*/ element position; int top = 0; mark11 = 1; /* maze11已經(jīng)被走過了*/ stack0.row = 1; stack0.col

19、 = 1; stack0.dir = 1; /*第一步的狀態(tài)*/ move0.vert = -1; move0.horiz = 0 ; move1.vert = -1; move1.horiz = 1 ; move2.vert = 0 ; move2.horiz = 1 ; move3.vert = 1 ; move3.horiz = 1 ; move4.vert = 1 ; move4.horiz = 0 ; move5.vert = 1 ; move5.horiz = -1; move6.vert = 0 ; move6.horiz = -1; move7.vert = -1; move7

20、.horiz = -1; initgraph(&gd,&gm,); /* 指定了八個方向*/ /*-* | 主要算法描述: | | 當 stack 不為空,移動到 stack 頂部的位置 | | 試著向各個方向移動，如果可以移動就移動到 | 下一個位置并把它標志成 1。 | | 然后保存狀態(tài)并加入到 stack 中 | | 如果路徑被破壞，或者不存在，就將其刪除 | | 并返回到上一點繼續(xù)遍歷其他方向的點 | | 直到一條路徑被發(fā)現(xiàn)。 | *-*/ while ( top -1 & !found) /*stack 不為空*/ position = delete(&

21、;top); /*刪除 stack 中的元素*/ row = position.row; col = position.col; dir = position.dir;數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告（2017）11 while (dir 8 & !found) next_row = row + movedir.vert; next_col = col + movedir.horiz; if (next_row = EXIT_ROW & next_col = EXIT_COL) found = TRUE; /*發(fā)現(xiàn)路徑*/ else if ( !mazenext_rownext_col &

22、amp; !marknext_rownext_col) /*如果這點沒有被走過并且可以走*/ marknext_rownext_col = 1; /*設(shè)成 1*/ position.row = row; position.col = col; position.dir = +dir; add(&top, position); /*加入到 stack*/ row = next_row; col = next_col; dir = 0; /* 移動到下一個點 */ else +dir; /*嘗試其他方向*/ for(j=1;j=N;j+) for(k=1;k=N;k+) setcolor(WHITE); circle(j*LEN,k*LEN,10); setcolor(MAGENTA); outtextxy(j*LEN-2,k*LEN-2,mazekj?1:0); if (found) /* 如果發(fā)現(xiàn)路徑，則打印出來*/ outtextxy(20,10,The path is:); setcolor(YELLOW); for (i=0; i top;i+) line(stacki.col*LEN, stacki.row*LEN,stacki+1.col*LEN,sta