动态规划:为什么需要最优的子结构

Question

我正在重新审视我的笔记Dynamic Programming.它基本上是一种记忆递归技术,它将解决方案存储到较小的子问题中,以便以后在相对较大的子问题的计算解决方案中重用.

我的问题是,为了将DP应用于递归问题,它必须具有最佳子结构.这基本上需要对问题的最佳解决方案包含对子问题的最佳解决方案.

否则可能吗？我的意思是你见过一个问题的最佳解决方案不包含子问题的最佳解决方案的情况.

如果您想加深我的理解,请分享一些例子.

Answer 1

在动态规划中, 如果通过使用其子问题的最优解可以获得给定问题的最优解,则给定问题具有最优子结构属性.

例如,最短路径问题具有以下最优子结构属性:如果节点X位于从源节点U到目的节点V的最短路径中,则从U到V的最短路径是从U到X的最短路径和最短路径的组合.从X到V.

但是最长路径问题没有最优子结构属性. 即,两个节点之间的最长路径不必是节点之间的最长路径.

例如,最长路径q-> r-> t不是从q到r的最长路径和从r到t的最长路径的组合,因为从q到r的最长路径是q-> s-> t->河

所以这里:问题的最佳解决方案不包含子问题的最优解决方案.

有关详细信息,请阅读

1. 来自维基百科的最长路径问题
2. 来自维基百科的最佳子结构

Answer 2

据我所知,这种"最佳子结构"属性不仅对于动态规划是必要的,而且首先要获得解决方案的递归公式.请注意,除了关于动态编程的维基百科文章之外,还有一篇关于最佳子结构属性的文章.为了使事情更加复杂,还有一篇关于贝尔曼方程的文章.

Answer 3

你的定义是不精确的,这是完全正确的.DP是一种获取算法加速的技术,而不是算法本身.术语"最佳子结构"是一个模糊的概念.(你又来了!)也就是说,每个循环都可以表示为一个递归函数:每次迭代都会解决连续函数的子问题.每个算法都有一个DP循环吗？显然不是.

人们通过"最优子结构"和"重叠子问题"实际意味着子问题结果经常被用来降低解决方案的渐近复杂性.换句话说,记忆是有用的!在大多数情况下,微妙的暗示是从指数到多项式时间的减少,O(n ^ k)到O(n ^ p),p <k或类似.

例如:密集图中的两个节点之间存在指数路径.DP找到最短路径只查看它们的多项式数,因为备忘录在这种情况下非常有用.

另一方面,旅行推销员可以表示为记忆功能(例如,参见此讨论),其中备忘录导致保存O((1/2)^ n)因子的时间.但是,通过n个城市的TS路径的数量是O(n!).这是如此之大,以至于渐近运行时间仍然是超指数的:O(n!)/ O(2 ^ n)= O(n!).这种算法通常不称为动态程序,即使它遵循与最短路径的DP非常相同的模式.显然它只是一个DP,如果它给出了一个很好的结果!