[數(shù)據(jù)結(jié)構(gòu)]深度與廣度優(yōu)先搜索：迷宮問題

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)深度與廣度優(yōu)先搜索:迷宮問題數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)深度與廣度優(yōu)先搜索：迷宮問題專業(yè)Xxxxx學(xué)生姓名xxxxxx班級xxxxxxxxx 學(xué)號(hào)xxxxxxxxxxxxxxxx1目錄1 設(shè)計(jì)題目12 設(shè)計(jì)分析13 設(shè)計(jì)實(shí)現(xiàn)34測試方法34.1測試目的84.2 測試輸入84.3 正確輸出94.4 實(shí)際輸出94.5 錯(cuò)誤原因115 分析與探討115.1 測試結(jié)果分析115.2 探討與改進(jìn)116 設(shè)計(jì)小結(jié)11 7 參考文獻(xiàn) 11 設(shè)計(jì)題目 a)迷宮問題求解的目標(biāo)：尋找一條從入口點(diǎn)到出口點(diǎn)的通路。(迷宮可表示為一個(gè)二維平面圖形，將迷宮的左上角作入口，右下角作出口。)例如，可以設(shè)計(jì)一個(gè)8*8矩陣m

2、aze88來表示迷宮，如下所示：0 1 0 0 0 0 1 10 0 0 1 0 0 1 01 0 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 01 0 1 0 0 0 1 11 0 1 1 0 1 0 0左下角maze00為起點(diǎn)，右下角maze77為終點(diǎn)；設(shè)“0”為通路，“1”為墻，既無法穿越。假設(shè)一只老鼠從起點(diǎn)出發(fā)，目的為右下角終點(diǎn)，可向“上、下、左、右、左上、左下、右上、右下”8個(gè)方向行走。b)設(shè)計(jì)程序要求：能自動(dòng)生成或者手動(dòng)生成這樣一個(gè)8*8矩陣；針對這個(gè)矩陣，程序判斷是否能從起點(diǎn)經(jīng)過迷宮走到終點(diǎn)。如果不能，請指出；如果

3、能，請用圖形界面標(biāo)出走出迷宮的路徑。2 設(shè)計(jì)分析a)首先明確題目中的已知條件：·迷宮是一個(gè)8*8大小的矩陣。·從迷宮的左上角進(jìn)入，右下角為迷宮的終點(diǎn)。·mazeij=0代表第i+1行第j+1列的點(diǎn)是通路；mazeij=1代表該點(diǎn)是墻，無法通行。·迷宮有兩種生成方式：手工設(shè)定和自動(dòng)生成。·當(dāng)老鼠處于迷宮中某一點(diǎn)的位置上，它可以向8個(gè)方向前進(jìn)，分別是：“上、下、左、右、左上、左下、右上、右下”8個(gè)方向。·要實(shí)現(xiàn)這個(gè)程序，首先要考慮如何表示這個(gè)迷宮。在實(shí)例程序中使用二維數(shù)組,mazeN+2N+2來表示這個(gè)迷宮，其中N為迷宮的行、列數(shù)。當(dāng)值為

4、“0”時(shí)表示該點(diǎn)是通路，當(dāng)值為“1”時(shí)表示該點(diǎn)是墻。老鼠在迷宮中的位置在任何時(shí)候都可以用行號(hào)row和列號(hào)col表示。b)為什么指定mazeN+2N+2表示迷宮，而不是使用mazeNN來表示迷宮？·原因是當(dāng)老鼠跑到迷宮的邊界點(diǎn)時(shí)就有可能跳出迷宮；而使用mazeN+2N+2就可以把迷宮的外面再包一層“1”，這樣就能阻止老鼠走出格。c)老鼠再每一點(diǎn)都有8種方向可以走，分別是：North，NorthEast,East,SouthEast,East,South,SouthWest,West,NorthWest.可以用數(shù)組move8來表示在每一個(gè)方向上的橫縱坐標(biāo)的偏移量，見表21。根據(jù)這個(gè)數(shù)組，

5、就很容易計(jì)算出沿某個(gè)方向行走后的下一點(diǎn)的坐標(biāo)。Namedir Movedir.vert Movedir.horiz N0-1 0 NE1-1 1 E20 1 SE31 1 S41 0 SW51 -1 W60 -1 NW60 -1 表21 8種方向move的偏移量d)迷宮問題可以用深度優(yōu)先搜索方法實(shí)現(xiàn)。當(dāng)老鼠當(dāng)老鼠在迷宮中移動(dòng)的時(shí)候，可能會(huì)有多種移動(dòng)選擇方向。程序需要記錄并用棧來保存當(dāng)前點(diǎn)的坐標(biāo)，然后任意選取一個(gè)方向進(jìn)行移動(dòng)。由于應(yīng)用棧保存了當(dāng)前通道上各點(diǎn)的坐標(biāo)，所以當(dāng)前各方向上都走不通時(shí)可以返回上一個(gè)點(diǎn)，然后選擇另一個(gè)方向前進(jìn)。·可定義element結(jié)構(gòu)用于存儲(chǔ)每一步的橫縱坐標(biāo)和方向

6、。 typedef struct short int row; short int col; short int dir; element;Element stackMAX _STACK_SIZE;根據(jù)表21可推算出每次移動(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=col+movedir.horiz;·可用另一個(gè)二維數(shù)組markN+2來記錄哪些點(diǎn)已經(jīng)被訪問過。當(dāng)經(jīng)過點(diǎn)mazerowcol時(shí)，相應(yīng)地將markrowcol的值從0置為1。e)本程序支持自動(dòng)生成迷宮。利用r

7、andom(2)函數(shù)可隨機(jī)產(chǎn)生0或1，來支持迷宮的自動(dòng)生成。注意mazeNN和maze11一定要等于0，因?yàn)樗麄兎謩e是起點(diǎn)和終點(diǎn)。f)如果找到了一條走出迷宮的路徑，則需要在屏幕中打印出走出迷宮的信息。這里要用到graphics.h。為畫出效果圖，可使用circle()函數(shù)畫圓，outtexttxy()函數(shù)標(biāo)記文字，并用line()函數(shù)來劃線。g)程序的主要函數(shù)如下：·函數(shù)void add(int*top,element item)，將當(dāng)前步的信息item壓入到作為全局變量的棧stack(棧頂為top)中。·函數(shù)element delete(int * top)，返回stac

8、k中棧頂?shù)脑亍?#183;函數(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)不是終點(diǎn)，則這個(gè)點(diǎn)的上一個(gè)點(diǎn)會(huì)從棧中被跑拋出，從而“回朔”到上一點(diǎn)；當(dāng)遇到終點(diǎn)時(shí)，程序結(jié)束，找到一條路徑；當(dāng)在程序循環(huán)過程中遇到棧為空，則說明該迷宮根本無法走到終點(diǎn)。3 設(shè)計(jì)實(shí)現(xiàn)/*This program can be compiled under VC6.0*/#inclu

9、de <stdio.h>#include <stdlib.h>#include <graphics.h>#include<time.h>#include<conio.h>#define N 8#define MAX_STACK_SIZE N*N/*最大棧容量 */#define TRUE 1#define FALSE 0#define LEN (300/N)/*結(jié)構(gòu)體記錄每一步的橫坐標(biāo)，縱坐標(biāo)和方向*/typedef struct short int row;short int col;short int dir;element;el

10、ement stackMAX_STACK_SIZE;/*結(jié)構(gòu)體記錄水平和垂直的偏移量*/typedef struct short int vert;short int horiz;offsets;offsets move8; /* 8個(gè)方向的move*/int mazeN+2N+2;/*二維數(shù)組記錄迷宮*/int markN+2N+2;/*記錄迷宮中每點(diǎn)是否可到達(dá)*/int EXIT_ROW = N, EXIT_COL = N;/*在棧中加入一個(gè)元素*/void add(int *top, element item)if (*top >= MAX_STACK_SIZE - 1)print

11、f("The stack is full!n");return; stack+*top = item;/*返回棧中頂部的元素*/element delete_top(int *top)if (*top = -1)printf("The stack is empty ! n");exit(1); return stack(*top)-;/*輸出走出迷宮的路徑*/void path(void) int i, j, k, row, col, next_row, next_col, dir, found = FALSE; int gd=VGA; int gm=V

12、GAHI;/*-*|i ->用來循環(huán)計(jì)數(shù) |row , col ->當(dāng)前位置的坐標(biāo) |next_row ->移動(dòng)后的位置的橫坐標(biāo) |next_col ->移動(dòng)后的位置的縱坐標(biāo)|dir ->移動(dòng)的方向 |found ->標(biāo)志路徑是否發(fā)現(xiàn) |*-*/ element position; int top = 0; mark11 = 1; /* maze11已經(jīng)被走過了*/ stack0.row = 1; stack0.col = 1; stack0.dir = 1; /*第一步的狀態(tài)*/ move0.vert = -1; move0.horiz = 0 ; mov

13、e1.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.horiz = -1; initgraph(&gd,&gm,""); /* 指定了八個(gè)方向*/ /*-*

14、 | 主要算法描述: | | 當(dāng)stack不為空,移動(dòng)到stack頂部的位置 | | 試著向各個(gè)方向移動(dòng)，如果可以移動(dòng)就移動(dòng)到 | 下一個(gè)位置并把它標(biāo)志成1。 | | 然后保存狀態(tài)并加入到stack中 | | 如果路徑被破壞，或者不存在，就將其刪除 | | 并返回到上一點(diǎn)繼續(xù)遍歷其他方向的點(diǎn) | | 直到一條路徑被發(fā)現(xiàn)。 | *-*/ while ( top > -1 && !found) /*stack不為空*/ position = delete_top(&top); /*刪除stack中的元素*/ row = position.row; col = posi

15、tion.col; dir = position.dir; 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 && !marknext_rownext_col) /*如果這點(diǎn)沒有被走過并且可以走*/ markne

16、xt_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; /* 移動(dòng)到下一個(gè)點(diǎn) */ else +dir; /*嘗試其他方向*/ for(j=1;j<=N;j+) for(k=1;k<=N;k+) setcolor(WHITE); circle(j*LEN,k*LEN,10); setcolor(MAGENT

17、A); 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,stacki+1.row*LEN); line(stacki.col*LEN, stacki.row*LEN,col*LEN,row

18、*LEN); line(col*LEN, row*LEN,EXIT_COL*LEN,EXIT_ROW*LEN); else outtextxy(20,10,"The maze does not have a path"); /* 否則打印不存在信息*/void main()int i, j, c;srand(time(0);system("cls");for (i=0;i<N+2;i+)maze0i=1;mazei0=1;mazeN+1i=1;mazeiN+1=1; /* 將迷宮的四周設(shè)為1（墻壁） */printf("Would you

19、 like to input the maze by youself?nYes or No?");c = getchar();if(c='Y' | c= 'y') printf("Enter the %d * %d maze:n",N,N); /*手動(dòng)輸入*/for (i=1; i<N+1; i+) for(j=1; j<N+1; j+) scanf("%d",&mazeij); else printf("The maze is created by the computer:n&q

20、uot;); for (i=1; i<N+1; i+) for(j=1; j<N+1; j+) mazeij=rand()%2; mazeNN = 0; maze11 = 0; for(i=1;i<N+1;i+) for(j=1;j<N+1;j+) printf("%3d",mazeij); printf("n"); path(); /* 調(diào)用函數(shù)path() */getch();4測試方法4.1測試目的針對迷宮生成方式不同，本程序的測試分為兩類：手動(dòng)輸入迷宮測試和計(jì)算機(jī)自動(dòng)生成迷宮測試。另外，根據(jù)測試用例不同也可以分為兩類：有解

21、迷宮測試無解迷宮測試。即檢查是否可以自動(dòng)生成或手動(dòng)生成一個(gè)m*n的迷宮，并判斷生成的迷宮圖是否可從入口不經(jīng)過重復(fù)點(diǎn)通過路“0”走向出口。4.2 測試輸入a)按Y或y手動(dòng)生成迷宮矩陣(有解迷宮)：先輸入8*8的矩陣b)按任意鍵自動(dòng)生成迷宮矩陣（有解迷宮）：c) 按任意鍵自動(dòng)生成迷宮矩陣（無解迷宮）：4.3 正確輸出不管是手動(dòng)生成還是自動(dòng)生成迷宮，走數(shù)字為零的點(diǎn)且不經(jīng)過重復(fù)點(diǎn)走向出口。如果沒有通路則失敗。4.4 實(shí)際輸出 a)給出的迷宮路線如圖：b)對于自動(dòng)生成電腦路線（有解迷宮），給出的迷宮路線：c) 對于有些自動(dòng)生成的迷宮（無解迷宮），可能不可以完成走迷宮：4.5 錯(cuò)誤原因走迷宮失敗原因是從入

22、口通向出口的路上被墻“1”給堵住了，則無法走向出口。即沒有一條從入口到出口的通路。5 分析與探討5.1 測試結(jié)果分析 a. 手動(dòng)生成的迷宮圖是由一個(gè)8*8的矩陣構(gòu)成的，這是由最大棧容量MAX_STACK_SIZE決定的，0為路，1為墻，并且可以上、下、左、右、左上、左下、右上、右下行走，且不會(huì)走已經(jīng)走過的點(diǎn)。最終從左上入口點(diǎn)開始到右下出口點(diǎn)結(jié)束。b. 自動(dòng)生成的迷宮圖同樣遵循迷宮行走法則。5.2 探討與改進(jìn)上述的實(shí)驗(yàn)代碼及實(shí)驗(yàn)結(jié)果都是在vc中進(jìn)行的。因?yàn)閠urbo c現(xiàn)在有很多人不用且我習(xí)慣用的是vc，所以我用vc寫。教學(xué)中給的代碼適合在turbo C中進(jìn)行，從源代碼到現(xiàn)在代碼的改進(jìn)以及為完成實(shí)驗(yàn)要求。需先在vc中安裝graphics.h和graphics.lib文件。并修改一些方法如random(2)改成rand()%2，clrscr()改成system(“cls”