聊聊算法——回溯算法

dbhllnr 2020-05-15

“递归只应天上有,迭代还须在人间”,从这句话我们可以看出递归的精妙,确实厉害,递归是将问题规模逐渐减小,

然后再反推回去,但本质上是从最小的规模开始,直到目标值,思想就是数学归纳法,举个例子,求阶乘 N!=(N-1)!*N ,

而迭代是数学中的极限思想,利用前次的结果,逐渐靠近目标值,迭代的过程中规模不变,举例如For循环,直到终止条件。

递归的思想不复杂,但代码理解就麻烦了,要理解一个斐波那契数组递归也不难,比如下面的回溯算法递归,for 循环里面

带递归,看代码是不是晕了?好,下面我们专门来聊聊这个框架!

作者原创文章,谢绝一切形式转载,违者必究!

准备:

Idea2019.03/JDK11.0.4

难度: 新手--战士--老兵--大师

目标:

  1. 回溯算法分析与应用

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个数全排测试如下(严谨的讲,两者有数据结构不同的影响,并不是说仅有算法上的差异):

聊聊算法——回溯算法

总结:回溯和递归是两种思想,可以融合,也可以单独使用!

全文完!


我近期其他文章:

       只写原创,敬请关注 

聊聊算法——回溯算法

相关推荐