回溯算法案例分析

馮建

摘要

回溯算法是《數據結構與算法》課程中介紹的一種廣泛應用的搜索策略算法，本文作者在長期教學實踐中總結出一套實用的回溯算法的框架。本文描述回溯算法的基本思想，分析回溯算法的基本框架，通過案例詳細介紹回溯算法的實現過程，進一步驗證回溯算法程序框架的可行性。對回溯算法的分析總結，有助于加深對回溯算法的理解，提升程序設計的能力。

【關鍵詞】回溯 算法 案例

回溯算法是一種搜索策略算法，是一種從問題的解空間中尋找可行解或最優(yōu)解的一種算法。它廣泛應用于各種軟件系統(tǒng)的開發(fā)。應用回溯算法的經典案例有：獵人過河、分油問題、八皇后問題等。探討回溯算法的基本框架，對加深回溯算法的理解，增強編程興趣，提高編程能力具有重要意義。

獵人過河問題：一個獵人帶一匹狼、一只羊和一捆草來到河邊，河邊有一條小船，只有獵人會撐船，而且小船每次最多只能帶一樣東西過河。當獵人不場時，狼會吃羊，羊會吃草。問獵人該如何過河，才能使狼、羊、草全部安然到達河對岸。

分油問題：現有三件無油量刻度的油瓶，容量分別為10斤、7斤和7斤。其中，10斤容量油瓶裝滿油。如何操作，才能將10斤油平均分成兩份。

1回溯算法的基本思想

獵人過河問題、分油問題都可以歸結為一個結點沿著不同方案擴展為新結點的演變過程。如圖1所示，從初始狀態(tài)（根結點）有若干個方案向子結點擴展，每個子結點又有若干個方案向新的子結點擴展。依此類推，構成樹狀結構圖。

回溯算法尋找目標結點的基本思想是：每次優(yōu)先選擇第一個方案向下擴展，直到新產生的結點不合理或己產生過，再返回上一結點，若此時存在下一個未擴展方案，則選擇下一個方案繼續(xù)依此向下擴展，否則，繼續(xù)回退。直到找到目標結點或所有方案均窮盡為止。

2回溯算法的程序框架

2.1回溯算法的描述

設結點的擴展方案為n個。

（1）從當前結點current Node依次從方案1到方案n嘗試擴展新結點。

（2）每當產生的新結點合理時，就立即從新結點依次從方案1到方案n擴展新結點。

（3）當某結點所有方案均已擴展，并且未找到目標結點，則該結點視為不合理結點。

（4）直到找到目標結點或所有方案擴展完畢為止。

2.2回溯算法的結點結構

以下利用C語言格式的偽代碼描述回溯算法的程序框架。首先，將狀態(tài)值與該狀態(tài)已擴展的路徑編號合在一起，定義成狀態(tài)結點。如圖2所示。

結點結構定義如下：

struct node

{

狀態(tài)值：

int path; //上一次搜索過的路徑編號

};

typedef struct node State;

2.3回溯算法的非遞歸程序框架

對回溯算法的求解，通?？梢允褂眠f歸與非遞歸方式。借助棧的結構，可利用非遞歸方法實現回溯算法，其程序框架如下：

int total_path;//總方案數

State current，new_node;//定義變量

current-初始狀態(tài)值：

current.path=0;//初始，己擴展的方案為

push（current）;//當前結點進棧

while（棧非空）{

currenFpop（）;∥出棧

if（current.path！=total_path）{ //該結點可擴展

current.path++;

push（current）;

∥進棧

new_node=createNew（current）;//擴展新結點

if（new_node==最終目標）{

輸出棧中元素及最終目標。

程序結束;

}

else if（new_node與棧中元素不相同，并且new node是合理的）{

new_node.path=0;

push（new_node）;

}

}

}

2.4回溯算法的遞歸程序框架

回溯算法本質上是深度優(yōu)先搜索，具有明顯的遞歸特征，可利用遞歸的方法來實現。從當前出結點出發(fā)搜索目標結點的函數記為：dfs（State current），程序框架如下：

void dfs（State current）{

if（current==目標結點）

{

打印棧中元素，程序結束。

}

else{

for（i-1;i<-總方案數;i++）{

new_node= createNew（current，i）;∥按方案i擴展新結點

if（new node是合理結點，并且不與棧中元素相同）

{

push（new_node）;∥新結點進棧

dfs（new_node）;//從新結點開始搜索

pop（）;//出棧恢復現場

}

}

}

}

3回溯算法的案例分析

以下利用“獵人過河”案例，描述回溯算法非遞歸程序的具體實現過程。本程序為突出算法框架，省略對?？占皸M判斷等細節(jié)。結構體中h（human）代表人，w（wolf）代表狼，s（sheep）代表羊，g（grass）代表草。狀態(tài)值O表示未過河，1表示己過河。

#define MaxSize 10000

#define total_path 4

struct node

{

int h，w，s，g;//分別代表人、狼、羊、苴

int path; //上一次搜索過的路徑編號

};

typedef struct node State;

struct stackf

State data[MaxSize];

mt top;

};

typedef struct stack Stack;

void push（Stack* s，State current）{//進棧，本處省略棧滿情況

s->top++;

s->data[s->top]=current;

}

State pop（Stack* s）{ //出棧，本處省略棧空情況

State current;

current=s->data[s->top];

s->top--;

return current，

}

State createNew（State current）{//擴展新結點

State newState，

int path=current.path;

newState=current;

newState.path=0;

newState.h=（newState.h+l）%2; //人總要過河

if（path==l） newState.w=（newState.w+1）%2;//人帶狼過河

else if（path==2） newState.s=（newStates+11%2;//人帶羊過河

else if（path==3） newState.g=（newStateg+1）%2; 11人帶草過河

return newState;

//path=4時，只有人過河

}

int reasonable（State st）{

//判斷當前結點是否合理

if《st.w=st.s）&& （st.w！=st.h》 return 0;//人不在，狼吃羊

else if《st.s==st.g）&& （st.s！=st.h》 retumO;//人不在，羊吃草

else return 1：

}

int isSame（Stack* s，State cur）{//判斷當前結點在棧中是否存在

mt1：

State St：

for（i=O;i<=s->top;i++）{

st=s->data[i];

if（st.h==cur.h&&st.w==cur.w&&st.s==cur.s&&st.g==cur.g） return 1;//當前結點以前產生過

}

return 0：

}

void prt（Stack*s）{//打印棧中元素

mt1;

State St：

for（i=O;i<=s->top;i++）{

st=s->data[i];

printf（”（%d，%d，%d，%d）—“，st h，st W，st.s，st g）;//輸出人、狼、羊、草的狀態(tài)

}

}

in main（）{

State current， new_node;//定義變量，goal為目標結點。

Stack s;

s.top=-l;//初始棧為空棧

current.h=0;

current.w=0，

current.s=0;

current.g=0;

current.path=0; //初始，己擴展的方案為O

push（&s，current）;//當前結點進棧

while（s.top！=-l）{//棧非空

current=pop（&s）;∥出棧

if（current.path

current.path++;

push（&s，current）;

//進棧

new_node=createNew（current）;//擴展新結點

if（new_node.h*new_node.w*newnode.s*new_node.g==l）{//找到目標結點

pn（&s）;

printf（"（1，1，1，1）"）;//輸出棧中元素及終點狀態(tài)

retum0：

}

else if《！isSame（&s，new_node》&&reasonable（new_node》{

push（&s，new_node）;

}

}

}

}

程序運行結果按人、狼、羊、草的狀態(tài)輸出。0表示未過河，1表示己過河。運行結果如下： （0，O，O，0）一（1，0，1-o）一（0，0，1，0）一（1，l，1，0）一（O，1，O，0）一（1，1，O，1）一（O，1，0，1）一（1，1，1，1）

上述程序也可利用遞歸的方法來實現，同樣，可以利用回溯算法的程序框架，解決分油問題、八皇后問題等。程序不再贅述。

4結束語

回溯算法是應用較為廣泛的搜索算法，在具體應用中具有較大的改進與優(yōu)化空間。本文提出回溯算法的基本框架，并用實例驗證該框架的有效性。對初學者應用回溯算法解決問題具有借鑒意義。也為后續(xù)進一步學習分枝限界法等其它算法打下良好的基礎。

參考文獻

[1]程香，用回溯算法診斷數據庫性能故障[J].長春師范大學學報，2015，34 （12）：30-34.

[2]高小芳.回溯算法在可視化物流配送最優(yōu)路徑規(guī)劃模擬軟件中的應用[J]，聊城大學學報（自然科學版），2017，30 （04）：101-106.

[3]李志偉，曹陽，張凱，數據結構中八皇后問題的堆棧非遞歸方法的實現研究[J].福建電腦，2012 （02）：115-116.

[4]王永建，鐵小輝，董真等，一種人工智能搜索算法的改進研究[J].通信技術，2017， 50 （02）： 248-254.

[5]申云成，趙莉，顧慶傳，基于C語言的遞歸算法分析[J].福建電腦，2015 （06）：133-134.

[6]任小康，吳尚智，茍平章，基于動態(tài)狀態(tài)樹的回溯算法[J].計算機工程與設計，2007， 28 （04）： 755-756.