回溯法應該知道的知識點

• 2020 年 12 月 19 日
• 筆記
• 【數據結構與演算法】回溯

回溯法也可以叫做回溯搜索法，是一種搜索的方式，回溯和遞歸是相輔相成的，回溯是遞歸的副產品，只要有遞歸就會有回溯，所以可以簡單的理解回溯函數和遞歸函數是同一個函數。

大名鼎鼎的回溯法雖然很不好理解，但其本質就是暴力查找，窮舉所有可能，然後找出我們想要的答案，並不是什麼高效的演算法，雖然有些可以剪枝一下，沒有更優化的方法了，至於為什麼不高效還要用，那沒別的更好的了能解決問題就不錯了還想咋滴。

回溯法可以解決組合、排列、切割、子集、棋盤（N皇后，解數獨）等問題，其中組合無序，排列有序。以上這幾類問題都不簡單。

回溯法解決的所有問題其實都可以抽象為樹形結構，因為它解決的都是在結合中查找子集，集合的大小就構成了樹的寬度，遞歸的深度構成樹的深度（遞歸就要有終止條件，必然是一個棵高度有限的N叉樹）。

和遞歸函數一樣，三部曲：（1）確定回溯函數返回值和參數（一般不需要返回值，參數其實也不好確定，可以先寫邏輯，再定參數）（2）終止條件（3）回溯搜索的遍歷過程邏輯。

回溯法的問題有一個套用的模板幫助解決問題：

void backtracking(參數) {
    if (終止條件) {
        存放結果;
        return;
    }

    for (選擇：本層集合中元素（樹中節點孩子的數量就是集合的大小）) {
        處理節點;
        backtracking(路徑，選擇列表); // 遞歸
        回溯，撤銷處理結果
    }
}

終止條件說的就是一旦滿足了要求的條件（一般來說搜索到葉子結點），就是找到了滿足條件的一條答案，把這個答案存放起來，並接受這層遞歸。for循環是樹的橫向遍歷，而遞歸調用時樹的深度遍歷，這樣就能把一棵樹都遍歷到了。