sga*_*a62 5 algorithm recursion call memoization dynamic-programming
我刚读了这篇由Krishnamurthi教授撰写的关于递归记忆与动态规划的心理模型的简短帖子.在其中,Krishnamurthi将memoization的自上而下结构表示为递归树,将DP的自下而上结构表示为DAG,其中源顶点是第一个 - 可能是最小的 - 子问题求解,并且接收器顶点是最终计算(基本上是图形)与前面提到的递归树相同,但所有边都翻转了).很公平; 这很有道理.
无论如何,最后,他给读者一个心理锻炼:
Memoization是对答案的自上而下,深度优先计算的优化.DP是针对答案的自下而上,广度优先计算的优化.
我们应该自然地问,怎么样
- 自上而下,广度优先
- 自下而上,深度优先
他们在哪里适应技术空间,以避免重新计算,通过时间折衷空间？
- 我们已经有了他们的名字吗？如果是,那是什么？或者
- 我们是否错过了一两个重要的技巧？或者
- 我们没有这些名字的原因吗？
但是,他停在那里,没有对这些问题发表意见.
我迷路了,但是这里有:
我的解释是,自上而下,广度优先计算将需要为每个函数调用单独的过程.自下而上,深度优先的方法将以某种方式将最终解决方案拼凑在一起,因为每条迹线到达"接收器顶点".所有呼叫完成后,解决方案最终会"加起来"到正确的答案.
我怎么了？有谁知道他的三个问题的答案？
让我们分析一下这两个图中的边是什么意思。从子问题a到b的边表示一种关系，其中b的解用于计算a并且必须在它之前求解。（在另一种情况下反过来。）
会想到拓扑排序吗？
进行拓扑排序的一种方法是执行深度优先搜索，然后在离开每个节点的途中对其进行处理。这基本上就是递归记忆的作用。你从每个子问题开始向下深度优先，直到遇到一个你没有解决的问题（或者你没有访问过的节点），然后你解决了它。
动态规划，或自下而上 - 广度优先解决问题的方法涉及解决较小的问题并从中构建解决较大问题的方法。这是进行拓扑排序的另一种方法，您访问入度为 0 的节点，对其进行处理，然后将其删除。在 DP 中，最小的问题首先被解决，因为它们的入度较低。（较小是对手头问题的主观感受。）
这里的问题是生成必须解决子问题集的序列。自上而下的广度优先和自下而上的深度优先都不能做到这一点。即使进程被分成线程，自上而下的广度优先最终仍然会做一些与深度优先计数器非常相似的事情。有一个必须解决问题的顺序。自底向上的深度优先方法可能能够部分解决问题，但最终结果仍然类似于广度优先的对应部分。子问题将以类似的顺序解决。
鉴于这些方法与其他方法相比几乎没有任何改进，不能很好地与类比转化并且实施起来很乏味，因此它们还没有很好地建立。
小智 4
@AndyG 的评论非常切中要点。我也喜欢@shebang的答案，但这里是在这种情况下直接回答这些问题的答案，而不是通过简化为另一个问题。
只是不清楚自上而下、广度优先的解决方案会是什么样子。但是，即使您以某种方式暂停计算以不进行任何子计算（可以想象各种基于连续的方案可以实现这一点），这样做也是没有意义的，因为会共享子问题。
同样，目前还不清楚自下而上、深度优先的解决方案是否能够解决问题。如果你自下而上地进行，但一直在计算的某个脊柱上进行充电，但其他子问题的解决方案还没有准备好并处于等待状态，那么你就会计算垃圾。
因此，自上而下、广度优先没有任何好处，而自下而上、深度优先甚至没有提供解决方案。
顺便说一句，上述博客文章的更新版本现在已成为我文本中的一个部分（这是 2014 年版本；期待更新。