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