C++回溯 小結(jié)

重點(diǎn)回顧

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

Q & A