动态规划与贪婪方法的区别？ [英] Difference between dynamic programming and greedy approach?
问题描述
我观察到在某些问题中，贪心的方法给出了最佳解决方案，在其他时间动态编程方法提供最优解。是否有特殊的条件（规则）用于跟踪特定的方法？
我遇到这么多例子，但无法作出一个标准的结论。
根据维基百科的文章。
贪婪的方法
贪心算法是一个算法，遵循解决问题的启发式，使
成为每个阶段的局部最优选择[1]，希望找到全局最优。在
的许多问题中，贪心的策略通常不会产生最佳解决方案，但是
尽管如此，一个贪婪的启发式可以产生在合理的时间内近似一个
全局最优解的本地最优解。 / p>
我们现在可以做出最好的选择，然后解决稍后出现的子问题。通过贪心算法进行的选择可能取决于迄今为止所做的选择，但不取决于未来选择或子问题的所有解决方案 。
动态编程
动态规划背后的想法很简单。一般来说，为了解决给定的问题，我们需要解决问题的不同部分（子问题）， 然后将子问题的解决方案结合起来，以达到整体解决方案 。通常，当使用更幼稚的方法时，许多子问题被生成和解决了很多次。动态规划方法寻求解决每个子问题只有一次 ，从而减少计算次数：一旦计算了给定子问题的解决方案，它被存储或备忘录化：下次需要同样的解决方案时，只需查询即可。当重复子问题的数量随着输入的大小而呈指数增长时，这种方法特别有用。
差异
贪婪选择属性
我们现在可以做出最好的选择，然后解决稍后出现的子问题。贪心算法的选择可能取决于迄今所做的选择，但不取决于未来的选择或子问题的所有解决方案。它反复地使一个贪婪的选择之一，减少每个给定的问题成一个较小的。换句话说，贪心算法从不重新考虑其选择。
这是动态编程的主要区别，它是详尽无遗的，有保证找到解决方案。在每个阶段之后，动态规划都会根据前一阶段的所有决策进行决策，并且可以重新考虑前一阶段的解决方案路径。
例如，假设在高峰时段，您必须尽快从A点到B点。动态规划算法将研究整个流量报告，查看可能采取的道路的所有可能组合，然后只会告诉您哪种方式是最快的。当然，您可能需要等待一段时间，直到算法完成，然后才能开始驾驶。您将采取的路径将是最快的路径（假设外部环境没有改变）。
另一方面，贪婪的算法将开始您立即开车，并选择在每个十字路口看起来最快的道路。你可以想象，这个策略可能不会导致最快的到达时间，因为你可能会采取一些容易的街道，然后发现自己绝望地堵住了交通堵塞。
其他细节...
在数学优化中，贪心算法解决具有matroids 。
动态编程适用于展示的问题>重叠子问题和最佳子结构的属性。
What is the main difference between dynamic programming and greedy approach in terms of usage?
I observed that in some problems greedy approach gives optimal solution, in some other time dynamic programming approach gives optimal solution. Are there any particular conditions(rules) for following particular approach?
I came across so many examples but unable to make a standard conclusion.
Based on Wikipedia's articles.
Greedy Approach
A greedy algorithm is an algorithm that follows the problem solving heuristic of making the locally optimal choice at each stage[1] with the hope of finding a global optimum. In many problems, a greedy strategy does not in general produce an optimal solution, but nonetheless a greedy heuristic may yield locally optimal solutions that approximate a global optimal solution in a reasonable time.
We can make whatever choice seems best at the moment and then solve the subproblems that arise later. The choice made by a greedy algorithm may depend on choices made so far but not on future choices or all the solutions to the subproblem. It iteratively makes one greedy choice after another, reducing each given problem into a smaller one.
Dynamic programming
The idea behind dynamic programming is quite simple. In general, to solve a given problem, we need to solve different parts of the problem (subproblems), then combine the solutions of the subproblems to reach an overall solution. Often when using a more naive method, many of the subproblems are generated and solved many times. The dynamic programming approach seeks to solve each subproblem only once, thus reducing the number of computations: once the solution to a given subproblem has been computed, it is stored or "memo-ized": the next time the same solution is needed, it is simply looked up. This approach is especially useful when the number of repeating subproblems grows exponentially as a function of the size of the input.
Difference
Greedy choice property
We can make whatever choice seems best at the moment and then solve the subproblems that arise later. The choice made by a greedy algorithm may depend on choices made so far but not on future choices or all the solutions to the subproblem. It iteratively makes one greedy choice after another, reducing each given problem into a smaller one. In other words, a greedy algorithm never reconsiders its choices.
This is the main difference from dynamic programming, which is exhaustive and is guaranteed to find the solution. After every stage, dynamic programming makes decisions based on all the decisions made in the previous stage, and may reconsider the previous stage's algorithmic path to solution
For example, let's say that you have to get from point A to point B as fast as possible, in a given city, during rush hour. A dynamic programming algorithm will look into the entire traffic report, looking into all possible combinations of roads you might take, and will only then tell you which way is the fastest. Of course, you might have to wait for a while until the algorithm finishes, and only then can you start driving. The path you will take will be the fastest one (assuming that nothing changed in the external environment).
On the other hand, a greedy algorithm will start you driving immediately and will pick the road that looks the fastest at every intersection. As you can imagine, this strategy might not lead to the fastest arrival time, since you might take some "easy" streets and then find yourself hopelessly stuck in a traffic jam.
Some other details...
In mathematical optimization, greedy algorithms solve combinatorial problems having the properties of matroids.
Dynamic programming is applicable to problems exhibiting the properties of overlapping subproblems and optimal substructure.
这篇关于动态规划与贪婪方法的区别？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
