基于迷宮問題的回溯法求解及算法實(shí)現(xiàn)

畢智超

（陜西職業(yè)技術(shù)學(xué)院,陜西西安,710100)

0 引言

回溯法也稱為試探法。這種方法是按照某種次序?qū)栴}的候選解逐一進(jìn)行列舉和檢驗(yàn)。本文將利用迷宮問題作為實(shí)例，討論回溯法的求解過(guò)程。迷宮問題的提法如下：把一只小白鼠從一個(gè)無(wú)頂蓋的大盒子（迷宮）的入口處趕進(jìn)迷宮。迷宮中設(shè)置了很多墻壁，對(duì)前進(jìn)方向形成了多處障礙。在迷宮的唯一出口處放置了鼠糧，吸引老鼠在迷宮中尋找通路以到達(dá)出口。如果從迷宮的入口到達(dá)出口，途中不出現(xiàn)行進(jìn)方向錯(cuò)誤，則得到一條最佳路線。我們利用回溯法可獲得迷宮從入口到出口的最佳路線。

1 迷宮數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)

針對(duì)上述問題的提出，我們可以給出相應(yīng)設(shè)計(jì)思想。首先對(duì)問題進(jìn)行抽象給出數(shù)學(xué)模型。為此，用一個(gè)二維數(shù)組maze[m+2][p+2]來(lái)表示迷宮，當(dāng)數(shù)組元素maze[i][j]=1時(shí)，表示該位置是墻壁，不能通行：當(dāng)maze[i][j]=0時(shí)，表示該位置是通路。1≤i≤m，1≤j≤p。數(shù)組的第0行，第m+1行，第0列和第p+1列是迷宮的圍墻。如圖1所示。

圖2 可能的前進(jìn)方向

2 算法設(shè)計(jì)思想

在求解迷宮問題的過(guò)程中，當(dāng)沿著某一條路徑一步步走向出口但發(fā)現(xiàn)進(jìn)入死胡同走不通時(shí)，就回溯一步或多步，尋找其他可走的路徑。這就需要回溯。老鼠在迷宮中任一時(shí)刻的位置可用數(shù)組行下標(biāo)i和列下標(biāo)j表示。從maze[i][j]出發(fā)，可能的前進(jìn)方向有8個(gè)，按順時(shí)針方向?yàn)镹[i-1][j]，NE[i-1][j+1]，E[i][j+1]，SE[i+1][j+1]，S[i+1][j]，SW[i+1][j-1]，W[i][j-1],NW[i-1][j-1]。如圖2所示。

設(shè)位置[i][j]標(biāo)記為X，它實(shí)際是一系列交通路口。X周圍有8個(gè)前進(jìn)方向，分別代表8個(gè)前進(jìn)位置。如果某一方向是0值，表示該方向有路可通，否則表示該方向已堵死。為了有效地選擇下一位置，可以將從位置[i][j]出發(fā)可能的前進(jìn)方向預(yù)先定義在一個(gè)表內(nèi)。參看表1，我們稱該表為前進(jìn)方向表(附上程序清單1-前進(jìn)方向表的結(jié)構(gòu)化定義)，它給出向各個(gè)方向的偏移量。

程序清單1 前進(jìn)方向表的結(jié)構(gòu)化定義

struct offsets

{//位置在直角坐標(biāo)下的偏移

int a,b; //a，b是x，y方向的偏移

char *dir; //指針dir指示方向

};offsets move[8]; //所有方向的偏移表

當(dāng)在迷宮中向前試探時(shí)，可根據(jù)表1所示的前進(jìn)方向表，選擇某一個(gè)前進(jìn)方向向前試探。如果該前進(jìn)方向走不通，則在前進(jìn)路徑上回退一步，再嘗試其他的允許方向。

為了防止重走原路，另外設(shè)置一個(gè)標(biāo)志矩陣mark[m+2][p+2],它的所有元素都初始化為0。一旦行進(jìn)到迷宮的某個(gè)位置[i][j]，則將mark[i][j]置為1。下次這個(gè)位置就不能再走了。

3 算法實(shí)現(xiàn)

回溯法解決迷宮問題的遞歸算法參見程序清單2。

程序清單2 解決迷宮問題的遞歸算法實(shí)現(xiàn)

int Seekpath(int x,int y)

{/*從迷宮某一位置[i][j]開始，尋找通向出口[m][p]的一條路徑。如果找到，則函數(shù)返回1。否則函數(shù)返回0。試探的出發(fā)點(diǎn)為[1][1]。*/

int i,g,h;char *d;

if(x==m & & y==p)return 1;//已到達(dá)出口，函數(shù)返回1

for(i=0;i＜8;i++)

{//依次按每一個(gè)方向?qū)ふ彝ㄏ虺隹诘穆窂?/p>

g=x+move[i].a; h=y+move[i].b; d=move[i].dir;

if(maze[g][h]==0 & & mark[g][h]==0)

{//下一個(gè)位置可通，試探該方向

mark[g][h]=1;

if(Seekpath(g,h))

{//從此位置遞歸試探

cout＜＜"("＜＜g＜＜","＜＜h＜＜"),"＜＜"Direction"＜＜dir＜＜",";

return 1;

}

}

//回溯，換一個(gè)方向再試探通向出口的路徑

}

if(x==1 & & y==1)

cout＜＜"no path in maze"＜＜endl;

return 0;

}

為了將遞歸算法改為非遞歸算法，需要使用一個(gè)堆棧來(lái)存儲(chǔ)在試探的過(guò)程中所走過(guò)的路徑。一旦需要回退，可以從棧中取得剛才走過(guò)位置的坐標(biāo)和前進(jìn)方向。棧中需保存一系列三元組以記錄這些信息，這些三元組的結(jié)構(gòu)定義如下：

程序清單3 棧中的三元組結(jié)構(gòu)

struct items

{

int x,y,dir;//位置和前進(jìn)方向序號(hào)

}；

當(dāng)在迷宮中向前試探時(shí)，可能同時(shí)存在幾個(gè)允許的前進(jìn)方向。我們利用三元組記下當(dāng)前位置和上一步前進(jìn)的方向，然后根據(jù)表1所示的前進(jìn)方向表，選擇某一個(gè)允許的前進(jìn)方向前進(jìn)一步，并將活動(dòng)記錄進(jìn)棧，以記下前進(jìn)路徑。如果該前進(jìn)方向走不通，則將位于棧頂?shù)幕顒?dòng)記錄退棧，以在前進(jìn)路徑上回退一步，再嘗試其他的允許方向。如果?？談t表示已經(jīng)回退到開始位置。

因?yàn)閿?shù)組maze中的每個(gè)位置最多只訪問一次，故用來(lái)記錄搜索路徑的棧的大小一般不超過(guò)m*p。若設(shè)棧的大小為m*p，一般不存在棧滿問題。迷宮問題的非遞歸算法如程序清單4所示。

程序清單4 解決迷宮問題的非遞歸算法實(shí)現(xiàn)

void path(int m,int p)

{/*算法輸出迷宮maze中的一條路徑。作為圍墻，maze[0][i]=maze[m+1][i]=maze[j][0]

=maze[j][p+1]=1，0≤i≤p+1，0≤j≤m+1。在算法中用到一個(gè)棧st的重載函數(shù)＜＜，功能是順序輸出棧中的各個(gè)元素。*/

int i,j,d,g,h; mark[1][0]=1;

Stack＜items＞st(m*p);items tmp;

tmp.x=1;tmp.y=0;tmp.dir=2;

st.Push(tmp);

while(st.IsEmpty()==false)

{

st.Pop(tmp);

i=tmp.x;j=tmp.y;d=tmp.dir;

while(d＜8)

{

g=i+move[d].a;h=j+move[d].b;

if(g==m & & h==p)

{

cout＜＜st;

cout＜＜m＜＜" "＜＜p＜＜endl;

return;

}

if(maze[g][h]==0 & & mark[g][h]==0)

{

mark[g][h]=1;

tmp.x=i;tmp.y=j;temp.dir=d;

st.Push(tmp);

i=g;j=h;d=0;

}

else d++;

}

}

cout＜＜"no path in maze"＜＜endl;

}

此程序的內(nèi)部循環(huán)的循環(huán)次數(shù)是固定的，時(shí)間復(fù)雜度為O（1）；假設(shè)maze數(shù)組中零元素的個(gè)數(shù)為n，那么最多有n個(gè)位置可以標(biāo)志，而n≤mp，因此在外層循環(huán)的控制下，內(nèi)部循環(huán)的計(jì)算時(shí)間為 O（m*p）。

4 結(jié)束語(yǔ)

綜上所述，用回溯法求解迷宮問題時(shí)常常使用遞歸方法進(jìn)行試探，或使用棧幫助向前試探和回溯。本文中用遞歸和非遞歸兩種方法詮釋了回溯法解迷宮問題的算法設(shè)計(jì)思想。不僅迷宮問題，許多復(fù)雜的問題，規(guī)模較大的問題都可以使用回溯法求解。這對(duì)于今后其他問題的研究會(huì)有很大幫助。

表1 前進(jìn)方向表move

[1]遇娜.基于迷宮問題的算法新解[J].渭南師范學(xué)院學(xué)報(bào),2011,26(2):66-68.

[2]崔兆順.基于遺傳規(guī)劃的迷宮問題高效求解[J].制造業(yè)自動(dòng)化,2011,33(1),:194-196.

[3]鄧延安.機(jī)器鼠走迷宮的優(yōu)化路徑算法及實(shí)踐[J].蕪湖職業(yè)技術(shù)學(xué)院學(xué)報(bào), 2007, 9(2):37-39.

[4]周蕾.改良填充法實(shí)現(xiàn)和解決迷宮問題[J].電腦知識(shí)與技術(shù),2007,13:186-188.

[5]胡小兵，黃席樾.蟻群算法在迷宮最優(yōu)路徑問題中的應(yīng)用[J].計(jì)算機(jī)仿真.2005，22（4）：115-116.