[psac]

五、回溯法

回溯法也稱為試探法，該方法首先暫時放棄關於問題規模大小的限制，並將問題的候選解按某種順序逐一枚舉和檢驗。當發現當前候選解不可能是解時，就選項下一個候選解；倘若當前候選解除了還不滿足問題規模要求外，滿足所有其他要求時，繼續擴大當前候選解的規模，並繼續試探。如果當前候選解滿足包括問題規模在內的所有要求時，該候選解就是問題的一個解。在回溯法中，放棄當前候選解，尋找下一個候選解的程序稱為回溯。擴大當前候選解的規模，以繼續試探的程序稱為向前試探。
1、回溯法的一般描述
可用回溯法求解的問題P，通常要能表達為：對於已知的由n元組（x1，x2，…，xn）組成的一個狀態空間E={（x1，x2，…，xn）∣xi∈Si ，i=1，2，…，n}，給定關於n元組中的一個份量的一個約束集D，要求E中滿足D的全部約束條件的所有n元組。其中Si是份量xi的定義域，且 |Si| 有限，i=1，2，…，n。我們稱E中滿足D的全部約束條件的任一n元組為問題P的一個解。
解問題P的最樸素的方法就是枚舉法，即對E中的所有n元組逐一地檢測其是否滿足D的全部約束，若滿足，則為問題P的一個解。但顯然，其計算量是相當大的。
我們發現，對於許多問題，所給定的約束集D具有完備性，即i元組（x1，x2，…，xi）滿足D中僅涉及到x1，x2，…，xi的所有約束意味著j（j<i）元組（x1，x2，…，xj）一定也滿足D中僅涉及到x1，x2，…，xj的所有約束，i=1，2，…，n。換句話說，只要存在0≤j≤n-1，使得（x1，x2，…，xj）違反D中僅涉及到x1，x2，…，xj的約束之一，則以（x1，x2，…，xj）為前綴的任何n元組（x1，x2，…，xj，xj+1，…，xn）一定也違反D中僅涉及到x1，x2，…，xi的一個約束，n≥i>j。因此，對於約束集D具有完備性的問題P，一旦檢測斷定某個j元組（x1，x2，…，xj）違反D中僅涉及x1，x2，…，xj的一個約束，就可以肯定，以（x1，x2，…，xj）為前綴的任何n元組（x1，x2，…，xj，xj+1，…，xn）都不會是問題P的解，因而就不必去搜尋它們、檢測它們。回溯法正是針對這類問題，利用這類問題的上述性質而提出來的比枚舉法效率更高的算法。
回溯法首先將問題P的n元組的狀態空間E表示成一棵高為n的帶權有序樹T，把在E中求問題P的所有解轉化為在T中搜尋問題P的所有解。樹T類似於檢索樹，它可以這樣構造：
設Si中的元素可排成xi(1) ，xi(2) ，…，xi(mi-1) ，|Si| =mi，i=1，2，…，n。從根開始，讓T的第I層的每一個結點都有mi個兒子。這mi個兒子到它們的雙親的邊，按從左到右的次序，分別帶權xi+1(1) ，xi+1(2) ，…，xi+1(mi) ，i=0，1，2，…，n-1。照這種構造方式，E中的一個n元組（x1，x2，…，xn）對應於T中的一個葉子結點，T的根到這個葉子結點的路徑上依次的n條邊的權分別為x1，x2，…，xn，反之亦然。另外，對於任意的0≤i≤n-1，E中n元組（x1，x2，…，xn）的一個前綴I元組（x1，x2，…，xi）對應於T中的一個非葉子結點，T的根到這個非葉子結點的路徑上依次的I條邊的權分別為x1，x2，…，xi，反之亦然。特別，E中的任意一個n元組的空前綴（），對應於T的根。
因而，在E中尋找問題P的一個解等價於在T中搜尋一個葉子結點，要求從T的根到該葉子結點的路徑上依次的n條邊相應帶的n個權x1，x2，…，xn滿足約束集D的全部約束。在T中搜尋所要求的葉子結點，很自然的一種方式是從根出發，按深度優先的原則逐步深入，即依次搜尋滿足約束條件的前綴1元組（x1i）、前綴2元組（x1，x2）、…，前綴I元組（x1，x2，…，xi），…，直到i=n為止。
在回溯法中，上述引入的樹被稱為問題P的狀態空間樹；樹T上任意一個結點被稱為問題P的狀態結點；樹T上的任意一個葉子結點被稱為問題P的一個解狀態結點；樹T上滿足約束集D的全部約束的任意一個葉子結點被稱為問題P的一個回答狀態結點，它對應於問題P的一個解。
【問題】 組合問題
問題描述：找出從自然數1、2、……、n中任取r個數的所有組合。
例如n=5，r=3的所有組合為：
（1）1、2、3 （2）1、2、4 （3）1、2、5
（4）1、3、4 （5）1、3、5 （6）1、4、5
（7）2、3、4 （8）2、3、5 （9）2、4、5
（10）3、4、5
則該問題的狀態空間為：
E={（x1，x2，x3）∣xi∈S ，i=1，2，3 } 其中：S={1，2，3，4，5}
約束集為： x1<x2<x3
顯然該約束集具有完備性。


2、回溯法的方法
對於具有完備約束集D的一般問題P及其相應的狀態空間樹T，利用T的層次結構和D的完備性，在T中搜尋問題P的所有解的回溯法可以形象地描述為：
從T的根出發，按深度優先的原則，系統地搜尋以其為根的子樹中可能包含著回答結點的所有狀態結點，而跳過對肯定不含回答結點的所有子樹的搜尋，以提高搜尋效率。具體地說，當搜尋按深度優先原則到達一個滿足D中所有有關約束的狀態結點時，即「啟動」該狀態結點，以便繼續往深層搜尋；否則跳過對以該狀態結點為根的子樹的搜尋，而一邊逐層地向該狀態結點的祖先結點回溯，一邊「殺死」其兒子結點已被搜尋遍的祖先結點，直到遇到其兒子結點未被搜尋遍的祖先結點，即轉向其未被搜尋的一個兒子結點繼續搜尋。
在搜尋程序中，只要所啟動的狀態結點又滿足終結條件，那麼它就是回答結點，應該把它輸出或儲存。由於在回溯法求解問題時，一般要求出問題的所有解，因此在得到回答結點後，同時也要進行回溯，以便得到問題的其他解，直至回溯到T的根且根的所有兒子結點均已被搜尋過為止。
例如在組合問題中，從T的根出發深度優先遍歷該樹。當遍歷到結點（1，2）時，雖然它滿足約束條件，但還不是回答結點，則應繼續深度遍歷；當遍歷到葉子結點（1，2，5）時，由於它已是一個回答結點，則儲存（或輸出）該結點，並回溯到其雙親結點，繼續深度遍歷；當遍歷到結點（1，5）時，由於它已是葉子結點，但不滿足約束條件，故也需回溯。
3、回溯法的一般流程和技術
在用回溯法求解有關問題的程序中，一般是一邊建樹，一邊遍歷該樹。在回溯法中我們一般採用非遞回方法。下面，我們指出回溯法的非遞回算法的一般流程：

在用回溯法求解問題，也即在遍歷狀態空間樹的程序中，如果採用非遞回方法，則我們一般要用到棧的資料結構。這時，不僅可以用棧來表示正在遍歷的樹的結點，而且可以很方便地表示建立孩子結點和回溯程序。
例如在組合問題中，我們用一個一維陣列Stack[ ]表示棧。開始棧空，則表示了樹的根結點。如果元素1進棧，則表示建立並遍歷（1）結點；這時如果元素2進棧，則表示建立並遍歷（1，2）結點；元素3再進去棧，則表示建立並遍歷（1，2，3）結點。這時可以判斷它滿足所有約束條件，是問題的一個解，輸出（或儲存）。這時只要推疊頂端元素（3）出棧，即表示從結點（1，2，3）回溯到結點（1，2）。
【問題】 組合問題
問題描述：找出從自然數1，2，…，n中任取r個數的所有組合。
採用回溯法找問題的解，將找到的組合以從小到大順序存於a[0]，a[1]，…，a[r-1]中，組合的元素滿足以下性質：
（1） a[i+1]>a，後一個數位比前一個大；
（2） a-i<=n-r+1。
按回溯法的思想，找解程序可以敘述如下：
首先放棄組合數個數為r的條件，候選組合從只有一個數位1開始。因該候選解滿足除問題規模之外的全部條件，擴大其規模，並使其滿足上述條件（1），候選組合改為1，2。繼續這一程序，得到候選組合1，2，3。該候選解滿足包括問題規模在內的全部條件，因而是一個解。在該解的基礎上，選下一個候選解，因a[2]上的3調整為4，以及以後調整為5都滿足問題的全部要求，得到解1，2，4和1，2，5。由於對5不能再作調整，就要從a[2]回溯到a[1]，這時，a[1]=2，可以調整為3，並向前試探，得到解1，3，4。重複上述向前試探和向後回溯，直至要從a[0]再回溯時，說明已經找完問題的全部解。按上述思想寫成程序如下：
【程序】
# define MAXN 100
int a[MAXN];
void comb(int m,int r)
{ int i,j;
i=0;
a=1;
do {
if (a-i<=m-r+1
{ if (i==r-1)
{ for (j=0;j<r;j++)
printf(「%4d」,a[j]);
printf(「\n」);
}
a++;
continue;
}
else
{ if (i==0)
return;
a[--i]++;
}
} while (1)
}

main()
{ comb(5,3);
}
【問題】 填字遊戲
問題描述：在3×3個方格的方陣中要填入數位1到N（N≥10）內的某9個數位，每個方格填一個整數，似的所有相鄰兩個方格內的兩個整數之和為質數。試求出所有滿足這個要求的各種數位填法。
可用試探發找到問題的解，即從第一個方格開始，為當前方格尋找一個合理的整數填入，並在當前位置正確填入後，為下一方格尋找可填入的合理整數。如不能為當前方格找到一個合理的可填證書，就要回退到前一方格，調整前一方格的填入數。當第九個方格也填入合理的整數後，就找到了一個解，將該解輸出，並調整第九個的填入的整數，尋找下一個解。
為找到一個滿足要求的9個數的填法，從還未填一個數開始，按某種順序（如從小到大的順序）每次在當前位置填入一個整數，然後檢查當前填入的整數是否能滿足要求。在滿足要求的情況下，繼續用同樣的方法為下一方格填入整數。如果最近填入的整數不能滿足要求，就改變填入的整數。如對當前方格試盡所有可能的整數，都不能滿足要求，就得回退到前一方格，並調整前一方格填入的整數。如此重複執行增強、檢查或調整、檢查，直到找到一個滿足問題要求的解，將解輸出。
回溯法找一個解的算法：
{ int m=0,ok=1;
int n=8;
do{
if (ok) 增強;
else 調整;
ok=檢查前m個整數填放的合理性;
} while ((!ok||m!=n)&&(m!=0))
if (m!=0) 輸出解;
else 輸出無解報告；
}
如果程序要找全部解，則在將找到的解輸出後，應繼續調整最後位置上填放的整數，試圖去找下一個解。相應的算法如下：
回溯法找全部解的算法：
{ int m=0,ok=1;
int n=8;
do{
if (ok)
{ if (m==n)
{ 輸出解；
調整；
}
else 增強;
}
else 調整;
ok=檢查前m個整數填放的合理性;
} while (m!=0);
}
為了確保程序能夠終止，調整時必須保證曾被放棄過的填數序列不會再次實驗，即要求按某種有許模型產生填數序列。給解的候選者設定一個被檢驗的順序，按這個順序逐一形成候選者並檢驗。從小到大或從大到小，都是可以採用的方法。如增強時，先在新位置填入整數1，調整時，找當前候選解中下一個還未被使用過的整數。將上述增強、調整、檢驗都編寫成程序，細節見以下找全部解的程序。
【程序】
# include <stdio.h>
# define N 12
void write(int a[ ])
{ int i,j;
for (i=0;i<3;i++)
{ for (j=0;j<3;j++)
printf(「%3d」,a[3*i+j]);
printf(「\n」);
}
scanf(「%*c」);
}

int b[N+1];
int a[10];
int isprime(int m)
{ int i;
int primes[ ]={2,3,5,7,11,17,19,23,29,-1};
if (m==1||m%2=0) return 0;
for (i=0;primes>0;i++)
if (m==primes) return 1;
for (i=3;i*i<=m
{ if (m%i==0) return 0;
i+=2;
}
return 1;
}

int checkmatrix[ ][3]={ {-1},{0,-1},{1,-1},{0,-1},{1,3,-1},
{2,4,-1},{3,-1},{4,6,-1},{5,7,-1}};
int selectnum(int start)
{ int j;
for (j=start;j<=N;j++)
if (b[j]) return j
return 0;
}

int check(int pos)
{ int i,j;
if (pos<0) return 0;
for (i=0;(j=checkmatrix[pos])>=0;i++)
if (!isprime(a[pos]+a[j])
return 0;
return 1;
}

int extend(int pos)
{ a[++pos]=selectnum(1);
b[a][pos]]=0;
return pos;
}

int change(int pos)
{ int j;
while (pos>=0&&(j=selectnum(a[pos]+1))==0)
b[a[pos--]]=1;
if (pos<0) return –1
b[a[pos]]=1;
a[pos]=j;
b[j]=0;
return pos;
}

void find()
{ int ok=0,pos=0;
a[pos]=1;
b[a[pos]]=0;
do {
if (ok)
if (pos==8)
{ write(a);
pos=change(pos);
}
else pos=extend(pos);
else pos=change(pos);
ok=check(pos);
} while (pos>=0)
}

void main()
{ int i;
for (i=1;i<=N;i++)
b=1;
find();
}
【問題】 n皇后問題
問題描述：求出在一個n×n的棋碟上，放置n個不能互相捕捉的國際象棋「皇后」的所有佈局。
這是來源於國際象棋的一個問題。皇后可以沿著縱橫和兩條斜線4個方向相互捕捉。如圖所顯示，一個皇后放在棋盤的第4行第3列位置上，則棋碟上凡打「×」的位置上的皇后就能與這個皇后相互捕捉。

1 2 3 4 5 6 7 8
× ×
× × ×
× × ×
× × Q × × × × ×
× × ×
× × ×
× ×
× ×
從圖中可以得到以下啟示：一個合適的解應是在每列、每行上只有一個皇后，且一條斜線上也只有一個皇后。
求解程序從空組態開始。在第1列至第m列為合理組態的基礎上，再組態第m+1列，直至第n列組態也是合理時，就找到了一個解。接著改變第n列組態，希望獲得下一個解。另外，在任一列上，可能有n種組態。開始時組態在第1行，以後改變時，順次選項第2行、第3行、…、直到第n行。當第n行組態也找不到一個合理的組態時，就要回溯，去改變前一列的組態。得到求解皇后問題的算法如下：
{ 輸入棋盤大小值n；
m=0;
good=1;
do {
if (good)
if (m==n)
{ 輸出解；
改變之，形成下一個候選解;
}
else 增強當前候選接至下一列；
else 改變之，形成下一個候選解；
good=檢查當前候選解的合理性；
} while (m!=0);
}
在編寫程序之前，先確定邊式棋盤的資料結構。比較直觀的方法是採用一個二維陣列，但仔細觀察就會發現，這種表示方法給調整候選解及檢查其合理性帶來困難。更好的方法乃是盡可能直接表示那些常用的訊息。對於本題來說，「常用訊息」並不是皇后的具體位置，而是「一個皇后是否已經在某行和某條斜線合理地安置好了」。因在某一列上恰好放一個皇后，引入一個一維陣列（col[ ]），值col表示在棋盤第i列、col行有一個皇后。例如：col[3]=4，就表示在棋盤的第3列、第4行上有一個皇后。另外，為了使程序在找完了全部解後回溯到最初位置，設定col[0]的初值為0當回溯到第0列時，說明程序已求得全部解，結束程序執行。
為使程序在檢查皇后組態的合理性方面簡易方便，引入以下三個工作陣列：
（1） 陣列a[ ]，a[k]表示第k行上還沒有皇后；
（2） 陣列b[ ]，b[k]表示第k列右高左低斜線上沒有皇后；
（3） 陣列 c[ ]，c[k]表示第k列左高右低斜線上沒有皇后；
棋盤中同一右高左低斜線上的方格，他們的行號與列號之和相同；同一左高右低斜線上的方格，他們的行號與列號之差均相同。
初始時，所有行和斜線上均沒有皇后，從第1列的第1行組態第一個皇后開始，在第m列col[m]行放置了一個合理的皇后後，準備考察第m+1列時，在陣列a[ ]、b[ ]和c[ ]中為第m列，col[m]行的位置設定有皇后標誌；當從第m列回溯到第m-1列，並準備調整第m-1列的皇后組態時，清除在陣列a[ ]、b[ ]和c[ ]中設定的關於第m-1列，col[m-1]行有皇后的標誌。一個皇后在m列，col[m]行方格內組態是合理的，由陣列a[ ]、b[ ]和c[ ]對應位置的值都為1來確定。細節見以下程序：
【程序】
# include <stdio.h>
# include <stdlib.h>
# define MAXN 20
int n,m,good;
int col[MAXN+1],a[MAXN+1],b[2*MAXN+1],c[2*MAXN+1];

void main()
{ int j;
char awn;
printf(「Enter n: 「); scanf(「%d」,&n);
for (j=0;j<=n;j++) a[j]=1;
for (j=0;j<=2*n;j++) cb[j]=c[j]=1;
m=1; col[1]=1; good=1; col[0]=0;
do {
if (good)
if (m==n)
{ printf(「列\t行」);
for (j=1;j<=n;j++)
printf(「%3d\t%d\n」,j,col[j]);
printf(「Enter a character (Q/q for exit)!\n」);
scanf(「%c」,&awn);
if (awn==』Q』||awn==』q』) exit(0);
while (col[m]==n)
{ m--;
a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=1;
}
col[m]++;
}
else
{ a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=0;
col[++m]=1;
}
else
{ while (col[m]==n)
{ m--;
a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=1;
}
col[m]++;
}
good=a[col[m]]&&b[m+col[m]]&&c[n+m-col[m]];
} while (m!=0);
}
試探法找解算法也常常被編寫成遞回函數，下面兩程序中的函數queen_all()和函數queen_one()能分別用來解皇后問題的全部解和一個解。
【程序】
# include <stdio.h>
# include <stdlib.h>
# define MAXN 20
int n;
int col[MAXN+1],a[MAXN+1],b[2*MAXN+1],c[2*MAXN+1];
void main()
{ int j;
printf(「Enter n: 「); scanf(「%d」,&n);
for (j=0;j<=n;j++) a[j]=1;
for (j=0;j<=2*n;j++) cb[j]=c[j]=1;
queen_all(1,n);
}

void queen_all(int k,int n)
{ int i,j;
char awn;
for (i=1;i<=n;i++)
if (a&&b[k+i]&&c[n+k-i])
{ col[k]=i;
a=b[k+i]=c[n+k-i]=0;
if (k==n)
{ printf(「列\t行」);
for (j=1;j<=n;j++)
printf(「%3d\t%d\n」,j,col[j]);
printf(「Enter a character (Q/q for exit)!\n」);
scanf(「%c」,&awn);
if (awn==』Q』||awn==』q』) exit(0);
}
queen_all(k+1,n);
a=b[k+i]=c[n+k-i];
}
}
採用遞回方法找一個解與找全部解稍有不同，在找一個解的算法中，遞回算法要對當前候選解最終是否能成為解要有回答。當它成為最終解時，遞回函數就不再遞回試探，立即返回；若不能成為解，就得繼續試探。設函數queen_one()返回1表示找到解，返回0表示當前候選解不能成為解。細節見以下函數。
【程序】
# define MAXN 20
int n;
int col[MAXN+1],a[MAXN+1],b[2*MAXN+1],c[2*MAXN+1];
int queen_one(int k,int n)
{ int i,found;
i=found=0;
While (!found&&i<n)
{ i++;
if (a&&b[k+i]&&c[n+k-i])
{ col[k]=i;
a=b[k+i]=c[n+k-i]=0;
if (k==n) return 1;
else
found=queen_one(k+1,n);
a=b[k+i]=c[n+k-i]=1;
}
}
return found;
}