微信公眾號(hào)：小白算法
關(guān)注可了解更多算法，并能領(lǐng)取免費(fèi)資料。問(wèn)題或建議，請(qǐng)公眾號(hào)留言;
文末有資料領(lǐng)取
上一期算法回顧--貪婪法：https://mp.weixin.qq.com/s/978Tdplj3IaSG2dc-5F-aw
算法導(dǎo)讀
本期算法講解思路：
白話算法->算法思路->實(shí)例：八皇后問(wèn)題->實(shí)例：01背包問(wèn)題->算法教你玩數(shù)獨(dú)
白話算法
回溯法（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)”。
白話：回溯法可以理解為通過(guò)選擇不同的岔路口尋找目的地，一個(gè)岔路口一個(gè)岔路口的去嘗試找到目的地。如果走錯(cuò)了路，繼續(xù)返回來(lái)找到岔路口的另一條路，直到找到目的地。
實(shí)例一：八皇后問(wèn)題
八皇后問(wèn)題是一個(gè)古老而著名的問(wèn)題，是回溯算法的典型例題。該問(wèn)題是十九世紀(jì)著名的數(shù)學(xué)家高斯1850年提出：在8X8格的國(guó)際象棋上擺放八個(gè)皇后（棋子），使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上。
小白面試經(jīng)：理解如何解決這個(gè)問(wèn)題，回溯法的精髓已經(jīng)get。如果只是想了解算法面試知識(shí)，知道解決這個(gè)問(wèn)題就能完成你的算法積累了。想快速掌握算法，可以直接查看解題思路的四個(gè)步驟。
八皇后問(wèn)題解題思路：
問(wèn)題簡(jiǎn)化：下面我們將八皇后問(wèn)題轉(zhuǎn)化為四皇后問(wèn)題，并用回溯法來(lái)找到它的解
目的：在4x4棋盤上，使得4個(gè)皇后不能在同行同列以及同斜線上。
step1
嘗試先放置第一枚皇后，被涂黑的地方是不能放皇后
step2
第二行的皇后只能放在第三格或第四格，比方我們放第三格，則：
此時(shí)我們也能理解為什么叫皇后問(wèn)題了，皇后旁邊容不下其他皇后。而在同一個(gè)房間放下四個(gè)皇后確實(shí)是個(gè)不容易的問(wèn)題。
step3
可以看到再難以放下第三個(gè)皇后，此時(shí)我們就要用到回溯算法了。我們把第二個(gè)皇后更改位置，此時(shí)我們能放下第三枚皇后了。
step4
雖然是能放置第三個(gè)皇后，但是第四個(gè)皇后又無(wú)路可走了。返回上層調(diào)用（3號(hào)皇后），而3號(hào)也別無(wú)可去，繼續(xù)回溯上層調(diào)用（2號(hào)），2號(hào)已然無(wú)路可去，繼續(xù)回溯上層（1號(hào)），于是1號(hào)皇后改變位置如下，繼續(xù)回溯。
這就是回溯算法的精髓，雖然沒有最終把問(wèn)題解決，但是可以劇透一波，就是根據(jù)這個(gè)算法，最終能夠把四位皇后放在4x4的棋盤里。也能用同樣的方法解決了八皇后問(wèn)題。下面我們用代碼解決八皇后問(wèn)題。
代碼實(shí)現(xiàn)八皇后問(wè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;
}
第二步 我們用十行代碼來(lái)進(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)算法也是比較簡(jiǎn)單的，主要還是看是否掌握算法思想。
實(shí)例二：01背包問(wèn)題
有N件物品和一個(gè)容量為V的背包。第i件物品的價(jià)格（即體積，下同）是w[i]，價(jià)值是c[i]。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過(guò)背包容量，且價(jià)值總和最大。
這是最基礎(chǔ)的背包問(wèn)題，總的來(lái)說(shuō)就是：選還是不選，這是個(gè)問(wèn)題
相當(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]
接下來(lái)的實(shí)例屬于算法進(jìn)階，可做了解
提兩點(diǎn)，
1.與上期貪婪法所解決的背包問(wèn)題相比，回溯法將能更能顧及尋找全局最優(yōu)。
2.背包問(wèn)題與八皇后問(wèn)題所用的算法雖然都是回溯法，但是他們的目的不一樣，八皇后只要求把所有的棋子放在棋盤上（即只需解決深度最優(yōu)）。而01背包問(wèn)題不僅需要讓物品都放進(jìn)背包，而且要使得物品質(zhì)量最大，在八皇后問(wèn)題上多提出了一個(gè)限制。
問(wèn)題的解空間
用回溯法解問(wèn)題時(shí)，應(yīng)明確定義問(wèn)題的解空間。問(wèn)題的解空間至少包含問(wèn)題的一個(gè)(最優(yōu))解。對(duì)于 n=3 時(shí)的 0/1 背包問(wèn)題，可用一棵完全二叉樹表示解空間，如圖所示：
求解步驟
1)針對(duì)所給問(wèn)題，定義問(wèn)題的解空間；
2)確定易于搜索的解空間結(jié)構(gòu)；
3)以深度優(yōu)先方式搜索解空間，并在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索。
常用的剪枝函數(shù)：用約束函數(shù)在擴(kuò)展結(jié)點(diǎn)處剪去不滿足約束的子樹；用限界函數(shù)剪去得不到最優(yōu)解的子樹。
回溯法對(duì)解空間做深度優(yōu)先搜索時(shí)，有遞歸回溯和迭代回溯（非遞歸）兩種方法，但一般情況下用遞歸方法實(shí)現(xiàn)回溯法。
算法描述
解 0/1 背包問(wèn)題的回溯法在搜索解空間樹時(shí)，只要其左兒子結(jié)點(diǎn)是一個(gè)可行結(jié)點(diǎn)，搜索就進(jìn)入其左子樹。當(dāng)右子樹中有可能包含最優(yōu)解時(shí)才進(jìn)入右子樹搜索。否則將右子樹剪去。
我們直接上手代碼解決這個(gè)問(wèn)題
算法部分
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) //是否超過(guò)了最大價(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ú)問(wèn)題其實(shí)就是一個(gè)的八皇后問(wèn)題。在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ì)枯燥。
回溯算法代碼：https://github.com/haixiansheng/algorithm
如果只是想對(duì)算法進(jìn)行了解，你就可以選擇關(guān)注“小白算法”公眾號(hào)，我們每周都會(huì)有新的算法介紹，并有相關(guān)學(xué)習(xí)資料贈(zèng)送。
