算法设计与分析耿国华第四章

第四章贪心算法算法设计与分析算法设计与分析主编耿国华本章内容4.1贪心算法基础•4.1.1贪心算法的基本思想•4.1.2贪心算法的基本要素•4.1.3贪心算法适合的问题•4.1.4贪心算法的基本步骤•4.1.5贪心算法实例——背包问题4.2汽车加油问题4.3最优服务次序问题4.4区间相交问题4.5单源最短路径4.6本章小结Chapter4引言假设有四种硬币，它们的面值分别为二角、一角、五分和一分。现在要找给某顾客五角三分钱，并且要找硬币数目个数最少，通过上章学习，我们可以用动态规划算法列出所有解，然后找出其中硬币数目最少的解。我们也可以用一种更为简便的贪心算法来求解问题。这种找硬币方法与其他的找法相比，方法简便，效率高。我们会拿出2个二角的硬币，1个一角的硬币和3个一分的硬币交给顾客。选择硬币时所采用的贪心算法如下：为使找回的零钱的硬币数最小，从最大面值的币种开始，按递减的顺序考虑各币种，先尽量用大面值的币种，只当大面值币种的金额不足才会去考虑下一种较小面值的币种。每一次都选择可选的面值最大的硬币。为确保解法的可行性（即：所给的零钱等于要找的零钱数），所选择的硬币不应使零钱总数超过最终所需的数目。Chapter4上述找硬币的算法利用了硬币面值的特殊性.如果硬币的面值改为一分,五分,一角一分3种,要找给顾客的是一角五分钱.还用贪心算法,我们将找给顾客1个一角一分的硬币和4个一分的硬币，然而3个5分的硬币显然是最好的找法。由此可见贪心算法并不是总能得到最优解。4.1贪心算法基础Chapter44.1.1贪心算法的基本思想4.1.2贪心算法的基本要素4.1.3贪心算法适合的问题4.1.4贪心算法的基本步骤4.1.5贪心算法实例——背包问题4.1.1贪心算法的基本思想•贪心算法是从问题的某一个初始解出发，向给定的目标推进。但它与普通递推求解过程不同的是，其推动的每一步不是依据某一固定的递推式，而是做一个当时看似最佳的贪心选择，不断地将问题实例归纳为更小的相似的子问题，并期望通过所做的局部最优选择产生出一个全局最优解。Chapter44.1.2贪心算法的基本要素一个贪心算法求解的问题必须具备以下两要素：•1.贪心选择性质所谓贪心选择性质是指应用同一规则，将原问题变为一个相似的、但规模更小的子问题、而后的每一步都是当前看似最佳的选择。这种选择依赖于已做出的选择，但不依赖于未做出的选择。Chapter42、最优子结构性质当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。由于运用贪心策略解题在每一次都取得了最优解，问题的最优子结构性质是该问题可用贪心算法或动态规划算法求解的关键特征。4.1.2贪心算法的基本要素表4-1动态规划算法和贪心算法的区别Chapter4基本思想依赖子问题的解解问题的方向最优解复杂程度贪心选择贪心选择否自顶向下局部最优简单有效动态规划递归定义填表是自底向上整体最优较复杂4.1.3贪心算法适合的问题贪心算法通常用来解决具有最大值或最小值的优化问题。它是从某一个初始状态出发，根据当前局部而非全局的最优决策，以满足约束方程为条件，以使得目标函数的值增加最快或最慢为准则，选择一个最快地达到要求的输入元素，以便尽快地构成问题的可行解。Chapter44.1.4贪心算法的基本步骤•步骤：(1)选定合适的贪心选择的标准；(2)证明在此标准下该问题具有贪心选择性质；(3)证明该问题具有最优子结构性质；(4)根据贪心选择的标准，写出贪心选择的算法，求得最优解。Chapter4贪心算法求最优解的一般过程Greedy(C)//C是问题的输入集合即候选集合{S={};//初始解集合为空集while(notsolution(S))//集合S没有构成问题的一个解{x=select(C);//在候选集合C中做贪心选择iffeasible(S,x)//判断集合S中加入x后的解是否可行S=S+{x};C=C-{x};}returnS;}4.1.5贪心算法的例子例4-1：n＝3，M=20，p＝(25，24，15)，w=(18，15，10)。假设物品可分，故有可行解无数个，其中的四个可行解如表4-2所示。•表4-2部分背包问题的四个可行解Chapter4(x0，x1，x2)∑wixi∑pixi①(1/2，1/3，1/4)16.524.25②(1，2/15,0)2028.2③(0，2/3，1)2031④(0，1,1/2)2031.5在这四个可行解中，第④个解的效益值最大。但这个解是否是背包问题的最优解，尚无法确定，但有一点是可以肯定的，即对于一般背包问题，其最优解显然必须装满背包。4.1.5贪心算法的例子•(1)”效益”优先,使每装入一件物品就使背包获得最大可能的效益值增量.按物品收益从大到小排序0,1,2解为:(x0，x1，x2)=(1,2/15,0)收益:25+24*2/15=28.2此方法解非最优解。原因:只考虑当前收益最大,而背包可用容量消耗过快.•(2)选重量作为量度,使背包容量尽可能慢地被消耗.按物品重量从小到大排序:2,1,0;解为:(x0，x1，x2)=(0,2/3,1)收益:15+24*2/3=31此方法解非最优解。原因:虽然容量消耗慢，但效益没有很快的增加.Chapter44.1.5贪心算法的例子•(3)选利润/重量为量度，使每一次装入的物品应使它占用的每一单位容量获得当前最大的单位效益。按物品的pi/wi重量从大到小排序:1,2,0;解为:(x0，x1，x2)=(0,1,1/2)收益:24+15/2=31.5此方法解为最优解。可见，可以把pi/wi作为背包问题的最优量度标准。4Chapter4.1.5贪心算法的例子——设计与实现•算法4.1用贪心算法求解部分背包问题voidGreedyKnapsack(float*p,float*w,floatM,intn,float*x){//前置条件：w[i]已按p[i]/w[i]的非增次序排列floatu=M;//u为背包剩余载重量，初始时为mfor(inti=0;in;i++)x[i]=0;//对解向量x初始化for(i=0;in;i++)//按最优量度标准选择解的分量{if(w[i]u)break;x[i]=1.0;u=uw[i];}if(in)x[i]=u/w[i];}Chapter44.1.5贪心算法的例子——算法分析1）贪心选择性质证明：设背包按其单位价值量pi/wi由高到低排序，(x1,x2,…,xn)是背包问题的一个最优解。又设易知，如果给定问题有解，则。当k=1,(x1,x2,…,xn)是以贪心算法开始的最优解。当k1,设有一个集合(y1,y2,…,yn)，其中y1=pk/p1*xk,yk=0,yi=xi,.则因为所以因此，(y1,y2,…,yn)时所给部分背包问题的一个可行解。另一方面，由知，(y1,y2,…,yn)是一个满足贪心选择性质的最优解.所以，部分背包问题具有贪心选择性质。Chapter410miniinkixnk1ni21111*/*nniiiiiikkkkkkwpwp//11cxppwxwxwywkkkkniiiniii1111niiniiyx1111/*vpwwkk4.1.5贪心算法的例子——算法分析•2）最优子结构性质贪心选择物体1之后，问题转化为背包重量为m-w1*x1，物体集为{物体2,物体3,…，物体n}的背包问题。且该问题的最优解包含在初始问题的最优解中。对于部分背包和0-1背包这两类问题都具有最优子结构性质。对于部分背包问题，类似地，若它的一个最优解包含物品j，则从该最优解中拿出所含的物品j的那部分重量w，剩余的将是n-1Chapter4个原重物品1,2,...,j-1,j+1,...,n及重为wj-w的物品j中可装入容量为c-w的背包且具有最大价值的物品。对于0-1背包问题，设A是能装入容量为c的背包的具有最大价值的物品集合，则Aj=A-{j}是n-1个物品1,2,...,j-1,j+1,...,n可装入容量为c-wj的背包的具有最大价值的物品集合。对于0/1背包问题，使用贪心法，并不一定能求得最优解，因此，贪心法不能用来求解0/1背包问题。4.1.5贪心算法的例子对于0/1背包问题，使用贪心法，并不一定能求得最优解，因此，贪心法不能用来求解0/1背包问题•例4-2•n＝3，M=25，p＝(32，24，15)，w=(16，15，10).则p/w=(2,1.6,1.5)。选利润/重量为量度，取最大值得到解：X=(0)∑p=32,背包剩余重量CU=M-w(0)=9.不能放下任何物品，显然X=(0)不是最优解。最优解是(1,2)，利润为39。Chapter44.2汽车加油问题本节内容1.问题分析2.算法分析3.设计与实现Chapter44.2汽车加油问题•问题描述一辆汽车加满油后可以行驶N千米。旅途中有若干个加油站，如图4-1所示。指出若要使沿途的加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油（前提：行驶前车里加满油）。Chapter40123…….n图4-1汽车加油图例4.2汽车加油问题——问题分析•由于汽车是由始向终点方向开的，我们最大的麻烦就是不知道在哪个加油站加油可以使我们既可以到达终点又可以使我们加油次数最少。我们可以假设不到万不得已我们不加油，即除非我们油箱里的油不足以开到下一个加油站，我们才加一次油。在局部找到一个最优的解。每加一次油我们可以看作是一个新的起点，用相同的递归方法进行下去。最终将各个阶段的最优解合并为原问题的解得到我们原问题的求解。Chapter4贪心策略：汽车行驶过程中，应走到自己能走到并且离自己最远的那个加油站，在那个加油站加油后再按照同样的方法贪心选择下一个加油站。4.2汽车加油问题——问题分析•例4-3•在汽车加油问题中，设各个加油站之间的距离为（假设没有环路）:1,2,3,4,5,1,6,6.汽车加满油以后行驶的最大距离为7，则根据贪心算法求得最少加油次数为4，需要在3,4,6,7加油站加油，如下图所示：•计算过程如下表所示。Chapter41号2号3号4号5号6号7号终点加满油后行驶公里数13645666剩余行驶数64132111是否加油00110114.2汽车加油问题——算法分析•1）贪心选择性质设在加满油后可行驶的N千米这段路程上任取两个加油站Ａ、Ｂ，且Ａ距离始点比Ｂ距离始点近，则若在Ｂ加油不能到达终点那么在Ａ加油一定不能到达终点，如下图：Chapter4•由图可知：因为m+Nn+N，即在B点加油可行驶的路程比在A点加油可行驶的路程要长n-m千米，所以只要终点不在A、B之间且在B的右边的话，根据贪心选择，为使加油次数最少就会选择距离加满油得点远一些的加油站去加油，因此，加油次数最少满足贪心选择性质。4.2汽车加油问题——算法分析2）最优子结构性质•当一个大问题的最优解包含着它的子问题的最优解时，称该问题具有最优子结构性质。(b[1],b[2],……b[n])整体最优解b[1]=1,(b[2],b[3],……b[n])局部最优解每一次加油后与起点具有相同的条件，每个过程都是相同且独立。Chapter44.2汽车加油问题——设计与实现算法4.2用贪心算法求解汽车加油问题intGreedy(inta[],intn,intk){int*b=newint[k+1];//加油站加油最优解b1~bkintnum=0;ints=0;//加满油后行驶的公里数for(inti=0;i=k;i++){if(a[i]n){coutnosolution\n;return;}}for(inti=0,s=0;i=k;i++){s+=a[i];if(sn){num++;b[i]=1;s=a[i];}}returnnum;}Chapter44.3最优服务次序问题本节内容1.问题分析2.算法分析3.设计与实现Chapter44.3最优服务次序问题•问题描述最优服务次序问题:设有n