大家好，又见面了，我是全栈君，祝每个程序员都可以多学几门语言。
贪心算法的设计思想
贪心算法在解决这个问题的策略上目光短浅，仅仅依据当前已有的信息就做出选择，并且一旦做出了选择，无论将来有什么结果，这个选择都不会改变。换言之，贪心法并非从总体最优考虑，它所做出的选择仅仅是在某种意义上的局部最优。贪心算法对于大部分的优化问题都能产生最优解，但不能总获得总体最优解，通常能够获得近似最优解。
引例 [找零钱]
一个小孩买了价值少于1美元的糖，并将1美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。如果提供了数目不限的面值为2 5美分、1 0美分、5美分、及1美分的硬币。售货员分步骤组成要找的零钱数，每次添�一个硬币。选择硬币时所採用的贪婪准则例如以下：每一次选择应使零钱数尽量增大。为保证解法的可行性（即：所给的零钱等于要找的零钱数），所选择的硬币不应使零钱总数超过终于所需的数目
引例分析
为使找回的零钱的硬币数最小，不考虑找零钱的全部各种方案，而是从最大面值的币种開始，按递减的顺序考虑各币种，先尽量用大面值的币种，仅仅当不足大面值币种的金额才会去考虑下一种较小面值的币种。这就是在採用贪婪法。这样的方法在这里之所以总是最优，是由于银行对其发行的硬币种类和硬币面值的巧妙安排。假设仅仅有面值分别为1，5和11单位的硬币，而希望找回总额为15单位的硬币，按贪婪算法，应找1个11单位面值的硬币和4个1单位面值的硬币，共找回5个硬币。但最优的解答应是3个5单位面值的硬币。
贪心法的求解过程
用贪心法求解问题应该考虑例如以下几个方面：
（1）候选集合C：为了构造问题的解决方式，有一个候选集合C作为问题的可能解，即问题的终于解均取自于候选集合C。比如，在付款问题中，各种 面值的货币构成候选集合。
（2）解集合S：随着贪心选择的进行，解集合S不断扩展，直到构成一个满足问题的完整解。比如，在付款问题中，已付出的货币构成解集合。
（3）解决函数solution：检查解集合S是否构成问题的完整解。比如，在付款问题中，解决函数是已付出的货币金额恰好等于应付款。
（4）选择函数select：即贪心策略，这是贪心法的关键，它指出哪个候选对象最有希望构成问题的解，选择函数通常和目标函数有关。比如，在付款 问题中，贪心策略就是在候选集合中选择面值最大的货币。
（5）可行函数feasible：检查解集合中添�一个候选对象是否可行，即解集合扩展后是否满足约束条件。比如，在付款问题中，可行函数是每一步选 择的货币和已付出的货币相加不超过应付款。
贪心法的一般流程
Greedy(C) //C是问题的输入集合即候选集合
{
S={ }; //初始解集合为空集
while (not solution(S)) //集合S没有构成问题的一个解
{
x=select(C); //在候选集合C中做贪心选择
if feasible(S, x) //推断集合S中添�x后的解是否可行
S=S+{x};
C=C-{x};
}
return S;
贪心法的基本要素
对于一个详细的问题，怎么知道是否可用贪心算法解此问题，以及是否能得到问题的最优解呢?这个问题非常难给予肯定的回答。
可是，从很多能够用贪心算法求解的问题中看到这类问题一般具有2个重要的性质：
贪心选择性质和
最优子结构性质。
贪心选择性质和
最优子结构性质。
子问题：如果为了解决某一优化问题，须要依次作出n个决策D1，D2，…，Dn，对于不论什么一个整数k，1 < k < n，以Dk作为问题的初始状态，来进行以后的决策，这种问题就成为是原问题的一个子问题。
1.贪心选择性质
所谓
贪心选择性质是指所求问题的
总体最优解能够通过一系列
局部最优的选择，换句话说，当考虑做何种选择的时候，我们仅仅考虑对当前问题最佳的选择而不考虑子问题的结果。这是贪心算法可行的第一个基本要素。
贪心选择性质是指所求问题的
总体最优解能够通过一系列
局部最优的选择，换句话说，当考虑做何种选择的时候，我们仅仅考虑对当前问题最佳的选择而不考虑子问题的结果。这是贪心算法可行的第一个基本要素。
贪心算法以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。
对于一个详细问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择终于导致问题的总体最优解。
2.最优子结构性质
当一个问题的最优解包括其子问题的最优解时，称此问题具有
最优子结构性质。问题的最优子结构性质是该问题可用贪心算法求解的关键特征。
最优子结构性质。问题的最优子结构性质是该问题可用贪心算法求解的关键特征。
贪心法的应用
- 哈夫曼编码
- 0-1背包问题
- 磁盘文件的存储
- 生产调度问题
- 信息查询
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/118543.html原文链接：https://javaforall.net
