动态编程和贪婪方法有什么区别？ [英] What is the difference between dynamic programming and greedy approach?

问题描述

动态编程和贪婪方法在使用方面的主要区别是什么？

据我了解，贪婪方法有时会提供最佳解决方案;在其他情况下，动态编程方法提供了一个最佳解决方案。

是否有任何特定条件必须满足才能使用一种方法（或其他方法）来获得最佳解决方案？

解决方案

基于维基百科的文章。

贪婪方法

贪婪算法是一种算法，它遵循问题求解的启发式，使
成为每个阶段的局部最优选择[1]，希望找到全局最优。在
许多问题中，贪婪策略通常不会产生最佳解决方案，但
却是一种贪婪的启发式方法，可能会产生局部最优解，在合理的时间内逼近
全局最优解。 / p>

我们现在可以做出最好的选择，然后解决稍后出现的子问题。由贪婪算法做出的选择可能取决于迄今为止的选择，但不取决于未来的选择或子问题的所有解决方案 。它迭代地做出一个接一个的贪婪选择，将每个给定的问题缩小为一个小问题。

动态编程

动态编程背后的想法很简单。一般来说，为了解决一个给定的问题，我们需要解决问题的不同部分（子问题）， 然后结合子问题的解决方案来达到整体解决方案 。通常当使用更天真的方法时，许多子问题都会生成并解决许多次。动态规划方法旨在解决每个子问题只有一次 ，从而减少了计算次数：一旦计算出给定子问题的解决方案，就将其存储或备忘录化：下次需要相同的解决方案时，只需查看它。当重复子问题的数量随着输入大小的函数呈指数增长时，这种方法尤其有用。

差异

贪婪的选择属性

我们现在可以做出最好的选择，然后解决稍后出现的子问题。贪婪算法做出的选择可能取决于迄今为止做出的选择，但不取决于未来的选择或子问题的所有解决方案。它迭代地做出一个接一个的贪婪选择，将每个给定的问题缩小为一个较小的问题。换句话说，贪婪算法从不会重新考虑它的选择。

这是与动态编程的主要区别，它是详尽无遗的，并且可以保证找到解决方案。在每个阶段之后，动态规划会根据前一阶段做出的所有决策作出决策，并且可能会重新考虑前一阶段的解决方案的算法路径。例如，让我们假设您必须在高峰时段在特定城市尽可能快地从A点到B点。动态规划算法会查看整个交通报告，研究所有可能的道路组合，然后才会告诉您哪条路最快。当然，您可能需要等待一段时间，直到算法结束，然后才能开始驾驶。你将采取的路径是最快的（假设外部环境没有任何变化）。另一方面，一个贪婪算法会立即开始你的驾驶，并会选择在每个路口看起来最快的路段。正如你可以想象的，这种策略可能不会导致最快的到达时间，因为你可能会采取一些简单的街道，然后发现自己陷入了绝望的交通堵塞。

其他细节...

在数学优化中，贪婪算法解决了具有主题。

动态规划 适用于展示 >重叠子问题和最佳子结构的属性。

What is the main difference between dynamic programming and greedy approach in terms of usage?

As far as I understood, the greedy approach sometimes gives an optimal solution; in other cases, the dynamic programming approach gives an optimal solution.

Are there any particular conditions which must be met in order to use one approach (or the other) to obtain an optimal solution?

解决方案

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屋！