算法现学现卖—— 回溯算法

作者:杨润炜
日期:2020/4/25 12:15

回溯算法

简述

  • 如果理解了递归、DFS,那么理解回溯就很简单了,它就是在递归的每一层处理完成后,将其造成的影响抹去,上一层就像没事发生一样,继续运行其它层的逻辑
  • 如果大家看过《蝴蝶效应》(没看的抓紧啦)都知道里面的主角能够回到过去更改某一时刻的决定,这个过程就是回溯,回到过去再做另外的决定。

代码模板

  1. dfs (level, params):
  2. # 递归终止条件
  3. if level >= max_level:
  4. return
  5. do_something()
  6. # 下探到下一层
  7. dfs(level + 1, params)
  8. # 撤消当前的影响,以便回溯
  9. revert_current_status()

例题解析

全排列

先来看递归不回溯的形式


每次都从可选数字里选择当前节点数组里不存在的元素,然后继续下一层,直到数组元素个数为3,详情请看代码实现

  1. class Solution:
  2. def permute(self, nums: List[int]) -> List[List[int]]:
  3. res = []
  4. self.dfs(nums, res, [])
  5. return res if res else [res]
  6. def dfs(self, nums, res, item):
  7. if len(item) >= len(nums):
  8. return res.append(item)
  9. for k in nums:
  10. if k not in item:
  11. self.dfs(nums, res, item + [k])

再看看回溯的方式


红色线代表撤消操作,如[1,2]撤消为[1],然后按递归顺序深度优先地运行下去

  1. class Solution:
  2. def permute(self, nums: List[int]) -> List[List[int]]:
  3. res = []
  4. self.dfs(nums, res, [])
  5. return res if res else [res]
  6. def dfs(self, nums, res, item):
  7. if len(item) >= len(nums):
  8. return res.append(item[:])
  9. for k in nums:
  10. if k not in item:
  11. item.append(k)
  12. self.dfs(nums, res, item)
  13. item.pop()

回溯的方式主要是多了item的pop操作,它的作用是恢复该层对数据的影响,这样整个过程就复用一个item列表,节省了空间

LeetCode题目

全排列
N皇后

感谢您的阅读!
如果看完后有任何疑问,欢迎拍砖。
欢迎转载,转载请注明出处:http://www.yangrunwei.com/a/106.html
邮箱:glowrypauky@gmail.com
QQ: 892413924