C++回溯 小結(jié)

重點回顧

• 回溯算法本質(zhì)是窮舉法，通過對解空間進行深度優(yōu)先遍歷來尋找符合條件的解。在搜索過程中，遇到滿足條件的解則記錄，直至找到所有解或遍歷完成后結(jié)束。
• 回溯算法的搜索過程包括嘗試與回退兩個部分。它通過深度優(yōu)先搜索來嘗試各種選擇，當(dāng)遇到不滿足約束條件的情況時，則撤銷上一步的選擇，退回到之前的狀態(tài)，并繼續(xù)嘗試其他選擇。嘗試與回退是兩個方向相反的操作。
• 回溯問題通常包含多個約束條件，它們可用于實現(xiàn)剪枝操作。剪枝可以提前結(jié)束不必要的搜索分支，大幅提升搜索效率。
• 回溯算法主要可用于解決搜索問題和約束滿足問題。組合優(yōu)化問題雖然可以用回溯算法解決，但往往存在更高效率或更好效果的解法。
• 全排列問題旨在搜索給定集合的所有可能的排列。我們借助一個數(shù)組來記錄每個元素是否被選擇，剪枝掉重復(fù)選擇同一元素的搜索分支，確保每個元素只被選擇一次。
• 在全排列問題中，如果集合中存在重復(fù)元素，則最終結(jié)果會出現(xiàn)重復(fù)排列。我們需要約束相等元素在每輪中只能被選擇一次，這通常借助一個哈希表來實現(xiàn)。
• 子集和問題的目標(biāo)是在給定集合中找到和為目標(biāo)值的所有子集。集合不區(qū)分元素順序，而搜索過程會輸出所有順序的結(jié)果，產(chǎn)生重復(fù)子集。我們在回溯前將數(shù)據(jù)進行排序，并設(shè)置一個變量來指示每一輪的遍歷起點，從而將生成重復(fù)子集的搜索分支進行剪枝。
• 對于子集和問題，數(shù)組中的相等元素會產(chǎn)生重復(fù)集合。我們利用數(shù)組已排序的前置條件，通過判斷相鄰元素是否相等實現(xiàn)剪枝，從而確保相等元素在每輪中只能被選中一次。
• $n$ 皇后旨在尋找將 $n$ 個皇后放置到 $n\times n$ 尺寸棋盤上的方案，要求所有皇后兩兩之間無法攻擊對方。該問題的約束條件有行約束、列約束、主對角線和副對角線約束。為滿足行約束，我們采用按行放置的策略，保證每一行放置一個皇后。
• 列約束和對角線約束的處理方式類似。對于列約束，我們利用一個數(shù)組來記錄每一列是否有皇后，從而指示選中的格子是否合法。對于對角線約束，我們借助兩個數(shù)組來分別記錄該主、副對角線是否存在皇后；難點在于找處在到同一主（副）對角線上格子滿足的行列索引規(guī)律。

Q & A