一、基本概念

??回溯法，又稱為試探法，按選優(yōu)條件向前不斷搜索，以達(dá)到目標(biāo)。但是當(dāng)探索到某一步時(shí)，如果發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)，就會(huì)退回一步重新選擇，這種達(dá)不到目的就退回再走的算法稱為回溯法。

與窮舉法的區(qū)別和聯(lián)系：

相同點(diǎn)：它們都是基于試探的。

區(qū)別：窮舉法要將一個(gè)解的各個(gè)部分全部生成后，才檢查是否滿足條件，若不滿足，則直接放棄該完整解，然后再嘗試另一個(gè)可能的完整解，它并沒(méi)有沿著一個(gè)可能的完整解的各個(gè)部分逐步回退生成解的過(guò)程。而對(duì)于回溯法，一個(gè)解的各個(gè)部分是逐步生成的，當(dāng)發(fā)現(xiàn)當(dāng)前生成的某部分不滿足約束條件時(shí)，就放棄該步所做的工作，退到上一步進(jìn)行新的嘗試，而不是放棄整個(gè)解重來(lái)。

二、基本思想

??對(duì)于可以使用回溯法來(lái)解決的問(wèn)題，首先可以將其解空間可以看成一棵解空間樹(shù)。在回溯法中，每次擴(kuò)大當(dāng)前部分解時(shí)，都面臨一個(gè)可選的狀態(tài)集合（所有的子樹(shù)），每個(gè)樹(shù)結(jié)點(diǎn)代表一個(gè)可能的部分解。

??回溯法對(duì)任一解的生成，一般都采用逐步擴(kuò)大解的方式。每前進(jìn)一步，都試圖在當(dāng)前部分解的基礎(chǔ)上擴(kuò)大該部分解。它在問(wèn)題的狀態(tài)空間樹(shù)中，從開(kāi)始結(jié)點(diǎn)（根結(jié)點(diǎn)）出發(fā)，以深度優(yōu)先搜索整個(gè)狀態(tài)空間。這個(gè)開(kāi)始結(jié)點(diǎn)成為活結(jié)點(diǎn)，同時(shí)也成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。在當(dāng)前擴(kuò)展結(jié)點(diǎn)處，搜索向縱深方向移至一個(gè)新結(jié)點(diǎn)。這個(gè)新結(jié)點(diǎn)成為新的活結(jié)點(diǎn)，并成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。如果在當(dāng)前擴(kuò)展結(jié)點(diǎn)處不能再向縱深方向移動(dòng)，則當(dāng)前擴(kuò)展結(jié)點(diǎn)就成為死結(jié)點(diǎn)。此時(shí)，應(yīng)往回移動(dòng)（回溯）至最近的活結(jié)點(diǎn)處，并使這個(gè)活結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。回溯法以這種工作方式遞歸地在狀態(tài)空間中搜索，直到找到所要求的解或解空間中已無(wú)活結(jié)點(diǎn)時(shí)為止。

三、解題步驟(思路)

針對(duì)給定的問(wèn)題，定義問(wèn)題的解空間；

確定易于搜索的解空間結(jié)構(gòu)；

以深度優(yōu)先方式搜索解空間，并且在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索。（這里的剪枝函數(shù)就是判斷該結(jié)點(diǎn)是否滿足問(wèn)題題設(shè)，如果滿足則向下搜索，不滿足則在此剪枝）

四、算法框架

1. 遞歸實(shí)現(xiàn)：

?變量解釋：

??x：存儲(chǔ)試探解的數(shù)組

??n：解空間樹(shù)的層數(shù)

??i：搜索目前所達(dá)到的層數(shù)

??start：子節(jié)點(diǎn)解空間的最小值

??end：子節(jié)點(diǎn)解空間的最大值

int x[n]; void backtrack (int i) {if (i > n) {回溯結(jié)束； } else {// 這里回溯子節(jié)點(diǎn)的解空間為start~endfor (j = start; j <= end; j++) {// 滿足條件，向下搜索if (j滿足題設(shè)條件) {x[i] = j;backtrack(i+1);// 不滿足條件，在此剪枝（即回溯）} else {}}} }

?2. 非遞歸實(shí)現(xiàn)：

?變量解釋：

??x：存儲(chǔ)試探解的數(shù)組

??n：解空間樹(shù)的層數(shù)

??i：搜索目前所達(dá)到的層數(shù)

??start：子節(jié)點(diǎn)解空間的最小值

??end：子節(jié)點(diǎn)解空間的最大值

void f_backtrack(int i) {//初始化解向量for (int j = 0; j < n; j++) {x[j] = 1;}while (i >= 1) {while (x[i] <= n) {if (place(i)) {if (i == n) {回溯結(jié)束；break;// 滿足條件，向下搜索} else {i++;x[i] = 1;}// 不滿足條件，在此剪枝（即回溯）} else {x[i]++;}}//遍歷完子節(jié)點(diǎn)解空間后，向上剪枝（即回溯）x[i] = 1;i--;x[i]++;} }

相比之下，遞歸設(shè)計(jì)方法比較簡(jiǎn)單，而非遞歸方法，也就是循環(huán)方法設(shè)計(jì)細(xì)節(jié)比較多，但如果掌握了其特點(diǎn)，對(duì)不同問(wèn)題的適用性很強(qiáng)（即代碼只需要很少的修改就可以應(yīng)用到不同問(wèn)題），加之其最大的優(yōu)勢(shì)：效率更高（因?yàn)檫f歸的實(shí)現(xiàn)是通過(guò)調(diào)用函數(shù)本身，函數(shù)調(diào)用的時(shí)候，每次調(diào)用時(shí)要做地址保存，參數(shù)傳遞等，這是通過(guò)一個(gè)遞歸工作棧實(shí)現(xiàn)的。具體是每次調(diào)用函數(shù)本身要保存的內(nèi)容包括：局部變量、形參、調(diào)用函數(shù)地址、返回值。那么，如果遞歸調(diào)用N次，就要分配N局部變量、N形參、N調(diào)用函數(shù)地址、N返回值。這勢(shì)必是影響效率的。）

五、經(jīng)典實(shí)現(xiàn)

經(jīng)典問(wèn)題：八皇后問(wèn)題

??八皇后問(wèn)題，是一個(gè)古老而著名的問(wèn)題，是回溯算法的典型例題。該問(wèn)題是十九世紀(jì)著名的數(shù)學(xué)家高斯1850年提出：

??在8X8格的國(guó)際象棋上擺放八個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上（斜率為1），問(wèn)有多少種擺法。高斯認(rèn)為有76種方案。1854年在柏林的象棋雜志上不同的作者發(fā)表了40種不同的解，后來(lái)有人用圖論的方法解出92種結(jié)果。

遞歸實(shí)現(xiàn)為以下代碼中backtrack方法

非遞歸實(shí)現(xiàn)為以下代碼中f_backtrack方法：

#include <iostream> using namespace std; int n; int *x; int sum; bool place(int k) {for (int j = 1; j < k; j++)if (abs(x[k] - x[j]) == abs(k - j) || x[j] == x[k])return false;return true; }void output() {sum++; //sum為所有的可行的解for (int m = 1; m <= n; m++){cout << "<" << m << "," << x[m] << ">"; //這一行用輸出當(dāng)遞歸到葉節(jié)點(diǎn)的時(shí)候，一個(gè)可行解}cout << endl; }void f_backtrack(int i) {for (int j = 0; j < n; j++){ //初始化解向量x[j] = 1;}while (i >= 1){while (x[i] <= n){if (place(i)){ //得到可行解if (i == n){output();break;} //得到最終可行解，退出else{ //得到部分可行解，搜索下一行i++;x[i] = 1;}}else{ //當(dāng)前解不可行x[i]++;}}x[i] = 1;i--;x[i]++; //回溯} }void backtrack(int i) {if (i > n){output();}else{for (int j = 1; j <= n; j++){x[i] = j;if (place(i)){backtrack(i + 1);}else{}}} }int main() {n = 8;sum = 0;x = new int[n + 1];for (int i = 0; i <= n; i++)x[i] = 0;backtrack(1);cout << "方案共有" << sum << endl; }

轉(zhuǎn)載于:https://www.cnblogs.com/codernie/p/9070015.html

總結(jié)

以上是生活随笔為你收集整理的五大经典算法之回溯法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。