13.5 小結¶
1. 重點回顧¶
- 回溯演算法本質是窮舉法，透過對解空間進行深度優先走訪來尋找符合條件的解。在搜尋過程中，遇到滿足條件的解則記錄，直至找到所有解或走訪完成後結束。
- 回溯演算法的搜尋過程包括嘗試與回退兩個部分。它透過深度優先搜尋來嘗試各種選擇，當遇到不滿足約束條件的情況時，則撤銷上一步的選擇，退回到之前的狀態，並繼續嘗試其他選擇。嘗試與回退是兩個方向相反的操作。
- 回溯問題通常包含多個約束條件，它們可用於實現剪枝操作。剪枝可以提前結束不必要的搜尋分支，大幅提升搜尋效率。
- 回溯演算法主要可用於解決搜尋問題和約束滿足問題。組合最佳化問題雖然可以用回溯演算法解決，但往往存在效率更高或效果更好的解法。
- 全排列問題旨在搜尋給定集合元素的所有可能的排列。我們藉助一個陣列來記錄每個元素是否被選擇，剪掉重複選擇同一元素的搜尋分支，確保每個元素只被選擇一次。
- 在全排列問題中，如果集合中存在重複元素，則最終結果會出現重複排列。我們需要約束相等元素在每輪中只能被選擇一次，這通常藉助一個雜湊集合來實現。
- 子集和問題的目標是在給定集合中找到和為目標值的所有子集。集合不區分元素順序，而搜尋過程會輸出所有順序的結果，產生重複子集。我們在回溯前將資料進行排序，並設定一個變數來指示每一輪的走訪起始點，從而將生成重複子集的搜尋分支進行剪枝。
- 對於子集和問題，陣列中的相等元素會產生重複集合。我們利用陣列已排序的前置條件，透過判斷相鄰元素是否相等實現剪枝，從而確保相等元素在每輪中只能被選中一次。
- \(n\) 皇后問題旨在尋找將 \(n\) 個皇后放置到 \(n \times n\) 尺寸棋盤上的方案，要求所有皇后兩兩之間無法攻擊對方。該問題的約束條件有行約束、列約束、主對角線和次對角線約束。為滿足行約束，我們採用按行放置的策略，保證每一行放置一個皇后。
- 列約束和對角線約束的處理方式類似。對於列約束，我們利用一個陣列來記錄每一列是否有皇后，從而指示選中的格子是否合法。對於對角線約束，我們藉助兩個陣列來分別記錄該主、次對角線上是否存在皇后；難點在於找處在到同一主（副）對角線上格子滿足的行列索引規律。
2. Q & A¶
Q：怎麼理解回溯和遞迴的關係？
總的來看，回溯是一種“演算法策略”，而遞迴更像是一個“工具”。
- 回溯演算法通常基於遞迴實現。然而，回溯是遞迴的應用場景之一，是遞迴在搜尋問題中的應用。
- 遞迴的結構體現了“子問題分解”的解題範式，常用於解決分治、回溯、動態規劃（記憶化遞迴）等問題。