多種數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)迷宮問(wèn)題詳解

章麗玲

(湖北第二師范學(xué)院 計(jì)算機(jī)學(xué)院，武漢 430205)

迷宮問(wèn)題是“數(shù)據(jù)結(jié)構(gòu)”課程中經(jīng)典的非數(shù)值型的程序設(shè)計(jì)問(wèn)題，理解迷宮問(wèn)題的不同解決思路，對(duì)掌握《數(shù)據(jù)結(jié)構(gòu)》課程的核心知識(shí)點(diǎn)具有非常重要的意義，本文將采用幾種典型的數(shù)據(jù)結(jié)構(gòu)，利用不同的算法來(lái)實(shí)現(xiàn)迷宮問(wèn)題。

1構(gòu)造迷宮

用一個(gè)二維數(shù)組mg[M+2][N+2]表示迷宮，如圖1所示，M=8，N=8，狀態(tài)為0時(shí)表示對(duì)應(yīng)方塊是通道(可走)，狀態(tài)為1時(shí)表示對(duì)應(yīng)方塊是障礙物(不可走)，為了算法方便，一般迷宮的外圍加一條圍墻。設(shè)定入口為mg[1][1]，出口為mg[8][8]。

圖1 迷宮圖

2 算法思路

求解迷宮問(wèn)題通常采用“窮舉探索求解法”，即從入口出發(fā)，順某一方向向前探索，若能走通，則繼續(xù)往前走，否則沿原路退回(回溯)，換一個(gè)可行的方向再繼續(xù)探索，直至所有可能的通路都探索到為止。為了保證在任何位置上都能原路退回，常用的數(shù)據(jù)結(jié)構(gòu)有棧和隊(duì)列，如果把迷宮中的每一個(gè)位置看作是一個(gè)點(diǎn)的話，那么就可以把迷宮轉(zhuǎn)換為一個(gè)個(gè)相連或分?jǐn)嗟母鱾€(gè)頂點(diǎn)之間的關(guān)系，因此，可以使用另一種數(shù)據(jù)結(jié)構(gòu)——無(wú)向圖來(lái)表示。下面將針對(duì)不同的數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)迷宮問(wèn)題。

2.1 用棧實(shí)現(xiàn)迷宮

棧是一種只能在一端進(jìn)行插入和刪除操作的線性表。允許進(jìn)行插入和刪除操作的一端稱為棧頂(top)，另一端稱為棧底(bottom)。棧的主要特點(diǎn)是后進(jìn)先出，正是棧的這一特點(diǎn)使得它成為解決迷宮問(wèn)題的數(shù)據(jù)結(jié)構(gòu)。

2.1.1 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

采用順序棧實(shí)現(xiàn)迷宮，迷宮棧聲明如下：

typedef struct

{

int i; //當(dāng)前方塊的行號(hào)

int j; //當(dāng)前方塊的列號(hào)

int di; //di是下一相鄰可走方位的方位號(hào)

}Box;

typedef struct

{

Box data[MaxSize]; //棧中每一個(gè)結(jié)點(diǎn)存放i,j,di.

int top;

} StType;

2.1.2 棧實(shí)現(xiàn)的算法設(shè)計(jì)思路

對(duì)于迷宮中的每個(gè)方塊，有上、下、左、右四個(gè)方塊相鄰，如圖2所示，第i行第j列的當(dāng)前方塊的位置記為(i,j)，規(guī)定上方方塊為方位0，并按順時(shí)針?lè)较蜻f增編號(hào)。在試探過(guò)程中，按從方位0到方位3的方向查找下一個(gè)可走的相鄰方塊。為了保證在任何位置上都能沿原路退回(稱為回溯)，需要保存從入口到當(dāng)前位置的路徑上走過(guò)的方塊，若一個(gè)非出口方塊(i,j)是可走的，將它進(jìn)棧，每個(gè)剛剛進(jìn)棧的方塊，其方位di置為-1(表示尚未試探它的周圍)，然后開(kāi)始從方位0到方位3試探這個(gè)棧頂方塊的四周，如果找到某個(gè)方位d的相鄰方塊(i1,j1)是可走的，則將棧頂方塊(i,j)的方位di置為d，同時(shí)將方塊(i1,j1)進(jìn)棧，再繼續(xù)從方塊(i1,j1)做相同的操作。若方塊(i,j)的四周沒(méi)有一個(gè)方位是可走的，將它退棧，繼續(xù)其他的路徑。實(shí)際上，該算法思路是利用棧的后進(jìn)先出的特點(diǎn)，一步一步地查找可走的方塊，直到找到出口為止，該方法類似于圖的深度優(yōu)先搜索方法。

圖2 迷宮方位圖

2.1.3 算法描述

Bool mgpath(int xi,int yi,int xe,int ye) //求解路徑為(xi,yi)->(xe,ye)

{

將入口(xi,yi)進(jìn)棧(其初始方位設(shè)置為-1);

mg[xi][yi]=-1;

while(棧不空)

{

取棧頂方塊(i,j,di);

if((i,j)是出口(xe,ye))

{輸出棧中全部方塊構(gòu)成一條迷宮路徑；

return true;}

查找(i,j,di)的下一個(gè)相鄰可走方塊；

If(找到一個(gè)相鄰可走方塊)

{該方塊為(i1,j1)，對(duì)應(yīng)的方位為d；

將棧頂方塊的di設(shè)置為d;

(i1,j1,-1)進(jìn)棧；

mg[i1][j1]=-1;}

if(沒(méi)有找到(i,j,di)的任何相鄰可走方塊)

{將(i,j,di)出棧；

mg[i][j]=0; }

}

return false;

}

2.2 用隊(duì)列實(shí)現(xiàn)迷宮

隊(duì)列也是一種操作受限的線性表，其限制為僅允許在表的一端進(jìn)行插入操作，而在表的另一端進(jìn)行刪除操作。進(jìn)行插入的一端稱為隊(duì)尾(rear)，進(jìn)行刪除的一端稱為隊(duì)首(front)。隊(duì)列的主要特點(diǎn)為“先進(jìn)先出”，可以利用隊(duì)列的這個(gè)特點(diǎn)來(lái)實(shí)現(xiàn)迷宮問(wèn)題。

2.2.1 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

采用順序隊(duì)列qu保存走過(guò)的方塊，這里不使用循環(huán)隊(duì)列，因?yàn)樵谡业匠隹跁r(shí)需要利用隊(duì)列中的所有方塊查找一條迷宮路徑，因此要求順序隊(duì)列qu有足夠大的空間。

typedef struct

{ int i,j; //方塊的位置

int pre; //本路徑中上一方塊在隊(duì)列中的下標(biāo)

} Box; //方塊類型

typedef struct

{

Box data[MaxSize];

int front,rear; //隊(duì)頭指針和隊(duì)尾指針

} QuType; //順序隊(duì)類型

2.2.2 隊(duì)列實(shí)現(xiàn)算法設(shè)計(jì)思路

首先將入口(xi,yi)進(jìn)隊(duì)，在隊(duì)列qu不為空時(shí)循環(huán)，出隊(duì)一個(gè)方塊e，其下標(biāo)為front，然后查找方塊e的所有相鄰可走方塊，假設(shè)e1和e2兩個(gè)方塊，將它們進(jìn)隊(duì)，它們?cè)陉?duì)列中的位置分別是rear1和rear2，并且將他們的pre均設(shè)置為front，當(dāng)找到出口時(shí)，通過(guò)出口方塊的pre值前推找到入口，所有經(jīng)過(guò)的中間方塊構(gòu)成一條迷宮路徑。實(shí)際上，該算法思路是利用隊(duì)列的特點(diǎn)，一層一層向外擴(kuò)展查找可走的方塊，直到找到出口為止，該方法類似于圖的廣度優(yōu)先搜索方法。

2.2.3 算法描述

Bool mgpath1(int xi,int yi,int xe,int ye)

{

將入口(xi,yi)的pre置為-1并進(jìn)隊(duì)；

mg[xi][yi]=-1;

while(隊(duì)列qu不空)

{出隊(duì)一個(gè)方塊e，其在隊(duì)列中的位置是front;

if(方塊e是出口)

{ 輸出一條路徑; return true;}

for(對(duì)于方塊e的所有相鄰可走方塊e1)

{ 設(shè)置e1的pre為front;

將方塊e1進(jìn)隊(duì)；

將方塊e1的迷宮數(shù)組值設(shè)置為-1;}

}

return false;

}

2.3 用圖搜索方法實(shí)現(xiàn)迷宮

圖都是由頂點(diǎn)和邊構(gòu)成的，可以把迷宮圖中的每一個(gè)方塊看成一個(gè)頂點(diǎn)，方塊和方塊之間的連通性看出頂點(diǎn)與頂點(diǎn)的邊，因此，可以把迷宮問(wèn)題看成圖的問(wèn)題，可采用圖的深度優(yōu)先搜索和廣度優(yōu)先搜索算法來(lái)求解迷宮問(wèn)題。

2.3.1 圖的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

常用的圖的存儲(chǔ)結(jié)構(gòu)有鄰接矩陣和鄰接表。這里采用鄰接表比較好，因此首先需要將迷宮圖的二維矩陣轉(zhuǎn)化為對(duì)應(yīng)的鄰接表，其思路為：一個(gè)方塊看成一個(gè)頂點(diǎn)，編號(hào)為(i,j)，根據(jù)周圍4個(gè)方向狀態(tài)為0的方塊建立鄰接表，鄰接表的頭結(jié)點(diǎn)是一個(gè)二維數(shù)組。對(duì)應(yīng)的鄰接表類型聲明如下：

typedef struct Anode

{ int i,j;

Struct Anode *nextarc;

} ArcNode; //邊節(jié)點(diǎn)類型

typedef struct Vnode

{ ArcNode *firstarc; //指向第一個(gè)相鄰可走方塊

} VNode; //頭結(jié)點(diǎn)

typedef struct

{ VNode adjlist[M+2][N+2];

} AdjGrapgh;

Typedef struct

{ int i;

Int j;

} Box; //定義方塊

Typedef struct

{ Box data[MaxSize];

Int length;

} PathType; //定義路徑類型

鄰接表的表頭用一個(gè)二維數(shù)組adjlist表示,adjlist[i][j]僅含有一個(gè)firstarc指針，它指向方塊(i,j)的四周可走方塊構(gòu)成的一個(gè)單鏈表，圖一對(duì)應(yīng)的迷宮鄰接表如圖3所示。

圖3 迷宮鄰接表

2.3.2 算法設(shè)計(jì)

在搜索迷宮路徑時(shí)可以采用DFS(深度優(yōu)先搜索)或者BFS(廣度優(yōu)先搜索)算法，將訪問(wèn)標(biāo)記數(shù)組改為visited[M+2][N+2]，入口作為初始頂點(diǎn)，結(jié)束條件為找到出口。下面算法采用的深度優(yōu)先搜索算法求(xi,yi)到(xe,ye)的所有路徑。

Void FindPath(AdjGraph *G,int xi,int yi,int xe,int ye,PathType path)

{ ArcNode *p;

visited[xi][yi]=1; //入口置已訪問(wèn)標(biāo)記

入口加入路徑，并將路徑長(zhǎng)度加一

If(xi==xe && yi==ye) //找到出口

{ 輸出迷宮路徑； }

p=G->adjlist[xi][yi].firstarc;//p指向頂點(diǎn)v的第一條邊頂點(diǎn)

//采用遞歸的方法深度優(yōu)先搜索

while(p!=null)

{ if(visited[p->i][p->j]==0)

FindPath(G,p->i,p->j,xe,ye,path);

P=p->nextarc;

}

visited[xi][yi]=0;

}

3 小結(jié)

線性表、棧、隊(duì)列、遞歸、圖、深度優(yōu)先搜索(DFS)和廣度優(yōu)先搜索(BFS)屬于“數(shù)據(jù)結(jié)構(gòu)”課程的核心知識(shí)點(diǎn)，他們既是教學(xué)重點(diǎn)，又屬于教學(xué)難點(diǎn)，然而，通過(guò)求解迷宮問(wèn)題，可以把這些知識(shí)點(diǎn)串在一起，使學(xué)生能夠靈活地應(yīng)用線性表解決實(shí)際問(wèn)題，分清棧和隊(duì)列應(yīng)用的區(qū)別，為了拓展學(xué)生的邏輯思維，將迷宮問(wèn)題描述成圖的搜索問(wèn)題，可采用深度優(yōu)先搜索的遞歸思想和廣度優(yōu)先搜索的非遞歸思想來(lái)實(shí)現(xiàn)。總之，采用多種數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)迷宮問(wèn)題可大大提高學(xué)生對(duì)數(shù)據(jù)結(jié)構(gòu)核心知識(shí)點(diǎn)的理解深度，提高學(xué)生對(duì)迷宮算法的多維性理解能力。