「回溯算法 backtracking algorithm」是一種通過窮舉來解決問題的方法,它的核心思想是從一個(gè)初始狀態(tài)出發(fā),暴力搜索所有可能的解決方案,當(dāng)遇到正確的解則將其記錄,直到找到解或者嘗試了所有可能的選擇都無法找到解為止。
回溯算法通常采用“深度優(yōu)先搜索”來遍歷解空間。在二叉樹章節(jié)中,我們提到前序、中序和后序遍歷都屬于深度優(yōu)先搜索。接下來,我們利用前序遍歷構(gòu)造一個(gè)回溯問題,逐步了解回溯算法的工作原理。
例題一
給定一個(gè)二叉樹,搜索并記錄所有值為
對于此題,我們前序遍歷這顆樹,并判斷當(dāng)前節(jié)點(diǎn)的值是否為 res
之中。相關(guān)過程實(shí)現(xiàn)如圖 13-1 和以下代碼所示。
preorder_traversal_i_compact.cpp
/* 前序遍歷:例題一 */
void preOrder(TreeNode *root) {
if (root == nullptr) {
return;
}
if (root->val == 7) {
// 記錄解
res.push_back(root);
}
preOrder(root->left);
preOrder(root->right);
}
圖 13-1 在前序遍歷中搜索節(jié)點(diǎn)
之所以稱之為回溯算法,是因?yàn)樵撍惴ㄔ谒阉鹘饪臻g時(shí)會采用“嘗試”與“回退”的策略。當(dāng)算法在搜索過程中遇到某個(gè)狀態(tài)無法繼續(xù)前進(jìn)或無法得到滿足條件的解時(shí),它會撤銷上一步的選擇,退回到之前的狀態(tài),并嘗試其他可能的選擇。
對于例題一,訪問每個(gè)節(jié)點(diǎn)都代表一次“嘗試”,而越過葉結(jié)點(diǎn)或返回父節(jié)點(diǎn)的 return
則表示“回退”。
值得說明的是,回退并不僅僅包括函數(shù)返回。為解釋這一點(diǎn),我們對例題一稍作拓展。
例題二
在二叉樹中搜索所有值為
在例題一代碼的基礎(chǔ)上,我們需要借助一個(gè)列表 path
記錄訪問過的節(jié)點(diǎn)路徑。當(dāng)訪問到值為 path
并添加進(jìn)結(jié)果列表 res
。遍歷完成后,res
中保存的就是所有的解。
preorder_traversal_ii_compact.cpp
/* 前序遍歷:例題二 */
void preOrder(TreeNode *root) {
if (root == nullptr) {
return;
}
// 嘗試
path.push_back(root);
if (root->val == 7) {
// 記錄解
res.push_back(path);
}
preOrder(root->left);
preOrder(root->right);
// 回退
path.pop_back();
}
在每次“嘗試”中,我們通過將當(dāng)前節(jié)點(diǎn)添加進(jìn) path
來記錄路徑;而在“回退”前,我們需要將該節(jié)點(diǎn)從 path
中彈出,以恢復(fù)本次嘗試之前的狀態(tài)。
觀察圖 13-2 所示的過程,我們可以將嘗試和回退理解為“前進(jìn)”與“撤銷”,兩個(gè)操作是互為逆向的。
圖 13-2 嘗試與回退
復(fù)雜的回溯問題通常包含一個(gè)或多個(gè)約束條件,約束條件通??捎糜凇凹糁Α?/strong>。
例題三
在二叉樹中搜索所有值為
為了滿足以上約束條件,我們需要添加剪枝操作:在搜索過程中,若遇到值為
preorder_traversal_iii_compact.cpp
/* 前序遍歷:例題三 */
void preOrder(TreeNode *root) {
// 剪枝
if (root == nullptr || root->val == 3) {
return;
}
// 嘗試
path.push_back(root);
if (root->val == 7) {
// 記錄解
res.push_back(path);
}
preOrder(root->left);
preOrder(root->right);
// 回退
path.pop_back();
}
剪枝是一個(gè)非常形象的名詞。如圖 13-3 所示,在搜索過程中,我們“剪掉”了不滿足約束條件的搜索分支,避免許多無意義的嘗試,從而提高了搜索效率。
圖 13-3 根據(jù)約束條件剪枝
接下來,我們嘗試將回溯的“嘗試、回退、剪枝”的主體框架提煉出來,提升代碼的通用性。
在以下框架代碼中,state
表示問題的當(dāng)前狀態(tài),choices
表示當(dāng)前狀態(tài)下可以做出的選擇。
/* 回溯算法框架 */
void backtrack(State *state, vector<Choice *> &choices, vector<State *> &res) {
// 判斷是否為解
if (isSolution(state)) {
// 記錄解
recordSolution(state, res);
// 停止繼續(xù)搜索
return;
}
// 遍歷所有選擇
for (Choice choice : choices) {
// 剪枝:判斷選擇是否合法
if (isValid(state, choice)) {
// 嘗試:做出選擇,更新狀態(tài)
makeChoice(state, choice);
backtrack(state, choices, res);
// 回退:撤銷選擇,恢復(fù)到之前的狀態(tài)
undoChoice(state, choice);
}
}
}
接下來,我們基于框架代碼來解決例題三。狀態(tài) state
為節(jié)點(diǎn)遍歷路徑,選擇 choices
為當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)和右子節(jié)點(diǎn),結(jié)果 res
是路徑列表。
preorder_traversal_iii_template.cpp
/* 判斷當(dāng)前狀態(tài)是否為解 */
bool isSolution(vector<TreeNode *> &state) {
return !state.empty() && state.back()->val == 7;
}
/* 記錄解 */
void recordSolution(vector<TreeNode *> &state, vector<vector<TreeNode *>> &res) {
res.push_back(state);
}
/* 判斷在當(dāng)前狀態(tài)下,該選擇是否合法 */
bool isValid(vector<TreeNode *> &state, TreeNode *choice) {
return choice != nullptr && choice->val != 3;
}
/* 更新狀態(tài) */
void makeChoice(vector<TreeNode *> &state, TreeNode *choice) {
state.push_back(choice);
}
/* 恢復(fù)狀態(tài) */
void undoChoice(vector<TreeNode *> &state, TreeNode *choice) {
state.pop_back();
}
/* 回溯算法:例題三 */
void backtrack(vector<TreeNode *> &state, vector<TreeNode *> &choices, vector<vector<TreeNode *>> &res) {
// 檢查是否為解
if (isSolution(state)) {
// 記錄解
recordSolution(state, res);
}
// 遍歷所有選擇
for (TreeNode *choice : choices) {
// 剪枝:檢查選擇是否合法
if (isValid(state, choice)) {
// 嘗試:做出選擇,更新狀態(tài)
makeChoice(state, choice);
// 進(jìn)行下一輪選擇
vector<TreeNode *> nextChoices{choice->left, choice->right};
backtrack(state, nextChoices, res);
// 回退:撤銷選擇,恢復(fù)到之前的狀態(tài)
undoChoice(state, choice);
}
}
}
根據(jù)題意,我們在找到值為 return
語句刪除。圖 13-4 對比了保留或刪除 return
語句的搜索過程。
圖 13-4 保留與刪除 return 的搜索過程對比
相比基于前序遍歷的代碼實(shí)現(xiàn),基于回溯算法框架的代碼實(shí)現(xiàn)雖然顯得啰嗦,但通用性更好。實(shí)際上,許多回溯問題都可以在該框架下解決。我們只需根據(jù)具體問題來定義 state
和 choices
,并實(shí)現(xiàn)框架中的各個(gè)方法即可。
為了更清晰地分析算法問題,我們總結(jié)一下回溯算法中常用術(shù)語的含義,并對照例題三給出對應(yīng)示例。
表 13-1 常見的回溯算法術(shù)語
名詞 | 定義 | 例題三 |
---|---|---|
解 Solution | 解是滿足問題特定條件的答案,可能有一個(gè)或多個(gè) | 根節(jié)點(diǎn)到節(jié)點(diǎn) |
約束條件 Constraint | 約束條件是問題中限制解的可行性的條件,通常用于剪枝 | 路徑中不包含節(jié)點(diǎn) |
狀態(tài) State | 狀態(tài)表示問題在某一時(shí)刻的情況,包括已經(jīng)做出的選擇 | 當(dāng)前已訪問的節(jié)點(diǎn)路徑,即 path 節(jié)點(diǎn)列表 |
嘗試 Attempt | 嘗試是根據(jù)可用選擇來探索解空間的過程,包括做出選擇,更新狀態(tài),檢查是否為解 | 遞歸訪問左(右)子節(jié)點(diǎn),將節(jié)點(diǎn)添加進(jìn) path ,判斷節(jié)點(diǎn)的值是否為 |
回退 Backtracking | 回退指遇到不滿足約束條件的狀態(tài)時(shí),撤銷前面做出的選擇,回到上一個(gè)狀態(tài) | 當(dāng)越過葉結(jié)點(diǎn)、結(jié)束結(jié)點(diǎn)訪問、遇到值為 |
剪枝 Pruning | 剪枝是根據(jù)問題特性和約束條件避免無意義的搜索路徑的方法,可提高搜索效率 | 當(dāng)遇到值為 |
Tip
問題、解、狀態(tài)等概念是通用的,在分治、回溯、動態(tài)規(guī)劃、貪心等算法中都有涉及。
回溯算法本質(zhì)上是一種深度優(yōu)先搜索算法,它嘗試所有可能的解決方案直到找到滿足條件的解。這種方法的優(yōu)勢在于它能夠找到所有可能的解決方案,而且在合理的剪枝操作下,具有很高的效率。
然而,在處理大規(guī)?;蛘邚?fù)雜問題時(shí),回溯算法的運(yùn)行效率可能難以接受。
即便如此,回溯算法仍然是某些搜索問題和約束滿足問題的最佳解決方案。對于這些問題,由于無法預(yù)測哪些選擇可生成有效的解,因此我們必須對所有可能的選擇進(jìn)行遍歷。在這種情況下,關(guān)鍵是如何進(jìn)行效率優(yōu)化,常見的效率優(yōu)化方法有兩種。
回溯算法可用于解決許多搜索問題、約束滿足問題和組合優(yōu)化問題。
搜索問題:這類問題的目標(biāo)是找到滿足特定條件的解決方案。
約束滿足問題:這類問題的目標(biāo)是找到滿足所有約束條件的解。
組合優(yōu)化問題:這類問題的目標(biāo)是在一個(gè)組合空間中找到滿足某些條件的最優(yōu)解。
請注意,對于許多組合優(yōu)化問題,回溯都不是最優(yōu)解決方案。
更多建議: