自下而上和自上而下有什么区别? [英] What is the difference between bottom-up and top-down?

问题描述

自底向上方法(用于动态编程)在于首先查看较小"的子问题，然后使用较小问题的解决方案来解决较大的子问题.

The bottom-up approach (to dynamic programming) consists in first looking at the "smaller" subproblems, and then solve the larger subproblems using the solution to the smaller problems.

自上而下在于以一种自然的方式"解决问题，并检查您之前是否已经计算过该子问题的解决方案.

The top-down consists in solving the problem in a "natural manner" and check if you have calculated the solution to the subproblem before.

我有点困惑.两者有什么区别?

I'm a little confused. What is the difference between these two?

推荐答案

rev4:用户Sammaron的一个非常有说服力的评论指出，也许这个答案以前使自上而下和自下而上混淆.虽然最初这个答案(rev3)和其他答案说自下而上是记忆"(假设子问题")，但可能是相反的(即自上而下"可能是假设子问题"和自下而上"可能是组成子问题").以前，我读过备忘录是与动态编程的子类型相对的另一种动态编程.尽管没有订阅，但我还是引用了该观点.我将这个答案改写为与术语无关，直到可以在文献中找到适当的参考文献为止.我还将此答案转换为社区Wiki.请选择学术来源.参考文献列表:{Web: 1 ， 5 }

rev4: A very eloquent comment by user Sammaron has noted that, perhaps, this answer previously confused top-down and bottom-up. While originally this answer (rev3) and other answers said that "bottom-up is memoization" ("assume the subproblems"), it may be the inverse (that is, "top-down" may be "assume the subproblems" and "bottom-up" may be "compose the subproblems"). Previously, I have read on memoization being a different kind of dynamic programming as opposed to a subtype of dynamic programming. I was quoting that viewpoint despite not subscribing to it. I have rewritten this answer to be agnostic of the terminology until proper references can be found in the literature. I have also converted this answer to a community wiki. Please prefer academic sources. List of references: {Web: 1,2} {Literature: 5}

回顾

动态编程就是要以一种避免重新计算重复工作的方式对计算进行排序.您有一个主要问题(子问题树的根)和子问题(子树). 子问题通常会重复并重叠.

例如，考虑您最喜欢的Fibonnaci示例.如果我们进行了幼稚的递归调用，这就是子问题的完整树:

For example, consider your favorite example of Fibonnaci. This is the full tree of subproblems, if we did a naive recursive call:

TOP of the tree
fib(4)
 fib(3)...................... + fib(2)
  fib(2)......... + fib(1)       fib(1)........... + fib(0)
   fib(1) + fib(0)   fib(1)       fib(1)              fib(0)
    fib(1)   fib(0)
BOTTOM of the tree

(在其他一些罕见的问题中，该树在某些分支中可能是无限的，代表不终止，因此树的底部可能会无限大.此外，在某些问题中，您可能不知道完整树的外观就像提前.因此，您可能需要一个策略/算法来确定要揭示的子问题.)

(In some other rare problems, this tree could be infinite in some branches, representing non-termination, and thus the bottom of the tree may be infinitely large. Furthermore, in some problems you might not know what the full tree looks like ahead of time. Thus, you might need a strategy/algorithm to decide which subproblems to reveal.)

至少有两种主要的动态编程技术是互不排斥的:

There are at least two main techniques of dynamic programming which are not mutually exclusive:

• 记忆化-这是一种自由放任的方法:您假设您已经计算了所有子问题，并且不知道最佳评估顺序是什么.通常，您将从根目录执行递归调用(或某些迭代等效项)，或者希望您接近最佳评估顺序，或者获得证明可以帮助您达到最佳评估顺序.您将确保递归调用永远不会重新计算子问题，因为您缓存结果，因此不会重新计算重复的子树.

• Memoization - This is a laissez-faire approach: You assume that you have already computed all subproblems and that you have no idea what the optimal evaluation order is. Typically, you would perform a recursive call (or some iterative equivalent) from the root, and either hope you will get close to the optimal evaluation order, or obtain a proof that you will help you arrive at the optimal evaluation order. You would ensure that the recursive call never recomputes a subproblem because you cache the results, and thus duplicate sub-trees are not recomputed.

• 示例:如果要计算斐波那契数列fib(100)，则只需调用它，它就会调用fib(100)=fib(99)+fib(98)，这将调用fib(99)=fib(98)+fib(97)等. .，它将称为fib(2)=fib(1)+fib(0)=1+0=1.然后它将最终解析fib(3)=fib(2)+fib(1)，但不需要重新计算fib(2)，因为我们已将其缓存.
• 这从树的顶部开始，并评估从叶子/子树一直到根的子问题.

• example: If you are calculating the Fibonacci sequence fib(100), you would just call this, and it would call fib(100)=fib(99)+fib(98), which would call fib(99)=fib(98)+fib(97), ...etc..., which would call fib(2)=fib(1)+fib(0)=1+0=1. Then it would finally resolve fib(3)=fib(2)+fib(1), but it doesn't need to recalculate fib(2), because we cached it.
• This starts at the top of the tree and evaluates the subproblems from the leaves/subtrees back up towards the root.

制表法-您也可以将动态编程视为一种表格填充"算法(尽管通常是多维的，但在极少数情况下，此表格"可能具有非欧几里德几何形状*).这就像记忆，但更加活跃，并且涉及一个额外的步骤:您必须提前选择执行计算的确切顺序.这并不意味着订单必须是静态的，而是您比备忘录具有更大的灵活性.

Tabulation - You can also think of dynamic programming as a "table-filling" algorithm (though usually multidimensional, this 'table' may have non-Euclidean geometry in very rare cases*). This is like memoization but more active, and involves one additional step: You must pick, ahead of time, the exact order in which you will do your computations. This should not imply that the order must be static, but that you have much more flexibility than memoization.

• 示例:如果执行斐波那契，则可以选择按以下顺序计算数字:fib(2)，fib(3)，fib(4) ...缓存每个值，以便您可以计算下一个更容易.您也可以将其视为填满表格(另一种缓存形式).
• 我个人很少听到制表"一词，但这是一个非常体面的术语.有人认为这是动态编程".
• 在运行算法之前，程序员会考虑整个树，然后编写一种算法，以朝根的特定顺序评估子问题，通常填写一张表.
• *脚注:有时，表"本身并不是具有网格状连接性的矩形表.相反，它可能具有更复杂的结构，例如树，或特定于问题域的结构(例如，地图上飞行距离内的城市)，甚至是网格图，而网格图却没有网格例如，user3290797链接了一个动态编程示例，该示例查找

• example: If you are performing fibonacci, you might choose to calculate the numbers in this order: fib(2),fib(3),fib(4)... caching every value so you can compute the next ones more easily. You can also think of it as filling up a table (another form of caching).
• I personally do not hear the word 'tabulation' a lot, but it's a very decent term. Some people consider this "dynamic programming".
• Before running the algorithm, the programmer considers the whole tree, then writes an algorithm to evaluate the subproblems in a particular order towards the root, generally filling in a table.
• *footnote: Sometimes the 'table' is not a rectangular table with grid-like connectivity, per se. Rather, it may have a more complicated structure, such as a tree, or a structure specific to the problem domain (e.g. cities within flying distance on a map), or even a trellis diagram, which, while grid-like, does not have a up-down-left-right connectivity structure, etc. For example, user3290797 linked a dynamic programming example of finding the maximum independent set in a tree, which corresponds to filling in the blanks in a tree.

(在最一般的情况下，在动态编程"范式中，我想说程序员考虑了整个树，然后编写了一种算法，该算法实现了用于评估子问题的策略，该子问题可以优化任何属性您想要的(通常是时间复杂性和空间复杂性的组合).您的策略必须从某个地方开始，并带有一些特定的子问题，并且可能会根据这些评估的结果进行调整.一般而言，动态编程"您可以尝试缓存这些子问题，更普遍的是，尝试避免以细微的区别重新访问子问题，也许是各种数据结构中的图的情况.通常，这些数据结构是它们的核心，如数组或表.如果我们不再需要它们了，那就扔掉.)

(At it's most general, in a "dynamic programming" paradigm, I would say the programmer considers the whole tree, then writes an algorithm that implements a strategy for evaluating subproblems which can optimize whatever properties you want (usually a combination of time-complexity and space-complexity). Your strategy must start somewhere, with some particular subproblem, and perhaps may adapt itself based on the results of those evaluations. In the general sense of "dynamic programming", you might try to cache these subproblems, and more generally, try avoid revisiting subproblems with a subtle distinction perhaps being the case of graphs in various data structures. Very often, these data structures are at their core like arrays or tables. Solutions to subproblems can be thrown away if we don't need them anymore.)

[以前，此答案说明了自上而下与自下而上的术语；显然有两种主要的方法称为记忆化"和制表"，与这些术语可能是双射的(尽管不完全相同).大多数人使用的通用术语仍然是动态编程"，有些人说记忆化"是指动态编程"的特定子类型.在社区可以在学术论文中找到适当的参考文献之前，这个答案拒绝说是自上而下和自下而上的.最终，重要的是要了解区别而不是术语.]

[Previously, this answer made a statement about the top-down vs bottom-up terminology; there are clearly two main approaches called Memoization and Tabulation that may be in bijection with those terms (though not entirely). The general term most people use is still "Dynamic Programming" and some people say "Memoization" to refer to that particular subtype of "Dynamic Programming." This answer declines to say which is top-down and bottom-up until the community can find proper references in academic papers. Ultimately, it is important to understand the distinction rather than the terminology.]

记忆是非常容易编写的代码(通常，您可以*编写一个自动为您执行的"memoizer"注释或包装函数)，并且应该是您的第一步.制表的缺点是您必须提出命令.

Memoization is very easy to code (you can generally* write a "memoizer" annotation or wrapper function that automatically does it for you), and should be your first line of approach. The downside of tabulation is that you have to come up with an ordering.

*(实际上只有在您自己编写函数和/或使用不纯/非函数式编程语言进行编码时，这才容易...例如，如果某人已经编写了预编译的fib函数，它必然会使递归调用本身，而不能确保这些递归调用无法调用您的新的已记忆功能(而不是原始的未记忆功能)，就无法神奇地记忆该功能

*(this is actually only easy if you are writing the function yourself, and/or coding in an impure/non-functional programming language... for example if someone already wrote a precompiled fib function, it necessarily makes recursive calls to itself, and you can't magically memoize the function without ensuring those recursive calls call your new memoized function (and not the original unmemoized function))

请注意，自顶向下和自底向上都可以通过递归或迭代表填充来实现，尽管这可能不是很自然.

Note that both top-down and bottom-up can be implemented with recursion or iterative table-filling, though it may not be natural.

通过记忆，如果树很深(例如fib(10^6))，您将用完堆栈空间，因为每个延迟的计算都必须放在堆栈上，并且将有10 ^ 6.

With memoization, if the tree is very deep (e.g. fib(10^6)), you will run out of stack space, because each delayed computation must be put on the stack, and you will have 10^6 of them.

如果您执行(或尝试)访问子问题的顺序不是最优的，则这两种方法都不是时间最优的，特别是如果有多种方法来计算子问题(通常通过缓存可以解决此问题，但是从理论上讲，这是可能的)在某些特殊情况下可能不会缓存).记忆化通常会增加时间复杂度，从而增加空间复杂度(例如，使用列表制表法时，您有更大的自由度可以放弃计算，例如使用Fib制表法可以使用O(1)空间，而使用Fib进行制表法则可以使用O(N)堆栈空间).

Either approach may not be time-optimal if the order you happen (or try to) visit subproblems is not optimal, specifically if there is more than one way to calculate a subproblem (normally caching would resolve this, but it's theoretically possible that caching might not in some exotic cases). Memoization will usually add on your time-complexity to your space-complexity (e.g. with tabulation you have more liberty to throw away calculations, like using tabulation with Fib lets you use O(1) space, but memoization with Fib uses O(N) stack space).

如果您也遇到了非常复杂的问题，则可能别无选择，只能进行制表(或者至少在将备忘录移至所需位置时扮演更积极的角色).同样，如果您处于优化绝对至关重要且必须进行优化的情况下，则制表将使您能够进行优化，而备忘录不会让您以理智的方式进行优化.以我的拙见，在正常的软件工程中，这两种情况都不会出现，因此，除非有必要(例如堆栈空间)使制表成为必需，否则我将只使用备忘录(缓存其答案的函数").从技术上讲，为避免堆栈崩溃，您可以1)增加允许使用的语言的堆栈大小限制，或2)消耗恒定的额外工作量来虚拟化您的堆栈(ick)，或3)以连续传递样式编写程序，实际上还可以虚拟化您的堆栈(不确定其复杂性，但是基本上，您将有效地从大小为N的堆栈中获取延迟的调用链，并将其事实上保留在N个连续嵌套的thunk函数中……尽管在某些语言中，它们没有尾部调用优化，您可能需要蹦蹦跳跳来避免堆栈爆裂.

If you are also doing a extremely complicated problems, you might have no choice but to do tabulation (or at least take a more active role in steering the memoization where you want it to go). Also if you are in a situation where optimization is absolutely critical and you must optimize, tabulation will allow you to do optimizations which memoization would not otherwise let you do in a sane way. In my humble opinion, in normal software engineering, neither of these two cases ever come up, so I would just use memoization ("a function which caches its answers") unless something (such as stack space) makes tabulation necessary... though technically to avoid a stack blowout you can 1) increase the stack size limit in languages which allow it, or 2) eat a constant factor of extra work to virtualize your stack (ick), or 3) program in continuation-passing style, which in effect also virtualizes your stack (not sure the complexity of this, but basically you will effectively take the deferred call chain from the stack of size N and de-facto stick it in N successively nested thunk functions... though in some languages without tail-call optimization you may have to trampoline things to avoid a stack blowout).

在这里，我们列出了特别令人感兴趣的示例，这些示例不仅是一般的DP问题，而且还有趣地区分了记忆和制表.例如，一种配方可能比另一种配方容易得多，或者可能存在基本上需要列表的优化:

Here we list examples of particular interest, that are not just general DP problems, but interestingly distinguish memoization and tabulation. For example, one formulation might be much easier than the other, or there may be an optimization which basically requires tabulation:

• 计算编辑距离的算法[ 4 ]，有趣作为二维表格填充算法的一个重要例子

• the algorithm to calculate edit-distance[4], interesting as a non-trivial example of a two-dimensional table-filling algorithm

这篇关于自下而上和自上而下有什么区别?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！