算法的乐趣之贪婪法
贪婪法(Greedy Algorithm),又称贪心算法,是寻找最优解问题的常用方法,这种方法模式一般将求解过程分成若干个步骤,但每个步骤都应用贪心原则,选取当前状态下最好的或最优的选择(局部最有利的选择),并以此希望最后堆叠出的结果也是最好或最优的解。因为不进行回溯处理,贪婪法只在很少的情况下可以得到真正的最优解,比如最短路径问题、图的最小生成树问题。在大多数情况下,由于选择策略的“短视”,贪婪法会错过真正的最优解,而得不到问题的真正答案。但是贪婪法简单、高效,省去了为找最优解可能需要的穷举操作,可以得到与最优解比较接近的近似最优解,通常作为其他算法的辅助算法来使用。