动态规划中的最优子结构

Question

动态规划中的最优子结构

dynamic-programming

21

我一直在尝试理解动态规划，我的理解是DP有两个部分。

最优子结构
重叠子问题

我理解第二个部分，但是我不理解第一个部分。

- AKS

3个回答

10

另一个很好的例子是在图中找到每对顶点之间的最短简单路径和找到每对顶点之间的最长简单路径之间的差异。("简单"意味着路径上不能重复访问任何顶点; 如果我们不为问题的“最长”版本放入此约束条件，那么当图包含一个环时，我们可能会得到无限长的路径。)

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 的最长简单路径。

作为一般规则，我们总是可以通过选择使用足够详细的子问题定义来“解决”这个问题：在这种情况下，我们可以要求在给定集合S中仅使用顶点来寻找两个给定顶点u和v之间的最长路径，而不是询问它们之间的最长路径。以前，我们可以建立一个带有两个参数的函数shortest(u, v)，现在我们必须建立一个带有三个参数的函数longest(u, v, S)；然后可以使用longest(u, v, V)计算两个顶点u和v之间的整个最长路径，其中V是图的整个顶点集。通过这个新的定义，我们现在再次可以通过仅组合子问题的最优解来产生最优解，因为我们可以确保只尝试将来自其S集不相交的子问题的路径粘合在一起。我们现在可以通过计算最大值来正确地确定仅使用S中的顶点从u到v的最长路径，即longest(u, v, S)，其中x是S中的所有顶点，并且将S-{x}分成两个子集A和B的所有方法的最大值的和为longest(u, x, A) + longest(x, v, B)。

很不幸，现在需要解决的子问题呈指数级增长，因为n个顶点的集合可以被划分为2^(n-1)种不同的方式。(刚才描述的算法并不是该问题最有效的DP算法，但即使是已知的最有效的DP算法仍然具有这种指数级因素的运行时间。)设计DP算法的挑战始终是找到一种定义子问题的方法，使得产生足够少的不同子问题(理想情况下只有多项式个)，同时仍保持重叠子问题和最优子结构这两个属性。

- j_random_hacker

对于一个给定的问题，我应该如何找出是否存在最优子结构？是通过试错法，解决较小的n，然后找出答案，还是有一种具体的方法来找到它？ - AKS

如果你想使用特定的子问题定义来进行DP，那么你必须证明最优子结构是存在的。但在尝试数学证明之前，你可以尝试一些例子--也许有一些简单的反例可以表明它行不通。 - j_random_hacker

@j_random_hacker 你说“我们不能简单地将这两条路径粘在一起，以获得从u到v的最长简单路径。” 你能给我一个这种情况的图的例子吗？我实际上想不出来。我开始相信最长路径是最优子结构... - Ogen

2

@Ogen：首先，最重要的是，你（或者想要尝试使用多项式时间DP解决最长路径问题的人）需要证明这种不良情况不可能发生。无论如何，几乎任何足够大的图都会给出反例。这里有一个小例子：三角形图形上的顶点a、b和c。从a到c的最长简单路径是a-b-c；从c到b的最长简单路径是c-a-b，因此为了使DP工作，我们必须接受从a到b的最长简单路径是a-b-c-a-b——但是当然这条路径并不简单。 - j_random_hacker

@j_random_hacker 在你的第三段中，你提出了这个观点，所以实际上需要你来举证。此外，我认为那并不算数，因为图是循环的。我说的是一个非循环简单路径图。在这种情况下，最长路径问题确实具有最优子结构。请查看这个答案http://cs.stackexchange.com/questions/56756/what-is-the-intuition-on-why-the-longest-path-problem-does-not-have-optimal-subs - Ogen

显示剩余2条评论

1

在简单的话语中，"最优性原理指出，在解决优化问题时，必须解决子问题，子问题的解决方案将成为优化问题的一部分"，如果问题可以通过最优子问题解决，则它包含最优子结构。

例如：假设在一个图形中，源顶点是s，目标是d。我们必须找到最短路径(s,d)。

    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

注意：(s,e)或(s,f)没有直接的边。在考虑为此编写算法时，如果我们编写一个优先级队列结构，它将以最短的总路径长度遍历。我们将为每个顶点从源顶点分配路径长度。

如果新的路径长度小于现有的路径长度，我们将继续为相邻的顶点分配路径长度。

Example : Len(s,b) > Len(s,a)+Len(a,b);
               reset len(s,b)=2;

从S开始的相邻节点创建了一条路径，以获得最小的路径长度，无论目标节点如何，因为它们正在创建导致解决方案的子结构。

- dinesh kandpal

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

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

- amit · Accepted Answer

最优子结构意味着，对于规模为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' 的最优解组成。