算法设计技巧5: 回溯法 (Backtracking algorithm)

Open ylqi007 opened this issue 2 years ago • 1 comments

回溯算法(backtracking)也叫试探法，它是一种系统地搜索问题解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退，换一条路再试。回溯算法其实就是穷举法。不过回溯算法使用剪枝函数，剪去一些不可能到达的最终状态的节点，从而减少状态空间树节点的生成。

Backtracking属于DFS。

普通的DFS主要用于可达性问题，这种问题只需要执行到特定点的位置然后返回即可。
而Backtracking主要用于排列组合问题，这种问题在执行到特定的位置之后还会继续执行求解过程。因为Backtracking不是立即就返回，而要继续求解，因此在实现算法时，需要注意对元素的标记问题：
在访问一个新元素进入新的递归调用时，需要将新元素标记为已经访问，这样才能在继续递归调用时不再重复访问该元素。
但是在递归返回时，需要将元素标记为未访问，因为只需要保证在一个递归链中不同时访问一个元素，可以访问已经访问过但是不在当前递归链中的元素。

Reference:

Template:

result = []
func backtrack(选择列表,路径):
    if 满足结束条件:
        result.add(路径)
        return
    for 选择 in 选择列表:
        做选择
        backtrack(选择列表,路径)
        撤销选择

Nov 19 '23 06:11 ylqi007

Backtracking一般可以解决如下几种问题：

组合问题：N个数里面按照一定规则找出k个数的集合
切割问题：一个字符串按一定规则有几种切割方式
子集问题：一个N个数的集合里有多少符合条件的子集
排列问题：N个数按一定规则全排列，有几种排列方式
棋盘问题：N皇后，解数独问题

LeetCode中的题目：

Nov 19 '23 06:11 ylqi007