C++回溯算法

「回溯算法 backtracking algorithm」是一種通過窮舉來解決問題的方法，它的核心思想是從一個(gè)初始狀態(tài)出發(fā)，暴力搜索所有可能的解決方案，當(dāng)遇到正確的解則將其記錄，直到找到解或者嘗試了所有可能的選擇都無法找到解為止。

回溯算法通常采用“深度優(yōu)先搜索”來遍歷解空間。在二叉樹章節(jié)中，我們提到前序、中序和后序遍歷都屬于深度優(yōu)先搜索。接下來，我們利用前序遍歷構(gòu)造一個(gè)回溯問題，逐步了解回溯算法的工作原理。

對于此題，我們前序遍歷這顆樹，并判斷當(dāng)前節(jié)點(diǎn)的值是否為 $7$ ，若是則將該節(jié)點(diǎn)的值加入到結(jié)果列表 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)訪問到值為 $7$ 的節(jié)點(diǎn)時(shí)，則復(fù)制 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   嘗試與回退

13.1.2   剪枝

復(fù)雜的回溯問題通常包含一個(gè)或多個(gè)約束條件，約束條件通常可用于“剪枝”。

為了滿足以上約束條件，我們需要添加剪枝操作：在搜索過程中，若遇到值為 $3$ 的節(jié)點(diǎn)，則提前返回，停止繼續(xù)搜索。

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ù)約束條件剪枝

13.1.3   框架代碼?

接下來，我們嘗試將回溯的“嘗試、回退、剪枝”的主體框架提煉出來，提升代碼的通用性。

在以下框架代碼中，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ù)題意，我們在找到值為 $7$ 的節(jié)點(diǎn)后應(yīng)該繼續(xù)搜索，因此需要將記錄解之后的 return 語句刪除。圖 13-4 對比了保留或刪除 return 語句的搜索過程。

圖 13-4   保留與刪除 return 的搜索過程對比

相比基于前序遍歷的代碼實(shí)現(xiàn)，基于回溯算法框架的代碼實(shí)現(xiàn)雖然顯得啰嗦，但通用性更好。實(shí)際上，許多回溯問題都可以在該框架下解決。我們只需根據(jù)具體問題來定義 state 和 choices ，并實(shí)現(xiàn)框架中的各個(gè)方法即可。

13.1.4   常用術(shù)語

為了更清晰地分析算法問題，我們總結(jié)一下回溯算法中常用術(shù)語的含義，并對照例題三給出對應(yīng)示例。

表 13-1   常見的回溯算法術(shù)語

13.1.5   優(yōu)勢與局限性

回溯算法本質(zhì)上是一種深度優(yōu)先搜索算法，它嘗試所有可能的解決方案直到找到滿足條件的解。這種方法的優(yōu)勢在于它能夠找到所有可能的解決方案，而且在合理的剪枝操作下，具有很高的效率。

然而，在處理大規(guī)模或者復(fù)雜問題時(shí)，回溯算法的運(yùn)行效率可能難以接受。

• 時(shí)間：回溯算法通常需要遍歷狀態(tài)空間的所有可能，時(shí)間復(fù)雜度可以達(dá)到指數(shù)階或階乘階。
• 空間：在遞歸調(diào)用中需要保存當(dāng)前的狀態(tài)（例如路徑、用于剪枝的輔助變量等），當(dāng)深度很大時(shí)，空間需求可能會變得很大。

即便如此，回溯算法仍然是某些搜索問題和約束滿足問題的最佳解決方案。對于這些問題，由于無法預(yù)測哪些選擇可生成有效的解，因此我們必須對所有可能的選擇進(jìn)行遍歷。在這種情況下，關(guān)鍵是如何進(jìn)行效率優(yōu)化，常見的效率優(yōu)化方法有兩種。

• 剪枝：避免搜索那些肯定不會產(chǎn)生解的路徑，從而節(jié)省時(shí)間和空間。
• 啟發(fā)式搜索：在搜索過程中引入一些策略或者估計(jì)值，從而優(yōu)先搜索最有可能產(chǎn)生有效解的路徑。

13.1.6   回溯典型例題

回溯算法可用于解決許多搜索問題、約束滿足問題和組合優(yōu)化問題。

搜索問題：這類問題的目標(biāo)是找到滿足特定條件的解決方案。

• 全排列問題：給定一個(gè)集合，求出其所有可能的排列組合。
• 子集和問題：給定一個(gè)集合和一個(gè)目標(biāo)和，找到集合中所有和為目標(biāo)和的子集。
• 漢諾塔問題：給定三個(gè)柱子和一系列大小不同的圓盤，要求將所有圓盤從一個(gè)柱子移動(dòng)到另一個(gè)柱子，每次只能移動(dòng)一個(gè)圓盤，且不能將大圓盤放在小圓盤上。

約束滿足問題：這類問題的目標(biāo)是找到滿足所有約束條件的解。

• $n$ 皇后：在 $n\times n$ 的棋盤上放置 $n$ 個(gè)皇后，使得它們互不攻擊。
• 數(shù)獨(dú)：在 $9\times 9$ 的網(wǎng)格中填入數(shù)字 $1$ ~ $9$ ，使得每行、每列和每個(gè) $3\times 3$ 子網(wǎng)格中的數(shù)字不重復(fù)。
• 圖著色問題：給定一個(gè)無向圖，用最少的顏色給圖的每個(gè)頂點(diǎn)著色，使得相鄰頂點(diǎn)顏色不同。

組合優(yōu)化問題：這類問題的目標(biāo)是在一個(gè)組合空間中找到滿足某些條件的最優(yōu)解。

• 0-1 背包問題：給定一組物品和一個(gè)背包，每個(gè)物品有一定的價(jià)值和重量，要求在背包容量限制內(nèi)，選擇物品使得總價(jià)值最大。
• 旅行商問題：在一個(gè)圖中，從一個(gè)點(diǎn)出發(fā)，訪問所有其他點(diǎn)恰好一次后返回起點(diǎn)，求最短路徑。
• 最大團(tuán)問題：給定一個(gè)無向圖，找到最大的完全子圖，即子圖中的任意兩個(gè)頂點(diǎn)之間都有邊相連。

請注意，對于許多組合優(yōu)化問題，回溯都不是最優(yōu)解決方案。

• 0-1 背包問題通常使用動(dòng)態(tài)規(guī)劃解決，以達(dá)到更高的時(shí)間效率。
• 旅行商是一個(gè)著名的 NP-Hard 問題，常用解法有遺傳算法和蟻群算法等。
• 最大團(tuán)問題是圖論中的一個(gè)經(jīng)典問題，可用貪心等啟發(fā)式算法來解決。