分治策略（3篇）之贪婪选择

 第三篇：分治法之贪婪选择

目的：

    本篇博客并不具体的讨论某一个算法，而是将同类型的问题集中展示，从而对分治法有       更进一步的认识。

目录：

    1）问题1：部分背包问题

    2）问题2：找零钱问题

    3）问题3：教室规划问题

    4）问题4：最小生成树问题

    5）问题5：最优二叉树问题

 

问题1：部分背包问题(最大)

        在上一篇“分治法之动态规划”中最后一个案例，接触到了0-1背包问题，大家都知道背包问题是一系列问题，此处再讨论一下部分背包问题。

 所谓部分背包是指，此次不是要么拿走整个珍宝，要么就不拿走，是非黑即白，非0即1的问题，而是去掉了这个约束，你可以拿走珍宝的任何部分，即任何分之一，事情会变得相当简单。你完全可以不必考虑什么算法的，凭借直觉就能做出选择即：拿走整个1号珍宝，2号珍宝和3号珍宝的2/3，总价值是240。其实这个选择里面涉及到算法中的分治法之贪婪选择。也许贪婪就是人的本性，所以一般人都可以很容易做出这个经常做的选择。（至于何处贪婪，等过完这几个案例就很容易明白了。）

问题2：找零钱问题（最少）

       一个小孩买了价值少于10块钱的东西，并将50块钱的钱交给店老板。店老板希望用数目最少的纸币找给小孩。假设提供了数目不限的面值为20块、10块、5块、1块、5角和1角的纸币。

假设需要找给小孩47块7角，聪明的店老板首先是选了1张20块，之后又选了1张20块，第3张选了5块，第4张选的是1块，第5张选的是1块，第6张选5角，第7张选1角，第8张选1角，结束。

分析：

店老板分步骤组成要找的零钱数，每次选1张纸币。选择纸币时每次都选择允许范围内（不赔钱）面值最大的纸币，例如上面的例子，店老板选择了1张20块的，当选择完了之后，问题就变成了用数目最少的纸币找给小孩27块7角的同类型规模更小的问题。

那么我们仔细分析一下这个老板的行为即为什么每次选取最大面值的纸币就能保证用到的数目是最少的呢？

证明：

假设符合条件的最少纸币的集合是M即由20块，20块，5块，1块，1块，5角，1角，1角组成，M的大小是8。假设第一次我们不选择20块，但是这20块还是要给这个小孩，我可以用2张10块代替或者1张10块，2张5块代替。这个问题一眼就能看的出来，集合M的大小变了，变成了9或者10。所以说，选择20块是最明智的。等找了这20块之后，剩下的问题就变成了用数目最少的纸币找给小孩27块7角的同类型规模更小的问题，称之为子问题，而且是属于要找到最优的结果的来解决子问题。

 找零钱问题，第一步是做出了一个选择，选择了最大面值的纸币20块，而且这个选择确保了获得最优解。这个是找零钱问题的一个特性，最长公共子序列没有，0-1背包也没有（在保证获得最优解的情况下，如果不是你可以选择价值最大的，但是没有获得最优解，这个和本例中选择20块结果保证了最优解是不同的）等等。这个问题的特性是每次都找最大的，有点贪婪，因此我们称之为贪婪选择属性。

强调：贪婪选择和贪婪选择属性的差异，前者是一种行为，不一定能保证正确的结果，就像考试的时候选择题不会做，我们可以贪婪的选择一个自己认为最好的，这种行为不一定能带来正确的解。然而贪婪选择属性是一种能够保证获得最优解的一种属性，一旦确定了这种属性，加上你的贪婪选择，事情就有保证了~~。   

 此例子虽然很简单，但是却包含了本篇问题的两个特性：贪婪选择属性和最优子结构（最有子问题），现在可以去分析问题1了~~。

问题3：教室规划问题

 以上两个问题，第一思路都偏向于直觉。教室规划问题可以拿来具体分析一下。

 教室规划问题是指：假设某大学有n门课程需要使用同一间教室，所有的课程的开始时间和结束时间已知，那么该如何安排教室才能使得在某段时间内，该教室内上的课程数目最多？

课程集合c=｛c1,c2,c3…c12｝

每个课程的起始时间和终止时间如下图所述：
   

 
如:

C1[0,3] ,C2[2,5] ,C3[4,7]

最大的课程集合C：{C1,C3,C6,C8,C12}

但是这个结果并不是唯一的： {C1,C4,C6,C10,C11}或者{C1,C4,C6,C10,C12}等也是符合条件的。

分析：

类似最长公共子序列中使用的方法一样，我们定义S[i,j]表示所有在课程Ci结束后开始，在Cj开始前结束的课程。为了方便，引入两门课程C0 =[-∞,0]和Cn=[∞,∞+1]

例如：S[3,10]表示C3,C4,C5,C6课程的集合。

           S[9,15]表示C7,C8,C9,C10课程的集合。

我们称S[3,10]和S[9,15]是兼容的集合。像集合｛C1,C2,C6｝是不兼容的集合，因为C1和C2两门课程有重叠的时间。

所以问题3就转换成了求S[i,j]的最大兼容的集合。

下面来说明一个很重要的性质：

假设S[i,j]非空，课程Cm是S[i,j]里面结束时间最早的课程。

1）Cm必定属于S[i,j]里面某个最大兼容子集。（S[i,j]可能不唯一，本例就列举了3个）

2）S[i,m]为空集，选择课程Cm使得S[m,j]成为唯一的非空子集。

证明：

假设A[i,j]是S[i,j]的某一个最大的兼容子集（像本问题中开始列举的3个中的一个）。课程Ck是A[i,j]里面最早结束的课程。

1）如果Cm = Ck,证明完毕

2）如果Cm并不是Ck。那么由于课程Cm是S[i,j]所有课程里最早结束的，我们可以用Cm代替Ck,这样集合A[i,j]仍然是兼容的。如下图

       S[2,10]的一个最大的兼容结合｛C3,C6｝.但是C3并不是最早结束的课程，最早结束的课程是C2.所以我们可以用C2代替C3,组成集合｛C2,C6｝该集合显然是兼容的，所以Cm必定是某一个最大的兼容集合中的元素。

对于第2点，由于Cm是最早结束的课程，选择了Cm之后，问题就变成了求解同种类型但是规模更小的S[m,j]的最大兼容集合。

如果你看明白了，那么就会发现这种现象很熟悉，类似问题2找零钱的时候，先是选择一个面值最大的如20块钱纸币（选择结束时间最早的一门课程），剩下的问题就变成了用数目最少的纸币找给小孩27块7角的同类型规模更小的问题（变成在S[m,j]里面寻找最大的兼容集合）。

所以我们可以使用贪婪策略来解决该S[i,j]最大兼容集合问题，具体步骤：

1）每次选择结束最早的一门课程Cm(贪婪选择)

2）解决子问题S[m,j]的最大兼容集合

比如本问题，先是选择课程C1,之后是C4,C6,C10,C11.所以该集合就是｛C1, C4,C6,C10,C11｝

 

本案例之所以能够成功，是因为第1）步的贪婪选择的时候，贪婪选择属性成立，同时第2）步表示的是最优子问题属性成立。

       但是，很容易发现使用贪婪选择策略存在一些问题，该方法只是能够找出其中一个最优解，并不能找出所有的最优解。该怎么办？动态规划。

       大概说一下动态规划是如何解决此问题的：

       求S[i,j]的最大兼容子集的时候，我们不像贪婪选择策略中选择结束时间最早的课程，而是选择S[i,j]中某一个课程Cm，例如本例中的C7或者C3都行。以C7为例，选择了C7之后，问题转换成了求S[0,9]最大兼容子集和S[11,19] 最大兼容子集。设S[i,j]的最大兼容结合大小为A[i,j].上述情况用数学表达式表示是：

 同样可以看出类似于最优二叉搜索树中一样，存在重叠子问题和最优子结构。每次选择Cm的时候，可能有几个值，比如S[0,19]可以选择12个课程里面的任何一个。S[4,10]的时候Cm可以选择为C3,C5或者C6.

 

此题如果用动态规划解决，你会发现问题立即变得相当复杂（相对于贪婪选择策略），但是它是可以找出所有的解的。

      想要具体了解可参考：

      http://liyiwen.iteye.com/blog/345796 

http://wlh0706-163-com.iteye.com/blog/1839787

 

       难道贪婪选择就找不出所有的解吗？可定不是，此处只是想将动态规划和贪婪选择做一个对比。

       对于使用贪婪选择，想要找出所有的解，需要在选择第一个最早结束的课程如C1,如果在C1结束之前已经有课程开始，那么该课程也有可能是最大兼容集合的一员，只需找出所有在C1结束时间之前开始的课程替换C1,找出所有的解，和以C1为第一门课的最大兼容集合比较，如果相同则它也是属于最大兼容集合，如果小于则不是（当然不可能大于，因为选择C1就以为这选择了最大的兼容子集）。

 

代码实现：       

 参数s 和 f是按照课程结束时间排好序的。

//数据
int s[] = { 0, 2, 4, 3, 6, 8, 9, 10, 11, 12, 13, 15 };
int f[] = { 3, 5, 7, 8, 10, 10, 11, 13, 15, 15,17, 19 };


/**
	 * 根据按照结束时间排好序的时间数组，得出最大兼容集合
	 * @param s 
	 * @param f 排好序的时间数组
	 * @return
	 */
	public static int greedy(int[] s, int[] f) {
		boolean result[] = new boolean[f.length];
		// 默认选择了第一门课
		if (s.length >= 1) {
			result[0] = true;
		}
		//集合总大小
		int count = 1;
		//比较课程i的开始时间和j结束时间 如果大于j的结束时间，可以。
		int j = 0;
		for (int i = 1; i < s.length; i++) {
			if (s[i] >= f[j]) {
				result[i] = true;
				j = i;
				count++;
			} else {
				result[i] = false;
			}
		}
		
		for(int i = 0;i<result.length;i++){
			if(result[i]){
				System.out.println("start = "+s[i]+"  finish = "+f[i]);
			}
		}
		return count;
	}

 这是我的测试结果

 问题4：最小生成树问题

        最小生成树问题是指：一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图联通的最少的边。

也许上述理论总是表达的过于严密是中心意思变得不再突出，抽象的东西并不是每个人都能很好的理解的。所以下面以一个具体例子，一张最为经典的图片来说明： 

 需求：

       可以将上图理解成某个计算机中心，每一个结点代表一台计算机如A,B,C等。每条边代表从一台计算机联网到另外一台计算机花费的代价。那么该如何在保证所有计算机联通的情况下，花费的代价最小呢？其实红色表示的线路就是最小的，不行你可以试一试。

     假设你之前并不了解最小生成树，该如何自己“创造”出这个理论呢而不只是接受创建这个理论的人的理论？就像找零钱问题应该没有人教过你一样。

     为了达到这个目的，我们再举一个相对来讲感性一点的例子。

     1，2，3，4，5，6...99，100.

   我们在这100个数字里面找出10个数字，而且这10个数字之和最小。毫无疑问，选择1-10。那么我们增加限制，这10个数字任何一个数字不能由其他数字相加得到。例如我们选择1，选择2，之后就不能选择3，因为3能够由1+2得到。那么这10个数字是谁呢？

 

也许你已经拿着笔自己算了起来，应该是这样算的：

 可以选择1，2，4，7，12，15 再往后25可以吗?就稍稍超出计算范围之内的了，容易出错。相信你也是从小到大开始选的，先试1，再试2，发现2可以，再试3，发现不行（可以由1+2组合成），再试4，发现行，再试5，发现不行（可以由1+4组合成），6也不行…反正思路就是这样，如果想做的更好就是优化的问题了。一个问题第一难的应该是思路，之后第二难的才会是优化。现在我们有思路了，那么最小生成树问题变迎刃而解了。

 

假设上述问题，我们借助“老天爷”之手，将已经排好序的100个数字打乱，比如24，1，2，14，3，8，4等，相信你可以解决，我们可以借助自己的手将他们排好序，呵呵。

下面我们里讨论本问题：

    这里一共有14个数字（相当于1-100共个数字）【1，2，2，4，4，6，7，7，8，8，9，10，11，14】。

    我已经借助自己的手帮它排好了序。一共有9个结点，所以我们要选出来至少8个边（相当于选出10个数字）才能保证联通，但是并不是每一条边都可以，如果这条边的连接的两个结点已经联通了（相当于选择3的时候，发现1+2已经可以组成3了），我们就没必要再要这条边，要了纯粹浪费。那么问题解决了吗？解决了。

 

真的解决了吗？其实没有。因为你并没有证明你选择1-100这些数字的做法是正确的，只是感性上认为是这样的，像找零钱。不过大部分问题已经解决了，过了感性这一关，理性这一关相对来讲（这句话只是说针对本题）就简单一些。我们以最小生成树为例：

 

    类似找零钱中，我们用反证法。假设理论上的最小生成树为T(类似找零钱中的集合M),如果这棵最小生成树t中并不包含连接H和G的花费代价为1边，例如我么可以用上图中的连接B和C的那一条权值为8的边代替这个1.

    这样H和G也是联通的.假设这可树叫做T。那么我们完全可以断掉t中联通H和G这条线路中的任何一条边.

    把它换成权值为1的这一条边。这样所有的结点仍然是联通的。当然并不是只能断掉C和F的连接边，而是任何一个连接，因为这些连接花费的代价都比1大。

这个就是最小生成树的贪婪选择属性即每次必须选择最小的边。

下面但是有贪婪选择属性还是不够的，下面来说明另外一个属性最优子结构。

当H和G联通以后，我们可以这样理解

    我还擦出了连接HG和I的那条边权值为7，因为我会义无反顾的选择6这条边来代替。剩下的问题就转换成了上图的8个结点，是不是也一定组成最小生成树呢？是的如果这8个顶点不组合成最小生成树，那么整个树即这8个顶点的树加上连接H和G之间的权值1组合成的树就不是最小生成树了。这个意思是说要想用9个顶点组合成最小生成树T,则这8个顶点组成的生成树也必须是最小的，原问题的最优解包含子问题的最优解：最优子结构。

证明完毕！

 

问题5：最优二叉树问题

   需求：铁球分类  

现有一批球磨机上的铁球，需要将它分成四类：直径不大于20的属于第一类;直径大于20而不大于50的属于第二类；直径大于50而不大于100的属于第三类；其余的属于第四类；假定这批球中属于第一、二、三、四类铁球的个数之比例是1:2:3:4。

 

假设球的数目是1000个，第一类有100个，第二类有200个，第三类有300个，第四类有400个。

图一共需要判断次数为：100*1+200*2+300*3+400*3 = 2600

 

 

        图二一共需要判断的次数是：400*1+300*2+200*3+100*3 =1700

 

        看来设计一个好点的最优的判断树（实际就是哈夫曼树）还是相当有必要。

    图二就是一个哈夫曼树，而哈夫曼树创建的过程相当简单。

    叶子结点被赋上权值，本例中有4个叶子结点分别是结点1（第一类）结点2（第二类），结点3（第三类）和结点4（第四类），权值就是他们出现的比例（概率）：1，2，3和4。

 

第一步：选择权值最小的两个结点即结点1和结点2（第一类和第二类）。组成一个新的结点我们称为结点a，它的权值是结点1和结点2的权值之和3.然后删除结点1和结点2，就剩下了结点a（权值为3），结点3（权值为3）和结点4（权值为4）。

第二步：选取权值最小的两个结点即结点a和结点3组合成新的结点b，权值为3+3=6；然后删除这两个结点。之后剩下了结点b和结点4。

第三步：选取权值最小的两个结点即结点b和结点4组合成新的结点c,实际上只能组装它俩成新的结点c，就是根节点，权值是4+6=10.结束

为什么这样做呢？即每次选择权值最小的两个结点。因为这就是这个问题的贪婪选择属性，只不过是被哈夫曼给发现了。

   下面我们证明这个就是贪婪选择属性，即要想构造出最优的判断数，必须选择两个权值最小的两个，使之称为深度最大的结点（当然它俩不一定是唯一一对最深的结点，但是肯定是深度最深的）

 

 我们假设上图即为构造的最优二叉树T，叶子结点x和y的权值是最小的分别为f(x)和f(y),但是他们没有被安排在了深度最深的地方，而是将结点a和b安排了深度最深的地方。

 

  结点的深度用dep(i)表示,树的判断的总代价为B(T)即叶子结点权值和深度乘积之和。

 则T的总代价

 B(T)=B(P)+f(x)dep(x) +f(y)dep(y)+ f(a)dep(a)+ f(b)dep(b)

下面我们交换结点x和结点a的位置

 该树我们称为T1:

B(T1) = B(P)+ f(x)dep(a) +f(y)dep(y)+ f(a)dep(x)+ f(b)dep(b)

则：B(T)-B(T1)= {f(x)-f(a)}{dep(x)-dep(a)}>=0

也就是说：T1可以是比最小生成树T代价更小的树，最小生成树易主了变成了T1。

同样在T1的基础上我们以相同方式交换b和y得到树T2，则T2是比T1代价更下的树。

这就意味着，要想构造出最小二叉树，必须要选择当前结点中权值最小的两个，组成新的结点。这就是哈夫曼树的最终要的选择，即贪婪选择。

问题完了吗？显然是少了一步：证明做出贪婪选择之后，剩下的子问题必须也要是最优解才行吗？即原问题的最优解包含子问题的最优解，最优子结构属性。

   证明：

   当结点x和结点y组合成新的结点C之后，剩下的这些结点构成任何一颗二叉树，设为T0.我们的目的就是证明T0必须也是一个最优二叉树，即原问题的最优解包含子问题的最优解。

 T0的代价：B(T0)=B(P)+f(c)*dep(c)

其中f(c)= f(x)+(y);dep(c)=dep(x)-1或者dep(y)-1

原树T的代价：B(T) = B(P)+f(x)dep(x)+f(y)+dep(y)

B(T)用B(T0)表示：B(T) = B(T0)-f(x)-f(y)

上式表明：B(T)和B(T0)是线性关系，如果想B(T)获得最小值，B(T0)必须获得最小值。即最优子结构属性。

证明完毕。

 

贪婪选择策略总结：

贪婪选择策略实际也是一种分治策略。标准分治法包含3个步骤：

1)Divide  2）Conquer 3）Combine

贪婪选择，相当于第1步Divide，当选择完之后，原问题就分解成了1个子问题，之后就是第2步Conquer递归的调用，解决子问题。再然后第3步合并，即将前2步的结果组合到一起。

分析到这，我们就可以和动态规划与标准分治进行一次比较了。

1）贪婪选择和动态规划可以解决最优问题，标准分治解决通用的问题。

2）贪婪选择是每次先是根据贪婪选择属性做出一个选择，之后再解决子问题；动态规划每次做出选择之前，必须先解决包含的子问题，然后从子问题中选择最优解；标准分治先做出选择，再解决所有子问题，和贪婪选择相同。

3）贪婪选择的子问题数目是1个，只解决一个子问题；而动态规划是不止1个，需要解决全部的子问题，这一点和标准分治相同。

4）这3种策略都运用了分治策略，只不过标准分治一般在分界点分成两个子问题；动态规划一般也是分成多个子问题；贪婪选择是分成唯一一个子问题。但也有例外，比如已经排好序的列表，使用标准分治即快速排序的时候，就是分成了一个子问题。

 

当然以上只是比较了几个明显的区别，可能还有其他区别。

（这篇博客写的真是揪心，ITEYE的排版真是一个DT的问题，加上今天ITEYE服务器总是断断续续的挂掉，不是图片上传不了就是网页突然无法访问，吐槽一下，汗！！）