查看: 20693| 回复: 42
收起左侧

[树/链表/图] 谈一谈backtracking算法

   
本楼:   👍  14
100%
0%
0   👎
全局:   717
100%
0%
3

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
本帖最后由 不知道小帅 于 2020-1-9 02:45 编辑

刚开始刷题的时候,backtrack对我特别tricky,我一直在想,这是些什么鬼东西,为什么加上,移除。
后来,慢慢参考了一些资料,也理解了其中的逻辑。原创不易,欢迎加米。
其实,要理解backtrack,首先必须理解recursion和dfs。
这里提一下。
Capture.PNG



这张图是树的dfs,或者说先序遍历(preorder traversal),上一个伪代码吧。
  1. private void dfs(TreeNode root) {
  2. if (root == null) return;
  3. visit(root);
  4. dfs(root.left);
  5. dfs(root.right);
  6. }
复制代码


visit就是一个函数,可以是加入数组,也可以是打印,这里我们不管。或者写一个多叉树的伪代码。
  1. def dfs(root):
  2.         if root is None: return
  3.         visit(root)
  4.         for child in root.children:
  5.                 dfs(child)
复制代码


参考上图,红色点代表我们进入了这一个call stack,或者说开始调用dfs,作用在当前的node上面。
红色的×代表,当前调用结束,控制权返回上一层的recursion call。
下面写一个backtrack的模板:
  1. private void backtrack(int[] nums, List<Integer> track, List<List<Integer>> ans) {
  2.     if (true) ans.add(new ArrayList<>(track); //base case

  3.     else {
  4.         for (int i: nums) {
  5.             track.add(i); // choose
  6.             backtrack(nums, track, ans); //explore (recursion call)
  7.             track.remove(track.size() - 1); // unchoose
  8.         }
  9. }
  10. }
复制代码


其实这个本质上就是dfs。继续参考上图,这个不过是在红色圆点的地方,执行了choose这个过程,也就是把结果加进track这个list。
然后remove的过程发生在红色×的地方,这个时候track里面的数字被移除,同时,控制权返回上一层recursion。
也就是说,track其实track的是你的call stack,因为backtracking的问题实质上是输出所有可能的路径。
base case指的就是你在叶节点的时候,大部分情况下base case会是track.size() == nums.length 之类的判断。

我们来看几道例题。
leetcode 46 permutations
permu.PNG


我们先来看一下决策树。第一个红点处,我们的track加入1这个数字,第二个红点处,加入2, 第三个红点处,加入3。track = {1, 2, 3}
这时候,我们触发了base case 的条件,我们把第一个permutation加入了我们的ans list。然后第一个×的地方,我们执行remove操作,
这时候track只剩{1, 2}, 然后沿着这条线继续走,到了下一个×,这时候移除2。我们的track只剩{1}。然后经过后两个红点,得到{1, 3, 2}。
通过开始的base case,把这个结果加进我们的ans list里面。如此往复,直到函数结束。
因为backtrack的过程,choose explore unchoose 在代码上是挨着的,先执行choose,也就是在红点处执行,把这个结果加进track里面。
然后执行backtrack(explore),就看一下往哪走,然后是不是base case。之后执行unchoose,也就是在红色×的位置。此时这次调用执行完毕,
控制权移交上一层的recursion。
我们看一下代码。
  1. class Solution {
  2.     public List<List<Integer>> permute(int[] nums) {
  3.         List<List<Integer>> ans = new ArrayList<>();
  4.         List<Integer> track = new ArrayList<>();
  5.         backtrack(ans, track, nums);
  6.         return ans;
  7.     }
  8.     private void backtrack(List<List<Integer>> ans, List<Integer> track, int[] nums) {
  9.         if (track.size() == nums.length){
  10.             ans.add(new ArrayList<>(track));
  11.         }
  12.         else {
  13.             for (int i = 0;i < nums.length;++i){
  14.                 if (track.contains(nums)) {
  15.   continue;
  16.                 }
  17.                 track.add(nums);
  18.                 backtrack(ans, track, nums);
  19.                 track.remove(track.size() - 1);
  20.             }
  21.         }
  22.     }
  23. }
复制代码


这个代码其实有可以优化的地方,但是这里我们只讲思想。优化是后来的事情。
这个算法的时间复杂度首先要看有多少个节点,最底下一层有n!个叶节点,总共n层,也就是节点总数不超过n*n!。
因为在每一个节点都有一次track.contains,这是线性扫描。所以,复杂度是n。最终总的复杂度是O(n^2 * n!)。有优化的空间,
但是不论如何优化,不会低于n!的时间复杂度。
因为暴力枚举所有情况,其实复杂度还是很爆炸的。
我们再来看一道例题。
leetcode 78 Subsets
这个题目其实有两种决策树。
还是以[1, 2, 3]为例子。
第一种办法我觉得比较直观。
subset1.PNG


这个方法就是说,第一层加不加1,第二层加不加2,第三层加不加3. 直到最后我们初始的list为空。
比较直观。我们来贴一下代码。
  1. class Solution {
  2.     public List<List<Integer>> subsets(int[] nums) {
  3.         List<List<Integer>> ans = new ArrayList<>();
  4.         List<Integer> track = new ArrayList<>();
  5.         List<Integer> numslist = new ArrayList<>();
  6.         for (int i: nums) numslist.add(i);
  7.         backtrack(ans, track, numslist);
  8.         return ans;
  9.         
  10.     }
  11.    
  12.     private void backtrack(List<List<Integer>> ans, List<Integer> track, List<Integer> nums) {
  13.         if (nums.isEmpty()) ans.add(new ArrayList<>(track));
  14.         else {
  15.             int n = nums.remove(nums.size() - 1);
  16.             //left branch
  17.             //choose since choose empty, implicitly choose
  18.             backtrack(ans, track, nums);
  19.             //since choose empty, no need to remove
  20.             
  21.             //right branch
  22.             track.add(n);
  23.             backtrack(ans, track, nums);
  24.             nums.add(n);  // when unchoose, we need to restore the original list
  25.             track.remove(track.size() - 1);
  26.         }
  27.     }
  28. }
复制代码


base case就是num这个list为空的时候。这个代码和图片有一点点不符合,应该3是在第一层。因为对list来说,removelast的复杂度是常数级别,
但是remove头部就是线性的。但是思想是一样的。
这种做法的时间复杂度,每个节点其实是O(1)的,所以就看多少个节点,叶子节点总共2^n个,因为是完全二叉树,总节点数量应该是2*2^n,
所以复杂度是O(2*2^n),也就是O(2^n)。指数级别。

方法二
subset2.PNG


我们引入了start index防止重复,start从上一层到下一层一定是递增的。需要注意的是,这个时候我们没有base case的判定了。我们会把所有节点(包括根节点)
一起加入我们的answer list里面去。下面是代码。
  1. class Solution {
  2.     public List<List<Integer>> subsets(int[] nums) {
  3.         List<List<Integer>> ans = new ArrayList<>();
  4.         List<Integer> track = new ArrayList<>();
  5.         backtrack(ans, track, nums, 0);
  6.         return ans;
  7.         
  8.     }
  9.    
  10.     private void backtrack(List<List<Integer>> ans, List<Integer> track, int[] nums, int start) {
  11.         ans.add(new ArrayList<Integer>(track));
  12.         for (int i = start; i < nums.length; ++i) {
  13.             track.add(nums);
  14.             backtrack(ans, track, nums, i + 1);
  15.             track.remove(track.size() - 1);
  16.         }
  17.     }
  18. }
复制代码


这个代码更短,但是对我来说,更难想到一些。复杂度是所有的节点数量,也就是O(2^n)。对比上一个解法,有常数项的优势。

leetcode 113 Path Sum 2
直接贴代码,这里其实if 和 else重叠的地方可以放在外面,但是为了更好的符合模板,或者更好想到一些。
base case,然后主体是 choose explore unchoose。
  1. class Solution {
  2.     public List<List<Integer>> pathSum(TreeNode root, int sum) {
  3.         List<Integer> track = new ArrayList<>();
  4.         List<List<Integer>> ans = new ArrayList<>();
  5.         backtrack(root, sum, track, ans);
  6.         return ans;
  7.     }
  8.    
  9.     private void backtrack(TreeNode root, int sum, List<Integer> track, List<List<Integer>> ans) {
  10.         if (root == null) return;
  11.         if (root.left == null && root.right == null && root.val == sum) {
  12.             track.add(root.val);
  13.             ans.add(new ArrayList<>(track));
  14.             track.remove(track.size() - 1);
  15.         }
  16.         else {
  17.             track.add(root.val);
  18.             backtrack(root.left, sum - root.val, track, ans);
  19.             backtrack(root.right, sum - root.val, track, ans);
  20.             track.remove(track.size() - 1);
  21.         }
  22.     }
  23. }
复制代码


时间复杂度就是节点的总数,因为每个节点只过一遍。O(n)
leetcode 51 N- Queens
有了上面几个题目的积累,这个题目其实就迎刃而解了。主要是需要多一些剪枝和判定的过程。
Nqueens.PNG



我们就是每一列,每个点去放置queen,看看是否可行。如果可行就继续,不可行就剪枝。
所以终止条件(base case)就是col == n的时候。
  1. class Solution {
  2.     public List<List<String>> solveNQueens(int n) {
  3.         List<List<String>> ans = new ArrayList<>();
  4.         List<String> track = new ArrayList<>();
  5.         char[][] board = new char[n][n];
  6.         for (int i = 0; i < n; ++i) {
  7.             for (int j = 0; j < n; ++j) {
  8.                 board[j] = '.';
  9.             }
  10.         }
  11.         backtrack(n, board, ans, 0);
  12.         return ans;
  13.     }
  14.    
  15.     private void backtrack(int n, char[][] board, List<List<String>> ans, int col) {
  16.         if (col == n) ans.add(construct(board));
  17.         else {
  18.             for (int row = 0; row < n; ++row) {
  19.                 if (isSafe(board, row, col)) {
  20.                     board[row][col] = 'Q';  // choose
  21.                     backtrack(n, board, ans, col + 1); //explore
  22.                     board[row][col] = '.';  // unchoose
  23.                 }
  24.             }
  25.         }
  26.         
  27.     }
  28.     private boolean isSafe(char[][] board, int row, int col) {
  29.         for (int i = col - 1; i >= 0; --i) {
  30.             if (board[row] == 'Q') return false;
  31.             if (row + col - i < board.length && board[row + col - i] == 'Q')
  32.                 return false;
  33.             if (row - col + i >= 0 && board[row - col + i] == 'Q')
  34.                 return false;
  35.         }
  36.         return true;
  37.     }
  38.    
  39.    
  40.    
  41.     private List<String> construct(char[][] board) {
  42.         List<String> track = new ArrayList<>();
  43.         for (int i = 0; i < board.length; ++i) {
  44.             track.add(new String(board));
  45.         }
  46.         return track;
  47.     }
  48. }
复制代码


这个时间复杂度如果没有剪枝直接到最后一层的话有n^n个叶节点,总共节点数量是n^n + n^(n-1) + n^ (n -2) + ..+ n,等比数列求和。不会超过2*n^n,也就是O(n^n)
而且每一步判定是否安全也是O(n)的时间复杂度。最坏最坏就是O(n*n^n) 即O(n^(n+1)),当然实际上还是比这好得多。这里每一层的意思就是每一列,每个分支的意思就是从第0行开始放置。


原创不易,欢迎加米。为了造福新人,就不设置隐藏了。总结:
backtrack心中一定要有“树”,然后知道每一层的意义是什么,每一个分支又是什么意义。然后套用模板,从做题的角度来看,可以解决大部分问题。
楼主刷题时间不多,代码可能写得不是那么好,主要是思路要表达到位。如果讲得不清楚的地方,或者讲得不好的地方欢迎指正和讨论。









补充内容 (2020-1-9 06:22):
对于Subsets的时间复杂度有一点异议,“ans.add(new ArrayList<Integer>(track));” 应该是线性时间的操作,在worst case中,每一次backtrack都需要执行一次,所以总体的TC应该是O(N * 2^N). 这里之前没有想到。

补充内容 (2020-1-9 06:22):
还有就是,不知道为什么代码中间有些地方nums[i]的[i]被吞掉了。。。

补充内容 (2020-1-9 09:08):
主要的参考资料是两个人的视频,第一个是一个印度小哥 Ravindrababu Ravula, youtube上有。他讲的recursion。
第二个是Marty Stepp的CS106B的lec 9 -  11, B站有存档。

补充内容 (2020-1-9 22:20):
发现很多人收藏。很高兴可以分享自己看法,但是花很久码字,还是希望打赏大米。如果大家觉得讲得清楚的话,也会考虑出其他类型的讲解。
更多图片 小图 大图
组图打开中,请稍候......

评分

参与人数 74大米 +263 收起 理由
14417335 + 20
可乐瑶瑶瑶瑶 + 1 给你点个赞!
Falldawn + 2 很有用的信息!
yyt913 + 5 很有用的信息!
notfrom1m3fd + 2 欢迎分享你知道的情况,会给更多积分奖励!

查看全部评分


上一篇:不要盲目参考Accept rate
下一篇:转码求建议

本帖被以下淘专辑推荐:

 楼主| 不知道小帅 2020-1-9 04:16:06 来自APP | 显示全部楼层
本楼:   👍  6
100%
0%
0   👎
全局:   717
100%
0%
3
不知道小帅 发表于 2020/01/09 02:36:02
刚开始刷题的时候,backtrack对我特别tricky,我一直在想,这是些什么鬼东西,为什么加上,移除。
后来,慢慢...
主要参考资料有两个。一个是一个印度小哥,名字叫Ravindrababu Ravula。 https://youtu.be/sfmaf4QpVTw
他给我讲明白了recursion,也就是文章开头DFS的那颗树。第二个是Marty Stepp的CS106B,Youtube已经删掉了。这个老师讲课很好。B站上还有链接。手把手给你写backtracking,然后看不同情况下的输出。


补充内容 (2020-1-8 12:22):
所以我们对比阿三还是有优势的。我们可以看懂印度人做的精品视频。IIT的公开课。还有几个印度小哥讲算法和数据结构都是精品。同时我们也可以看花花酱,邓公的课程。但是他们就看不懂了。。

评分

参与人数 2大米 +4 收起 理由
14417335 + 3
windpuppy + 1 赞一个

查看全部评分

回复

使用道具 举报

heronalps 2020-1-9 04:27:19 | 显示全部楼层
本楼:   👍  3
100%
0%
0   👎
全局:   383
99%
1%
5
图形化思路的方法很好!

我对于Subsets的时间复杂度有一点异议,“ans.add(new ArrayList<Integer>(track));” 应该是线性时间的操作,在worst case中,每一次backtrack都需要执行一次,所以总体的TC应该是O(N * 2^N).

评分

参与人数 3大米 +4 收起 理由
14417335 + 2
mlwhut + 1 赞一个
不知道小帅 + 1 赞一个

查看全部评分

回复

使用道具 举报

404NoneFound 2020-1-9 13:26:26 | 显示全部楼层
本楼:   👍  2
100%
0%
0   👎
全局:   75
99%
1%
1
讲得真的是很好了。

评分

参与人数 1大米 +1 收起 理由
不知道小帅 + 1 给你点个赞!

查看全部评分

回复

使用道具 举报

 楼主| 不知道小帅 2020-1-9 04:30:04 来自APP | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   717
100%
0%
3
heronalps 发表于 2020/01/09 04:27:19
图形化思路的方法很好!

我对于Subsets的时间复杂度有一点异议,“ans.add(new ArrayList&...
是的,你说得对,我打字的时候忘记考虑copy也是线性的复杂度了。
回复

使用道具 举报

heronalps 2020-1-9 05:49:55 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   383
99%
1%
5
不知道小帅 发表于 2020-1-8 15:30
是的,你说得对,我打字的时候忘记考虑copy也是线性的复杂度了。

你能不能谈一下,Permutations那道题如何优化?
回复

使用道具 举报

 楼主| 不知道小帅 2020-1-9 06:03:25 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   717
100%
0%
3
本帖最后由 不知道小帅 于 2020-1-9 06:14 编辑
heronalps 发表于 2020-1-9 05:49
你能不能谈一下,Permutations那道题如何优化?

最直接和显然的做法就是把track那里加一个类似hash table 的boolean array,这样判断的成本就只有O(1)了。
还有就是可以通过swap的做法来处理这个问题。swap的话主要逻辑如下,当然最后需要把array变成list,然后copy。感觉这一步通过recursion好像很难去掉。。
  1.                         for (int i=start; i<array.length; i++) {
  2.                                 swap(array, start, i);
  3.                                 permute(result, array, start+1);
  4.                                 swap(array, start, i);
  5.                         }
复制代码



回复

使用道具 举报

WarriorZ 2020-1-9 06:30:54 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   4041
97%
3%
121
不知道小帅 发表于 2020-1-9 06:03
最直接和显然的做法就是把track那里加一个类似hash table 的boolean array,这样判断的成本就只有O(1)了 ...

递归树解释的挺清楚的,赞一个。针对优化的问题我觉得一共有2^n个Permutation,加上每生成一个新的结果需要n的时间去复制,时间复杂度再怎么优化不可能低于n2^n了。加个visited数组确实能减少判断时间,但是时间复杂度还是一样的。

评分

参与人数 1大米 +1 收起 理由
不知道小帅 + 1 很有用的信息!

查看全部评分

回复

使用道具 举报

 楼主| 不知道小帅 2020-1-9 06:41:59 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   717
100%
0%
3
WarriorZ 发表于 2020-1-9 06:30
递归树解释的挺清楚的,赞一个。针对优化的问题我觉得一共有2^n个Permutation,加上每生成一个新的结果需 ...

是的,感觉copy的O(n)复杂度基本去不掉。不过permutation的数量应该是n!,另外求大米。。。。
不过想想也是,最后结果里面一个list of list,总共元素的数量就是n * n!了。

评分

参与人数 2大米 +4 收起 理由
windpuppy + 1 赞一个
WarriorZ + 3 给你点个赞!

查看全部评分

回复

使用道具 举报

windpuppy 2020-1-9 10:38:24 来自APP | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   7
100%
0%
0
楼主体力惊人,手动赞一个。subset也有bfs和bitwise做法,可以准备一手,现场炫技。

顺便复习一下2^n和n!比较大小怎么推。现场被问过。

评分

参与人数 1大米 +1 收起 理由
biorainy + 1 给你点个赞!

查看全部评分

回复

使用道具 举报

windpuppy 2020-1-9 10:39:31 来自APP | 显示全部楼层
本楼:   👍  2
100%
0%
0   👎
全局:   7
100%
0%
0
另外C++的话如果不传reference而是传value,很多情况下不需要手动"remove"来backtrack。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

Advertisement
>
快速回复 返回顶部 返回列表