我一直在尝试理解动态规划,我的理解是DP有两个部分。
- 最优子结构
- 重叠子问题
我理解第二个部分,但是我不理解第一个部分。
最优子结构意味着,对于规模为n
的问题,任何最优解都基于同样问题规模下n' < n
的最优解。
这意味着,在解决大小为n
的问题时,将问题分解成较小的问题之一,其规模为n'
。现在,您只需要考虑基于最优子结构属性的n'
的最优解,而不是所有可能的解。
一个例子是背包问题:
D(i,k) = min { D(i-1,k), D(i-1,k-weight(i)) + cost(i) }
这里的最优子结构假设是,D(i,k)
只能检查 D(i-1,k)
的最优解,而非最优解不予考虑。
一个不满足此条件的例子是 点覆盖问题。
如果你有一个图 G=(V,E),假设你已经有了一个子图 G'=(V',E[intersection]V'xV')
的最优解,使得 V' <= V
- 对于 G
的最优解不必由 G'
的最优解组成。
Floyd-Warshall算法可以高效地计算第一个问题的答案,因为它利用了这样一个事实:如果从u到v的路径是最短的,那么对于该路径上的任何顶点x,从u到x的子路径和从x到v的子路径也必须是最短的。 (假设相反,存在一条从u到v的“最短可能”路径上的顶点x,使得从u到x的子路径不是最短的:那么可以找到一些其他更短的从u到x的路径-并且这也可以用来使从u到v的整个路径缩短相同的量,因此原始的从u到v的路径不能是最短的。)这意味着在寻找最短的从u到v的路径时,算法只需要考虑由其他顶点对之间的最短可能(即最优)子路径构建而成的路径-而不是由所有这样的子路径构建而成的路径。
相比之下,考虑在图中确定任意两个顶点之间的最长简单路径的问题。如果从 u 到 v 的最长路径经过某个顶点 x,那么从 u 到 x 和从 x 到 v 的子路径是否也必须是最长的呢?不幸的是,答案是否定的:可能会出现从 u 到 x 的最长路径使用了其内部一些点,在从 x 到 v 的最长路径中同样需要这些点,这意味着我们不能简单地将这两条路径拼接在一起以得到从 u 到 v 的最长简单路径。 graph is
a g
b e h d
s c f i
d
length(s,a)=14
length(s,b)=10
length(s,c)=1
length(s,d)=6
length(c,b)=1
Example : Len(s,b) > Len(s,a)+Len(a,b);
reset len(s,b)=2;