如何从贪心算法动态规划有什么不同？ [英] How is dynamic programming different from greedy algorithms?

问题描述

在这本书中，我使用介绍设计放大器;算法分析，动态规划的是说把重点放在最优的原则，坚持以最优化问题的任何实例的最优解由最优解它的子实例。

In the book I am using Introduction to the Design & Analysis of Algorithms, dynamic programming is said to focus on the Principle of Optimality, "An optimal solution to any instance of an optimization problem is composed of optimal solutions to its subinstances".

然而，在贪婪的技术的侧重于扩大部分构建的解决方案，直到你在一个完整的问题的一个解决办法。它接着说，它必须是一切可行的选择中最好的地方可以选择上一步。

Whereas, the greedy technique focuses on expanding partially constructed solutions until you arrive at a solution for a complete problem. It is then said, it must be "the best local choice among all feasible choices available on that step".

由于都涉及本地最优，是不是一个接一个的子集？

Since both involve local optimality, isn't one a subset of the other?

推荐答案

动态规划适用于表现出的性能问题：

Dynamic programming is applicable to problems exhibiting the properties of:

• 在重叠的子问题，和
• 最优子。

最优子意味着，你可以贪婪地解决子问题，并结合解决方案来解决更大的问题。 动态规划和贪心算法之间的区别是，动态规划，子问题重叠。这意味着，由memoizing的解决方案，一些子问题，您可以更快地解决其他子问题。

Optimal substructure means that you can greedily solve subproblems and combine the solutions to solve the larger problem. The difference between dynamic programming and greedy algorithms is that with dynamic programming, the subproblems overlap. That means that by "memoizing" solutions to some subproblems, you can solve other subproblems more quickly.

这个答案已经得到了一定的关注，所以我会举一些例子。

This answer has gotten some attention, so I'll give some examples.

考虑问题让改变与美元，镍，和便士。这是一个贪婪的问题。它具有最优子，因为你可以解决的美元数量。然后，解出镍的数量。然后便士的数目。然后，您可以有效地结合起来，解决这些子问题。它并没有真正表现出重叠的子问题，因为解决每个子并没有多大帮助的人（​​也许一点点）。

Consider the problem "Making change with dollars, nickels, and pennies." This is a greedy problem. It exhibits optimal substructure because you can solve for the number of dollars. Then, solve for the number of nickels. Then the number of pennies. You can then combine the solutions to these subproblems efficiently. It does not really exhibit overlapping subproblems since solving each subproblem doesn't help much with the others (maybe a little bit).

考虑问题Fibonnaci数字。它显示出最优子，因为可以从F（9）和F解决F（10）（8）有效（通过加入）。这些子问题重叠，因为它们都共享F（7）。如果你memoize的f的结果（7）当你解决F（8），就可以解决F（9）更快。

Consider the problem "Fibonnaci numbers." It exhibits optimal substructure because you can solve F(10) from F(9) and F(8) efficiently (by addition). These subproblems overlap because they both share F(7). If you memoize the result of F(7) when you're solving F(8), you can solve F(9) more quickly.

在回答有关动态规划不得不与重新考虑决定评论：这显然是任何线性动态规划算法类似的最大子阵列问题以上斐波那契问题。

In response to the comment about dynamic programming having to do with "reconsidering decisions": This is obviously not true for any linear dynamic programming algorithm like the maximum subarray problem or the Fibonacci problem above.

实质上，想象具有最优子作为一个有向非循环图，其节点重新present子问题（其中整个问题是重新由一个节点，其入度是零psented $ P $）的一个问题，并且其重$向边p $的子之间psent依赖关系。然后，一个贪婪的问题是一棵树（除了根所有节点都具有单位入度）。动态规划问题与入度大于一的一些节点。这说明了重叠的子问题。

Essentially, imagine a problem having optimal substructure as a directed acyclic graph whose nodes represent subproblems (wherein the whole problem is represented by a node whose indegree is zero), and whose directed edges represent dependencies between subproblems. Then, a greedy problem is a tree (all nodes except the root have unit indegree). A dynamic programming problem has some nodes with indegree greater than one. This illustrates the overlapping subproblems.

这篇关于如何从贪心算法动态规划有什么不同？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！