暴力之美:回溯算法教了我这些

前言

忙碌的搬砖,终于在最近有了缓解,每天重复的代码和两点一线的生活让我觉得异常枯燥,我真的很喜欢沉浸式的学习与生活,按照自己的规划和步骤来安排日程,倾向于自我成长和提升。但公司的主体业务以项目和服务为准(半外包),还有领导和测试UI时不时的消息轰炸和种种需求令我疲惫不堪。于是我打算出去尝试一波,但去年的经历让我认识到算法在面试中的重要性,自己其实没有系统的学习过算法的一些常识和技巧,所以需要好好沉淀下来,做一波分享和输出。

何谓回溯算法

在尝试探索中寻找问题的解,如果不满足结果条件,就“回溯”到上一步,换一条路重新查找,在生活中我们找不到路了,就返回到起点换条路继续找

常见的场景有:组合,排列,搜索,数独等等,其本质上是一种穷举法(一条路不行换一条),所以回溯属于暴力搜索,但回溯法有很强的套路和模板。

回溯的通用模板

  1. 它属于递归的一种,那么必然有递归调用,也肯定有递归的截止条件.
  2. 遍历,一般来说都有一个for循环.
  3. 回溯,在循环里有回溯(前进和后退)
  4. 关于回溯的优化:剪枝
function test(arr) {
    let res = [];
    const backtracking = () => {
        let path = []; // 记录回溯路径,不局限与path数组,也有可能是字符串或者数字
        if(中止条件) {
            res.push(...) // 对结果进行操作
            return;
        }
        for(let i = 0;i < arr.length;i++) {
            // 回溯
            path.push(arr[i]);
            backtracking(); // 递归
            path.pop();
        }
    }
    backtracking([])
    return res;
}

回溯实践

关于最后一点剪枝,需要根据最后的结果来修正for循环的边界,或者排除某些情况,打标识去重等等,对原先结果的筛选,性能的优化,我们一开始先以写出来为准,下边来实践一下回溯,

求[1,2,3]的全排列:Leecode题目链接

结果为:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

function test(arr) {
    let res = [];
    const backtracking = (path) => {
        if(path.length === arr.length) {
            res.push(path);
            return;
        }
        for(let i = 0;i < arr.length;i++) {
            // 回溯
            path.push(arr[i]);
            backtracking(path); // 递归
            path.pop();
        }
    }
    backtracking([]);
    return res;
}
test([1,2,3])

暴力之美:回溯算法教了我这些
这样写出来会有两个问题

  1. 得到的res里有27个空数组,为什么呢,因为path作为一个对象,保存的是一开始对空数组的引用,在pushpop一系列操作之后,最后的值也会变成空数组,所以应该把res.push(path)变成res.push([...path]),做一个拷贝,保留当时的数据
  2. 这样回溯操作变成了三步:
  • push操作入栈

  • […path]保留当时数据

  • pop出栈

    那有没有办法可以把三步变成一步呢,concat方法会生成一个新的数组,backtracking(path.concat(arr[i]

  1. 27个元素证明[1,2,3]每个元素都对自身进行了组合,有大量重复的结果,比如[1,1,2],[1,1,1]这种,对于这种我们很容易想到用includes去重.

修整过的代码如下:

function test(arr) {
    let res = [];
    const backtracking = (path) => {
        if(path.length === arr.length) {
            res.push(path);
            return;
        }
        for(let i = 0;i < arr.length;i++) {
            if(path.includes(arr[i])) {
              continue;
            }
            // 回溯+递归
            backtracking(path.concat(arr[i]));
        }
    }
    backtracking([]);
    return res;
}
test([1,2,3])

最后得到的结果如下:

暴力之美:回溯算法教了我这些

Tips:concat是我在网上寻找答案的时候偶然发现的简便写法,但这里并不推荐,因为我觉得对于算法来说,重要的并不是具体的解题方案,而是面对问题的解题套路和思维方式,有需要的情况再去转换为concat。

回溯法的起始位置与遍历范围

再来看另一道经典题目:在1-n个数中取k个不重复的数,问都有哪些组合?Leecode题目链接

输入:n = 4,k = 2,输出:[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

这道题可以解释为:求k层的n轮for循环,首先确认输入输出,并带入到回溯公式:

function test(n, k) {
    let res = []; // 存放结果
    let backtracking = (path) => {
        if(path.length === k) {
            res.push([...path]); // 回溯中止条件
            return
        }
        for(let i = 1;i <= n;i++) {
            path.push(i);
            backtracking(path);
            path.pop();
        }
    }
    backtracking([]);
    return res;
}

拿第一个数字1来举例,[1,1],[1,2],[1,3],[1,4]一共四个数,4*4一共16种可能,那么该如何调整呢?
分两步:

  1. 累加索引不走回头路:对于第一轮的i来说,后面的i会依次累加,意思就是去掉[2,1],[3,1],[4,2]这种情况
for(let i = 1;i <= n;i++) {
    path.push(i);
    backtracking(path, i + 1);
    path.pop();
}
backtracking([], 1);

改过之后,结果变成了10种可能分别是[1,1],[1,2],[1,3],[1,4],[2,2],[2,3]...
2. 去重:去掉[1,1],[2,2],首轮起始位置i = 1,下次的开始位置i就应该从2开始,最后修正的代码:

function test(n, k) {
    let res = []; // 存放结果
    let backtracking = (path, start) => {
        if(path.length === k) {
            res.push([...path]); // 回溯中止条件
            return
        }
        for(let i = start;i <= n;i++) { // 起始位置,去重[1,1][2,2]
            path.push(i);
            backtracking(path, i + 1); // 不走回头路,去掉[2,1]
            path.pop();
        }
    }
    backtracking([], 1);
    return res;
}

优化空间:剪枝,当n = 7, k = 7,这个时候只有一种可能[1,2,3,4,5,6,7],所以每层的遍历只需要保留一个数字就好。

如何做:
我们的结果最后是落在path上的,所以

  1. 已经选择的元素个数为path.length
  2. 还需要插入k – path.length个元素7,6,5,4,3,2,1,仔细观察这就是我们要舍弃的区间
  3. 用n找齐:最后的右边界是 n – (k – path.length) + 1,加一是因为以start作为开始,右边需要闭区间

可能大家对第二点持有疑问,仔细想想就会明白:

  • 第一层只能取1,2-7都不可以,所以第一层右边界是1
  • 对于第一层的1来说,第二层[1,3],[1,4]...都是不需要的,第二层的右边界应该是2
  • 对于第二层的2来说,第三层[2,4],[2,5]...都是不需要的,第三层的右边界应该是3

把层数看做path.length + 1,每层需要舍弃的区间就是k – path.length – 1(对于第一层,后6个数都不能取),从n中去掉就是n - (k - path.length - 1) –> n - (k - path.length) + 1

整个过程如下图所示:这里以n = 4,k = 2举例

暴力之美:回溯算法教了我这些

最后附上我们整理过的结果:

    function test(n, k) {
    let res = []; // 存放结果
    let backtracking = (path, start) => {
        if(path.length === k) {
            res.push([...path]); // 回溯中止条件
            return
        }
        // 剪枝,去除k - path.length
        for(let i = start;i <= n - (k - path.length) + 1;i++) { // 起始位置,去重[1,1][2,2]
            path.push(i);
            backtracking(path, i + 1); // 不走回头路,去掉[2,1]
            path.pop();
        }
    }
    backtracking([], 1);
    return res;
}

筛选过程如图所示:

暴力之美:回溯算法教了我这些

Tips:关于start开始位置和i+1索引的变化,应根据题目需要自行筛选,切不可硬套公式,有些题目需要有[1,1]或者[2,1]这样的结果,需要根据具体情况具体分析

标记法区分树干层和树枝

给定一个数组arr和目标数字target,在arr中筛选所有相加结果为target的结果:Leecode题目链接

let arr = [10,1,2,7,6,1,5]; target = 8,结果为:
[ [1,1,6], [1,2,5], [1,7] [2,6] ]
首先,套用上面总结回溯公式,如下:

function test(arr, target) {
    let copyArr = arr.sort((a,b) => (a - b)); // 先做排序,求和的时候不会遗漏
    let sum = 0;
    let res = [];
    const backtracking = (path, start) => {
        if(sum === target) {
            res.push([...path]);
            return;
        }
        for(let i = start;i < copyArr.length;i++) {
            path.push(copyArr[i]);
            sum += copyArr[i];
            backtracking(path,i + 1);
            path.pop();
            sum -= copyArr[i];
        }
    }
    backtracking([], 0);
    return res;
}

得到的结果如下:

[
    [1, 1, 6],
    [1, 2, 5],
    [1, 7],
    [1, 2, 5],
    [1, 7],
    [2, 6]
]

仔细观察下copyArr, [1, 1, 2, 5, 6, 7, 10] 不难发现有两个重复元素1,我们尝试把重复的节点筛选掉

for(let i = start;i < copyArr.length;i++) {
    // 跳过重复节点
    if(copyArr[i] === copyArr[i - 1] && copyArr[i - 1]) {
        continue;
    }
    path.push(copyArr[i]);
    sum += copyArr[i];
    backtracking(path,i + 1);
    path.pop();
    sum -= copyArr[i];
}

得到结果中[1,1,6]也被抹掉了,我们其实想保留树枝节点的1,抹掉树干层上的1节点,如下图,那树枝和树干层如何区分呢?

for循环中使用used对递归前后做标记

同一树枝上used[i]都是true,树干层前一个为false,如下图所示:

let used = {};
for(let i = start;i < copyArr.length;i++) {
    used[i] = true;
    backtracking(path,i + 1);
    used[i] = false;
}

首层树枝上的节点在递归结束之前used[i]一直是true,树层的不同节点,前一树层的used[i]一直是false,所以加入筛选条件如下:

function test(arr, target) {
    let copyArr = arr.sort((a,b) => (a - b));
    let sum = 0;
    let res = [];
    let used = {};
    const backtracking = (path, start) => {
        if(sum === target) {
            res.push([...path]);
            return;
        }
        for(let i = start;i < copyArr.length;i++) {
            
            if((i > 0 && copyArr[i] === copyArr[i - 1] && !used[i - 1]) || copyArr[i] > target - sum) {// 去掉超限的数字,比如10这种
                continue;
            }
            used[i] = true;
            path.push(copyArr[i]);
            sum += copyArr[i];
            backtracking(path,i + 1);
            used[i] = false;
            path.pop();
            sum -= copyArr[i];
        }
    }
    backtracking([], 0);
    return res;
}

回顾一下刚开始的[1,2,3]求全排列,也可以通过used标记的方式去做,代码如下:

    function test(arr) {
        let res = [];
        let used = {};
        const backtracking = (path) => {
            if(path.length === arr.length) {
                res.push(path);
                return;
            }
            for(let i = 0;i < arr.length;i++) {
                if(used[i]) { // 判断是同枝上的节点
                    continue;
                }
                used[i] = true; // 使用used进行标记
                // 回溯+递归
                backtracking(path.concat(arr[i]));
                used[i] = false;
            }
        }
        backtracking([]);
        return res;
    }
    test([1,2,3])

SKU组合

本人第一次接触组合遇到的也是一个经典题目:
以下有些羽绒服属性,需要将所有可能得搭配都展示出来:

[ ['黑色', '白色', '灰色'], ['L', 'XL', 'XXL'], ['加绒', '不加绒'] ]

求结果:

[ '黑色-L-加绒', '黑色-L-不加绒', '黑色-XL-加绒', '黑色-XL-不加绒', ... '白色-L-加绒' ]
现在看来这是经典的全排列问题,而且是要所有可能性的全排列

当时看了一个大佬写的文章,奈何本人比较笨拙一直都没有记住,学习了回溯法之后,自己写出的代码如下:

function test(arr) {
    let res = [];
    let path = [];
    const backtracking = (start) => {
        if(arr.length === path.length) {
            res.push([...path]);
            return;
        }
        for(let i = start;i < arr.length;i++) {
            for(let j = 0;j < arr[i].length;j++) {
                path.push(arr[i][j]);
                backtracking(i + 1);
                path.pop();
            }
        }
    }
    backtracking(0);
    return res;
}

回顾和总结

关于回溯问题我们有以下几点策略和办法:

  • 回溯法的基本模板和注意项
  • 使用used对需要重复的节点进行标记和筛选
  • 用startIndex和索引index控制循环的边界和结果
  • 剪枝优化循环

最后,在路上,行动才能改变未来,各位,加油!

原文链接:https://juejin.cn/post/7346155018343809060 作者:一名互联网小兵

(0)
上一篇 2024年3月15日 下午4:41
下一篇 2024年3月15日 下午4:52

相关推荐

发表回复

登录后才能评论