有人可以在动态编程中解释最佳子结构吗？

Question

我一直在努力理解动态编程,我理解的是DP有两个部分. 1.最优子结构2.重叠子问题

我理解第二个,但也无法获得第一个.

有人可以用简单的英语解释一下易于理解的例子吗？

Answer 1

最优子结构意味着对尺寸问题的任何最优解决方案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),并且不考虑最优解.

这不存在的一个例子是Vertex Cover问题.

如果你有一个图形G =(V,E),假定有一个子图的最佳解决方案G'=(V',E[intersection]V'xV'),使得V' <= V-为对最优解G不具有最优解的要被包括了G'/

Answer 2

另一个很好的例子是，在图中的每对顶点之间找到一条最短的简单路径，与在这两个对之间找到一条最长的简单路径之间的区别。（“简单”表示路径上的任何顶点都不能被访问两次；如果不对问题的“最长”版本施加此约束，那么只要图形包含一个循环，我们就可以获得无限长的路径。）

在弗洛伊德- 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的简单路径。

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

不幸的是，由于存在一组n个顶点可以以2 ^（n-1）种不同的方式进行划分，因此现在有指数级的子问题需要解决。（刚刚描述的算法并不是解决该问题的最有效DP，但是即使是最有效的已知DP，其运行时间仍然具有此指数因子。）设计DP算法的挑战始终是寻找一种定义子问题的方法。这样就导致了足够少的不同子问题（理想情况下，仅是多项式的许多子问题），同时仍然保持了子问题重叠和最优子结构的两个属性。