一个凭借直觉的算法——贪心算法及其应用：活动选择问题

贪心法是比较实用的算法，因为它是由局部考虑从而达到整个最优。
贪心策略就是人在面对一个问题时候的一种直观想法的策略，不断地利用这个策略可以让我们得到想要的结果
当然，贪心策略并不一定是正确的，也并不一定适用于整体。

贪心法是优先考虑的算法，因为算法考虑起来简单；而且代码的复杂性不这么高；时间和空间复杂性能够达到最优。所以在某些算法问题中，贪心法是一个先考虑的算法。
本篇主要介绍什么是贪心法，贪心法和动态规划算法的区别，贪心法的应用：活动选择问题

1、贪心法

什么是贪心法

贪心法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

贪心算法和动态规划算法也比较像，因为他们都是从子问题最优达到全局最优。只不过动态规划算法是一个自底向上的算法；而贪心算法是自定向下的算法。

贪心算法每做一次贪心选择就将所求问题简化为一个规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择的性质，我们必须证明每一步所作的贪心选择最终能得到问题的最优解。

选择一个好的贪心策略变得尤为重要，通过每一次贪心选择就将所求问题简化为一个规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择的性质，我们必须证明每一步所作的贪心选择最终能得到问题的最优解。

贪心算法的特点

1、贪心算法适用于组合优化问题
2、贪心算法挑选过程是多步判断，每步依据某种“短视”的策略进行选择。这种策略的好坏决定算法的成败
3、如果想要证明贪心策略的正确性，必须进行正确性证明
4、证明贪心策略不正确的方法是举反例

贪心算法的基本思路

从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到算法中的某一步不能再继续前进时，算法停止。

贪心算法存在的问题

1、不能保证求得的最后解是最佳的；

2、不能用来求最大或最小解问题；

3、只能求满足某些约束条件的可行解的范围。

下面我们来通过一个例子来熟悉下贪心算法

2、活动选择问题

什么是活动选择问题

有一个活动时间表

建立模型：
输入S={1,2,…,n}为n项活动的集合，si,fi分别为活动i的开始时间和结束时间。
求：最大的两两相容的活动集A

经过分析得出这个问题的解是：1，4，8

下面我们用贪心法解这个问题

用贪心算法解活动选择问题

考虑用贪心算法解决某问题的时候，首先要找到好的贪心策略。对于活动选择问题，我们找到了三个贪心策略供以选择
策略1：开始时间早的优先挑选
策略2：占用时间少的(fi-si)少的优先
策略3：结束早的优先

下面来分析下这三个策略

分析贪心策略

对于策略1，我们能找到一个反例：
在只有三个活动的时候
s1=0,f1=20
s2=2,f2=5
s3=8,f3=15

对于策略2，我们也能找到一个反例：
也是在只有三个活动的时候
s1=0,f1=8
s2=7,f2=9
s3=8,f3=15

要是说明一个贪心策略是正确的，是要通过证明来证策略的普遍性。
一般对贪心法进行证明，可以通过数学归纳法或者交换论证进行证明。

下面我们用数学归纳法证明贪心策略3

数学归纳法证明贪心策略

我在看到这个证明的时候很懵逼。因为很多博客或者其他老师证明这个问题时都给人一种奇怪的感觉：就是没用策略就糊里糊涂的证完了。
后来我才想明白，他们都没有说清楚。

接下来证明贪心策略3：结束早的优先
令S={1,2,…,n}是活动集，且f1<=f2<=…<=fn。也就是说第一个活动的结束时间最早

这里得先说清楚：大家考虑一下，怎么才能算这个活动我进行完了呢。是不是一个结束时间，考虑一下包括了结束时间也就是包括了这个活动。换句话说就是，在本例中，我要去参加一个活动，在活动开始时我已经到场了。在活动结束的时候，我离场了。然后再去参加另一个活动。细想下，是不是这个活动结束了，我离场了，才算我参加了这么一场活动。

不应该是以开始时间计算一个活动是否已参加。因为此时，这个活动还没有结束呢。所以，我们要计算参加了哪场活动，应该是要看活动的结束时间来评判。

说清楚这个才可以更好的进行证明。

下面我们用数学归纳法进行证明
首先进行归纳基础：
当k=1时，证明存在最优解包含活动1。
如若不然，我们找到一个活动j(j!=1)，作为第一个活动
接下来，我们用1来替换A的活动j得到解A’，即A’=(A-{j})∪{1}

继续证明：
我们已经用1替换了j得到了A’。而且f1<=fj。因为只是替换，所以活动个数没有改变。如果A中的活动是最优解，那么由于f1<=fj。第一个活动结束时间是要比第j个活动的结束时间早。那么A’显然是最优的。而且如果j与后面都相容（即：两两活动之间没有交叉）。1的活动结束时间比j更小，所以1与后面的活动都相容

加入1号活动仍然是与后面活动相容，而且A与A’的活动个数一样，而A’正好是算法第一步选择的活动，因次算法第一步是正确的，它最终会导致最优解。这个就是归纳基础。

下面进行归纳步骤：
假设命题对k为真，证明对k+1也为真
算法执行到第k步，选择了活动i1=1,i2,…,ik，根据归纳假设存在最优解包括i1,i2,…,ik
当然也有一些活动要从待选集里面选

若不然，在待选集里面找到一个B*,其活动比B多。

下面我们证明对k+1也为真
存在一个最优解B’是有S’中的第一个活动ik+1，且|B|=|B’|

因此，策略3是正确的。

如果用数学归纳法证明策略1。如果将开始时间最早优先的话，那么在归纳基础时。你选了个开始时间早，将这个活动的结束时间加进去了，那么我总能找到一个比你选的开始时间晚，但结束时间早的反例来推翻你。因此归纳基础就不正确，也就谈不到后面的归纳步骤了。

下面分析代码：
首先对活动结束时间进行排序，将第j（j<=i）个活动的结束时间与第i个活动的开始时间进行比较，如果第i个活动的开始时间>=第j（j<=i）个活动的结束时间。
那么j=i;将j序号活动加进去。（额，代码虽然写的是将开始时间加进去了。这个忽略就行）
下面直接上代码

public class ActivityTime {
	int index;  //序号
	int startTime;  //活动开始时间
	int endTime;  //活动结束时间
	
	public ActivityTime() {
		// TODO Auto-generated constructor stub
	}

	public ActivityTime(int index, int startTime, int endTime) {
		super();
		this.index = index;
		this.startTime = startTime;
		this.endTime = endTime;
	}
	
	
}

public static void main(String[] args) {
		// TODO Auto-generated method stub
		ActivityTime activityTime[]=new ActivityTime[10];
		activityTime[0]=new ActivityTime(1,1,4);
		activityTime[1]=new ActivityTime(2,8,12);
		activityTime[2]=new ActivityTime(3,5,7);
		activityTime[3]=new ActivityTime(4,8,11);
		activityTime[4]=new ActivityTime(5,4,9);
		activityTime[5]=new ActivityTime(6,3,5);
		activityTime[6]=new ActivityTime(7,2,6);
		activityTime[7]=new ActivityTime(8,5,9);
		activityTime[8]=new ActivityTime(9,6,10);
		activityTime[9]=new ActivityTime(10,2,13);
		
		System.out.println("活动安排表如下：");
		for(int i=0;i<activityTime.length;i++)
			System.out.print((i+1)+"  ");
		System.out.println();
		for(int i=0;i<activityTime.length;i++)
			System.out.print(activityTime[i].startTime+"  ");
		System.out.println();
		for(int i=0;i<activityTime.length;i++)
			System.out.print(activityTime[i].endTime+"  ");
		System.out.println();
		
		EndtimeSort(activityTime);
		
		List<Integer> activityPlan = ActivityPlan(activityTime);
		System.out.print("可以选择的活动有：");
		for(int i=0;i<activityPlan.size();i++)
		System.out.print(activityPlan.get(i)+"   ");
		
		
	}

	//先对结束时间进行升序排序，若结束时间一样的则对开始时间进行升序排序
	public static void EndtimeSort(ActivityTime activityTime[]) {
		Arrays.sort(activityTime, new Comparator<ActivityTime>() {
			public int compare(ActivityTime o1, ActivityTime o2) {
				if(o1.endTime>=o2.endTime) 
					if(o1.endTime==o2.endTime)
						return o1.startTime-o2.startTime;
					else
						return o1.endTime-o2.endTime;
				else 
					return o1.endTime-o2.endTime;
			} 
		});
		
	}
	
	//用贪心算法解活动选择问题
	public static List<Integer> ActivityPlan(ActivityTime activityTime[]) {
		List<Integer> list=new ArrayList<Integer>();
		int j=0;
		list.add(activityTime[j].index);
		for(int i=1;i<activityTime.length;i++) 
			if(activityTime[i].startTime>=activityTime[j].endTime) {
				j=i;
				list.add(activityTime[j].index);
			}
		return list;
	}

下面对贪心法解活动选择问题的分析

贪心法解活动选择问题的分析

首先时间复杂度是由排序+选择算法决定的
排序：O(nlogn)
选择算法：一层for循环，所以是O(n)
因此总的时间复杂度就是O(nlogn)+O(n)
故贪心法解活动选择问题就是O(nlogn)

以上就是贪心法解活动选择问题的内容

3、贪心算法和动态规划算法的异同

共同点：求解的问题都具有最优子结构性质

差异点：

动态规划算法

1、动态规划算法通常以自底向上的方式解各子问题，全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解

2、动态规划的关键是状态转移方程，即如何由以求出的局部最优解来推导全局最优解

3、边界条件：即最简单的，可以直接得出的局部最优解。

贪心算法

1、而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每做一次贪心选择就将所求问题简化为规模更小的子问题。

2、贪心算法中，作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一部之前的最优解则不作保留。

当然贪心算法并不一定能带来局部最优解，也许k=1满足，k=2满足。k>3可能就不满足。所以贪心算法并不一定带来局部最优解。

以上就是贪心算法的内容

            古之大化者，乃与无形俱生。《鬼谷子·反应》