[高等教育]《算法设计与分析》第06章.ppt

,第2部分 算法设计策略,6.1 一般方法 6.2 背包问题 6.3 带时限的作业排序 6.4 最佳合并模式 6.5 最小代价生成树 6.6 单源最短路径 6.7 磁带最优存储 6.8 贪心法的基本要素,第6章 贪心法,最优化问题（optimization problems）是指这样一类问题，问题给定某些约束条件（constraint），满足这些约束条件的问题解称为可行解（feasible solution）。通常满足约束条件的解不是惟一的。为了衡量可行解的好坏，问题还给出了某个数值函数，称为目标函数（objective function），使目标函数取最大（或最小）值的可行解称为最优解（optimal solution）。,6.1 一般方法,贪心法是通过分步决策（stepwise decision）的方法来求解问题的。 贪心法每一步上用作决策依据的选择准则被称为最优量度标准（optimization criterion）。 在根据最优量度标准选择分量的过程中，还需要使用一个可行解判定函数。 贪心策略并不是从整体上加以考虑的，它所做出的选择只是当前看似最佳选择，必须进一步证明该算法最终导致问题的一个整体最优解。,贪心技术(Greedy Technique),某一问题的n个输入,该问题的一种解（可行解）,是A的一 个子集,满足一定 的条件,约束条件,目标函数,取极值,最优解,【程序61】贪心法 SolutionType Greedy(SType a,int n) SolutionType solution=; for(int i=0;in;i+) SType x=Select(a); if (Feasiable(solution,x) solution=Union(solution,x); return solution; ,7,找零钱问题(change-making problem),用当地面额为d1d2dm的最少数量的硬币找出金额为n的零钱。 如d1=25,d2=10,d3=5,d4=1，n=48 该问题的一个解是： 1个25，2个10，3个1，且该解是最优的。 这种方法称为贪心法，建议通过一系列步骤来构造问题的解，每一步对目前构造的部分解做一个扩展，直到获得问题的完全解。 必须满足：可行、局部最优、不可取消,8,又如：d1=11,d2=5,d3=1,n=15 该问题的一个解是： 1个11，4个1，该解不是最优的。 最优解：3个5 本质上由硬币面值种类决定（问题其本身固有的特点） 。,贪心策略最优解的证明,基本思想 设X=x1,x2,.,xn为贪心策略得到的解 设Y=y1,y2,.,yn为该问题的最优解 很明显，XY，如果成立，则不用证明了。 证明过程： 依次比较X和Y中的每个元素，如果发现不一样，则用X中的替换Y中相应元素，比较完后得到一个新的解Y=X 此时，如能证明Y的最优值就是Y的最优值或者比Y还好，则说明X就是最优解。,问题 对容量为M的背包进行最佳装载的问题。,6.2 背包问题,6.2.1 问题描述,已知一个载重为M的背包和n件物品，第i件物品的重量为 wi，如果将第i件物品全部装入背包，将有收益pi，这里，wi0，pi0，0in。所谓背包问题是指求一种最佳装载方案，使得收益最大。所以，背包问题是现实世界一个常见的最优化问题。 两类背包问题:如果每一件物品不能分割，只能作为整体或者装入背包，或者不装入，称为 0/1背包问题；如果物品是可以分割的，也就是允许将其中的一部分装入背包为一般背包问题或简称背包问题。,6.2.2 贪心法求解,背包问题 背包问题的解可以表示成一个n-元组：X=(x0,x1,xn1)，0xi1，0in，每个xi是第i件物品装入背包中的部分。 判定可行解的约束条件是：,背包问题的最优解必须使下列目标函数取最大值：,例61 设有载重能力M=20的背包，3件物品的重量为:（w0,w1,w2）=(18,15,10)，物品装入背包的收益为：（p0,p1,p2）=(25,24,15)。,背包问题(Knapsack Problem),方案1：按物品价值降序装包,方案2：按物品重量升序装包,方案3：按物品价值与重量比值的降序装包,【程序62】背包问题的贪心算法 template class Knapsack public: Knapsack(int mSize,float cap,float *wei,T *prof); void GreedyKnapsack(float* x); private: float m,*w; T *p; int n; ;,template void Knapsack:GreedyKnapsack(float* x) /前置条件：wi已按pi/wi的非增次序排列 float u=m; for (int i=0;iu) break; xi=1.0; u=u-wi; if (i=n) xi=u/wi; ,6.2.3 算法正确性,定理61 如果p0/w0p1/w1pn1/wn1，则程序62求得的背包问题的解是最优解。,证明： 设X=(x0, x1, , xn-1)， 0xj 1 ,0in是贪心背包算法所生成的贪心解。 如果所有的xi都等于1,则显然X就是问题的最优解。否则， 设j是使xi1的最小下标。由算法的执行过程可知， 解的形式为： X=(1, , 1,xj,0, , 0) 即xi=1 0ij, 0xj 1,xi=0 jin-1,假设Y是问题的最优解：Y=(y0, y1, , yn-1) 且有： 若X Y，则X就是最优解。否则， X和Y至少在1个分量上存在不同。 设k是使得yk xk的最小下标，则有yk xk。可分以下情况说明： a) 若kj，则xk=1。因为yk xk,从而有yk xk b) 若k=j，由于 ，且对1ij，有yi=xi=1,而对jin,有xi0；故此时若ykxk，则将有 ，与Y是可行解相矛盾。而yk xk,所以yk xk c) 若kj，则 ，不能成立,在Y中作以下调整：将yk 增加到xk ，因为ykxk,为保持解的可行性，必须从(yk+1,yn-1)中减去同样多的量。设调整后的解为Z=(z0, z1, ,zk,zk+1, , zn-1)，其中zixi，0ik，且有： Z的效益值有：,差值0,由以上分析得， 若 ，则Y将不是最优解； 若 ，则或者Z=X，则X就是最优解； 或者ZX，则重复以上替代过程，或者证明Y不是最优解，或者把Y转换成X，从而证明X是最优解,最优装载,有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。 1.算法描述 最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略，可产生最优装载问题的最优解。具体算法描述如下页。,template void Loading(int x, Type w, Type c, int n) int *t = new int n+1; Sort(w, t, n); for (int i = 1; i = n; i+) xi = 0; for (int i = 1; i = n ,2.贪心选择性质 可以证明最优装载问题具有贪心选择性质。 3.最优子结构性质 最优装载问题具有最优子结构性质。 由最优装载问题的贪心选择性质和最优子结构性质，容易证明算法loading的正确性。 算法loading的主要计算量在于将集装箱依其重量从小到大排序，故算法所需的计算时间为 O(nlogn)。,活动安排问题,活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。,设有n个活动的集合E=1,2,n，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si fi 。如果选择了活动i，则它在半开时间区间si, fi)内占用资源。若区间si, fi)与区间sj, fj)不相交，则称活动i与活动j是相容的。也就是说，当sifj或sjfi时，活动i与活动j相容。,template void GreedySelector(int n, Type s, Type f, bool A) A1=true; int j=1; for (int i=2;i=fj) Ai=true; j=i; else Ai=false; ,下面给出解活动安排问题的贪心算法GreedySelector :,各活动的起始时间和结束时间存储于数组s和f中且按结束时间的非减序排列,由于输入的活动以其完成时间的非减序排列，所以算法greedySelector每次总是选择具有最早完成时间的相容活动加入集合A中。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。 算法greedySelector的效率极高。当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。,例：设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：,算法greedySelector 的计算过程如左图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动。,若被检查的活动i的开始时间Si小于最近选择的活动j的结束时间fi，则不选择活动i，否则选择活动i加入集合A中。 贪心算法并不总能求得问题的整体最优解。但对于活动安排问题，贪心算法greedySelector却总能求得的整体最优解，即它最终所确定的相容活动集合A的规模最大。这个结论可以用数学归纳法证明。,6.3.1 问题描述,设有一个单机系统、无其它资源限制且每个作业运行相等时间，不妨假定每个作业运行1个单位时间。现有n个作业，每个作业都有一个截止期限di0，di为整数。如果作业能够在截止期限之内完成，可获得pi0的收益。问题要求得到一种作业调度方案，该方案给出作业的一个子集和该作业子集的一种排列，使得若按照这种排列次序调度作业运行，该子集中的每个作业都能如期完成，并且能够获得最大收益。也就是说这种作业调度是最优的。,6.3 带时限的作业排序,6.3.2 贪心法求解,例62 设有4个作业，每个作业的时限为(d0,d1,d2,d3)=(2,1,2,1),收益为(p0,p1,p2,p3)=(100,10,15,27)。,【程序63】带时限作业排序的贪心算法 void GreedyJob(int d, Set X, int n) /前置条件：p0p1,pn-1 X=0; for (int i=1;in;i+) if ( 集合 Xi 中作业都能在给定时限内完成) X=Xi; ,6.3.3 算法正确性,定理62 程序62的贪心算法对于带时限作业排序问题将得到最优解。,证明： 设X =(x0, x1, , xK)是由贪心算法6-2所得的作业集合贪心解， Y =(y0, y1, , yr)是一个最优解的作业集合。 若Y=X，则X就是最优解；否则 ，则至少存在两个作业a和b，使得aX且 ,bY且 。（为什么） 并设a是这样的一个具有最高效益值的作业 (由算法的处理规则可得：对于在Y中而不在X中的作业所有b，有：papb),设和分别是X和Y的可行的调度表。因为X和Y都是可行解，故这样的调度表一定存在； 设x是既属于X又属于Y的一个作业，并设x在调度表中的调度时刻是t，t+1，而在中的调度时刻是t，t+1。 在X和Y中作如下调整： 若tt，则将中在t，t+1时刻调度的那个作业（如果有的话）与x相交换。如果X中在t，t+1时刻没有作业调度，则直接将x移到t，t+1调度。新的调度表也是可行的。, 若tt，则在中作类似的调换，即将中在t，t+1时刻调度的那个作业（如果有的话）与x相交换。如果Y中在t，t+1时刻没有作业调度，则直接将x移到t，t+1调度。同样，新的调度表也是可行的。 对X和Y中共有的所有作业作上述的调整。设调整后得到的调度表为和，则在和中X和Y中所有的共有作业将在相同时间被调度。,设a在中的调度时刻是ta, ta+1， b是中该时刻调度的作业，则有papb（为什么？）。 在中，去掉作业b，而去调度作业a，得到的是作业集合Y=（Y-b）a的 一个可行的调度表，且Y的效益值不小于X的效益值。而Y中比Y少了一个与X不同的作业。 重复上述的转换，可使Y在不减效益值的情况下转换成X。从而X至少有和Y一样的效益值。所以X也是最优解。 证毕。,=（x z ） =（ z x ） =（y x ） =（ y x ） (a) x与z交换前 (b) x与z交换后 =（y x ） =（ y x ） =（x z ） =（ z x ） (c) x与z交换前 (d) x与z交换后 图6-1 使相同作业在相同时刻被调度,6.3.4 可行性判定,定理63 X=（x0,x1,xk）是k个作业的集合，=（0, 1,k）是X 的一种特定排列，它使得d 0 d1dk ，其中， dj是作业j的时限。X是一个可行解当且仅当X中的作业能够按次序调度而不会有作业超期。,方法一：枚举法，检验X中作业所有可能的排列，对于任一种次序排列的作业序列，判断这些作业是否能够在其期限前完成 若X中有k个作业，则将要检查k!个序列 判断策略： 对于一个给定作业处理序列i1i2ik,由于作业ij完成的最早时间是j，因此只要判断出排列中的每个作业的期限有dijj，就可得知是一个允许的调度序列，从而X是一可行解。 反之，如果排列中有一个作业有dijj,则将是一个行不通的调度序列，因为至少作业ij不能在其期限之前完成。,方法二：检查X中作业的一个特定序列就可判断X的可行性：这一特定序列是按照作业期限的非降次序排列的作业序列,证明： 如果X中的作业可以按照的次序而又不违反任何一个作业期限的情况来处理，则X是一个可行解 现证若X是一个可行解，是否代表一个可行的调度序列？ X是可行解 必存在一可行的调度序列 r1r2rk，使得drjj, 1jk。 若 ，则即是可行的调度序列。否则， ，令a是使得raia的最小下标（如下图）, i1 i2 ia ic ik r1 r2 ra rb rk,设rb=ia。则有： ba 且 dradrb 故，在中调换ra与rb，所得的新序列 s1s2sk的处理次序不违反任何一个期限，而中位置a及a之前的作业均与相同。 重复上述过程，则可将转换成且不违反任何一个期限，故是一个可行的调度序列 故定理得证。,6.3.5 作业排序贪心算法,定理63提供了一种高效的可行解判定方法。使得在按最优量度标准，即按作业收益的非增次序选择下一个作业后，可以有效地判定是否可将该作业加入已生成的部分解向量X。,【程序64】带时限的作业排序程序 int JS(int *d, int *x, int n) /设p0p1pn-1 int k=0; x0=0; for (int j=1;j=0 ,6.3.6 一种改进算法,本小节将介绍一种带时限作业排序的快速算法，它采用不同于前者的可行解判定方法，可使算法的时间从(n2)减少到接近O(n)。,例63 设n=5个作业， 作业的时限为:(d0,d1,d2,d3,d4)=(2,2,1,3,3), 收益为: (p0,p1,p2,p3,p4)=(20,15,10,5,1)。,【程序65】使用并查集的带时限作业排序 int FJS(int *d,int *x,int n) UFSet s(n); int b,k=-1,*f=new intn+1; for (int i=0;i=n;i+) fi=i;,for (i=0;in;i+) if(ndi) b=n;else b=di; int r=s.Find(b); if (fr) x+k=i; int t=s.Find(fr-1); s.Union(t,r); fr=ft; delete f; return k; ,多机调度问题,多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。 这个问题是NP完全问题，到目前为止还没有有效的解法。对于这一类问题,用贪心选择策略有时可以设计出较好的近似算法。,约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。,采用最长处理时间作业优先的贪心选择策略可以设计出解多机调度问题的较好的近似算法。 按此策略，当 nm时，只要将机器i的0, ti时间区间分配给作业i即可，算法只需要O(1)时间。 当nm时，首先将n个作业依其所需的处理时间从大到小排序。然后依此顺序将作业分配给空闲的处理机。算法所需的计算时间为O(nlogn)。,例如，设7个独立作业1,2,3,4,5,6,7由3台机器M1，M2和M3加工处理。各作业所需的处理时间分别为2,14,4,16,6,5,3。按算法greedy产生的作业调度如下图所示，所需的加工时间为17。,6.4.1 问题描述,两路合并外排序算法通过反复执行将两个有序子文件合并成一个有序文件的操作，最终将n个长度不等的有序子文件合并成一个有序文件。 合并n个有序子文件成为一个有序文件的合并过程可以有多种方式，称为合并模式。 在整个合并过程中，需从外存读写的记录数最少的合并方案称为最佳合并模式（optimal merge pattern）。,6.4 最佳合并模式,例64 设有5个有序子文件（F1,F2,F3,F4,F5），其长度分别为（20，30，30，10，5）。现通过两两合并将其合并成一个有序文件。,带权外路径长度是针对扩充二叉树而言的。扩充二叉树（extended binary tree）中除叶子结点外，其余结点都必须有两个孩子。扩充二叉树的带权外路径长度（weighted external path length）定义为：,6.4.2 贪心法求解,两路合并最佳模式问题的最优量度标准为带权外路径长度最小。,两路合并最佳模式的贪心算法简述如下： 设Ww0,w1 ,wn1是n个有序文件的长度；以每个权值作为根结点值，构造n棵只有根的二叉树； 选择两棵根结点权值最小的树，作为左右子树构造一棵新二叉树，新树根的权值是两棵子树根的权值之和； 重复第2步，直到合并成一棵二叉树为止。,【程序66】两路合并最佳模式的贪心算法 template struct HNode /优先权队列中的元素的类型 operator T()const return weight; BTNode *ptr; T weight; ;,template BTNode* CreateHfmTree (T* w,int n) /w 为一维数组保存n个权值 PrioQueue pq(2*n-1); BTNode*p;HNode a,b; for (int i=0;i(wi); a.ptr=p;a.weight=wi; pq.Append(a); ,for (i=1;i(a.weight,a.ptr,b.ptr); a.ptr=p; pq.Append(a); pq.Serve(a); return a.ptr; ,6.4.3 算法正确性,定理64 设有n个权值W=w0,w1 ,wn1作为外结点的权值，构造两路合并树的贪心算法将生成一棵具有最小带权外路径长度的二叉树。,6.5.1 问题描述,问题 一个无向连通图的生成树是一个极小连通子图，它包括图中全部结点，并且有尽可能少的边。 一棵生成树的代价是树中各条边上的代价之和。一个网络的各生成树中，具有最小代价的生成树称为该网络的最小代价生成树（minimum-cost spanning tree）。,6.5 最小代价生成树,网络的最小生成树在实际中有广泛应用。例如，在设计通信网络时，用图的顶点表示城市，用边(v,w)的权cvw表示建立城市v和城市w之间的通信线路所需的费用，则最小生成树就给出了建立通信网络的最经济的方案。,6.5.2 贪心法求解,最优量度标准 选择使得迄今为止已入选S中边的代价之和增量最小的边 克鲁斯卡尔算法的贪心准则是：按边代价的非减次序考察E中的边，从中选择一条代价最小的边e=(u,v)。 普里姆算法的贪心准则是：在保证S所代表的子图是一棵树的前提下选择一条最小代价的边e=(u,v)。,最小生成树性质 用贪心算法设计策略可以设计出构造最小生成树的有效算法。将介绍的构造最小生成树的Prim算法和Kruskal算法都可以看作是应用贪心算法设计策略的例子。尽管这两个算法做贪心选择的方式不同，它们都利用了下面的最小生成树性质： 设G=(V,E)是连通带权图，U是V的真子集。如果(u,v)E，且uU，vV-U，且在所有这样的边中，(u,v)的权cuv最小，那么一定存在G的一棵最小生成树，它以(u,v)为其中一条边。这个性质有时也称为MST性质。,【程序67】最小代价生成树的贪心算法 ESetType SpanningTree(ESetType E, int n) /G=(V,E)为无向图 ESetType S=; int u,v,k=0; EType e; while (kn-1 ,6.5.3 Prim(普里姆)算法,【程序68】普里姆算法 template struct ENode /带权图的边结点 int adjVex; T w; ENode* nextArc; ;,template class Graph public: Graph (int mSize); void Prim(); protected: void Prim(int k,int* nearest,T* lowcost); ENode* a; int n; ;,template void Graph:Prim(int s) /公有成员函数 int* nearest=new intn,*lowcost=new intn; Prim(s,nearest,lowcost); for(int j=0;jn;j+) cout“(“nearestj“,“ j“,“lowcostj“) “; coutendl; delete nearest; delete lowcost; ,template void Graph:Prim(int k, int* nearest,T* lowcost) /私有成员函数 bool* mark=new booln; ENode *p; if (kn-1) throw OutofBounds; for (int i=0;in;i+) nearesti=-1;marki=false; lowcosti=INFTY; lowcostk=0; nearestk=k; markk=true;,for (i=1;inextArc) int j= p-adjVex; if (!markj ) 普里姆算法的运行时间是O(n2)。,6.5.4 克鲁斯卡尔算法,克鲁斯卡尔算法从边的集合E中，按照边的权值从小到大的次序依次选取边加以考察。 template struct eNode operator T ()const return w; int u,v; T w; ;,【程序69】克鲁斯卡尔算法 template void Graph:Kruskal( PrioQueue ,while (kn-1 克鲁斯卡尔算法的时间复杂度为 O（elog e）。,6.5.5 算法正确性,定理65 设图G=（V，E）是一个带权连通图，U是V的一个真子集。若边(u,v)E是所有uU, vV-U的边中权值最小者，那么一定存在G的一棵最小代价生成树T=(V,S)，(u,v)S。这一性质称为MST（minimum spanning tree）性质。,定理66 普里姆算法和克鲁斯卡尔算法都将产生一个带权无向连通图的最小代价生成树。,6.6.1 问题描述,单源最短路径问题是：给定带权的有向图G=(V,E)和图中结点sV，求从s到其余各结点的最短路径，其中，s称为源点。,6.6 单源最短路径,6.6.2 贪心法求解,迪杰斯特拉（Dijkstra） 算法 首先求得长度最短的一条最短路径，再求得长度次短的一条最短路径，依此类推，直到从源点到其它所有结点之间的最短路径都已求得为止。,6.6.3 迪杰斯特拉算法,【程序610】迪杰斯特拉算法 template class MGraph public: MGraph(int mSize); void Dijkstra(int s,T* ,private: int Choose(int* d, bool* s); T*a; int n; ;,template int MGraph:Choose(int* d, bool* s) int i,minpos; T min; min=INFTY; minpos=-1; for (i=1;in;i+) if (dimin ,template void MGraph:Dijkstra(int s, T* ,inSs=true; ds=0; for (i=1;in-1;i+) k=Choose(d,inS); inSk=true; for (j=0; jn; j+) if (!inSj ,6.6.4 算法正确性,定理67 已知带权有向图G=(V,E)，其源点为s，迪杰斯特拉算法使得对所有i，iV-s，di(s,i)，且一旦di=