Greedy Analysis Strategies

本文主要是介绍Greedy Analysis Strategies，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Greedy Analysis Strategies

• Greedy algorithm stays ahead.
  Show that after each step of the greedy algorithm, its solution is at least as good as other algorithm’s.
  Ex.Interval scheduling

• Structural.
  Discover a simple “structural” bound asserting that every possible solution must have a certain value. Then show that your algorithm always achieves this bound.
  Ex.Interval partitioning

• Exchange argument
  Gradually transform any solution to the one found by the greedy algorithm without hurting its quality.
  Ex.Minimizing lateness

Remark.
Greedy algorithm do not always give an optimal solution but can produce a solution that is guaranteed to be close to optimal.

Basic Elements of Greedy Algorithm

Usually, if the given problem has the following ingredients(hallmark in other teaching material, Steve add this note), then it is more likely to develop a greedy algorithm for it.

• Greedy-choice property.
  A locally optimal choice is globally optimal。

We can assemble a globally optimal solution by making locally optimal(greedy) choices. That is, when we make the choice that looks best in the current problem, without considering results from subproblems.

• Optimal substructure.
  A problem exhibits optimal substructure if an optimal solution to the problem contain within it optimal solutions to subproblems.

注意，这里的最优子结构和动态规划的hallmark 1是一样的。事实上，贪心法解决不了的问题，可以尝试使用动态规划来解决。

0-1背包问题，有最优子结构，但使用贪心法无法解决，需要使用动态规划。

这篇关于Greedy Analysis Strategies的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---