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

问题描述

动态编程和贪婪方法在用法上的主要区别是什么?

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?

推荐答案

基于维基百科的文章.

贪心算法是一种遵循问题解决启发式的算法每个阶段的局部最优选择，希望找到一个全局最优.在在许多问题中，贪婪策略通常不会产生最优解，但贪婪启发式可能会在合理的时间内产生近似全局最优解的局部最优解.

A greedy algorithm is an algorithm that follows the problem solving heuristic of making the locally optimal choice at each stage 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.

动态规划背后的想法非常简单.一般来说，要解决一个给定的问题，我们需要解决问题的不同部分(子问题)，然后将子问题的解决方案组合起来，得出一个整体解决方案.通常当使用更简单的方法时，许多子问题会被多次生成和解决.动态规划方法寻求对每个子问题只求解一次，从而减少计算次数:一旦计算出给定子问题的解，就将其存储或执行".memo-ized":下次需要相同的解决方案时，只需查找即可.当重复子问题的数量作为输入大小的函数呈指数增长时，这种方法特别有用.

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.

我们可以做出目前看来最好的选择，然后解决以后出现的子问题.贪心算法做出的选择可能取决于目前所做的选择，但不取决于未来的选择或子问题的所有解决方案.它迭代地做出一个又一个贪婪的选择，将每个给定的问题缩减为一个更小的问题.换句话说，贪婪算法从不重新考虑它的选择.

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.

例如，假设您必须在特定城市的高峰时段尽快从 A 点到达 B 点.动态编程算法将查看整个交通报告，查看您可能采取的所有可能的道路组合，然后才会告诉您哪种方式最快.当然，您可能需要等待一段时间，直到算法完成，然后才能开始驾驶.您将采用的路径将是最快的(假设外部环境没有发生任何变化).

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.

在数学优化中，贪心算法解决具有拟阵.

In mathematical optimization, greedy algorithms solve combinatorial problems having the properties of matroids.

动态规划适用于具有重叠子问题和最优子结构性质的问题.

这篇关于动态规划和贪婪方法有什么区别?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！