贪心算法的原理以及应用

---

0、概念

0.1.定义

贪心算法（greedy algorithm ，又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解 。
贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择 。
贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。贪心算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择，就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解。虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪心算法不要回溯

0.2.特征

利用贪心法求解的问题应具备如下2个特征：
1、贪心选择性质
一个问题的整体最优解可通过一系列局部的最优解的选择达到，并且每次的选择可以依赖以前作出的选择，但不依赖于后面要作出的选择。这就是贪心选择性质。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解 。
2、最优子结构性质
当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心法求解的关键所在。在实际应用中，至于什么问题具有什么样的贪心选择性质是不确定的，需要具体问题具体分析 。

0.3.步骤

贪心算法一般按如下步骤进行：
①建立数学模型来描述问题 。
②把求解的问题分成若干个子问题 。
③对每个子问题求解，得到子问题的局部最优解 。
④把子问题的解局部最优解合成原来解问题的一个解 。

0.4.适用

由贪心算法的定义来说，贪心算法一般适用的场所：
1、贪心算法一般用来解决求最大或最小解 ；
2、贪心算法只能确定某些问题的可行性范围。

---

1、与动态规划的联系

1.1.区别

1.贪心：每一步的最优解一定包含上一步的最优解，上一步之前的最优解则不作保留；
动态规划：全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有的局部最优解 ；
2、动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常自顶向下的方式进行。
3、根据以上两条可以知道，贪心不能保证求得的最后解是最佳的，一般复杂度低；而动态规划本质是穷举法，可以保证结果是最佳的，复杂度高。

1.2.联系

1、都是分解成子问题来求解，都需要具有最优子结构
2、所有的贪心问题都可以用动态规划来求解，可以这么说，贪心算法是动态规划的特例。

举个列子：平时购物找零钱时，为使找回的零钱的硬币数最少，不要求找零钱的所有方案，而是从最大面值的币种开始，按递减的顺序考虑各面额，先尽量用大面值的面额，当不足大面值时才去考虑下一个较小面值，这就是贪心算法 。

有很多经典的应用，比如霍夫曼编码，普利姆和克鲁斯卡尔最小生成树算法，还有迪杰斯特拉单源最短路径算法，都是使用了这种思维。

---

2、例子

1、题目：n个作业组成的作业集，可由m台相同机器加工处理。要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。
2、思路：作业不能拆分成更小的子作业；每个作业均可在任何一台机器上加工处理。 这个问题是NP完全问题，还没有有效的解法(求最优解)，但是可以用贪心选择策略设计出较好的近似算法(求次优解)。当n<=m时，只要将作业时间区间分配给作业即可；当n>m时，首先将n个作业从大到小排序，然后依此顺序将作业分配给空闲的处理机。也就是说从剩下的作业中，选择需要处理时间最长的，把它分配给当前总累计需要工作时长最短的机器。这样一来，这个调度问题可以理解为一个分配问题，我们通过这种方案，使得几台机器获得接近的工作总时长，达到整体的最短的工作时长的效果。
3、算法实现：

	/**多机调度问题*/public void greedy(){int time[] = {9,7,8,4,2,1,3};int number = 3;int Sumtime = getNumber4(time,number);println("花费的最小总时间："+Sumtime);		}int getNumber(int time[] , int number){int usedTime=0;               //最长时间为总时间int[] fin = new int[number];  //单机处理时间		for(int k=0;k<number;k++)     //初始时间清零{fin[k]=0;}		if(number>time.length)return time[0];else {			for( int i=0 ; i<time.length-1 ;i++){  for( int j=0;j<time.length-i-1;j++) //冒泡选出任务时间最大的{if(time[j]>time[j+1]){int temp = time[j+1];time[j+1]=time[j];time[j]=temp;}}int min=0;; int value=100;for(int k=0;k<fin.length;k++)  //选出当前累计工时最小的机子{if(fin[k]<value){min=k;value=fin[k];}						  }					   						fin[min]+=time[time.length-1-i];							   } int min=0;; int value=100;for(int k=0;k<fin.length;k++)  //选出当前累计工时最小的机子{if(fin[k]<value){min=k;value=fin[k];}				  }fin[min]+=time[0];for( int n=0;n<fin.length;n++){if(fin[n]>usedTime){usedTime=fin[n];}}return usedTime;}		}

---

3、总结

1、贪心算法其实是动态规划的一种特列，能用贪心的地方动态规划也适用；
2、贪心算法比动态规划更高效，他不需要保存历史值，当前的局部值为当前最优值，所u以最后的结果不一定是全局最优值；
3、贪心算法自上而下，层层分解为子问题求值。

---

4、引用

1、动态规划和贪心算法的区别
2、贪心算法的几种经典例题
3、

---