algorithm - 动态规划是用缓存回溯吗

Question

我一直在想这个问题。没有任何书籍明确说明这一点。

回溯正在探索所有可能性，直到我们发现一种可能性无法引导我们找到可能的解决方案，在这种情况下我们将放弃它。

据我了解，动态编程的特点是子问题重叠。那么，动态规划是否可以表述为带缓存的回溯(针对之前探索过的路径)？

谢谢

Answer 1

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

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

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) “Backward DP”:当我们访问状态 u 时，我们查看它的所有依赖项 v 并计算该状态 u 的答案:

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

(2) “Forward DP”:当我们访问状态 u 时，我们会查看所有依赖于它的状态 v 并说明 u 在每个状态 v:

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 中所做的事情。尽管如此，我们向树中添加顶点的顺序是事先不知道的。