數(shù)據(jù)結構實驗-迷宮問題

1、實驗報告實驗課名稱：數(shù)據(jù)結構實驗實驗名稱：迷宮問題班級：20130613學號：16姓名：施洋時間：2015-5-18一、問題描述這是心理學中的一個經(jīng)典問題。心理學家把一只老鼠從一個無頂蓋的大盒 子的入口處放入，讓老鼠自行找到出口出來。迷宮中設置很多障礙阻止老鼠前行， 迷宮唯一的出口處放有一塊奶酪，吸引老鼠找到出口。簡而言之，迷宮問題是解決從布置了許多障礙的通道中尋找出路的問題。本題設置的迷宮如圖1所示。迷宮四周設為墻；無填充處，為可通處。設每個點有四個可通方向，分別為東、 南、西、北。左上角為入口。右下角為出口。迷宮有一個入口，一個出口。設計 程序求解迷宮的一條通路。二、數(shù)據(jù)結構設計以一個mK

2、 n的數(shù)組mg表示迷宮，每個元素表示一個方塊狀態(tài)，數(shù)組元素 0和1 分別表示迷宮中的通路和障礙。迷宮四周為墻，對應的迷宮數(shù)組的邊界元素均為 1。根據(jù)題目中的數(shù)據(jù)，設置一個數(shù)組mg如下int mgM+2N+2=1,1,1,1,1,1,1,1,1,0,0,1,0。0,1,1,1,0。0,1,1,1,1,0,0,1,0。0,1,1,0,0。0。0,1,1,1,1,1,1,1,1,1；在算法中用到的棧采用順序存儲結構，將棧定義為Struct int i; / 當前方塊的行號int j; / 當前方塊的列號int di; /di是下一個相鄰的可走的方位號stMaxSize;/ 定義棧int top=-1

3、 /初始化棧三、算法設計要尋找一條通過迷宮的路徑，就必須進行試探性搜索，只要有路可走就前進 一步，無路可進，換一個方向進行嘗試；當所有方向均不可走時，則沿原路退回 一步（稱為回溯），重新選擇未走過可走的路，如此繼續(xù)，直至到達出口或返回 入口（沒有通路）。在探索前進路徑時，需要將搜索的蹤跡記錄下來，以便走不 通時，可沿原路返回到前一個點換一個方向再進行新的探索。后退的嘗試路徑與 前進路徑正好相反，因此可以借用一個棧來記錄前進路徑。方向：每一個可通點有4個可嘗試的方向，向不同的方向前進時，目的地的 坐標不同。預先把4個方向上的位移存在一個數(shù)組中。如把上、右、下、左（即 順時針方向）依次編號為0、1

4、、2、3.其增量數(shù)組move4如圖3所示。-1001100-1move4 01 23x y圖2數(shù)組move4(i-i, j)方位o方位3方位I o方位示意圖如下:Q+LJ）方位2圖3.方位圖通路：通路上白每一個點有3個屬性：一個橫坐標屬性i、一個列坐標屬性 j和一個方向屬性di ,表示其下一點的位置。如果約定嘗試的順序為上、右、下、 左（即順時針方向），則每嘗試一個方向不通時，di值增1,當d增至4時，表 示此位置一定不是通路上的點，從棧中去除。在找到出口時，棧中保存的就是一 條迷宮通路。(1)下面介紹求解迷宮(xi,yj )到終點(xe,ye )的路徑的函數(shù)：先將入口進 棧(其初始位置設置為

5、一1),在棧不空時循環(huán)一一取棧頂方塊(不退棧)若該 方塊為出口，輸出所有的方塊即為路徑，其代碼和相應解釋如下：int mgpath(int xi,int yi,int xe,int ye)/ 求 解 路 徑為:(xi,yi)->(xe,ye)structint i;/當前方塊的行號int j;/當前方塊的列號int di;/di是下一可走方位的方位號 stMaxSize;/ 定義棧int top=-1;/初始化棧指針int i,j,k,di,find;top+;/初始方塊進棧sttop.i=xi;sttop.j=yi;sttop.di=-1;mg11=-1;while (top>-

6、1)/棧不空時循環(huán)i=sttop.i;j=sttop.j;di=sttop.di; /取棧頂方塊if (i=xe && j=ye)/找到了出口，輸出路徑printf("迷宮路徑如下：n");for (k=0;k<=top;k+)printf("t(%d,%d)",stk.i,stk.j);if (k+1)%5=0)/每輸出每5個方塊后換一行printf("n");printf("n");return(1); /找到一條路徑后返回1否則，找下一個可走的相鄰方塊若不存在這樣的路徑，說明當前的路徑不

7、可能走通，也就是恢復當前方塊為0后退棧。若存在這樣的方塊，則其方位保存在棧頂元素中，并將這個可走的相鄰方塊進棧(其初始位置設置為-1)求迷宮回溯過程如圖4所示_回國挑線查找其他路往基4迷宮工-4:It程示堂圖相鄰可走方塊，若沒有這樣則從當前方塊回溯到前從前一個方塊找到相鄰可走方塊之后， 再從當前方塊找在、 的方快，說明當前方塊不可能是從入口路徑到出口路徑的一個方塊, 一個方塊，繼續(xù)從前一個方塊找可走的方塊。為了保證試探的可走的相鄰方塊不是已走路徑上的方塊，如（ i,j）已經(jīng)進棧，在試探（i+1 , j）的下一方塊時，又試探道（i, j）,這樣會很悲劇的引起死循環(huán)，為此，在一個方 塊進棧后，將對

8、應的 mg數(shù)組元素的值改為-1 （變?yōu)椴豢勺叩南噜彿綁K），當退棧時（表示 該方塊沒有相鄰的可走方塊），將其值恢復0,其算法代碼和相應的解釋如下：find=0;while (di<4 && find=0)找下一個可走方塊di+;switch(di)case 0:i=sttop.i-1;j=sttop.j;break;case 1:i=sttop.i;j=sttop.j+1;break;case 2:i=sttop.i+1;j=sttop.j;break;case 3:i=sttop.i,j=sttop.j-1;break;if (mgij=0) find=1;/找到下一個可

9、走相鄰方塊if (find=1)找到了下一個可走方塊sttop.di=di;修改原棧頂元素的 di值top+;下一個可走方塊進棧sttop.i=i;sttop.j=j;sttop.di=-1;mgij=-1;避免重復走到該方塊else 沒有路徑可走，則退棧mgsttop.isttop.j=0;/ 讓該位置變?yōu)槠渌窂娇勺叻綁K top-;將該方塊退棧 return(0); 表示沒有可走路徑，返回0 (2)求解主程序 建立主函數(shù)調(diào)用上面的算法，將mg和st棧指針定義為全局變量void main() mgpath(1,1,M,N);四、界面設計設計很簡單的界面，輸出路徑。五、運行測試與分析圖5.基本

10、運行結果六、實驗收獲與思考思考：8個方向的問題1.設計思想(1)設置一個迷宮節(jié)點的數(shù)據(jù)結構。建立迷宮圖形。(3)對迷宮進行處理找出一條從入口點到出口點的路徑。輸出該路徑。（5）打印通路迷宮圖。圖6功能結構圖當迷宮采用二維數(shù)組表示時，老鼠在迷宮任一時刻的位置可由數(shù)組的行列序 號i, j來表示。而從i,j位置出發(fā)可能進行的方向見下圖 7.如果i,j周圍的位 置均為0值，則老鼠可以選擇這8個位置中的任一個作為它的下一位置。將這 8 個方向分別記作：E （東）、SE （東南）、S （南）SW （西南）W （西）、NW （西 北）、N （北）和NE （東北）。但是并非每一個位置都有8個相鄰位置。如果i,

11、j 位于邊界上，即i=1 ,或i=m,或j=1,或j=n ,則相鄰位置可能是3個或5個為 了避免檢查邊界條件，將數(shù)組四周圍用值為1的邊框包圍起來，這樣二維數(shù)組maze應該聲明為mazem+2,n+2在迷宮行進時，可能有多個行進方向可選，我 們可以規(guī)定方向搜索的次序是從東（E）沿順時針方向進行。為了簡化問題，規(guī) 定i,j的下一步位置的坐標是x,y,并將這8個方位傷的x和y坐標的增量預 先放在一個結構數(shù)組 move8中（見圖8）。該數(shù)組的每個分量有兩個域 dx和dy。 例如 要向東走，只要在j值上加上dy,就可以得到下一步位置的x,y值為i,j+dy。于是搜索方向的變化只要令方向值dir從0增至7

12、,便可以從move數(shù)組中得到從i,j點出發(fā)搜索到的每一個相鄰點x,yx=i+movedir.dxy=j+movedir.dy但1P1J1.0+-1*g-Ip-1P-2 Jp-1*5:6-I*3圖8向量差圖為了防止重走原路，我們規(guī)定對已經(jīng)走過的位置，將原值為 0改為-1,這既 可以區(qū)別該位置是否已經(jīng)走到過， 又可以與邊界值1相區(qū)別。當整個搜索過程結 束后可以將所有的-1改回到0,從而恢復迷宮原樣。這樣計算機走迷宮的方法是：采取一步一步試探的方法。每一步都從（E）開始，按順時針對8個方向進行探測，若某個方位上的mazex,y=0 ,表示可以 通行，則走一步；若mazex,y=1 ,表示此方向不可通

13、行須換方向再試。直至 8 個方向都試過，mazex,y均為1,說明此步已無路可走，需退回一步，在上一 步的下一個方向重新開始探測。為此需要設置一個棧，用來記錄所走過的位置和 方向（i, j, dir）。當退回一步時，就從棧中退出一個元素，以便在上一個位置的下一個方向上 探測，如又找到一個行進方向，則把當前位置和新的方向重新進棧， 并走到新的 位置。如果探測到x=m, y=n,則已經(jīng)到達迷宮的出口，可以停止檢測，輸出存 在棧中的路徑；若在某一位置的8個方向上都堵塞，則退回一步，繼續(xù)探測，如 果已經(jīng)退到迷宮的入口（棧中無元素），則表示此迷宮無路徑可通行。2系統(tǒng)算法（偽代碼描述）：(1)建立迷宮節(jié)點

14、的結構類型 stack口入迷宮圖形0表示可以通1表示不可以通。用二維數(shù)組mazem+2n+2 進行存儲。數(shù)組四周用1表示墻壁，其中入口點(1,1)與出口點(m, n)固定。(3)函數(shù)path()對迷宮進行處理，從入口開始：While(!(s->top=-1)&&(dir>=7)|(x=M)&&(y=N)&&(mazexy=-1)For(掃描八個可以走的方向)If(找到一個可以走的方向)進入棧標志在當前點可以找到一個可以走的方向避免重復選擇mazexy=-1不再對當前節(jié)點掃描If(八個方向已經(jīng)被全部掃描過，無可以通的路)標志當前節(jié)點沒有

15、往前的路后退一個節(jié)點搜索If(找到了目的地)輸出路徑退出循環(huán)未找到路徑#define N2 11#define maxlen M2 / 棧長度#include <stdio.h>#include<iostream.h>#include <malloc.h>int M=M2-2,N=N2-2;/M*N迷宮的大小typedef struct /定義棧元素的類型int x,y,dir;elemtype;typedef struct / 定義順序棧elemtype stack maxlen;int top;sqstktp;struct moved定義方向位移數(shù)組的元

16、素類型對于存儲坐標增量的方向位移數(shù)組move int dx,dy;/void inimaze(int maze口N2)/ 初始化迷宮int i,j,num;for(i=0,j=0;i<=M+1;i+) 設置迷宮邊界mazeij=1;for(i=0,j=0;j<=N+1;j+)mazeij=1;for(i=M+1,j=0;j<=N+1;j+)mazeij=1;cout<<"原始迷宮為："<<endl;for(i=1;i<=M;i+)for (j=1;j<=N;j+)num=(800*(i+j)+1500) % 327;/

17、根據(jù) MN 的值產(chǎn)生迷宮if (num<150)&&(i!=M|j!=N) mazeij=1;elsemazeij=0;cout<<mazeij<<""，顯示迷宮cout<<endl;cout<<endl;/inimazeIllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll void inimove(struct moved move)l

18、l 初始化方向位移數(shù)組 ll 依次為 East., Southeast, south, southwest, west, northwest, north, northeast move0.dx=0;move0.dy=1; move1.dx=1;move1.dy=1; move2.dx=1;move2.dy=0; move3.dx=1;move3.dy=-1; move4.dx=0;move4.dy=-1; move5.dx=-1;move5.dy-=1; move6.dx=-1;move6.dy=0; move7.dx=-1;move7.dy=1; ll void inistack(sqst

19、ktp *s)l* 初始化棧 *l s->top=-1; l*inistack*lint push(sqstktp*s,elemtype x) if(s->top=maxlen-1) return(false); else s->stack+s->top=x;l*棧不滿，執(zhí)行入棧操作*lreturn(true); l*push*l elemtype pop(sqstktp *s)l* 棧頂元素出棧 *l elemtype elem; if(s->top<0)如果?？?，返回空值 elem.x=NULL; elem.y=NULL; elem.dir=NULL;

20、return(elem); else s->top-; return(s->stacks->top+1);棧不空，返回棧頂元素 llpop llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll void path(int mazeN2,struct moved move,sqstktp *s)尋找迷宮中的條通路 ( int i,j,dir,x,y,f; elemtype elem; i=1;j=1;dir=0; maze11=-1; 設11為入口處 do ( x

21、=i+movedir.dx;/球下一步可行的到達點的坐標 y=j+movedir.dy; if(mazexy=0) ( elem.x=i;elem.y=j;elem.dir=dir; f=push(s,elem);/如果可行將數(shù)據(jù)入棧 if(f=false)如果返回假，說明棧容量不足 cout<<"棧長不足"i=x;j=y;dir=0;mazexy=-1; elseif (dir < 7) dir+; else ( elem=pop(s); /8個方向都不行，回退 if(elem.x!=NULL) ( i=elem.x; j=elem.y; dir=ele

22、m.dir+1; while(!(s->top=-1)&&(dir>=7)|(x=M)&&(y=N)&&(mazexy=-1);/循環(huán)if(s->top=-1)/若是入口，則無通路 cout<<"此迷宮不通" else ( elem.x=x; elem.y=y; elem.dir=dir;/將出口坐標入棧 f=push(s,elem); cout<<"迷宮通路是："<<endl; i=0; while (i <= s->top) ( cout

23、<<"("<<s->stacki.x<<","<<s->stacki.y<<")"/ 顯示迷宮通路 if(i!=s->top) cout<<"->"if(i+1)%4=0) cout<<endl; i+； / void draw(int mazeN2,sqstktp *s)在迷宮中繪制出通路 cout<<"逃逸路線為："<<endl; int i,j； elemtype elem; for(i=1;i<=M;i+)將迷宮中全部的-1值回復為0值 for(j=1;j<=N;j+) if(maze