贪心算法又称贪婪算法,是所有算法中最简单、最易实现的一种算法。
一个问题通常对应有多种算法,每种算法由多个步骤组成。贪心算法解决问题的核心思想是:算法的每一步都选择当前场景中最优的解决方案(又称局部最优解)。
举个例子,假设我们有面值分别为 1、2、5、10 的硬币,要求用尽可能少的硬币拼凑出的总面值为 18。如果采用贪心算法解决此问题,则解决方案为:
选择一个面值为 10 的硬币,可最大程度解决问题,剩余需要拼凑的面值数为 8;
选择一个面值为 5 的硬币,可最大程度解决问题,剩余需要拼凑的面值数为 3;
选择一个面值为 2 的硬币,可最大程度解决问题,剩余需要拼凑的面值数为 1;
选择一个面值为 1 的硬币。
贪心算法每一步都选择的是当前所允许的最大面值的硬币(即局部最优解),整个解决方案也是最优的。
注意,贪心算法并不是在任何场景中都可以得出最优的解决方案。比如,有面值分别为 1、7、10 的硬币,要求用尽可能少的硬币拼凑出的总面值为 15。如果采用贪心算法,则解决方案为:
选择一个面值为 10 的硬币,剩余面值为 5;
选择一个面值为 1 的硬币,剩余面值为 4;
选择一个面值为 1 的硬币,剩余面值为 3;
选择一个面值为 1 的硬币,剩余面值为 2;
选择一个面值为 1 的硬币,剩余面值为 1;
选择一个面值为 1 的硬币。
贪心算法使用了“10+1+1+1+1+1”共 6 枚硬币,但实际上,最优的解决方案只需要“7+7+1”共 3 枚硬币。所以,贪心算法追求的是局部最优解,它并不关心设计的整个解决方案是否最优。
贪心算法的实际应用
贪心算法可用于解决很多实际问题,例如:
部分背包问题;
使用克鲁斯卡尔算法求最小生成树;
使用迪杰斯特拉算法求两个顶点之间的最短路径。
我们会在后续的文章中,一一为您讲解这些问题。