<meta charset="utf-8">
回溯法（back tracking）（探索與回溯法）是一種選優(yōu)搜索法佑吝，又稱為試探法，按選優(yōu)條件向前搜索绳匀，以達(dá)到目標(biāo)。但當(dāng)探索到某一步時(shí)炸客，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)疾棵，就退回一步重新選擇，這種走不通就退回再走的技術(shù)為回溯法痹仙，而滿足回溯條件的某個(gè)狀態(tài)的點(diǎn)稱為“回溯點(diǎn)”是尔。
白話：回溯法可以理解為通過選擇不同的岔路口尋找目的地，一個(gè)岔路口一個(gè)岔路口的去嘗試找到目的地开仰。如果走錯(cuò)了路拟枚，繼續(xù)返回來找到岔路口的另一條路，直到找到目的地众弓。
實(shí)例一：八皇后問題
八皇后問題是一個(gè)古老而著名的問題恩溅，是回溯算法的典型例題。該問題是十九世紀(jì)著名的數(shù)學(xué)家高斯1850年提出：在8X8格的國際象棋上擺放八個(gè)皇后（棋子）谓娃，使其不能互相攻擊脚乡，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上滨达。
小白面試經(jīng)：理解如何解決這個(gè)問題奶稠，回溯法的精髓已經(jīng)get俯艰。如果只是想了解算法面試知識(shí)，知道解決這個(gè)問題就能完成你的算法積累了锌订。想快速掌握算法竹握，可以直接查看解題思路的四個(gè)步驟。
八皇后問題解題思路：
問題簡化：下面我們將八皇后問題轉(zhuǎn)化為四皇后問題辆飘，并用回溯法來找到它的解
目的：在4x4棋盤上啦辐，使得4個(gè)皇后不能在同行同列以及同斜線上。
step1
嘗試先放置第一枚皇后劈猪，被涂黑的地方是不能放皇后
step2
第二行的皇后只能放在第三格或第四格昧甘，比方我們放第三格，則：
此時(shí)我們也能理解為什么叫皇后問題了战得，皇后旁邊容不下其他皇后充边。而在同一個(gè)房間放下四個(gè)皇后確實(shí)是個(gè)不容易的問題。
step3
可以看到再難以放下第三個(gè)皇后常侦，此時(shí)我們就要用到回溯算法了浇冰。我們把第二個(gè)皇后更改位置，此時(shí)我們能放下第三枚皇后了聋亡。
step4
雖然是能放置第三個(gè)皇后肘习，但是第四個(gè)皇后又無路可走了。返回上層調(diào)用（3號(hào)皇后）坡倔，而3號(hào)也別無可去漂佩，繼續(xù)回溯上層調(diào)用（2號(hào)），2號(hào)已然無路可去罪塔，繼續(xù)回溯上層（1號(hào)）投蝉，于是1號(hào)皇后改變位置如下，繼續(xù)回溯征堪。
這就是回溯算法的精髓瘩缆，雖然沒有最終把問題解決，但是可以劇透一波佃蚜，就是根據(jù)這個(gè)算法庸娱，最終能夠把四位皇后放在4x4的棋盤里。也能用同樣的方法解決了八皇后問題谐算。下面我們用代碼解決八皇后問題熟尉。
代碼實(shí)現(xiàn)八皇后問題
我們將算法也設(shè)置成兩步，
第一步 我們要判斷每次輸入的皇后是否在同一行同一列洲脂，或者同一斜線上臣樱。
bool is_ok(int row){ //判斷設(shè)置的皇后是否在同一行，同一列，或者同一斜線上
for (int j=0;j<row;j++)
{
if (queen[row]==queen[j]||row-queen[row]==j-queen[j]||row+queen[row]==j+queen[j])
return false;
}
return true;
}
第二步 我們用十行代碼來進(jìn)入我們核心算法
void back_tracking(int row=0) //算法函數(shù)雇毫，從第0行開始遍歷
{
if (row==n)
t ++; //判斷若遍歷完成玄捕，就進(jìn)行計(jì)數(shù)
for (int col=0;col<n;col++) //遍歷棋盤每一列
{
queen[row] = col; //將皇后的位置記錄在數(shù)組
if (is_ok(row)) //判斷皇后的位置是否有沖突
back_tracking(row+1); //遞歸，計(jì)算下一個(gè)皇后的位置
}
}
代碼實(shí)現(xiàn)算法也是比較簡單的棚放，主要還是看是否掌握算法思想枚粘。
實(shí)例二：01背包問題
有N件物品和一個(gè)容量為V的背包。第i件物品的價(jià)格（即體積飘蚯，下同）是w[i]馍迄，價(jià)值是c[i]。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過背包容量局骤，且價(jià)值總和最大攀圈。
這是最基礎(chǔ)的背包問題，總的來說就是：選還是不選峦甩，這是個(gè)問題
相當(dāng)于用f[i][j]表示前i個(gè)物品裝入容量為v的背包中所可以獲得的最大價(jià)值赘来。
對(duì)于一個(gè)物品，只有兩種情況
情況一: 第i件不放進(jìn)去凯傲，這時(shí)所得價(jià)值為:f[i-1][v]
情況二: 第i件放進(jìn)去犬辰，這時(shí)所得價(jià)值為：f[i-1][v-c[i]]+w[i]
接下來的實(shí)例屬于算法進(jìn)階，可做了解
提兩點(diǎn)冰单，
1.與上期貪婪法所解決的背包問題相比幌缝，回溯法將能更能顧及尋找全局最優(yōu)。
2.背包問題與八皇后問題所用的算法雖然都是回溯法诫欠，但是他們的目的不一樣涵卵，八皇后只要求把所有的棋子放在棋盤上（即只需解決深度最優(yōu)）。而01背包問題不僅需要讓物品都放進(jìn)背包荒叼，而且要使得物品質(zhì)量最大轿偎，在八皇后問題上多提出了一個(gè)限制。
問題的解空間
用回溯法解問題時(shí)甩挫，應(yīng)明確定義問題的解空間。問題的解空間至少包含問題的一個(gè)(最優(yōu))解椿每。對(duì)于 n=3 時(shí)的 0/1 背包問題伊者，可用一棵完全二叉樹表示解空間，如圖所示：
求解步驟
1)針對(duì)所給問題间护，定義問題的解空間亦渗；
2)確定易于搜索的解空間結(jié)構(gòu)；
3)以深度優(yōu)先方式搜索解空間汁尺，并在搜索過程中用剪枝函數(shù)避免無效搜索法精。
常用的剪枝函數(shù)：用約束函數(shù)在擴(kuò)展結(jié)點(diǎn)處剪去不滿足約束的子樹；用限界函數(shù)剪去得不到最優(yōu)解的子樹。
回溯法對(duì)解空間做深度優(yōu)先搜索時(shí)搂蜓，有遞歸回溯和迭代回溯（非遞歸）兩種方法狼荞，但一般情況下用遞歸方法實(shí)現(xiàn)回溯法。
算法描述
解 0/1 背包問題的回溯法在搜索解空間樹時(shí)帮碰，只要其左兒子結(jié)點(diǎn)是一個(gè)可行結(jié)點(diǎn)相味，搜索就進(jìn)入其左子樹。當(dāng)右子樹中有可能包含最優(yōu)解時(shí)才進(jìn)入右子樹搜索殉挽。否則將右子樹剪去丰涉。
我們直接上手代碼解決這個(gè)問題
算法部分
void dfs(int i,int cv,int cw)
{ //cw當(dāng)前包內(nèi)物品重量，cv當(dāng)前包內(nèi)物品價(jià)值
if(i>n)
{
if(cv>bestval) //是否超過了最大價(jià)值
{
bestval=cv; //得到最大價(jià)值
for(i=1;i<=n;i++)
bestx[i]=x[i]; //得到選中的物品
}
}
else
for(int j=0;j<=1;j++) //枚舉物體i所有可能的路徑斯碌，
{
x[i]=j;
if(cw+x[i]*w[i]<=TotCap) //滿足約束,繼續(xù)向子節(jié)點(diǎn)探索
{
cw+=w[i]*x[i];
cv+=val[i]*x[i];
dfs(i+1,cv,cw);
cw-=w[i]*x[i]; //回溯上一層物體的選擇情況
cv-=val[i]*x[i];
}
}
}
主函數(shù)部分
int main()
{
int i;
bestval=0;
cout<<"請(qǐng)輸入背包最大容量:"<<endl;;
cin>>TotCap;
cout<<"請(qǐng)輸入物品個(gè)數(shù):"<<endl;
cin>>n;
cout<<"請(qǐng)依次輸入物品的重量:"<<endl;
for(i=1;i<=n;i++)
cin>>w[i];
cout<<"請(qǐng)依次輸入物品的價(jià)值:"<<endl;
for(i=1;i<=n;i++)
cin>>val[i];
dfs(1,0,0);
cout<<"最大價(jià)值為:"<<endl;
cout<<bestval<<endl;
cout<<"被選中的物品的標(biāo)號(hào)依次是:"<<endl;
for(i=1;i<=n;i++)
if(bestx[i]==1)
cout<<i<<" ";
cout<<endl;
return 0;
}
回溯算法帶你玩數(shù)獨(dú)
我們可以想象一死，我們經(jīng)常玩的數(shù)獨(dú)問題其實(shí)就是一個(gè)的八皇后問題。在9宮格數(shù)獨(dú)的約束為每一行每一列不能出現(xiàn)相同的數(shù)傻唾。這里我們限于篇幅投慈，不將細(xì)講代碼了。
#include <iostream>
using namespace std;
#define LEN 9
int a[LEN][LEN] = {0};
//查詢?cè)撔欣锸欠裼羞@個(gè)值
bool Isvaild(int count)
{
int i = count/9;
int j = count%9;
//檢測(cè)行
for(int iter = 0;iter!=j;iter++)
{
if(a[i][iter]==a[i][j])
{
return 1;
}
}
//檢測(cè)列
for(int iter=0;iter!=i;iter++)
{
if(a[iter][j]==a[i][j])
{
return 1;
}
}
//檢測(cè)九宮
for(int p =i/3*3;p<(i/3+1)*3;p++)
{
for(int q=j/3*3;q<(j/3+1)*3;q++)
{
if(p==i&&j==q)
{
continue;
}
if(a[p][q]==a[i][j])
{
return 1;
}
}
}
return 0;
}
void print()
{
cout<<"數(shù)度的解集為"<<":"<<endl;
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
cout<<a[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
}
void first_chek(int count)
{
if(81 ==count)
{
print();
return;
}
int i = count/9; //列
int j = count%9; //行
if(a[i][j]==0)
{
for(int n=1;n<=9;n++)
{
a[i][j] = n;
if(!Isvaild(count)) //這個(gè)值不沖突
{
first_chek(count+1) }
}
a[i][j] = 0;
}
else
{
first_chek(count+1);
}
}
int main()
{
a[1][2] = 3;
a[5][3] = 9;
a[8][8] = 1;
a[4][4] = 4;
first_chek(0);
return 0;
}
其中2行3列策吠、6行4列逛裤、9行9列、5行5列數(shù)字為已知猴抹。最后結(jié)果带族，
總結(jié)
回溯法屬于深度優(yōu)先搜索，由于是全局搜索蟀给，復(fù)雜度相對(duì)高蝙砌。
如果你想了解更深的了解回溯算法，可以翻閱相關(guān)的數(shù)據(jù)結(jié)構(gòu)書籍跋理。當(dāng)然择克，如果你選擇深入了解這個(gè)算法，必然會(huì)枯燥前普。
