《第3章 贪心算法》由会员分享，可在线阅读，更多相关《第3章 贪心算法（83页珍藏版）》请在文档大全上搜索。
1、第三章 贪心（贪婪）算法本章主要知识点（46学时）： 3.1 活动安排问题 3.2 贪心算法的基本要素 3.3 最优装载 3.4 哈夫曼编码 3.5 单源最短路径 3.6 最小生成树 3.7 多机调度问题引言【找零问题】希望用数目最少的硬币找零66美分假设提供了数目不限的面值为2 5美分、1 0美分、5美分、及1美分的硬币。 找给你66枚1美分硬币？假设需要找67美分，25+25+10+5+1+1，共6枚。引言在一些情况下，即使贪心算法不能得到在一些情况下，即使贪心算法不能得到整体最优整体最优解解，其最终结果却是，其最终结果却是最优解的很好近似最优解的很好近似。假设提供了数目不限的面值为1 1
2、美分、5美分及1美分的硬币？找零15美分 11+1+1+1+1，共5枚（贪心算法） 5+5+5，共3枚（非贪心算法）引言总是做出在当前看来最好的选择并不从整体最优考虑局部最优选择。贪心法的基本思路：从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。引言贪心法存在的问题：1. 不能保证求得的最后解是最佳的；2. 不能用来求最大或最小解问题；3. 只能求满足某些约束条件的可行解的范围。 3.1 活动安排问题【活动安排问题】就是要在所给的活动集合中选出最大的相容活动子集合。该问题要求高效地安排一系列争用某一公共资源的活动。3.1
3、 活动安排问题设有设有n个活动的集合个活动的集合E=1,2,n使用同一资源，使用同一资源，同一时间内只有一个活动能使同一时间内只有一个活动能使用这一资源。用这一资源。每个活动每个活动i都有一个要求使用该资源的起始时都有一个要求使用该资源的起始时间间si和一个结束时间和一个结束时间fi（si fi） 。如果选择了。如果选择了活动活动i，则它在半开时间区间，则它在半开时间区间si, fi)内占用资源。内占用资源。若区间若区间si, fi)与区间与区间sj, fj)不相交，则称不相交，则称活动活动i与活动与活动j是相容的是相容的。即。即sjfi时，活动时，活动i与活动与活动j相相容容。复杂性分析由于
4、输入的活动以其完成时间的升序排列，所以算法greedySelector每次总是选择最早完成时间的相容活动加入集合A中。为未安排活动留下尽可能多的时间。该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的活动。一个实例例：设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：i12345678910 11si130535688212fi45678910 11 12 13 14说明若被检查的活动i的开始时间Si小于最近选择的活动j的结束时间fj，则不选择活动i，否则选择活动i加入集合A中。贪心算法并不总能求得问题的整体最优解。对于活动安排问题，贪心算法greedyS
5、elector却总能求得的整体最优解，即它最终所确定的相容活动集合A的规模最大。这个结论可以用数学归纳法证明。贪心算法描述public static int greedySelector(int s, int f, boolean a) int n=s.length-1;a1=true; /选择最早结束活动选择最早结束活动int j=1;/j表示已安排活动编号表示已安排活动编号int count=1;/已安排活动数已安排活动数for (int i=2;i=fj) ai=true;j=i;count+; else ai=false;return count;各活动的起始时间和结束时间存储于数组s
6、和f中且按结束时间的非减序排列 复杂性分析当输入的活动已按结束时间的升序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按结束时间升序排列，可以用O(nlogn)的时间重排。3.2 贪心算法的基本要素对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢?这个问题很难给予肯定的回答。但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有2个重要的性质： 贪心选择性质 最优子结构性质1.贪心选择性质所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。动态规划算法通常以自底向上的方式解各
7、子问题，而贪心算法则通常以自顶向下的方式进行，每作一次贪心选择就将所求问题简化为规模更小的子问题。3.2 贪心算法的基本要素2.最优子结构性质当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。3.2 贪心算法的基本要素0-1背包问题与背包问题 0-1背包问题背包问题： 给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容重量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大？ 在选择装入背包的物品时，对每种物品i只有2种选择，即装入-不装入 背包问题背包问题: 与0-1背包问题类
8、似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1in。 这2类问题都具有最优子结构性质，但背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。贪心算法的数据选择策略1、以、以价值价值为量度标准为量度标准按价值从高到低的次序将物品一件件放到背包按价值从高到低的次序将物品一件件放到背包中中。2、以以重量重量作为量度作为量度按物品重量的从清到重次序来把物品放入背包。按物品重量的从清到重次序来把物品放入背包。3、采用、采用单位价值单位价值为度量标准为度量标准使物品的装入次序使物品的装入次序按按pi/wi比值的从大到小比值的从大到小来考来考虑。虑。用
9、贪心策略求解背包问题时，首先要选出用贪心策略求解背包问题时，首先要选出最最优的度量标准。优的度量标准。考虑下列情况的背包问题考虑下列情况的背包问题 n=3,M=20,(p1,p2,p3)=(25,24,15), (w1,w2,w3)=(18,15,10) 其中的其中的4个可行解是：个可行解是：(x1,x2,x3)wi xipixi(1/2,1/3,1/4)16.524.25策略1 (1,2/15,0)2028.2策略2 (0,2/3,1)2031策略3 (0,1,1/2)2031.5背包问题算法思路算法思路1).将各物体按将各物体按单位价值单位价值由高到低排序；由高到低排序； 2).取价值最高
10、者放入背包；取价值最高者放入背包；3).计算背包剩余；计算背包剩余；4).重复重复2-3直到背包剩余直到背包剩余=0或物体全部装入背或物体全部装入背包为止。包为止。用贪心算法解背包问题的基本步骤void Knapsack(int n,float M,float v,float w,float x) Sort(n,v,w); /计算每种物品单位价值vi/wiint i;for (i=1;i=n;i+) xi=0;float c=M;for (i=1;ic) break;xi=1;c-=wi;if (i=n) xi=c/wi; /填满背包void 0-1-Knapsack(int n,float
11、M,float v,float w,float x) /不一定是最优解不一定是最优解 Sort(n,v,w); int i;for (i=1;i=n;i+) xi=0;float c=M;for (i=1;ic) break;xi=1;c-=wi;0-1背包问题贪心选择之所以不能得到最优解：因为无法保证最终能将背包装满，部分闲置的背包空间使总价值降低了。思考题在杂货店比赛中你获得了第一名，奖品是一车免费杂货。店中有N种不同的货物。规则规定从每种货物中最多只能拿一件，车子的容量为C，物品i需占用wi的空间，价值为pi。你的目标是使车中装载的物品价值最大。当然，所装货物不能超过车的容量，且同一种物
12、品不得拿走多件。如何选择量度标准才能找到最优解？若N=3, w=100,10,10,p=20,15,15,C=105。利用价值贪心准则时所得结果是否是最优？问题: 设一个由N个城市v1,v2,vn组成的网络, ci,j 为从vi 到vj的代价不妨设ci,j = cj,i ,且ci,i= .一推销员要从某城市出发经过每城市一次且仅一次后返回出发地，如何选择路线使代价最小。抽象描述抽象描述:抽象为一个无向图G, G中每边的权值表示这段线路的代价. 问题转化为求一条最佳周游路线:从一点出发,经过每点一次且仅一次并返回原点,且该路线的总代价最小.思考题-旅行商问题(Traveling Salesman
13、 Problem)12751443241274135323C=费用矩阵思考题-旅行商问题(货郎担问题)在图中选一条代价最小的边。为了选择下一条边，先要检查一下候选边与已选入的边之间是否满足以下两点： 1)不会有三条边(候选边及已入选边)与同一顶点相关联。 2)不会使入选边形成回路，除非入选边的个数已等于图中的顶点总数。在满足以上两点的候选边中，挑选最短的边作为入选边。如此做下去，直到得到一个经过所有顶点的回路。最后求得的回路是最后求得的回路是125341，代价是，代价是14。实际图实际图1-1最小代价的回路是最小代价的回路是12543一一1，代价是，代价是10。输入:城市的数目n,代价矩阵c=
14、c(1.n,1.n).输出: 最小代价路线1. tour:=0; / tour 纪录路线/2. cost:=0; / cost 纪录到目前为止的花费/3. v:=N; / N为起点城市, v为当前出发城市/4. for k:=1 to N-1 do 5. tour:= tour+(v,w) /(v,w)为从v到其余城市代价中值最小的边/6. cost:= cost+c(v,w) 7 v:=w8 tour:= tour+(v,N)9 cost:= cost+c(v,N) print tour, cost 算法的最坏时间复杂性为O(n2)*该算法不能求的最优解.思考题-旅行商问题(货郎担问题)3.
15、3 最优装载有一批集装箱要装上一艘载重量为C的轮船。其中集装箱i的重量为Wi。要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。问题可形式化描述为其中变量xi=0表示不装入集装箱i，xi=1表示装入集装箱i。nixcxwxiniiinii110max11，3.3 最优装载例例设设N=8,w1，w8=100, 200, 50, 90, 150, 50, 20, 80，C=400。所考察货箱的次序为所考察货箱的次序为 t1.8=7, 3, 6, 8, 4, 1, 5, 2。货箱。货箱7, 3, 6, 8, 4, 1的总重量为的总重量为390个单位且已被装载个单位且已被装载, 剩下的装
16、载能力为剩下的装载能力为10 ,小于任意货箱小于任意货箱.所以得到解所以得到解x1,.x8= 1, 0, 1, 1, 0, 1, 1, 1算法思路算法思路 将装船过程划为多步选择，每步装一个将装船过程划为多步选择，每步装一个货箱，每次货箱，每次从剩下的货箱中选择重量最轻的货箱从剩下的货箱中选择重量最轻的货箱.如如此下去直到所有货箱均装上船或船上不能再容纳其此下去直到所有货箱均装上船或船上不能再容纳其他任何一个货箱。他任何一个货箱。3.3 最优装载算法描述最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略，可产生最优解。void Loading(int x, Type w, Type
17、 c, int n) int *t = new int n+1;Sort(w, t, n); /按货箱重量排序按货箱重量排序O(nlogn)for (int i = 1; i = n; i+) xi = 0; /O(n)for (int i = 1; i = n & wti = c; i+) xti = 1; c -= wti; /调整剩余空间调整剩余空间思考设设N=8,w1，w8=100, 200, 50, 90, 150, 50, 20, 80，C=400。编程求t1.8.3.4 哈夫曼编码哈夫曼编码是用于数据文件压缩的十分有效的编码方法。哈夫曼编码压缩率通常在20%90%之间。哈夫曼编码
18、算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长。3.4 哈夫曼编码例如一个包含例如一个包含100,000个字符的文件，各字符出现频个字符的文件，各字符出现频率不同，如下表所示。率不同，如下表所示。abcdef频率频率(千次千次)fc4513121695定长码定长码000001010011100101变长码变长码010110011111011100定长编码需要定长编码需要300,000位位按表中变长编码方案，文件的总码长为：按表中变长编码方案，文件的总码长为：（451+133+123+1
19、63+94+54）1000=224,000比定长码方案比定长码方案总码长少约总码长少约25%。1.前缀码对每一个字符规定一个对每一个字符规定一个0,1串作为其代码，并串作为其代码，并要求任一字符的代码都不是其它字符代码的要求任一字符的代码都不是其它字符代码的前缀。这种编码称为前缀。这种编码称为前缀码前缀码。编码的前缀性质可以使译码方法非常简单。编码的前缀性质可以使译码方法非常简单。表示最优前缀码的二叉树总是一棵表示最优前缀码的二叉树总是一棵完全二叉完全二叉树树，即树中任一结点都有，即树中任一结点都有2个儿子结点。个儿子结点。平均码长定义为：平均码长定义为：码长: )()()()(cdcdcfT
20、BTTCc使平均码长达到最小的前缀码编码方案称为使平均码长达到最小的前缀码编码方案称为给定编码字符集给定编码字符集C的最优前缀码。的最优前缀码。2.构造哈夫曼编码哈夫曼提出构造最优前缀码的贪心算法哈夫曼提出构造最优前缀码的贪心算法哈夫曼算法以哈夫曼算法以自底向上的方式构造自底向上的方式构造表示最优表示最优前缀码的二叉树前缀码的二叉树T。算法以算法以|C|个叶结点开始，执行个叶结点开始，执行|C|1次的次的“合并合并”运算后产生最终所要求的树运算后产生最终所要求的树T。3.构造哈夫曼树构造构造最优二叉树最优二叉树的具体算法如下：的具体算法如下： 与与n个权值个权值w1,w2,.,wn对应的对应的
21、n个结点构成个结点构成n棵棵二叉树组成的二叉树组成的森林森林F=T1,T2,.,Tn,其中每棵二叉其中每棵二叉树树Ti(1=i=n)都有一个权值为都有一个权值为wi的根结点，其左的根结点，其左右子树均为空；右子树均为空； 在森林在森林F中中选出两棵选出两棵根结点根结点的的权值最小权值最小的树的树作为作为一棵新树的左右子树，且置新树的附加根结点的权一棵新树的左右子树，且置新树的附加根结点的权值为其左右子树上根结点的权值之和；值为其左右子树上根结点的权值之和； 从从F中删除这两棵树，同时把新树加入中删除这两棵树，同时把新树加入F中；中； 重复重复(2)和和(3)，直到，直到F中只含有一棵树为止。此
22、树中只含有一棵树为止。此树便是哈夫曼树。便是哈夫曼树。算法说明huffmanTree中，编码字符集中每一字符c的频率是f(c)。以f为键值的优先队列Q用在贪心选择时有效地确定算法当前要合并的2棵具有最小频率的树。一旦2棵具有最小频率的树合并后，产生一棵新的树，其频率为合并的2棵树的频率之和，并将新树插入优先队列Q。经过n1次的合并后，优先队列中只剩下一棵树，即所要求的树T。算法huffmanTree用最小堆实现优先队列Q。初始化优先队列需要O(n)计算时间，由于最小堆的removeMin和put运算均需O(logn)时间，n1次的合并总共需要O(nlogn)计算时间。因此，关于n个字符的哈夫曼
23、算法的计算时间为O(nlogn) 。3.5 单源最短路径(Single-Source Shortest-Paths Problem) 给定带权有向图G =(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。单源最短路径问题：已知图G（V，E），找出从某给定的源结点SV到V中的每个结点的最短路径。3.5 单源最短路径3.5.1 Dijkstra算法Dijkstra算法是解单源最短路径问题的贪心算法。基本思想：设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。特殊路径设u是G的某一个顶点，把从源到u且中间只经过S中顶点的
24、路称为从源到u的特殊路径，用数组Di记录顶点i当前所对应的最短特殊路径长度。1、 Dijkstra算法的基本思想设S为最短距离已确定的顶点集（红点集）V-S是最短距离尚未确定的顶点集（蓝点集）。初始化初始化 最初只有源点s的最短距离是已知的(D(s)=0)，故红点集S=s 。重复以下工作，重复以下工作，按按路径长度递增路径长度递增次序产生各顶点最短路次序产生各顶点最短路径径 在当前蓝点集中选择一个Di最小的蓝点扩充到红点集，更新其余蓝点集D 值。 当蓝点集中仅剩下最短距离为的蓝点，或者所有蓝点已扩充到红点集时，s到所有顶点的最短路径就求出来了。一个实例Dijkstra(G，D，s) /Dijk
25、stra 算法算法 O(V2) /初始化操作初始化操作 S=s；Ds=0； for( all i V-S ) Di=Gsi； /O(V) /扩充红点集扩充红点集 for (i=1;iDk+Gkj) Dj=Dk+Gkj； /设置初始的红点集及最短距离设置初始的红点集及最短距离/最多扩充最多扩充V-1V-1个蓝点到红点集个蓝点到红点集 /O(V)/O(V) /在蓝点集找特殊距离在蓝点集找特殊距离最小的顶点最小的顶点k k/蓝点集中所有点的特殊蓝点集中所有点的特殊距离均为距离均为, ,表示这些顶表示这些顶点的最短路径不存在点的最短路径不存在/将蓝点将蓝点k k扩充到红点集扩充到红点集/调整剩余蓝点的
26、特殊距离调整剩余蓝点的特殊距离 /O(V)/O(V)#define VEX 5/定义结点的个数定义结点的个数#define maxpoint 100double graphmaxpoint= 0 , 10 , -1 , 30 , 100 , -1 , 0 , 50 , -1 , -1 , -1 , -1 , 0 , -1 , 10 , -1 , -1 , 20 , 0 , 60 , -1 , -1 , -1 , -1 , 0 ; /邻接矩阵，邻接矩阵，-1代表节点间无边相连代表节点间无边相连int Rmaxpoint=0,Bmaxpoint;int DVEX,PVEX;/定义数组定义数组D用来
27、存放结点特殊用来存放结点特殊距离，距离，P数组存放父亲结点数组存放父亲结点/初始时，红点集中仅有源结点初始时，红点集中仅有源结点0R0=1; B0=0;for(int i=1;iVEX;i+) /初始化蓝点集节点初始化蓝点集节点Bi=1;/对数组对数组D、P进行初始化进行初始化 for(i=0;iVEX;i+)Di=graph0i; if(Di!=-1) Pi=0; else Pi=-1;for(int k=1;kVEX;k+) /每次从蓝点集中取出具有最短特殊路长每次从蓝点集中取出具有最短特殊路长度的结点度的结点min for(int min=0;Bmin=0;) min+; for(int
28、 j=min;jVEX;j+) /求蓝点集结点最小下标元素求蓝点集结点最小下标元素if(Dj!=-1&DjDmin&Bj=1) min=j; coutmin=min ; /将具有最短特殊路长度的结点将具有最短特殊路长度的结点min添加到红点集中添加到红点集中 Rmin=1; Bmin=0; /对数组对数组D作必要的修改作必要的修改 for(j=1;jDmin+graphminj|Dj=-1) Dj=Dmin+graphminj; /每次迭代求最小值，最后每次迭代求最小值，最后一次即为到源点的最短路径一次即为到源点的最短路径 Pj=min; 3.5.2 Dijkstra算法Relax描述du:s
29、u的距离的距离 pu:记录前一节点记录前一节点Relax松弛算法松弛算法Init-single-source(G,s) for each vVG dodv= pv=NIL ds=0, ps=NILRelax(u,v,w) if dvdu+w(u,v)then dv=du+wu,v pv=u 算法描述dijkstra(G,w,s)1. Init-single-source(G,s) /O(v)2. S=s 3. Q=VG-S4.while Q do u=min(Q) /用数组用数组O(V) S=Su Q=VG-S for each vadju & v Q /O(E) do Relax(u,v,w
30、)3.5.3 Bellman-Ford算法 dijkstra算法的前提是算法的前提是所有边是正的所有边是正的 Bellman-Ford算法算法允许负边允许负边的的：不能包含：不能包含()，如下，如下图所示。图所示。20117-2(c)3.5.3 Bellman-Ford算法 dijkstra算法的前提是算法的前提是所有边是正的所有边是正的 Bellman-Ford算法算法允许负边允许负边(1) 初始化：将除源点外的所有顶点的最短距离估计初始化：将除源点外的所有顶点的最短距离估计值值 dv +, ds 0;(2) 迭代求解：反复对边集迭代求解：反复对边集E中的每条边进行松弛操中的每条边进行松弛操
31、作，使得顶点集作，使得顶点集V中的每个顶点中的每个顶点v的最短距离估的最短距离估计值逐步逼近其最短距离；（运行计值逐步逼近其最短距离；（运行|v|-1次）次）(3) 检验负权回路：如果存在负环，则算法返回检验负权回路：如果存在负环，则算法返回false，表明问题无解；否则算法返回表明问题无解；否则算法返回true，并且从源点，并且从源点可达的顶点可达的顶点v的最短距离保存在的最短距离保存在 dv中。中。3.5.3 Bellman-Ford算法思想dijkstra算法的前提是所有边是正的Bellman-Ford算法允许负边1. Init-single-source(G,s) 2. for i 1
32、 to |VG| - 1 /O(V) 3. do for each edge (u, v) EG/O(E)4. do RELAX(u, v, w) 5. for each edge (u, v) EG /O(E)6. do if du + w(u, v) dv 7. then return FALSE /存在负环8. return TRUE存在负权回路的图是不能求两点间最短路径，因为存在负权回路的图是不能求两点间最短路径，因为只要在负权回路上不断兜圈子，所得的最短路长度只要在负权回路上不断兜圈子，所得的最短路长度可以任意小。可以任意小。为从源点为从源点v到终点到终点u的只经过一条边的最短的只经
33、过一条边的最短路径长度，并有路径长度，并有dist 1 u =Edgevu；为从源点为从源点v到达终点到达终点u的最的最短路径长度；短路径长度；为从源点为从源点v出发出发到达终点到达终点u的最短路径长度；的最短路径长度； 为从源点为从源点v出发出发到达终点到达终点u的最短路径长度；的最短路径长度；算法的最终目的是计算出算法的最终目的是计算出dn-1 u，为源点，为源点v到到顶点顶点u的最短路径长度。的最短路径长度。 递推公式递推公式(求顶点求顶点u到源点到源点v的最短路径的最短路径)： = = min , , j=0,1,n-1,ju461230565-2-25-1-1133(c)kdk 0d
34、k1d k2d k3dk 4d k5dk 610655205303544013545013504601350436/3/15/35/5/2/0/7/5/3/4无负环312056-2-11kdk 0dk1d k2d k31065205302验证负环验证负环0130有负环Dijkstra算法与Bellman算法的区别Dijkstra算法在求解过程中，源点到集合算法在求解过程中，源点到集合S内内各顶点的最短路径一旦求出，则之后不变了，各顶点的最短路径一旦求出，则之后不变了，修改的仅仅是源点到修改的仅仅是源点到T集合中各顶点的最短集合中各顶点的最短路径长度。路径长度。Bellman算法在求解过程中，每
35、次循环都要算法在求解过程中，每次循环都要修改所有顶点的修改所有顶点的d ，也就是说源点到各顶，也就是说源点到各顶点点最短路径长度一直要到最短路径长度一直要到Bellman算法结束算法结束才确定下来才确定下来。3.5.4 其他最短路径问题其他最短路径问题单目标单目标最短路径问题最短路径问题(Single-Destination Shortest-Paths Problem)：找出图中每一顶点v到某指定顶点u的最短路径。只需将图中每条边反向，就可将这一问题变为单源最短路径问题，单目标u变为单源点u。单顶点对单顶点对间最短路径问题间最短路径问题(Single-Pair Shortest-Paths
36、Problem)：对于某对顶点u和v，找出从u到v的一条最短路径。显然，若解决了以u为源点的单源最短路径问题，则上述问题亦迎刃而解。而且从数量级来说，两问题的时间复杂度相同。所有顶点对所有顶点对间最短路径问题间最短路径问题(All-Pairs Shortest-Paths Problem)：对图中每对顶点u和v，找出u到v的最短路径问题。这一问题可用每个顶点作为源点调用一次单源最短路径问题算法予以解决。3.6 最小生成树设G =(V,E)是无向连通带权图，即一个网络。E中每条边(v,w)的权为cvw。如果G的子图G是一棵包含G的所有顶点的树，则称G为G的生成树。生成树上各边权的总和称为该生成树
37、的耗费。在G的所有生成树中，耗费最小的生成树称为G的最小生成树。网络的最小生成树在实际中有广泛应用。例如，在设计通信网络时，用图的顶点表示城市，用边(v,w)的权cvw表示建立城市v和城市w之间的通信线路所需的费用，则最小生成树就给出了建立通信网络的最经济的方案。1、最小生成树性质用贪心算法设计策略可以设计出构造最小生成树的有效算法。Prim算法和Kruskal算法2个算法都利用了最小生成树性质：最小生成树性质：设G=(V，E)是一个连通网络，U是顶点集V的一个真子集。若(u，v)是G中所有的一个端点在U(uU)里、另一个端点不在U(即vV-U)里的边中，具有最小权值的一条边，则一定存在G的一
38、棵最小生成树包括此边(u，v)。这个性质称为MST（Minimum Spanning Tree ）性质。1、最小生成树性质MST性质的证明： 约定：集合U中的顶点红色顶点V-U中的顶点蓝色顶点连接红点和蓝点的边紫色边权最小的紫边称为轻边(即权重最“轻”的边)。用反证法证明MST性质1、最小生成树性质假设G中任何一棵MST都不含轻边(u，v)。则若T是G的一棵MST，则它不含此轻边。由于T是包含了G中所有顶点的连通图，所以T中必有一条从红点u到蓝点v的路径P，且P上必有一条紫边(u ，v )连接红点集和蓝点集，否则u和v不连通。当把轻边(u，v)加入树T时，该轻边和P必构成了一个回路。删去紫边(
39、u ，v )后回路亦消除，由此可得另一生成树T 。 T 和T的差别仅在于T用轻边(u，v)取代了T中权重可能更大的紫边(u ，v )。因为w(u，v)w(u ，v )，所以 w(T)=w(T)+w(u，v)-w(u，v)w(T)故T亦是G的MST，它包含边(u，v)，这与假设矛盾。 所以，MST性质成立。2、Prim（普里姆）算法设G=(V,E)是连通带权图，V=1,2,n。Prim算法构造G的最小生成树基本思想：初始U=1只要U是V的真子集，就作如下的贪心选择：选取满足条件iU，jV-U，且cij最小的边，将顶点j添加到U中。这个过程一直进行到U=V时为止。在这个过程中选取到的所有边恰好构成
40、G的一棵最小生成树。2、Prim（普里姆）算法关键点思想是：将定点集合分成两个U，V-U（初始状态U中只有一个Uo），再加上一个TE集合来表示最小生成树边的集合。2、Prim（普里姆）算法例如，对于右图中的带权图，按Prim算法选取边的过程如图所示。2、Prim（普里姆）算法PrimMST(G，T，r) /求图G的以r为根的MST，结果放在T中 T=；U=1; while(U!=V) /O(V) (i,j)=iU，jV-U，且cij最小的边/O(V) T=T (i，j) /轻边 (i，j) 加入T U=U j; / 节点j 加入U，变为红点 http:/ 2、Prim（普里姆）算法如何有效地找
41、出满足条件iU, jV-U，且权cij最小的边(i,j)？ 较简单的办法是设置2个数组closest和lowcost。 在Prim算法执行过程中，先找出V-U中使lowcost值最小的顶点j，然后根据数组closest选取边(j,closestj)，将j添加到U中，并对closest和lowcost作必要的修改。3、Kruskal（克鲁斯卡尔）算法Kruskal算法构造最小生成树的基本思想：(1)新建图G，G中拥有原图中相同的节点，但没有边(2)将原图中所有的边按权值从小到大排序(3）从权值最小的边开始，如果这条边连接的两个节点于图G中不在同一个连通分量中，则添加这条边到图G中(4)重复(3)
42、，直至图G中所有的节点都在同一个连通分量中3、Kruskal（克鲁斯卡尔）算法例如，对前面的连通带权图，按Kruskal算法顺序得到的最小生成树上的边如图所示。3、Kruskal（克鲁斯卡尔）算法（1）算法思想T的初始状态 只有n个顶点而无边的森林T=(V， )按边长递增的顺序选择E中的n-1安全边(u，v)并加入T，生成MST注意： 安全边指两个端点分别是森林T里两棵树中的顶点的边。加入安全边，可将森林中的两棵树连接成一棵更大的树 因为每一次添加到T中的边均是当前权值最小的安全边，MST性质也能保证最终的T是一棵最小生成树 3、Kruskal（克鲁斯卡尔）算法MST-Kruskal (G)
43、/求连通网G的一棵MST T=(V，)； /初始化，T是只含n个顶点不包含边的森林/依权值递增序对E(G)中的边排序，并设结果在E0.e-1中 O(Elog(E)sort the edges of E by non-decreasing weight w for(i=0;ie;i+) /e为图中边总数，O(E) 取第i条边（u,v） if u和v分别属于T中两棵不同的树 T=T(u，v)；/(u，v)是安全边，将其加入T中 return T；说明有关说明： 该算法的时间复杂度为O(ElogE)。 Kruskal算法的时间主要取决于边数。它较适合于稀疏图。 3.7 多机调度问题设有 n 个独立的
44、作业 1 , 2 , . , n ，由 m 台相同的机器进行加工处理。作业 i 所需的处理时间为 ti。约定： 任何作业可以在任何一台机器上加工处理，但未完工前不允许中断处理。 任何作业不能拆分成更小的作业。多机调度问题要求给出一种作业调度方案，使所给的 n 个作业在尽可能短的时间内由 m 台机器加工处理完成。3.7 多机调度问题这个问题是NP完全问题(Non-deterministic Polynomial Complete Problem) ，也即是多项式复杂程度的非确定性问题 ，到目前为止还没有有效的解法。对于这一类问题,用贪心选择策略有时可以设计出较好的近似算法。非确定性问题:无法按部
45、就班直接地计算出来。找大质数的问题。没有一个公式，一套公式，就可以一步步推算出来，下一个质数应该是多少呢？大的合数分解质因数的问题，有没有一个公式，把合数代进去，就直接可以算出，它的因子各自是多少？也没有这样的公式。3.7 多机调度问题采用最长处理时间作业优先的贪心选择策略可以设计出解多机调度问题的较好的近似算法。按此策略，当nm时(作业数m时，首先将n个作业依其所需的处理时间从大到小排序。然后依此顺序将作业分配给空闲的处理机。算法所需的计算时间为O(nlogn)。一个实例例如，设7个独立作业1,2,3,4,5,6,7由3台机器M1，M2和M3加工处理。各作业所需的处理时间分别为2,14,4,
46、16,6,5,3。按算法greedy产生的作业调度如下图所示，所需的总加工时间为17。作业编号数据输入：首先输入 2 个正整数 n 和 m，分别表示有 n 个作业和 m台相同的机器。然后输入 n 个正整数，第 i 个数表示作业 i 所需的处理时间。#define N 10 /作业数作业数#define M 3 /机器数机器数static int timeN=2,8,18,32,50,72,98,128,182,200；int sM=0,0,0; /S数组存储每台机器当前已分配任务总耗时数组存储每台机器当前已分配任务总耗时void main() sort(time,N); /将处理时间从大到小排
47、序将处理时间从大到小排序 if(M=N) /作业数小于机器数作业数小于机器数 coutset_work1(time,N)endl; else coutset_work2(time,N)endl;/用选择法将处理时间从大到小排序，用选择法将处理时间从大到小排序，O(n2)void sort(int t,int n)for(int k=0;kn-1;k+) int j=k; for (int i=k; itj) j=i; int temp=tj;tj=tk;tk=temp; 当然，最好选O(nlogn)或O(n)时间复杂度算法。int set_work1(int t,int n) int m=0;
48、 for(int i=0;in;i+) /分派作业分派作业 sm+=ti;m+； return max(s,N);int set_work2(int t,int n) for(int i=0;in;i+) smin(M)+=ti; return max(s,M);int min(int m) int min=0; /min记录目前处理作业记录目前处理作业时间和时间和最小的最小的机器号机器号 for(int i=1;isi) min=i; return min;int max(int t,int num) /max函数求最长处理时间函数求最长处理时间 int max=t0; for(int i=1;inum;i+) if(max 0 ） i=1; /从串首开始找从串首开始找while (ilength(n)&(ni1)& (n1=0) delete(n,1); /删去串首可能产生的无删去串首可能产生的无用零用零输出输出n;
