微信公眾號：小白算法
關注可了解更多算法，并能領取免費資料。問題或建議，請公眾號留言;小白算法，簡單白話算法，每個人都能看懂的算法
上一期算法回顧--貪婪法：https://mp.weixin.qq.com/s/978Tdplj3IaSG2dc-5F-aw

算法導讀

本期算法講解思路：
白話算法->算法思路->實例：八皇后問題->實例：01背包問題->算法教你玩數獨

白話算法

回溯法(back tracking)(探索與回溯法)是一種選優搜索法，又稱為試探法，按選優條件向前搜索，以達到目標。但當探索到某一步時，發現原先選擇并不優或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法，而滿足回溯條件的某個狀態的點稱為“回溯點”。

白話：回溯法可以理解為通過選擇不同的岔路口尋找目的地，一個岔路口一個岔路口的去嘗試找到目的地。如果走錯了路，繼續返回來找到岔路口的另一條路，直到找到目的地。

實例一：八皇后問題

八皇后問題是一個古老而著名的問題，是回溯算法的典型例題。該問題是十九世紀著名的數學家高斯1850年提出：在8X8格的國際象棋上擺放八個皇后(棋子)，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上。

小白面試經：理解如何解決這個問題，回溯法的精髓已經get。如果只是想了解算法面試知識，知道解決這個問題就能完成你的算法積累了。想快速掌握算法，可以直接查看解題思路的四個步驟。

八皇后問題解題思路：

問題簡化：下面我們將八皇后問題轉化為四皇后問題，并用回溯法來找到它的解目的：在4x4棋盤上，使得4個皇后不能在同行同列以及同斜線上。

step1
嘗試先放置第一枚皇后，被涂黑的地方是不能放皇后

step2
第二行的皇后只能放在第三格或第四格，比方我們放第三格，則：

此時我們也能理解為什么叫皇后問題了，皇后旁邊容不下其他皇后。而在同一個房間放下四個皇后確實是個不容易的問題。

step3
可以看到再難以放下第三個皇后，此時我們就要用到回溯算法了。我們把第二個皇后更改位置，此時我們能放下第三枚皇后了。

step4
雖然是能放置第三個皇后，但是第四個皇后又無路可走了。返回上層調用(3號皇后)，而3號也別無可去，繼續回溯上層調用(2號)，2號已然無路可去，繼續回溯上層(1號)，于是1號皇后改變位置如下，繼續回溯。

這就是回溯算法的精髓，雖然沒有最終把問題解決，但是可以劇透一波，就是根據這個算法，最終能夠把四位皇后放在4x4的棋盤里。也能用同樣的方法解決了八皇后問題。下面我們用代碼解決八皇后問題。

代碼實現八皇后問題

我們將算法也設置成兩步，第一步 ?我們要判斷每次輸入的皇后是否在同一行同一列，或者同一斜線上。

bool?is_ok(int?row){????????????//判斷設置的皇后是否在同一行，同一列，或者同一斜線上
????for?(int?j=0;j????{
????????if?(queen[row]==queen[j]||row-queen[row]==j-queen[j]||row+queen[row]==j+queen[j])
????????????return?false;???????
????}
????return?true;
}

第二步 ?我們用十行代碼來進入我們核心算法

void?back_tracking(int?row=0)????//算法函數，從第0行開始遍歷{
????if?(row==n)
????????t?++;???????????????//判斷若遍歷完成，就進行計數?????
????????for?(int?col=0;col//遍歷棋盤每一列
????????{
????????????queen[row]?=?col;???????????//將皇后的位置記錄在數組if?(is_ok(row))?????????????//判斷皇后的位置是否有沖突
????????????????back_tracking(row+1);???//遞歸，計算下一個皇后的位置
????????}
}

代碼實現算法也是比較簡單的，主要還是看是否掌握算法思想。

實例二：01背包問題

有N件物品和一個容量為V的背包。第i件物品的價格(即體積，下同)是w[i]，價值是c[i]。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。

這是最基礎的背包問題，總的來說就是：選還是不選，這是個問題

相當于用f[i][j]表示前i個背包裝入容量為v的背包中所可以獲得的最大價值。

對于一個物品，只有兩種情況

　　情況一: 第i件不放進去，這時所得價值為:f[i-1][v]

　　情況二: 第i件放進去，這時所得價值為：f[i-1][v-c[i]]+w[i]

接下來的實例屬于算法進階，可做了解
提兩點，
1.與上期貪婪法所解決的背包問題相比，回溯法將能更能顧及尋找全局最優。
2.背包問題與八皇后問題所用的算法雖然都是回溯法，但是他們的目的不一樣，八皇后只要求把所有的棋子放在棋盤上(即只需解決深度最優)。而01背包問題不僅需要讓物品都放進背包，而且要使得物品質量最大，在八皇后問題上多提出了一個限制。

問題的解空間

用回溯法解問題時，應明確定義問題的解空間。問題的解空間至少包含問題的一個(最優)解。對于 n=3 時的 0/1 背包問題，可用一棵完全二叉樹表示解空間，如圖所示：

1表示選取，0表示不選

求解步驟

1)針對所給問題，定義問題的解空間；

2)確定易于搜索的解空間結構；

3)以深度優先方式搜索解空間，并在搜索過程中用剪枝函數避免無效搜索。

常用的剪枝函數：用約束函數在擴展結點處剪去不滿足約束的子樹；用限界函數剪去得不到最優解的子樹。

回溯法對解空間做深度優先搜索時，有遞歸回溯和迭代回溯(非遞歸)兩種方法，但一般情況下用遞歸方法實現回溯法。

算法描述

　　解 0/1 背包問題的回溯法在搜索解空間樹時，只要其左兒子結點是一個可行結點，搜索就進入其左子樹。當右子樹中有可能包含最優解時才進入右子樹搜索。否則將右子樹剪去。

我們直接上手代碼解決這個問題

算法部分

void?dfs(int?i,int?cv,int?cw){??//cw當前包內物品重量，cv當前包內物品價值
????if(i>n)???
????{
????????if(cv>bestval)?????????????//是否超過了最大價值
????????{
????????????bestval=cv;????????????//得到最大價值
????????????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)??//滿足約束,繼續向子節點探索
????????????{
????????????????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];
????????????}
????????}
}

主函數部分

int?main(){
????int?i;
????bestval=0;?
????cout<<"請輸入背包最大容量:"<<endl;;
????cin>>TotCap;
????cout<<"請輸入物品個數:"<<endl;
????cin>>n;
????cout<<"請依次輸入物品的重量:"<<endl;
????for(i=1;i<=n;i++)?
????????cin>>w[i];
????cout<<"請依次輸入物品的價值:"<<endl;
????for(i=1;i<=n;i++)?
????????cin>>val[i];
????dfs(1,0,0);
????cout<<"最大價值為:"<<endl;
????cout<endl;cout<<"被選中的物品的標號依次是:"<<endl;for(i=1;i<=n;i++)if(bestx[i]==1)?cout<"?";cout<<endl;return?0;
}

回溯算法帶你玩數獨

我們可以想象，我們經常玩的數獨問題其實就是一個的八皇后問題。在9宮格數獨的約束為每一行每一列不能出現相同的數。這里我們限于篇幅，不將細講代碼了。

#include?
using?namespace?std;
#define???LEN??9
int?a[LEN][LEN]?=?{0};


//查詢該行里是否有這個值
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;p3;p++)
???{
????for(int?q=j/3*3;q3;q++)
????{??????
?????????if(p==i&&j==q)
?????????{?????????
???????????continue;
?????????}?????
?????????if(a[p][q]==a[i][j])
????????????{
????????????????return?1;
????????????}
???}
???}
???return?0;
}
void?print()
{
????cout<:"<<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))??//這個值不沖突
????????????{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列數字為已知。最后結果，

總結

回溯法屬于深度優先搜索，由于是全局搜索，復雜度相對高。
如果你想了解更深的了解回溯算法，可以翻閱相關的數據結構書籍。當然，如果你選擇深入了解這個算法，必然會枯燥。

回溯算法代碼：https://github.com/haixiansheng/algorithm

如果想對算法進行了解，你就可以選擇關注“小白算法”公眾號，我們每周都會有新的算法介紹，并有相關學習資料贈送。今天我們贈送的資料是《白話大數據與機器學習》，在公眾號發送“504”即可獲取。

總結

以上是生活随笔為你收集整理的人工智能实现a*算法解决八数码_小白带你学回溯算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。