动态规划是带有缓存的回溯算法吗？

Question

动态规划是带有缓存的回溯算法吗？

algorithmdynamic-programmingtheorybacktrackingmemoization

17

我一直对此感到困惑，也没有任何书籍明确说明。

回溯法是一种探索所有可能性的方法，直到我们发现某个可能性不能导致可行解，这时候我们就放弃它。

据我理解，动态规划的特点是具有重叠子问题。因此，可以将动态规划描述为带有缓存（用于先前探索过的路径）的回溯法吗？

谢谢

- Mohan

1

你所提到的，带缓存的回溯通常被称为“记忆化”。记忆化具有动态规划的大部分优点，但痛苦要少得多。DP和Memoization之间的关键区别在于DP使用最优递归顺序，这通常需要证明它是最优的。值得一提的是，动态规划是可以选择的编程“类型”中最俗气的名称。 - ldog

1

@ldog：记忆化是实现DP的一种方式，每种情况下都会生成最多相同数量的子问题需要解决（因为自底向上的DP，其中您循环遍历表单元格填充它们，可能会计算出您实际上不需要的子问题的解决方案）。如果您需要解决所有或大多数子问题，则通常自底向上会更快，因为您可以避免推送/弹出堆栈以进行递归和在记忆化解决方案中进行if（notAlreadyComputed）测试。 - j_random_hacker

2

@ldog：在“动态规划”中，“编程”一词是一个古老的术语，意思是“使用表格进行工作”，而不是与计算机有关的任何内容。同样的词源可以在短语“线性规划”中看到。 - Chris Okasaki

4

显然，“动态规划”这个名字听起来很俗气，因为算法的发明者为了躲避老板的监管而将自己从事数学研究的真实情况藏了起来。 - Bas Swinckels

@BasSwinckels 不错，这是一个很有趣的小知识:D确实这并不是一个非常合适的术语。 - Niklas B.

显示剩余2条评论

4个回答

6

不完全是。在回溯中，您沿着每条路径向下然后向上走。但是，动态规划是自底向上工作的，因此您只会得到向上返回部分而不是最初的向下部分。此外，动态规划的顺序更具广度优先性，而回溯通常是深度优先。

另一方面，备忘录（动态规划的近亲）很常常像使用缓存的回溯，就像您所描述的那样。

- Chris Okasaki

2

没错，记忆化是实现动态规划的一种方法（而且是很好的方法，因为表格会“自动魔法”地按正确顺序填充）。 - Niklas B.

2

据我理解，记忆化和“正确的”动态规划在复杂度和值的相对计算顺序方面是相同的；然而，记忆化虽然看似天真，但可能会跳过某些子问题的评估。 - Codor

1

@Codor：这取决于你对“相对顺序”是什么意思。它们在每个值被需要之前都会计算，但这仍然留下了各种有效的排序方式。记忆化将按照递归的就绪顺序进行，而动态规划通常不会这样做。 - Chris Okasaki

@Chris Okasaki：是的，我的评论有点不准确；我更多地是指像你所说的那样：“递归结束时的值首先得到求值”。如果状态空间具有多个维度，则在某些“较早的切片”中的值会在“较晚的切片”之前计算。 - Codor

4

是和不是。

动态规划基本上是一种实现递归公式的高效方式，而自顶向下的动态规划往往实际上是通过递归+缓存来完成的：

def f(x):
  if x is in cache:
    return cache[x]
  else:
    res <- .. do something with f(x-k)
    cahce[x] <- res
    return res

请注意，底部向上的DP实现方式完全不同 - 但仍然基本遵循递归方法的基本原则，每一步都在较小（已知）子问题上“计算”递归公式。

然而, 为了能够使用DP，您需要对问题具有某些特征，主要是：问题的最优解由其子问题的最优解组成。其中适用的一个例子是最短路径问题（从s到t经过u的最优路径必须由从s到u的最优路径组成）。

这在其他一些问题上不存在，如顶点覆盖或布尔可满足性问题，因此您不能用DP替换它的回溯解决方案。

- amit

它也适用于顶点覆盖和类似问题，但在那里我们通常有指数级别的不同子问题。 - Niklas B.

@NiklasB。无论如何都不是一条直接的道路，你可以创建一个满足所述特征的新问题 - 然后在其上应用DP，但最优VC不一定必须由最优子集构成。 - amit

1

不，你所谓的“带缓存的回溯”基本上就是记忆化。

在动态规划中，你是自底向上进行的。也就是说，你从一个不需要任何子问题的地方开始。特别地，当你需要计算第n步时，所有的n-1步已经被计算出来了。

而这对于记忆化来说并不是这样。在这里，你从第k步（你想要的步骤）开始，并在必要时解决前面的步骤。显然，你需要将这些值存储在某个地方，以便稍后访问。

尽管如此，无论是记忆化还是动态规划，在运行时间上并没有区别。

- HelloWorld123456789

4

备忘录算法实际上是一种实现动态规划的手段。 - Niklas B.

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Gassa · Accepted Answer

这是动态规划的一个方面，但还有更多内容。

举个简单的例子，以斐波那契数列为例：

F (n) =
        n = 0:  0
        n = 1:  1
        else:   F (n - 2) + F (n - 1)

我们可以将上面的代码称为“回溯”或“递归”。现在，让我们将其转化为“带缓存的回溯”或“带备忘录的递归”。

F (n) =
       n in Fcache:  Fcache[n]
       n = 0:  0, and cache it as Fcache[0]
       n = 1:  1, and cache it as Fcache[1]
       else:  F (n - 2) + F (n - 1), and cache it as Fcache[n]

但是，这还不够。

如果一个问题可以通过动态规划来解决，那么就有一个状态和它们之间的依赖关系的有向无环图。我们感兴趣的是一个状态。还有一些基础状态，我们已经知道了答案。

我们可以从我们感兴趣的顶点开始遍历该图，到达所有依赖项，然后依次到达它们的所有依赖项等等，在基础状态处停止进一步分支。这可以通过递归完成。

有向无环图可以被视为顶点上的偏序。我们可以对该图进行拓扑排序并按排序顺序访问顶点。此外，您可以找到一些简单的总序，与您的偏序一致。

还要注意，我们通常可以观察到状态上的某些结构。例如，状态通常可以表示为整数或整数元组。因此，我们可以预先分配一个常规数组，而不是使用通用缓存技术（例如，关联数组来存储状态-值对），这样更容易更快地使用。

回到我们的斐波那契示例，偏序关系只是状态n >= 2取决于状态n - 1和n - 2。基本状态是n = 0和n = 1。与此顺序关系一致的一个简单总序是自然顺序：0、1、2、...。以下是我们的起点：

Preallocate array F with indices 0 to n, inclusive
F[0] = 0
F[1] = 1

好的，我们已经确定了访问各个州的顺序。现在，“访问”是什么意思？有两种可能：

(1) “反向DP”：当我们访问一个状态u时，我们查看它所有的依赖项 v 并计算该状态u的答案:

for u = 2, 3, ..., n:
    F[u] = F[u - 1] + F[u - 2]

(2) “向前DP”：当我们访问一个状态u时，我们会查看所有依赖于它的状态v，并在每个这些状态v中考虑u：

for u = 1, 2, 3, ..., n - 1:
    add F[u] to F[u + 1]
    add F[u] to F[u + 2]

请注意，在前一种情况下，我们仍然直接使用斐波那契数列的公式。然而，在后一种情况中，命令式代码无法轻易地用数学公式表达出来。然而，在某些问题中，“正向DP”方法更为直观（目前没有好的例子；有人想提供吗？）。

动态规划的另一个难以用回溯法表达的用途是：Dijkstra算法也可以被视为DP。在算法中，我们通过添加顶点来构建最优路径树。当我们添加一个顶点时，我们使用了这样一个事实：除了路径中的最后一条边之外，整个路径已知是最优的。因此，我们实际上使用了子问题的最优解——这正是我们在DP中所做的事情。然而，我们添加顶点到树中的顺序事先是未知的。