畢智超

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

0 引言

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

1 迷宮數(shù)據(jù)結構的設計

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

圖2 可能的前進方向

2 算法設計思想

在求解迷宮問題的過程中，當沿著某一條路徑一步步走向出口但發(fā)現(xiàn)進入死胡同走不通時，就回溯一步或多步，尋找其他可走的路徑。這就需要回溯。老鼠在迷宮中任一時刻的位置可用數(shù)組行下標i和列下標j表示。從maze[i][j]出發(fā)，可能的前進方向有8個，按順時針方向為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所示。

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

程序清單1 前進方向表的結構化定義

struct offsets

{//位置在直角坐標下的偏移

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

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

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

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

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

3 算法實現(xiàn)

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

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

int Seekpath(int x,int y)

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

int i,g,h;char *d;

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

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

{//依次按每一個方向尋找通向出口的路徑

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

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

{//下一個位置可通，試探該方向

mark[g][h]=1;

if(Seekpath(g,h))

{//從此位置遞歸試探

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

return 1;

}

}

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

}

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

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

return 0;

}

為了將遞歸算法改為非遞歸算法，需要使用一個堆棧來存儲在試探的過程中所走過的路徑。一旦需要回退，可以從棧中取得剛才走過位置的坐標和前進方向。棧中需保存一系列三元組以記錄這些信息，這些三元組的結構定義如下：

程序清單3 棧中的三元組結構

struct items

{

int x,y,dir;//位置和前進方向序號

}；

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

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

程序清單4 解決迷宮問題的非遞歸算法實現(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。在算法中用到一個棧st的重載函數(shù)＜＜，功能是順序輸出棧中的各個元素。*/

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;

}

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

4 結束語

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

表1 前進方向表move

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

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

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

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

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