回溯法应该知道的知识点

回溯法也可以叫做回溯搜索法,是一种搜索的方式,回溯和递归是相辅相成的,回溯是递归的副产品,只要有递归就会有回溯,所以可以简单的理解回溯函数和递归函数是同一个函数。

大名鼎鼎的回溯法虽然很不好理解,但其本质就是暴力查找,穷举所有可能,然后找出我们想要的答案,并不是什么高效的算法,虽然有些可以剪枝一下,没有更优化的方法了,至于为什么不高效还要用,那没别的更好的了能解决问题就不错了还想咋滴。

回溯法可以解决组合、排列、切割、子集、棋盘(N皇后,解数独)等问题,其中组合无序,排列有序。以上这几类问题都不简单。

回溯法解决的所有问题其实都可以抽象为树形结构,因为它解决的都是在结合中查找子集,集合的大小就构成了树的宽度,递归的深度构成树的深度(递归就要有终止条件,必然是一个棵高度有限的N叉树)。

和递归函数一样,三部曲:(1)确定回溯函数返回值和参数(一般不需要返回值,参数其实也不好确定,可以先写逻辑,再定参数)(2)终止条件(3)回溯搜索的遍历过程逻辑。

回溯法的问题有一个套用的模板帮助解决问题:

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
        处理节点;
        backtracking(路径,选择列表); // 递归
        回溯,撤销处理结果
    }
}

终止条件说的就是一旦满足了要求的条件(一般来说搜索到叶子结点),就是找到了满足条件的一条答案,把这个答案存放起来,并接受这层递归。for循环是树的横向遍历,而递归调用时树的深度遍历,这样就能把一棵树都遍历到了。

Exit mobile version