回溯法在計算機程序設(shè)計中的應(yīng)用
2017-12-11 14:32:54裴南平畢傳林
電腦知識與技術(shù) 2017年31期
裴南平 畢傳林
摘要：回溯法是計算機程序設(shè)計中經(jīng)常使用的一種算法。為了在更好的理解和應(yīng)用回溯法，從人們熟知的窮舉法入手，層層展開，逐步過渡到回溯法，并分析回溯法中擴展、回溯、調(diào)整三個關(guān)鍵步驟，理解回溯法的運行過程，建立回溯法算法，從而使用回溯法解決程序設(shè)計中的實際問題。
關(guān)鍵詞：回溯法；窮舉法；算法模型
中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2017）31-0262-03
Application of Backtracking Method in Computer Programming
PEI Nan-ping， BI Chuan-lin
（Jiujiang Vocational and Technical College， Jiujiang 332007， China）
Abstract： Backtracking is one of the most frequently used programming algorithms in computer programming. In order to better understand and use backtracking in the program design. We start with the exhaustive method and gradually use backtracking to implement it， We analyzed three key steps of extension， backtracking and adjustment， establish backtracking algorithm model and use backtracking in program design.
Key words： backtracking method； exhaustive method； algorithm model
回溯法，又稱試探法，是計算機程序設(shè)計中經(jīng)常使用的一種算法，在實際中，有著廣泛的應(yīng)用。但是對于初學者又是一個比較難于理解的高級算法，如何在計算機程序設(shè)計中得心應(yīng)手的使用回溯法呢？我們從大家很容易理解的窮舉法展開，逐步過渡到回溯法的實現(xiàn)，詳細分析回溯法中中擴展、回溯、調(diào)整等三個關(guān)鍵步驟，幫助程序員設(shè)計人員理解回溯法的運行過程，建立回溯法算法模型，并在實際程序設(shè)計使用此方法。
1 回溯法模型
回溯法是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達到目標。但當探索到某一步時，發(fā)現(xiàn)原先選擇并不優(yōu)或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術(shù)為回溯法。
用回溯法求解問題規(guī)模有n層的所有解，其中m（0<=m<=n-1）是當前求解問題的層數(shù)。算法模型如下：
m=0； /* 當前從第0層開始 */
設(shè)置第0層的初始數(shù)據(jù)；
while（1）
if（第m層數(shù)據(jù)沒有越界 && 當前規(guī)模m符合解的所有條件）
if（m==n-1） /* 已達到問題要求解的規(guī)模 */
{
輸出一個解；
調(diào)整第m層到下一個數(shù)據(jù)；
}
else { /* 當前還沒有達到問題要求解的規(guī)模 */
m++； /*擴展到下一層 */
設(shè)置第m層初始數(shù)據(jù)；
}
else if（第m層數(shù)據(jù)越界）
{
if（m==0） /* 窮舉完畢，跳出循環(huán)結(jié)束程序 */
break；
m—； /* 回溯到上一層 */
調(diào)整第m層到下一個數(shù)據(jù)；
}
else 調(diào)整第m層到下一個數(shù)據(jù)； /* 當前數(shù)據(jù)沒有越界 */
該算法模型對于有經(jīng)驗的程序員是不難理解的，但對于初學者就有點茫然了，其動態(tài)運行過程更難想象。下面用一個簡單的示例，先用容易理解的窮舉法解決，逐步遞推，過渡到回溯法的思路。
2 程序舉例
問題：
從1至k的自然數(shù)字中取n個數(shù)字，組合成一個新的數(shù)值，輸出所有的組合數(shù)值。例如：k=5，n=3也就是從1至5中5個數(shù)字取3個數(shù)字，其所有的組合數(shù)如下：
123 124 125 132 134 135 142 …… 512 513 514 521 523 524 531 532 534 541 542 543。共60個解。
為了描述方便，下面所有程序設(shè)定k=8，n=5。當然可以修改程序中的常量為任意值。首先使用窮舉法來解決這個問題。
3 最簡單的窮舉法程序
k=8，n=5。從1至8中取5個數(shù)字，輸出所有的組合數(shù)值。程序如下：
#include
#define K 8
#define N 5
void main（）
{
int a0，a1，a2，a3，a4；
int total； /*解的總數(shù) */
total=0；
for（a0=1；a0<=K；a0++）
for（a1=1；a1<=K；a1++）
for（a2=1；a2<=K；a2++）
for（a3=1；a3<=K；a3++）
for（a4=1；a4<=K；a4++）
if（a1！=a0&&a2！=a0&&a2！=a1&&a3！=a0&&a3！=a1&&a3！=a2&&a4！=a0&&a4！=a1&&a4！=a2&&a4！=a3）
{
total++；
printf（"第%d個解： "，total）；
printf（"%d%d%d%d%d＼n"，a0，a1，a2，a3，a4）；
}
printf（"解的總數(shù)=%d＼n"，total）；
}
從1至8中取5個數(shù)字，每個數(shù)字的范圍都是1至8，因為每個數(shù)字只能取一次，所以取得的5個數(shù)字互不相同。程序中一個數(shù)字從1至8一層循環(huán)，5重循環(huán)包含了所有的取值。這個窮舉法的程序是很好理解的，其運行過程就是從11111至88888之間的所有的5位數(shù)值排列組合中輸出5位數(shù)字互不相同的數(shù)值。不過程序中有一些肯定不是解的排列組合，例如a0=1，a1=1時，由于a0和a1取的數(shù)字相同，一個數(shù)字不能取二次，后面a2、a3、a4三層循環(huán)不需要運行，其排列組合肯定不是解。
4 用數(shù)組元素作為循環(huán)變量的窮舉法程序
#include
#define K 8
#define N 5
void main（）
{
int a[N]；
int total； /*解的總數(shù) */
total=0；
for（a[0]=1；a[0]<=K；a[0]++）
for（a[1]=1；a[1]<=K；a[1]++）
if（a[1]==a[0]） continue；
else for（a[2]=1；a[2]<=K；a[2]++）
if（a[2]==a[0]||a[2]==a[1]） continue；
else for（a[3]=1；a[3]<=K；a[3]++）
if（a[3]==a[0]||a[3]==a[1]||a[3]==a[2]） continue；
else for（a[4]=1；a[4]<=K；a[4]++）
if（a[4]==a[0]||a[4]==a[1]||a[4]==a[2]||a[4]==a[3]）
continue；
else {
total++；
printf（"第%d個解： "，total）；
printf（"%d%d%d%d%d＼n"，a[0]，a[1]，a[2]，a[3]，a[4]）；
}
printf（"解的總數(shù)=%d＼n"，tota l）；
}
這個程序與上一個沒有多大差別，之所以定義數(shù)組元素作為循環(huán)變量是為后面采用回溯法程序進行設(shè)計。
窮舉法是應(yīng)用最廣的算法，可以解決很多問題，也是容易理解和掌握的算法，但也有一些不足之處。受語言編譯系統(tǒng)的限制，循環(huán)嵌套的重數(shù)不能太多；即使沒有限制，循環(huán)嵌套重數(shù)太多，代碼書寫也無法層次展開。這對于規(guī)模較大，層數(shù)較多的問題就無法使用窮舉法。本文討論的自然數(shù)1至k中取n個數(shù)，n超過6用窮舉法就不適合了，這是可以采用回溯法。
回溯法其實是一種變化的窮舉法。從某種意義說，所有的算法都是窮舉法，都是利用計算機強大快速的計算能力處理所有的情況?；厮莘ㄓ绕涿黠@，下面將要給出的回溯法程序與現(xiàn)在分析的窮舉法程序思路和運行過程幾乎一模一樣。為了對應(yīng)理解，將本程序幾個關(guān)鍵的地方用回溯法的術(shù)語描述一下。
從1至k中取n個數(shù)字，取一個數(shù)字一層，問題的規(guī)模有n層，分別是第0層、第1層、第2層、...、第n-1層。
n層規(guī)模對應(yīng)n重循環(huán)。
a[0]控制的循環(huán)是第0層，a[0]保存的值是從1至k中取的第1個數(shù)字；
a[1]控制的循環(huán)是第1層，a[1]保存的值是從1至k中取的第2個數(shù)字；
a[2]控制的循環(huán)是第2層，a[2]保存的值是從1至k中取的第3個數(shù)字；
......
a[n-1]控制的循環(huán)是第n-1層，a[n-1]保存的值是從1至k中取的第n個數(shù)字，這一層是最后一層；
本層循環(huán)進入下一層循環(huán)，回溯法稱為“擴展”；
本層循環(huán)結(jié)束，回退到上一層循環(huán)，回溯法稱為“回溯”；
本層循環(huán)if語句判斷循環(huán)變量（本層取的數(shù)字）與上幾層循環(huán)變量相同，取值非法，continue控制循環(huán)變量加1，繼續(xù)下一次循環(huán)，回溯法稱為“調(diào)整”。
5 回溯法程序
#include
#define K 8
#define N 5
int a[N]； /* 從1至K中取N個自然數(shù)，保存到數(shù)組a的N個元素中 */
int total； /* 解的總數(shù) */
void output（） /*輸出一個解 */
{
int i；
printf（"第%d個解： "，total）；
for（i=0；i printf（"%d"，a[i]）； printf（"＼n"）； } int right（int m） /* 判斷第m層是否符合條件，是返回1，否則返回0。 */ { int i； /* 判斷第m層取的數(shù)字與前面取的數(shù)字是否相同 */ for（i=0；i if（a[i]==a[m]） return 0； return 1； } void search（） /* 回溯法搜索所有解 */ { int m； m=0； /* 當前從第0層開始 */ a[m]=1； /* 設(shè)置第0層初始取的數(shù)字從1開始 */ while（1） if（a[m]<=K && right（m）==1） /*第m層數(shù)字沒有越界并且規(guī)模m符合條件*/ if（m==N-1） /* 已經(jīng)達到要求解的規(guī)模 */ { total++； /* 解的總數(shù)加1 */ output（）； /* 輸出一個解 */ a[m]++； /*調(diào)整第m層數(shù)字到下一個數(shù)字 */ } else { m++； /* 擴展到下一層 */ a[m]=1； /*設(shè)置第m層初始數(shù)字從1開始 */ } else if（a[m]>=K） /* 第m層數(shù)字超過K越界 */ { if（m==0） /* 窮舉完畢，跳出循環(huán)結(jié)束程序 */ break； m—； /* 回溯到上一層 */ a[m]++； /* 調(diào)整第m層數(shù)字到下一個數(shù)字 */ } else a[m]++； /* 沒有越界，調(diào)整第m層數(shù)字到下一個數(shù)字 */ } void main（） { total=0； printf（"求解開始，請稍候。＼n"）； search（）； printf（"解的總數(shù)=%d＼n"，total）； printf（"求解結(jié)束。＼n"）； } 為了突出回溯法的核心部分，也為以后解決復雜問題鋪墊，程序分解成幾個函數(shù)。函數(shù)output（）是輸出一個解；函數(shù)right（int m）是判斷當前第m層的規(guī)模是否符合解的所有的條件，也就是當前所有的取值是否合法；程序回溯法的主體部分也設(shè)計成一個函數(shù)search（），這里只解析回溯法的核心部分，其他的細枝末節(jié)就不再贅述。 函數(shù)search（）的運行過程基本與上面窮舉法程序一模一樣，雖然表面是一個單重循環(huán)，其實是n層循環(huán)嵌在其中。m是當前的層數(shù)，首先m=0，從第0層開始循環(huán)；當前第m層取的數(shù)字沒有超過k越界，并且當前第m層規(guī)模所有取的數(shù)字合法，m++，進入到下一層，也就是“擴展”，當m到了n-1最后一層，就不需要擴展，當前是一個合法的解，輸出這個解后，a[m]++，當前層取下一個數(shù)字，也就是“調(diào)整”。否則，當前層取的數(shù)字超過k越界，m—，退回到上一層，調(diào)整該層取的數(shù)字，也就是“回溯”，如果已經(jīng)退回到第0層，就不能再回溯，這時已經(jīng)將所有取的數(shù)字排列組合窮舉完畢，跳出死循環(huán)，結(jié)束程序。如果當前層取的數(shù)字沒有超過k越界，就調(diào)整到下一個數(shù)字。 結(jié)合上面窮舉法程序運行的過程，理解本程序運行的過程，明確“擴展”、“回溯”、“調(diào)整”等幾個關(guān)鍵術(shù)語的意思。再與本文開始給出的回溯法模型融會貫通，就可以建立算法模型，解決各類程序設(shè)計中的復雜問題。 參考文獻： [1] 聶華. 基于四皇后問題的回溯法求解及算法實現(xiàn)[J]. 電子測試， 2013（9）. [2] 謝玉庚. 用回溯法編程求解愛因斯坦謎題[J]. 電腦與電信， 2016（10）. [3] 田翠華， 等. 深度優(yōu)先遍歷算法、隨機布點法及回溯法在迷宮游戲中的應(yīng)用[J]. 河北北方學院學報：自然科學版， 2013（6）. [4] 王防修. 回溯法在物流車動態(tài)導航中的應(yīng)用[J]. 武漢輕工大學學報， 2017（6）.
