大家好,我是吴师兄。
这几天给训练营的同学总结回溯算法的题,发现没有想象中那么难,甚至可以说有套路,半小时可以学会。
简单来说,回溯算法是依托于 DFS 实现的,也是需要朝着一个方向不断的延伸搜索下去,但是回溯算法会在搜索过程中,达到结束条件时,恢复原状态,回溯到上一层,再次搜索。
即,回溯算法与 DFS 的区别是有无状态重置。
一般来说,回溯算法的思考步骤如下:
1、画出递归树,找到状态变量(回溯函数的参数)
2、寻找结束条件,由于回溯算法是借助递归实现,所以也就是去寻找递归终止条件
3、确定选择列表,即需要把什么数据存储到结果里面
4、判断是否需要剪枝,去判断此时存储的数据是否之前已经被存储过
5、做出选择,递归调用该函数,进入下一层继续搜索
6、撤销选择,回到上一层的状态
翻译成代码为如下的形式,也就是回溯算法解题的一个模板:
// 1、画出递归树,找到状态变量(回溯函数的参数)
private void backtrack("原始参数") {
// 2、寻找结束条件,由于回溯算法是借助递归实现,所以也就是去寻找递归终止条件
if ("终止条件") {
// 一些逻辑操作(可有可无,视情况而定)
// 比如,在 N 皇后问题中,在这一步把数据加入到了结果里面
return;
}
// 3、确定选择列表,即需要把什么数据存储到结果里面
// for 循环就是一个选择的过程
for ("遍历本层集合中元素") {
// 一些逻辑操作(可有可无,视情况而定)
// 4、判断是否需要剪枝,去判断此时存储的数据是否之前已经被存储过
// 5、做出选择,递归调用该函数,进入下一层继续搜索
// 递归
backtrack("新的参数");
// 一些逻辑操作(可有可无,视情况而定)
// 6、撤销选择,回到上一层的状态
}
}
按照这个思路,可以解决子集、组合、排列、N 皇后、岛屿等十几道回溯算法题。
给大家看一下效果。
结合动画来理解,半小时掌握 9 道回溯算法题是很轻松的。
明天把所有代码贴出来,让大家体验一下半小时刷 9 道回溯算法题的快感:)
这是我们每天学会一点知识的第 51 天,当前进度 51/100。
我已经将大部分算法题解文章同步到了个人网站,方便阅读。
“网站地址:https://www.cxyxiaowu.com/”