动态VS贪婪算法：对于在同一主题的尼尔·G的答案的争论 [英] Dynamic vs Greedy Algorithms : The debate regarding Neil G's answer on the same topic

问题描述

我是想了解动态和贪心算法之间的差异，并通过答案尼尔摹是相当有帮助，但是，有这个说法，他让这引起了评论部分的讨论。

I was trying to understand the differences between Dynamic and Greedy algorithms, and This answer by Neil G was quite helpful, but, there was this one statement that he made which caused a debate in the comments section.

动态规划和贪婪算法之间的差异在于，使用动态编程，子问题重叠。这意味着，由memoizing的解决方案，一些子问题，您可以更快地解决其他子问题。

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.

注释不是解决无疑是最好的地方，所以我创建这个职位。我的问题是：

Comments aren't the best place to solve a doubt, so i'm creating this post. My questions are :

最小生成树有最优子以及重叠的子问题。此外，在一个MST，一个局部最优选择是全局最优。因此，动态和贪婪性持有吗？如何在上面引述的部分撑起来的？

Minimum spanning trees have Optimal substructure as well as Overlapping Sub-problems. Also, in an MST, a locally optimal choice is globally optimal. Thus both Dynamic and Greedy properties hold right? How does the above quoted part hold up to this?

如何是最优子结构的不同的财产，该财产局部最优随后还全局最优？我的头是怎么回事：？？如果事情有一个最优子结构，那么所有的局部最优选择，也必须是全局最优权的谁能解释一下，我要去哪里错了这里。

How is the property of optimal substructure different to the property "locally optimal then also globally optimal" ? My head is going : If something has an optimal substructure, then all locally optimal choices must also be globally optimal right ? Can someone explain where i'm going wrong here ?

英语不是我的母语，所以请随时纠正的语言任何错误。

English is not my native language, so please feel free to correct any mistakes with the language.

推荐答案

我觉得一个贪婪的和动态的解决方案之间的差异的解释是不好的。贪婪的解决方案使得选择只使用IE看起来最好的，因为当前位置的本地信息。其结果是贪婪的解决方案可能会卡住在局部最优，而不是全球性的。动态编程是在你打破一个更复杂的问题简单的子问题，然后从子问题相结合的结果，获得的结果对初始问题的技术。一个解决方案可以是两个贪婪和动态。看看我的回答原来的主题。

I think the explanation of the difference between a greedy and dynamic solutions is not good. A greedy solution makes choices only using local information i.e. what looks best as of the current position. As a result greedy solutions may "get stuck" at a local optimum instead of the global one. Dynamic programming is a technique in which you break a single more complex problem to simpler subproblems and then you combine the results from the subproblems to obtain the result for the initial problem. A solution can be both greedy and dynamic. Take a look at my answer to the original thread.

的你然而这样的说法：

If something has an optimal substructure, then all locally optimal
choices must also be globally optimal right?

是错误的。就拿0,1背包例如：你是一个小偷，闯入一些商店一晚。你有一个背包，它有一个固定的承重能力。店内有每个部分产品相关的价格和重量。偷最大的价格。

Is wrong. Take for example the 0,1 knapsack example: you are a thief, breaking into some shop a night. You have a knapsack and it has a fixed weight capacity. The shop has some products each with associated price and weight. Steal the greatest price possible.

现在考虑其中有容量50和价格和重量分别产品（21，20）的背包的例子中，（30，22），（22，21），和（9,9）。如果你所做的选择都是局部最优（即你选择了一个最伟大的价格/质量比的项目，每次），你会选择的产品（30，22）和（21，20），而这个解决方案不是最优的。最佳的解决办法是采取（21，20），（22，21）和（9,9-），导致利润是更大的由2

Now take the example where you have knapsack of capacity 50 and products of price and weight respectively (21, 20), (30, 22), (22, 21), and (9, 9). If you make choices that are locally optimal(i.e. each time you select the item with greatest price/weight ratio) you will select the products (30, 22) and (21, 20) while this solution is not optimal. The optimal solution would be to take (21, 20), (22, 21) and (9,9) resulting in profit that is bigger by 2.

这篇关于动态VS贪婪算法：对于在同一主题的尼尔·G的答案的争论的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！