递归中的记忆化搜索和回溯法中的剪枝

Question

波波老师，这个问题可能不是我们学算法应该探究的，但是我想知道，递归中的记忆化搜索和回溯法中的剪枝是不是异曲同工还是同曲同工。上网查了很多，也没有两者比对的相关的文章，应该是我自己想多了，但是我还是想清楚一些，老师能够指点一下吗？我感觉对于这两种方法，都是避免不必要的计算，但是感觉它们还是有的差别的。它们有什么区别吗？递归是回溯的手段，但是递归不只是用来回溯，是否可以认为剪枝是用在回溯中类似记忆化搜索的手段。

Answer 1

liuyubobobo 2021-09-05 07:24:46

整体来讲，“回溯”这个词更强调“暴力搜索”，即搜索解空间中的所有可能性。但由于解空间是一个树形，所以需要递归地区做暴力搜索，即“回溯”。

“回溯剪枝”通常是指，在暴力搜索的过程中，某一个路径，我们提前就知道它不可能是解了，所以就可以不继续搜索了。

而记忆化搜索，你说它是剪枝，严格来看，是可以的，毕竟记忆化搜索表现在代码里，是：

if(某个状态之前已经解过了) return 这个状态对应的解。

这个 return，可以理解成不继续搜索了，你说是一种剪枝，有道理的。

但是为什么能直接 return“这个状态对应的解”？因为我们搜索过这个状态的话，就把这个状态的解记录下来了。这就是“记忆化”的意思。所以，我们不是因为知道这条路不是解，所以剪掉它，而是“已经求解过”，所以不需要重复求解，直接返回解就好了。

这就是所谓的“重叠子问题”的意思。而通常，当我们说回溯剪枝的时候，不是指这个意思，而是在暴力搜索的过程中，提前发现我们当前寻找的路径不可能是解。

=============

不过整体，这种“算法描述”上的区分，我是不认为那么重要的。这些“概念”也不是数学语言，有精准的定义和适用范围。更是自然语言，帮助人们交流算法的实现用的。甚至个人我认为，比如动态规划三要素都是什么一类的“概念”，都并不重要。因为严格区分它们，其实并不能帮助你在面对一个问题的时候更快地解决。把动态规划三要素说的头头是道，不代表动态规划掌握得好。

而且，更重要的是，其实在面试中，不会有人问你，回溯和记忆化搜索的区别是什么？动态规划的三要素是什么？

所以，上面我的解释，也只是我的理解。仅供参考。

继续加油！：）

Answer 2

提问者 Mosea 2021-09-05 11:20:38

    我明白了，异:记忆化搜索是不去解解过的问题，剪枝是不去解解不了的问题。同:两者避免不必要的解。谢谢波波老师!
   我内心的感慨，说一个题外话，同为慕课网的老师，目前我知道的只有波波老师的回复最积极，最快，即使问的问题超出了课程范围，也能即使指出不耽误学生。而一些老师问了一个星期都不理人。