自下而上和自上而下有什么区别？

Question

的自下而上的方法(动态编程)在于第一看"较小"的子问题,进而解决使用所述溶液到较小的问题较大子问题.

在自上而下的在于解决"自然地"的问题,并检查是否已计算出前解决的子问题.

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

Answer 1

rev4:用户Sammaron的一个非常有说服力的评论指出,或许,这个答案以前混淆了自上而下和自下而上.虽然最初这个答案(rev3)和其他答案说"自下而上是记忆"("假设子问题"),但它可能是反向的(也就是说,"自上而下"可能是"假设子问题"和"自下而上"可能"构成子问题").以前,我读过memoization是一种不同的动态编程,而不是动态编程的子类型.尽管没有订阅,但我引用了这个观点.我已经重写了这个答案,对术语不可知,直到在文献中找到适当的参考文献.我还将此答案转换为社区维基.请更喜欢学术资源.参考文献列表:{网页:1,2 } {文学:5 }

概括

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

例如,考虑您最喜欢的Fibonnaci示例.如果我们做了一个天真的递归调用,这是完整的子问题树:

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

(在一些其他罕见的问题中,这棵树在某些分支中可能是无限的,表示非终止,因此树的底部可能无限大.此外,在某些问题中,您可能不知道完整的树在未来之前是什么样的因此,您可能需要一个策略/算法来决定要揭示哪些子问题.)

记忆,制表

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

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

  • 例如:如果你正在计算Fibonacci序列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),因为我们缓存了它.
  • 这从树的顶部开始,并从叶子/子树到根目录的子问题进行评估.

• 制表 - 您还可以将动态编程视为"填表"算法(尽管通常是多维的,但这种'表'在极少数情况下可能具有非欧几里德几何*).这就像记忆,但更活跃,并涉及一个额外的步骤:您必须提前选择您将进行计算的确切顺序.这并不意味着订单必须是静态的,但是你比memoization有更多的灵活性.

  • 例如:如果要执行斐波那契,你可能会选择在这个顺序来计算数字:fib(2),fib(3),fib(4)...每一个缓存值,以便可以更容易地计算下一个人.您还可以将其视为填充表格(另一种形式的缓存).
  • 我个人并没有经常听到"制表"这个词,但这是一个非常好的术语.有些人认为这是"动态编程".
  • 在运行算法之前,程序员会考虑整个树,然后编写一个算法,以特定的顺序向根查询子问题,通常填写一个表.
  • *脚注:有时候,"桌子"本身并不是一个具有网格状连接的矩形桌子.相反,它可能有一个更复杂的结构,例如树,或特定于问题域的结构(例如地图上飞行距离内的城市),甚至是格子图,虽然网格状,但没有例如,user3290797链接了在树中查找最大独立集的动态编程示例,其对应于填充树中的空白.

(最常见的是,在"动态编程"范例中,我会说程序员会考虑整个树,然后编写一个算法来实现一个策略来评估子问题,这个子问题可以优化你想要的任何属性(通常是时间复杂度的组合)你的策略必须从某个特定的子问题开始,或许可以根据这些评估的结果自适应.在"动态编程"的一般意义上,你可能会尝试缓存这些子问题,等等一般来说,尽量避免重新审视子问题,但可能是各种数据结构中图形的细微差别.通常,这些数据结构的核心就像数组或表格一样.如果我们不需要它们,可以抛弃子问题的解决方案了.)

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

利弊

易于编码

Memoization很容易编码(你通常可以*编写一个"memoizer"注释或自动为你做的包装函数),应该是你的第一线方法.制表的缺点是你必须提出订购.

*(如果您自己编写函数,和/或使用不纯/非函数编程语言编写代码,这实际上很简单...例如,如果某人已编写预编译fib函数,则必然会对自身进行递归调用,并且你不能神奇地记住这个函数而不确保那些递归调用调用你的新memoized函数(而不是原来的unmemoized函数))

递归

请注意,自上而下和自下而上都可以通过递归或迭代表填充来实现,尽管它可能并不自然.

实际问题

通过memoization,如果树很深(例如fib(10^6)),你将耗尽堆栈空间,因为每个延迟计算必须放在堆栈上,你将有10 ^ 6个.

最优

如果您发生(或尝试)访问子问题的顺序不是最优的,那么这两种方法可能都不是时间最优的,特别是如果有多种方法来计算子问题(通常缓存会解决这个问题,但理论上可能是缓存可能不是在一些奇特的情况下).记忆通常会增加你的空间复杂性的时间复杂性(例如,通过制表你可以更自由地扔掉计算,比如使用Fib的制表可以让你使用O(1)空间,但是使用O的记忆使用O(N)堆栈空间).

高级优化

如果你也在做一个非常复杂的问题,你可能别无选择,只能做制表(或者至少在你想要它的地方转发备忘录方面发挥更积极的作用).此外,如果您处于优化至关重要并且必须进行优化的情况下,制表将允许您进行优化,而这些优化将使您无法以理智的方式进行备忘.在我看来,在正常的软件工程中,这两种情况都没有出现过,所以我只想使用memoization("一种缓存其答案的函数"),除非某些东西(如堆栈空间)需要制表......虽然从技术上讲,为了避免堆栈井喷,你可以1)增加允许它的语言的堆栈大小限制,或者2)吃一个额外工作的常数因素来虚拟化你的堆栈(ick)或3)程序的延续传递方式,这实际上也是虚拟化你的堆栈(不确定这个的复杂性,但基本上你会有效地从大小为N的堆栈中获取延迟的调用链,并且事实上将它粘贴在N个连续嵌套的thunk函数中......虽然在某些语言中没有尾调用优化你可能需要蹦床以避免堆栈井喷).

更复杂的例子

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

• 计算编辑距离的算法[ 4 ],有趣的是作为二维表填充算法的一个非平凡的例子

Answer 2

自上而下和自下而上DP是解决相同问题的两种不同方式.考虑一个记忆(自上而下)与动态(自下而上)编程解决方案来计算斐波那契数.

fib_cache = {}

def memo_fib(n):
  global fib_cache
  if n == 0 or n == 1:
     return 1
  if n in fib_cache:
     return fib_cache[n]
  ret = memo_fib(n - 1) + memo_fib(n - 2)
  fib_cache[n] = ret
  return ret

def dp_fib(n):
   partial_answers = [1, 1]
   while len(partial_answers) <= n:
     partial_answers.append(partial_answers[-1] + partial_answers[-2])
   return partial_answers[n]

print memo_fib(5), dp_fib(5)

我个人觉得备忘更加自然.您可以使用递归函数并通过机械过程对其进行记忆(首先在缓存中查找答案并在可能的情况下返回它,否则递归计算它然后在返回之前,将计算保存在缓存中以备将来使用),而自下而上动态编程要求您对计算解决方案的顺序进行编码,这样在它所依赖的较小问题之前不会计算出"大问题".

Answer 3

动态编程的一个关键特性是存在重叠的子问题.也就是说,您尝试解决的问题可以分解为子问题,并且许多子问题共享子问题.这就像"分而治之",但你最终会做很多次同样的事情.我自2003年以来在教授或解释这些问题时使用过的一个例子:你可以递归计算斐波纳契数.

def fib(n):
  if n < 2:
    return n
  return fib(n-1) + fib(n-2)

使用您喜欢的语言并尝试运行它fib(50).这将需要非常长的时间.大致和fib(50)自己一样多!但是,正在进行许多不必要的工作.fib(50)将调用fib(49)和fib(48),但后来这些都将最终调用fib(47),即使价值是一样的.实际上,fib(47)将被计算三次:通过直接调用fib(49),直接调用fib(48),以及来自另一个的直接调用fib(48),通过计算产生的那个fib(49)......所以你看,我们有重叠的子问题.

好消息:没有必要多次计算相同的值.计算一次后,缓存结果,下次使用缓存值!这是动态编程的本质.您可以将其称为"自上而下","备忘录"或其他任何您想要的内容.这种方法非常直观且易于实现.首先编写一个递归解决方案,在小测试中测试它,添加memoization(缓存已计算的值),然后--- bingo!---你完成了.

通常,您也可以编写一个自下而上的等效迭代程序,而不进行递归.在这种情况下,这将是更自然的方法:从1到50循环计算所有斐波那契数字.

fib[0] = 0
fib[1] = 1
for i in range(48):
  fib[i+2] = fib[i] + fib[i+1]

在任何有趣的场景中,自下而上的解决方案通常更难以理解.但是,一旦你理解了它,通常你会对算法的运作方式有一个更清晰的大局.在实践中,在解决重要问题时,我建议首先编写自上而下的方法并在小例子上进行测试.然后编写自下而上的解决方案,并比较两者,以确保你得到相同的东西.理想情况下,自动比较两种解决方案.编写一个小程序,可以生成大量的测试,理想情况下 - 全部小到一定尺寸的测试---并验证两种解决方案都能给出相同的结果.之后在生产中使用自下而上的解决方案,但保留上下代码,注释掉.这将使其他开发人员更容易理解您正在做的事情:自下而上的代码可能非常难以理解,即使您编写它,即使您确切知道自己在做什么.

在许多应用程序中,由于递归调用的开销,自下而上的方法稍快一些.堆栈溢出在某些问题中也可能是一个问题,请注意,这很大程度上取决于输入数据.在某些情况下,如果您不能很好地理解动态编程,则可能无法编写导致堆栈溢出的测试,但有一天这可能仍会发生.

现在,存在这样的问题:自上而下的方法是唯一可行的解​​决方案,因为问题空间太大而无法解决所有子问题.然而,"缓存"仍然在合理的时间内工作,因为你的输入只需要解决一小部分子问题 - 但是明确定义你需要解决哪些子问题,从而编写一个底部,这太棘手了.解决方案.另一方面,有些情况下您知道需要解决所有子问题.在这种情况下,继续使用自下而上.

我个人会使用Top-bottom进行段落优化,也就是Word包装优化问题(查找Knuth-Plass断行算法;至少TeX使用它,Adobe Systems的一些软件使用类似的方法).我会使用自下而上的快速傅立叶变换.

Answer 4

让我们以斐波那契系列为例

1,1,2,3,5,8,13,21....

first number: 1
Second number: 1
Third Number: 2

另一种说法,

Bottom(first) number: 1
Top (Eighth) number on the given sequence: 21

在前五个斐波纳契数的情况下

Bottom(first) number :1
Top (fifth) number: 5 

现在让我们看一下递归Fibonacci系列算法作为例子

public int rcursive(int n) {
    if ((n == 1) || (n == 2)) {
        return 1;
    } else {
        return rcursive(n - 1) + rcursive(n - 2);
    }
}

现在,如果我们使用以下命令执行此程序

rcursive(5);

如果我们仔细研究算法,为了生成第五个数字,它需要第3个和第4个数字.所以我的递归实际上从顶部(5)开始,然后一直到底部/更低的数字.这种方法实际上是自上而下的方法.

为避免多次进行相同的计算,我们使用动态编程技术.我们存储先前计算的值并重用它.这种技术称为memoization.动态编程除了记忆之外还有更多内容,这是讨论当前问题所不需要的.

自顶向下

让我们重写我们的原始算法并添加memoized技术.

public int memoized(int n, int[] memo) {
    if (n <= 2) {
        return 1;
    } else if (memo[n] != -1) {
        return memo[n];
    } else {
        memo[n] = memoized(n - 1, memo) + memoized(n - 2, memo);
    }
    return memo[n];
}

我们执行此方法如下

   int n = 5;
    int[] memo = new int[n + 1];
    Arrays.fill(memo, -1);
    memoized(n, memo);

这个解决方案仍然自上而下,因为算法从最高值开始,并逐步到达每个步骤以获得我们的最高值.

自下而上

但是,问题是,我们可以从底部开始,就像从第一个斐波那契数字开始,然后走向我们的方向.让我们用这种技术重写它,

public int dp(int n) {
    int[] output = new int[n + 1];
    output[1] = 1;
    output[2] = 1;
    for (int i = 3; i <= n; i++) {
        output[i] = output[i - 1] + output[i - 2];
    }
    return output[n];
}

现在,如果我们研究这个算法,它实际上从较低的值开始,然后转到顶部.如果我需要第5个斐波纳契数,我实际上计算第1个,然后第二个然后第三个一直到第5个数.这种技术实际上称为自下而上的技术.

最后两个,算法全填充动态编程要求.但一个是自上而下的,另一个是自下而上的.两种算法具有相似的空间和时间复杂度.

Answer 5

动态规划通常被称为记忆化！

1.记忆是自上而下的技术（通过分解来解决给定的问题），动态规划是一种自下而上的技术（从琐碎的子问题开始，解决给定的问题）

2.DP 通过从基本情况开始找到解决方案并向上工作。DP 解决了所有的子问题，因为它是自下而上的

与 Memoization 不同，它只解决所需的子问题

1. DP 有可能将指数时间的蛮力解决方案转换为多项式时间算法。

2. DP 可能更有效，因为它是迭代的

相反，由于递归，记忆化必须支付（通常是显着的）开销。

更简单地说，Memoization 使用自顶向下的方法来解决问题，即从核心（主要）问题开始，然后将其分解为子问题并类似地解决这些子问题。在这种方法中，同一个子问题可能会出现多次并消耗更多的 CPU 周期，从而增加了时间复杂度。而在动态规划中，相同的子问题不会被多次解决，而是会使用先前的结果来优化解决方案。

Answer 6

动态规划问题可以使用自下而上或自上而下的方法来解决。

一般来说，自下而上的方法使用制表技术，而自上而下的方法使用递归（带记忆）技术。

但您也可以使用递归来采用自下而上和自上而下的方法，如下所示。

自下而上：从基本条件开始，递归地传递到目前为止计算出的值。一般来说，这些都是尾递归。

int n = 5;
fibBottomUp(1, 1, 2, n);

private int fibBottomUp(int i, int j, int count, int n) {
    if (count > n) return 1;
    if (count == n) return i + j;
    return fibBottomUp(j, i + j, count + 1, n);
}

自上而下：从最终条件开始，递归地得到其子问题的结果。

int n = 5;
fibTopDown(n);

private int fibTopDown(int n) {
    if (n <= 1) return 1;
    return fibTopDown(n - 1) + fibTopDown(n - 2);
}