文章目录

  • 0、概念
    • 0.1.定义a
    • 0.2.特征
    • 0.3.步骤
    • 0.4.适用
  • 1、与动态规划的联系
    • 1.1.区别
    • 1.2.联系
  • 2、例子
  • 3、总结
  • 4、引用

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、