动态编程与贪婪算法有何不同？

Question

在我使用的算法设计和分析导论中,动态编程据说着重于优化原理,"优化问题的任何实例的最优解决方案都由其子实例的最优解决方案组成".

然而,贪婪技术专注于扩展部分构建的解决方案,直到您找到完整问题的解决方案.然后说,它必须是"在该步骤中所有可行选择中最好的本地选择".

既然两者都涉及局部最优性,那么它不是另一个的子集吗？

Answer 1

动态编程适用于具有以下特性的问题:

• 重叠的子问题,和
• 最佳子结构.

最优子结构意味着您可以贪婪地解决子问题并结合解决方案来解决更大的问题. 动态编程和贪婪算法之间的区别在于,动态编程存在重叠的子问题,并且这些子问题是使用memoization解决的."Memoization"是一种技术,通过该技术,子问题的解决方案可以更快地解决其他子问题.

这个答案得到了一些关注,所以我举一些例子.

考虑一下"用美元,镍币和便士做出改变"的问题.这是一个贪婪的问题.它展示了最佳的子结构,因为您可以解决美元的数量.然后,求解镍的数量.然后是便士的数量.然后,您可以有效地将解决方案组合到这些子问题中.它并没有真正表现出重叠的子问题,因为解决每个子问题对其他子问题没有多大帮助(可能有点).

考虑问题"Fibonnaci数字".它表现出最佳的子结构,因为你可以有效地(通过加法)从F(9)和F(8)求解F(10).这些子问题重叠,因为它们都共享F(7).如果在解决F(8)时记忆F(7)的结果,可以更快地求解F(9).

响应关于动态编程的评论与"重新考虑决策"有关:对于任何线性动态编程算法,如上面的最大子阵列问题或Fibonacci问题,这显然是不正确的.

本质上,将具有最优子结构的问题想象为有向无环图,其节点表示子问题(其中整个问题由其indegree为零的节点表示),并且其有向边表示子问题之间的依赖性.然后,一个贪婪的问题是一个树(除了root之外的所有节点都有单位indegree).动态编程问题有一些节点的indegree大于1.这说明了重叠的子问题.

Answer 2

不同之处在于,动态编程要求您记住较小状态的答案,而贪心算法是本地的,因为所需的所有信息都处于当前状态.当然,还有一些交集.

Answer 3

关键的区别在于,贪婪算法"静态地"构成解决方案,即解决方案中的每个本地选择都可以最终确定,而无需了解其他本地选择.然而,动态算法为子问题创建了一组可能的解决方案,并且只在考虑了所有子问题时才生成针对全局问题的单一解决方案.关于贪婪算法的维基百科页面说得很好:

贪婪算法做出的选择可能取决于目前为止做出的选择,而不取决于未来的选择或子问题的所有解决方案.它迭代地使一个接一个的贪婪选择,将每个给定的问题减少为一个较小的问题.换句话说,贪婪算法从不重新考虑其选择.这是与动态编程的主要区别,动态编程是详尽的,并保证找到解决方案.在每个阶段之后,动态编程基于前一阶段做出的所有决策做出决策,并可能重新考虑前一阶段的解决方案算法路径.

Answer 4

DP算法使用这样的事实(对于某些问题) - 对大小问题n的最佳解决方案由对大小问题的最优解决方案组成n'<n,并使用它来自下而上构建解决方案,从最小的问题到所需的尺寸.

它非常适合递归的原理(将问题减少到一个较小的子问题,并递归调用),实际上 - DP解决方案通常表示为递归公式.

贪婪算法正在查看本地点,并在此时对数据做出一些选择.对于一些问题(例如,没有负权重的最短路径) - 这种本地选择将导致最佳解决方案.

两种方法之间差异的一个很好的例子是最短路径问题:

• Dijsktra的算法是一种贪婪的方法(在每一步,选择当前最小化它的路径的节点 - 根据算法的本地状态贪婪地进行选择).
• Bellman-Ford算法是DP解决方案("放松"所有边缘有效地减少了问题)