聊聊演算法——回溯演算法

2020 年 5 月 15 日
筆記
回溯演算法

「遞歸只應天上有，迭代還須在人間」，從這句話我們可以看出遞歸的精妙，確實厲害，遞歸是將問題規模逐漸減小，

然後再反推回去，但本質上是從最小的規模開始，直到目標值，思想就是數學歸納法，舉個例子，求階乘 N!=(N-1)！*N ，

而迭代是數學中的極限思想，利用前次的結果，逐漸靠近目標值，迭代的過程中規模不變，舉例如For循環，直到終止條件。

遞歸的思想不複雜，但程式碼理解就麻煩了，要理解一個斐波那契數組遞歸也不難，比如下面的回溯演算法遞歸，for 循環裡面

帶遞歸，看程式碼是不是暈了？好，下面我們專門來聊聊這個框架！

作者原創文章，謝絕一切形式轉載，違者必究！

準備：

Idea2019.03/JDK11.0.4

難度： 新手–戰士–老兵–大師

目標：

回溯演算法分析與應用

1 回溯演算法

先給出個回溯演算法框架：

backtrack(路徑，選擇列表){
    //結束條件
    將中間結果加入結果集
    for 選擇 in 選擇列表:
        //做選擇，並將該選擇從選擇列表中移除
        路徑.add(選擇)
        backtrack(路徑，選擇列表)      
        //撤銷選擇 
        路徑.remove(選擇)
}

為了理解上述演算法，回想一下，我前篇文章中有說到，多路樹的遍歷演算法框架：

private static class Node {
    public int value;
    public Node[] children;
}
public static void dfs(Node root){
    if (root == null){
        return;
    }
    // 前序遍歷位置，對node做點事情
    for (Node child:children
    ) {
        dfs(child);
    }
    // 後序遍歷位置，對node做點事情
}

如果去掉路徑增加/撤銷的邏輯，是不是和多路樹的遍歷演算法框架一樣了呢？其實就是一個多路樹DFS的變種演算法！

另外，雖然遞歸程式碼的理解難度大，運行時是棧實現，但看官不要掉進了遞歸棧，否則就出不來了，如果試著用打斷

點逐行跟進的辦法非要死磕，那對不起，估計三頓飯功夫也可能出不來，甚至我懷疑起自己的智商來，所以，理解遞歸，

核心就是抓住函數體來看，抽象的理解，只看懂 N 和 N-1 的轉移邏輯即可！不懂的先套用再說，也不定哪天就靈感來了，

一下頓悟！

那就先上菜了！先是經典回溯演算法，代號A，我們要做個數組全排列，我看別人說回溯演算法也都是拿這個例子說事，

我就落個俗套：

class Permutation {
    // 排列組合演算法
    private static List<List<Integer>> output = new LinkedList();
    static List<List<Integer>> permute( List<Integer> nums, // 待排列數組
                                         int start //起始位置
     ){
        if (start == nums.size()){
            output.add(new ArrayList<>(nums));
        }
        for (int i = start; i < nums.size(); i++) {
            // 做選擇，交換元素位置
            Collections.swap(nums, start, i);
            // 遞歸，縮小規模
            permute( nums,start +1);
            // 撤銷選擇，回溯，即恢復到原狀態,
            Collections.swap(nums, start, i);
        }
        return output;
    }
    // 測試
    public static void main(String[] args) {
        List<Integer> nums = Arrays.asList(1,2,3,4);
        List<List<Integer>> lists = permute(nums,0);
        lists.forEach(System.out::println);
    }
}

程式碼理解：數組 {1,2,3} 的全排列，我們馬上知道有{1,2,3},{1,3,2},{2,1,3},{2,3,1},{3,1,2},{3,2,1}排列，具體過程就是通過遞歸縮小規模，

做 {1,2,3} 排列，先做 {2,3} 排列，前面在加上 1 即可，繼續縮小，就是做 {3} 的排列。排列就是同一個位置把所有不同的數都放一次，

那麼程式碼實現上可使用交換元素法，比如首個位置和所有元素都交換一遍，不就是全部可能了嗎。這樣，首個位置所有可能就遍歷了

一遍，然後在遞歸完後，恢復(回溯)一下，就是說每次交換都是某一個下標位置，去交換其他所有元素。

再來個全排列的演算法實現，代號B，也是使用回溯的思想：

public class Backtrack {
    public static void main(String[] args) {
       int[] nums = {1,2,3,4};
        List<Integer> track = new LinkedList<>();
        List<List<Integer>>  res = backtrack(nums,track);
        System.out.println(res);
    }
    // 存儲最終結果
    private static List<List<Integer>> result = new LinkedList<>();
    // 路徑：記錄在 track 中
    // 選擇列表：nums 中不存在於 track 的那些元素
    // 結束條件：nums 中的元素全都在 track 中出現
    private static List<List<Integer>> backtrack(int[] nums,List<Integer> track){
        // 結束條件
         if (track.size() == nums.length){
             result.add(new LinkedList<>(track));
             return null;
         }
        for (int i = 0; i < nums.length; i++) {
            if (track.contains(nums[i]))
                continue;
            // 做選擇
            track.add(nums[i]);
            backtrack(nums,track);
            // 撤銷選擇
            track.remove(track.size()-1);
        }
        return result;
    }
}

程式碼解析：對 {1,2,3} 做全排列，先將 List[0] 放入鏈表，如果鏈表中存在該元素，就忽略繼續，繼續放入List[0+1]，同樣的，

存在即忽略繼續，直到將List中所有元素，無重複的放入鏈表，這樣就完成了一次排列。這個演算法的技巧，是利用了鏈表的

有序性，第一個位置會因為回溯而嘗試放入所有的元素，同樣，第二個位置也會嘗試放入所有的元素。

畫出個決策樹：

以 {1-3-2} 為例，如果鏈表第一個位置為1，那第二個位置為 {2,3} 之一，{1}由於屬於存在的重複值忽略，

如果第二個位置放了{3}，那第三個位置就是{2}，就得出了一個結果。

我們對比一下以上兩個演算法實現：特別注意，演算法B是真正的遞歸嗎？有沒有縮小計算規模？

時間複雜度計算公式：分支個數 * 每個分支的計算時間

演算法A的分支計算只有元素交換，按Arraylist處理，視為O(1)，演算法B分支計算包含鏈表查找為O(N)，

演算法A：N！* O(1) ，階乘級別，耗時不送。

演算法B：N^n * O(N) ，指數級別，會爆炸！

我使用10個數全排測試如下(嚴謹的講，兩者有數據結構不同的影響，並不是說僅有演算法上的差異)：

總結：回溯和遞歸是兩種思想，可以融合，也可以單獨使用！

全文完！

我近期其他文章：

只寫原創，敬請關注

Tags: 回溯演算法