回溯法在我們解題步驟中經(jīng)常被提到，這也是一種常用的方法，回溯法是一種經(jīng)常被用在 深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS）的技巧。其本質(zhì)是：走不通就回頭。本篇將結(jié)合經(jīng)典例題幫助大家對回溯法的理解。

一、工作原理：

（1）構(gòu)造空間樹；

（2）進行遍歷；

（3）如遇到邊界條件，即不再向下搜索，轉(zhuǎn)而搜索另一條鏈；

（4）達到目標條件，輸出結(jié)果。

二、經(jīng)典例題

例題一：0-1背包問題

問題：給定n種物品和一背包。物品i的重量是wi，其價值為pi，背包的容量為C。問應如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?

分析：問題是n個物品中選擇部分物品，可知，問題的解空間是子集樹。比如物品數(shù)目n=3時，其解空間樹如下圖，邊為1代表選擇該物品，邊為0代表不選擇該物品。使用x[i]表示物品i是否放入背包，x[i]=0表示不放，x[i]=1表示放入?；厮菟阉鬟^程，如果來到了葉子節(jié)點，表示一條搜索路徑結(jié)束，如果該路徑上存在更優(yōu)的解，則保存下來。如果不是葉子節(jié)點，是中點的節(jié)點（如B），就遍歷其子節(jié)點（D和E），如果子節(jié)點滿足剪枝條件，就繼續(xù)回溯搜索子節(jié)點。

代碼如下：

#include <stdio.h>  
   
#define N 3         //物品的數(shù)量  
#define C 16        //背包的容量  
   
int w[N]={10,8,5};  //每個物品的重量  
int v[N]={5,4,1};   //每個物品的價值  
int x[N]={0,0,0};   //x[i]=1代表物品i放入背包，0代表不放入  
   
int CurWeight = 0;  //當前放入背包的物品總重量  
int CurValue = 0;   //當前放入背包的物品總價值  
   
int BestValue = 0;  //最優(yōu)值；當前的最大價值，初始化為0  
int BestX[N];       //最優(yōu)解；BestX[i]=1代表物品i放入背包，0代表不放入  
   
//t = 0 to N-1  
void backtrack(int t)  
{  
    //葉子節(jié)點，輸出結(jié)果  
    if(t>N-1)   
    {  
        //如果找到了一個更優(yōu)的解  
        if(CurValue>BestValue)  
        {  
            //保存更優(yōu)的值和解  
            BestValue = CurValue;  
            for(int i=0;i<N;++i) BestX[i] = x[i];  
        }  
    }  
    else  
    {  
        //遍歷當前節(jié)點的子節(jié)點：0 不放入背包，1放入背包  
        for(int i=0;i<=1;++i)  
        {  
            x[t]=i;  
   
            if(i==0) //不放入背包  
            {  
                backtrack(t+1);  
            }  
            else //放入背包  
            {  
                 //約束條件：放的下  
                if((CurWeight+w[t])<=C)  
                {  
                    CurWeight += w[t];  
                    CurValue += v[t];  
                    backtrack(t+1);  
                    CurWeight -= w[t];  
                    CurValue -= v[t];  
                }  
            }  
        }  
        //PS:上述代碼為了更符合遞歸回溯的范式，并不夠簡潔  
    }  
}  
   
int main(int argc, char* argv[])  
{  
    backtrack(0);  
   
    printf("最優(yōu)值：%d\n",BestValue);  
   
    for(int i=0;i<N;i++)  
    {  
       printf("最優(yōu)解：%-3d",BestX[i]);  
    }  
    return 0;  
}

例題二：描述N皇后問題

問題：在n×n格的棋盤上放置彼此不受攻擊的n個皇后。按照國際象棋的規(guī)則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。

N皇后問題等價于在n×n格的棋盤上放置n個皇后，任何2個皇后不放在同一行或同一列或同一斜線上。

分析：從n×n個格子中選擇n個格子擺放皇后?？梢娊饪臻g樹為子集樹。

使用Board[N][N]來表示棋盤，Board[i][j]=0 表示(I,j)位置為空，Board[i][j]=1 表示(I,j)位置擺放有一個皇后。

全局變量way表示總共的擺放方法數(shù)目。

使用Queen(t)來擺放第t個皇后。Queen(t) 函數(shù)符合子集樹時的遞歸回溯范式。當t>N時，說明所有皇后都已經(jīng)擺   放完成，這是一個可行的擺放方法，輸出結(jié)果；否則，遍歷棋盤，找皇后t所有可行的擺放位置，F(xiàn)easible(i,j) 判斷皇后t能否擺放在位置(i,j)處，如果可以擺放則繼續(xù)遞歸擺放皇后t+1，如果不能擺放，則判斷下一個位置。

Feasible(row,col)函數(shù)首先判斷位置(row,col)是否合法，繼而判斷(row,col)處是否已有皇后，有則沖突，返回0，無則繼續(xù)判斷行、列、斜方向是否沖突。斜方向分為左上角、左下角、右上角、右下角四個方向，每次從（row,col）向四個方向延伸一個格子，判斷是否沖突。如果所有方向都沒有沖突，則返回1，表示此位置可以擺放一個皇后。

代碼如下：

#include <stdio.h>  
   
#define N 8  
   
int Board[N][N];//棋盤 0表示空白 1表示有皇后  
int way;//擺放的方法數(shù)  
   
   
//判斷能否在(x,y)的位置擺放一個皇后；0不可以，1可以  
int Feasible(int row,int col)  
{  
    //位置不合法  
    if(row>N || row<0 || col >N || col<0)  
        return 0;  
   
    //該位置已經(jīng)有皇后了，不能  
    if(Board[row][col] != 0)  
    {   //在行列沖突判斷中也包含了該判斷，單獨提出來為了提高效率  
        return 0;  
    }  
   
    //  
    //下面判斷是否和已有的沖突  
   
    //行和列是否沖突  
    for(int i=0;i<N;++i)  
    {  
        if(Board[row][i] != 0 || Board[i][col]!=0)  
            return 0;  
    }  
   
    //斜線方向沖突  
   
    for(int i=1;i<N;++i)  
    {  
/* i表示從當前點(row,col)向四個斜方向擴展的長度 
  
左上角 \  / 右上角   i=2 
        \/           i=1 
        /\           i=1 
左下角 /  \ 右下角   i=2 
*/  
        //左上角  
        if((row-i)>=0 && (col-i)>=0)    //位置合法  
        {  
            if(Board[row-i][col-i] != 0)//此處已有皇后，沖突  
                return 0;  
        }  
   
        //左下角  
        if((row+i)<N && (col-i)>=0)  
        {  
            if(Board[row+i][col-i] != 0)  
                return 0;  
        }  
   
        //右上角  
        if((row-i)>=0 && (col+i)<N)  
        {  
            if(Board[row-i][col+i] != 0)  
                return 0;  
        }  
   
        //右下角  
        if((row+i)<N && (col+i)<N)  
        {  
            if(Board[row+i][col+i] != 0)  
                return 0;  
        }  
    }  
   
    return 1; //不會發(fā)生沖突，返回1  
}  
   
   
//擺放第t個皇后 ；從1開始  
void Queen(int t)  
{  
    //擺放完成，輸出結(jié)果  
    if(t>N)  
    {  
        way++;  
        /*如果N較大，輸出結(jié)果會很慢；N較小時，可以用下面代碼輸出結(jié)果 
        for(int i=0;i<N;++i){ 
            for(int j=0;j<N;++j) 
                printf("%-3d",Board[i][j]); 
            printf("\n"); 
        } 
        printf("\n------------------------\n\n"); 
        */  
    }  
    else  
    {  
        for(int i=0;i<N;++i)  
        {  
            for(int j=0;j<N;++j)  
            {  
                //（i,j）位置可以擺放皇后，不沖突  
                if(Feasible(i,j))  
                {  
                    Board[i][j] = 1;  //擺放皇后t  
                    Queen(t+1);       //遞歸擺放皇后t+1  
                    Board[i][j] = 0;  //恢復  
                }  
            }  
        }  
    }  
}  
   
//返回num的階乘,num!  
int factorial(int num)  
{  
    if(num==0 || num==1)  
        return 1;  
    return num*factorial(num-1);  
}  
   
   
int main(int argc, char* argv[])  
{  
    //初始化  
    for(int i=0;i<N;++i)  
    {  
        for(int j=0;j<N;++j)  
        {  
            Board[i][j]=0;  
        }  
    }  
   
    way = 0;  
   
    Queen(1);  //從第1個皇后開始擺放  
   
    //如果每個皇后都不同  
    printf("考慮每個皇后都不同，擺放方法：%d\n",way);//N=8時, way=3709440 種  
   
    //如果每個皇后都一樣，那么需要除以 N！出去重復的答案（因為相同，則每個皇后可任意調(diào)換位置）  
    printf("考慮每個皇后都不同，擺放方法：%d\n",way/factorial(N));//N=8時, way=3709440/8! = 92種  
   
    return 0;  
}

PS：該問題還有更優(yōu)的解法。充分利用問題隱藏的約束條件：每個皇后必然在不同的行(列)，每個行(列)必然也只有一個皇后。這樣我們就可以把N個皇后放到N個行中，使用Pos[i]表示皇后i在i行中的位置（也就是列號）（i = 0 to N-1）。這樣代碼會大大的簡潔，因為節(jié)點的子節(jié)點數(shù)目會減少，判斷沖突也更簡單。