什么是回溯法

回溯法也可以叫做回溯搜索法，它是一種搜索的方式。

回溯是遞歸的副產(chǎn)品，只要有遞歸就會(huì)有回溯。

所以回溯函數(shù)也就是遞歸函數(shù)，指的都是一個(gè)函數(shù)。

回溯法的效率

回溯法的性能如何呢，雖然回溯法很難，很不好理解，但是回溯法并不是什么高效的算法。

因?yàn)榛厮莸谋举|(zhì)是窮舉，窮舉所有可能，然后選出我們想要的答案，如果想讓回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是窮舉的本質(zhì)。

那么既然回溯法并不高效為什么還要用它呢？

因?yàn)闆]得選，一些問題能暴力搜出來就不錯(cuò)了，撐死了再剪枝一下，還沒有更高效的解法。

回溯法，一般可以解決如下幾種問題：

組合問題：N個(gè)數(shù)里面按一定規(guī)則找出k個(gè)數(shù)的集合
切割問題：一個(gè)字符串按一定規(guī)則有幾種切割方式
子集問題：一個(gè)N個(gè)數(shù)的集合里有多少符合條件的子集
排列問題：N個(gè)數(shù)按一定規(guī)則全排列，有幾種排列方式
棋盤問題：N皇后，解數(shù)獨(dú)等等

組合是不強(qiáng)調(diào)元素順序的，排列是強(qiáng)調(diào)元素順序。

如何理解回溯法

回溯法解決的問題都可以抽象為樹形結(jié)構(gòu)

因?yàn)榛厮莘ń鉀Q的都是在集合中遞歸查找子集，集合的大小構(gòu)成樹的寬度，遞歸的深度構(gòu)成樹的深度。

遞歸就要有終止條件，所以必然是一顆高度有限的樹（N叉樹）。

回溯法模板

回溯三部曲。

回溯函數(shù)模板返回值以及參數(shù)

回溯算法中函數(shù)返回值一般為void。

再來看一下參數(shù)，因?yàn)榛厮菟惴ㄐ枰膮?shù)可不像二叉樹遞歸的時(shí)候那么容易一次性確定下來，所以一般是先寫邏輯，然后需要什么參數(shù)，就填什么參數(shù)。

回溯函數(shù)偽代碼如下：

void backtracking(參數(shù))

回溯函數(shù)終止條件
既然是樹形結(jié)構(gòu)，那么我們?cè)谥v解二叉樹的遞歸的時(shí)候，就知道遍歷樹形結(jié)構(gòu)一定要有終止條件。
所以回溯也有要終止條件。

什么時(shí)候達(dá)到了終止條件，樹中就可以看出，一般來說搜到葉子節(jié)點(diǎn)了，也就找到了滿足條件的一條答案，把這個(gè)答案存放起來，并結(jié)束本層遞歸。

所以回溯函數(shù)終止條件偽代碼如下：

if (終止條件) {存放結(jié)果;return; }

回溯搜索的遍歷過程
在上面我們提到了，回溯法一般是在集合中遞歸搜索，集合的大小構(gòu)成了樹的寬度，遞歸的深度構(gòu)成的樹的深度。

如圖：

注意圖中，我特意舉例集合大小和孩子的數(shù)量是相等的！

回溯函數(shù)遍歷過程偽代碼如下：

for (選擇：本層集合中元素（樹中節(jié)點(diǎn)孩子的數(shù)量就是集合的大小）) {處理節(jié)點(diǎn);backtracking(路徑，選擇列表); // 遞歸回溯，撤銷處理結(jié)果 }

for循環(huán)就是遍歷集合區(qū)間，可以理解一個(gè)節(jié)點(diǎn)有多少個(gè)孩子，這個(gè)for循環(huán)就執(zhí)行多少次。

backtracking這里自己調(diào)用自己，實(shí)現(xiàn)遞歸。

大家可以從圖中看出for循環(huán)可以理解是橫向遍歷，backtracking（遞歸）就是縱向遍歷，這樣就把這棵樹全遍歷完了，一般來說，搜索葉子節(jié)點(diǎn)就是找的其中一個(gè)結(jié)果了。

分析完過程，回溯算法模板框架如下：

void backtracking(參數(shù)) {if (終止條件) {存放結(jié)果;return;}for (選擇：本層集合中元素（樹中節(jié)點(diǎn)孩子的數(shù)量就是集合的大小）) {處理節(jié)點(diǎn);backtracking(路徑，選擇列表); // 遞歸回溯，撤銷處理結(jié)果} }

這份模板很重要，后面做回溯法的題目都靠它了！

總結(jié)

本篇我們講解了，什么是回溯算法，知道了回溯和遞歸是相輔相成的。

接著提到了回溯法的效率，回溯法其實(shí)就是暴力查找，并不是什么高效的算法。

然后列出了回溯法可以解決幾類問題，可以看出每一類問題都不簡(jiǎn)單。

最后我們講到回溯法解決的問題都可以抽象為樹形結(jié)構(gòu)（N叉樹），并給出了回溯法的模板。

總結(jié)

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

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