辨析DFS 、回溯法和递归

本来题目叫做 Backtracking 回溯法总结的,搜了一圈发现好多既然连 DFS 、回溯法和递归之间的区别都傻傻分不清,所以也把内容重新组织下。

我的新书《LangChain编程从入门到实践》 已经开售!推荐正在学习AI应用开发的朋友购买阅读!
LangChain编程从入门到实践

回溯法

  • 回溯是一种通用的算法思想,把问题分步解决,在每一步都试验所有的可能(回溯本质上是一种穷举。),当发现已经找到一种方式或者目前这种方式不可能是结果的时候,退回上一步继续尝试其他可能。当每一步的处理都是一致的,这时候用递归来实现就很自然。

    识别回溯

  • 判断回溯很简单,拿到一个问题,你感觉如果不穷举一下就没法知道答案,那就可以开始回溯了。
  • 一般回溯的问题有三种:
    • Find a path to success 有没有解
    • Find all paths to success 求所有解
      • 求所有解的个数
      • 求所有解的具体信息
    • Find the best path to success 求最优解

      解决模板

  • 关于回溯的三种问题,模板略有不同,
    • 第一种,返回值是true/false。
    • 第二种,求个数,设全局counter,返回值是void;求所有解信息,设result,返回值void。
    • 第三种,设个全局变量best,返回值是void。

      八皇后问题

  • 给个n,有几种解;Leetcode N-Queens II
  • 给个n,给出所有解;Leetcode N-Queens I

    递归

  • 递归算法是一种直接或者间接调用自身函数或者方法的算法。有如下三个特点:
    1. 一个问题的解可以分解为几个子问题的解
    2. 这个问题与分解之后的子问题,除了数据规模不同,求解思路完全一样
    3. 存在递归终止条件,即必须有一个明确的递归结束条件,称之为递归出口

      解决模板

  • 总结一下如何写递归代码:
    1. 找到如何将大问题分解为小问题的规律
    2. 通过规律写出递推公式
    3. 通过递归公式的临界点推敲出终止条件
    4. 将递推公式和终止条件翻译成代码

      相关问题

  • 爬楼梯
  • 划分为k个相等的子集

    DFS

  • 深度优先搜索(DFS)算法,即是一种搜索算法。他的特点是在搜索时会面临多个选择,当选择某一个情况后仍然会面临多个选择。那么,他每一次都选择一个情况时,会继续沿着这个“方向”搜索下去,直到遇到边界无法在搜索时,结束当前分支路径的搜索。接着,进行其他路径的搜索。以这种方式持续下去,直到将所有的路径搜索完毕。经典的案例,比如对于BST(二叉搜索树)的先序遍历、中序遍历和后序遍历。
  • 回溯搜索是深度优先搜索(DFS)的一种,对于某一个搜索树来说(搜索树是起记录路径和状态判断的作用)。其主要的区别是,回溯法在求解过程中不保留完整的树结构,而深度优先搜索则记下完整的搜索树。在深度优先搜索中,用标志的方法记录访问过的状态,这种处理方法使得深度优先搜索法与回溯法没什么区别了。

    参考链接

  • Backtracking回溯法(又称DFS,递归)全解
  • 看动画轻松理解「递归」与「动态规划」

辨析DFS 、回溯法和递归

https://liduos.com/backtracking.html

作者

莫尔索

发布于

2022-07-08

更新于

2024-05-24

许可协议

评论