微信公眾號(hào)：小白算法
關(guān)注可了解更多算法改览，并能領(lǐng)取免費(fèi)資料。問題或建議缤言，請公眾號(hào)留言;
文末有資料領(lǐng)取
上一期算法回顧--貪婪法：https://mp.weixin.qq.com/s/978Tdplj3IaSG2dc-5F-aw
算法導(dǎo)讀
本期算法講解思路：
白話算法->算法思路->實(shí)例：八皇后問題->實(shí)例：01背包問題->算法教你玩數(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)”瞻离。
白話：回溯法可以理解為通過選擇不同的岔路口尋找目的地，一個(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à)值泛鸟。
對于一個(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))解勾徽。對于 n=3 時(shí)的 0/1 背包問題，可用一棵完全二叉樹表示解空間蓖谢，如圖所示：
求解步驟
1)針對所給問題譬涡，定義問題的解空間闪幽；
2)確定易于搜索的解空間結(jié)構(gòu)啥辨；
3)以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索盯腌。
常用的剪枝函數(shù)：用約束函數(shù)在擴(kuò)展結(jié)點(diǎn)處剪去不滿足約束的子樹溉知；用限界函數(shù)剪去得不到最優(yōu)解的子樹。
回溯法對解空間做深度優(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<<"請輸入背包最大容量:"<<endl;;
cin>>TotCap;
cout<<"請輸入物品個(gè)數(shù):"<<endl;
cin>>n;
cout<<"請依次輸入物品的重量:"<<endl;
for(i=1;i<=n;i++)
cin>>w[i];
cout<<"請依次輸入物品的價(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};
//查詢該行里是否有這個(gè)值
bool Isvaild(int count)
{
int i = count/9;
int j = count%9;
//檢測行
for(int iter = 0;iter!=j;iter++)
{
if(a[i][iter]==a[i][j])
{
return 1;
}
}
//檢測列
for(int iter=0;iter!=i;iter++)
{
if(a[iter][j]==a[i][j])
{
return 1;
}
}
//檢測九宮
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ù)雜度相對高捐晶。
如果你想了解更深的了解回溯算法，可以翻閱相關(guān)的數(shù)據(jù)結(jié)構(gòu)書籍妄辩。當(dāng)然惑灵，如果你選擇深入了解這個(gè)算法，必然會(huì)枯燥眼耀。
回溯算法代碼：https://github.com/haixiansheng/algorithm
如果只是想對算法進(jìn)行了解英支，你就可以選擇關(guān)注“小白算法”公眾號(hào)，我們每周都會(huì)有新的算法介紹哮伟，并有相關(guān)學(xué)習(xí)資料贈(zèng)送干花。
