weixin_43899069
2020-03-03 16:14 阅读 474

回溯、深搜、剪枝的区别是什么?

在刷题中,看题解时总是遇到DFS、回溯、剪枝这类字眼,但总是搞不懂他们有什么区别。

以下是我的理解,不知是否正确?

剪枝是用来优化的,深搜是将一种可能执行到底,而回溯是碰到不可行的情况就结束,开始下次遍历, 那么深搜+剪枝=回溯。

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享

1条回答 默认 最新

  • 已采纳
    weixin_43891765 格戮 2020-03-03 17:57

    以下是我个人理解:

    深搜可以理解为一直套用函数最后得出结果;

    回溯可以理解为对每一步或每一个位置上的不同操作的出多种结果,再根据所需取得想要的答案;

    剪枝就是对递归函数空间和时间上的优化,舍掉无用部分的递归,尽力去只递归有价值部分。

    点赞 评论 复制链接分享

相关推荐