C++回溯算法

為了滿足以上約束條件，我們需要添加剪枝操作：在搜索過程中，若遇到值為 $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è)柱子移動到另一個(gè)柱子，每次只能移動一個(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 背包問題通常使用動態(tài)規(guī)劃解決，以達(dá)到更高的時(shí)間效率。
• 旅行商是一個(gè)著名的 NP-Hard 問題，常用解法有遺傳算法和蟻群算法等。
• 最大團(tuán)問題是圖論中的一個(gè)經(jīng)典問題，可用貪心等啟發(fā)式算法來解決。