第3章贪心算法

1第三章贪心（贪婪）算法本章主要知识点（4~6学时）：3.1活动安排问题3.2贪心算法的基本要素3.3最优装载3.4哈夫曼编码3.5单源最短路径3.6最小生成树3.7多机调度问题2引言【找零问题】希望用数目最少的硬币找零66美分假设提供了数目不限的面值为25美分、10美分、5美分、及1美分的硬币。找给你66枚1美分硬币？假设需要找67美分，25+25+10+5+1+1，共6枚。3引言在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。假设提供了数目不限的面值为11美分、5美分及1美分的硬币？找零15美分

11+1+1+1+1，共5枚（贪心算法）

5+5+5，共3枚（非贪心算法）4引言总是做出在当前看来最好的选择并不从整体最优考虑局部最优选择。贪心法的基本思路：

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

5引言贪心法存在的问题：

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

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

3.只能求满足某些约束条件的可行解的范围。63.1活动安排问题【活动安排问题】就是要在所给的活动集合中选出最大的相容活动子集合。该问题要求高效地安排一系列争用某一公共资源的活动。73.1活动安排问题设有n个活动的集合E={1,2,…,n}使用同一资源，同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi（si<fi）

。如果选择了活动i，则它在半开时间区间[si,fi)内占用资源。若区间[si,fi)与区间[sj,fj)不相交，则称活动i与活动j是相容的。即sj≥fi时，活动i与活动j相容。8复杂性分析由于输入的活动以其完成时间的升序排列，所以算法greedySelector每次总是选择最早完成时间的相容活动加入集合A中。为未安排活动留下尽可能多的时间。该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的活动。9一个实例例：设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：i1234567891011s[i]130535688212f[i]456789101112131410说明若被检查的活动i的开始时间Si小于最近选择的活动j的结束时间fj，则不选择活动i，否则选择活动i加入集合A中。贪心算法并不总能求得问题的整体最优解。对于活动安排问题，贪心算法greedySelector却总能求得的整体最优解，即它最终所确定的相容活动集合A的规模最大。这个结论可以用数学归纳法证明。11贪心算法描述publicstaticintgreedySelector(int[]s,int[]f,booleana[]){intn=s.length-1;a[1]=true;//选择最早结束活动intj=1;//j表示已安排活动编号intcount=1;//已安排活动数for(inti=2;i<=n;i++)//i表示待安排活动{if(s[i]>=f[j]){a[i]=true;j=i;count++;}elsea[i]=false;}returncount;}各活动的起始时间和结束时间存储于数组s和f中且按结束时间的非减序排列12复杂性分析当输入的活动已按结束时间的升序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按结束时间升序排列，可以用O(nlogn)的时间重排。133.2贪心算法的基本要素对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢?这个问题很难给予肯定的回答。但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有2个重要的性质：贪心选择性质最优子结构性质141.贪心选择性质所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，每作一次贪心选择就将所求问题简化为规模更小的子问题。3.2贪心算法的基本要素152.最优子结构性质当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。3.2贪心算法的基本要素160-1背包问题与背包问题0-1背包问题：给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容重量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大？在选择装入背包的物品时，对每种物品i只有2种选择，即装入----不装入背包问题:与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。这2类问题都具有最优子结构性质，但背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。17贪心算法的数据选择策略1、以价值为量度标准按价值从高到低的次序将物品一件件放到背包中。2、以重量作为量度按物品重量的从清到重次序来把物品放入背包。3、采用单位价值为度量标准使物品的装入次序按pi/wi比值的从大到小来考虑。用贪心策略求解背包问题时，首先要选出最优的度量标准。18考虑下列情况的背包问题n=3,M=20,(p1,p2,p3)=(25,24,15),(w1,w2,w3)=(18,15,10)其中的4个可行解是：(x1,x2,x3)∑wixi∑pixi(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背包问题19[算法思路]1).将各物体按单位价值由高到低排序；2).取价值最高者放入背包；3).计算背包剩余；4).重复2-3直到背包剩余=0或物体全部装入背包为止。用贪心算法解背包问题的基本步骤voidKnapsack(intn,floatM,floatv[],floatw[],floatx[]){Sort(n,v,w);//计算每种物品单位价值vi/wiinti;for(i=1;i<=n;i++)x[i]=0;floatc=M;for(i=1;i<=n;i++){if(w[i]>c)break;x[i]=1;c-=w[i];}if(i<=n)x[i]=c/w[i];

//填满背包}void0-1-Knapsack(intn,floatM,floatv[],floatw[],floatx[])//不一定是最优解{Sort(n,v,w);inti;for(i=1;i<=n;i++)x[i]=0;floatc=M;for(i=1;i<=n;i++){if(w[i]>c)break;x[i]=1;c-=w[i];}}0-1背包问题贪心选择之所以不能得到最优解：因为无法保证最终能将背包装满，部分闲置的背包空间使总价值降低了。22思考题在杂货店比赛中你获得了第一名，奖品是一车免费杂货。店中有N种不同的货物。规则规定从每种货物中最多只能拿一件，车子的容量为C，物品i需占用wi的空间，价值为pi。你的目标是使车中装载的物品价值最大。当然，所装货物不能超过车的容量，且同一种物品不得拿走多件。如何选择量度标准才能找到最优解？若N=3,w=[100,10,10],p=[20,15,15],C=105。利用价值贪心准则时所得结果是否是最优？23问题:

设一个由N个城市v1,v2,…vn组成的网络,ci,j为从vi到vj的代价不妨设ci,j

=cj,i,且ci,i=.一推销员要从某城市出发经过每城市一次且仅一次后返回出发地，如何选择路线使代价最小。抽象描述:抽象为一个无向图G,G中每边的权值表示这段线路的代价.问题转化为求一条最佳周游路线:从一点出发,经过每点一次且仅一次并返回原点,且该路线的总代价最小.思考题-旅行商问题(TravelingSalesmanProblem)C=费用矩阵24思考题-旅行商问题(货郎担问题)在图中选一条代价最小的边。为了选择下一条边，先要检查一下候选边与已选入的边之间是否满足以下两点：

1)不会有三条边(候选边及已入选边)与同一顶点相关联。

2)不会使入选边形成回路，除非入选边的个数已等于图中的顶点总数。在满足以上两点的候选边中，挑选最短的边作为入选边。如此做下去，直到得到一个经过所有顶点的回路。最后求得的回路是1—2—5—3—4—1，代价是14。实际图1-1最小代价的回路是1—2—5—4—3一1，代价是10。25输入:城市的数目n,代价矩阵c=c(1..n,1..n).输出:最小代价路线1.tour:=0;//tour纪录路线/2.cost:=0;//cost纪录到目前为止的花费/3.v:=N;//N为起点城市,v为当前出发城市/4.fork:=1toN-1do5.{tour:=tour+(v,w)//(v,w)为从v到其余城市代价中值最小的边/6.cost:=cost+c(v,w)7v:=w}8tour:=tour+(v,N)9cost:=cost+c(v,N)printtour,cost算法的最坏时间复杂性为O(n2)*该算法不能求的最优解.思考题-旅行商问题(货郎担问题)263.3最优装载有一批集装箱要装上一艘载重量为C的轮船。其中集装箱i的重量为Wi。要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。问题可形式化描述为其中变量xi=0表示不装入集装箱i，xi=1表示装入集装箱i。273.3最优装载[例]设N=8,[w1，…w8]=[100,200,50,90,150,50,20,80]，C=400。所考察货箱的次序为t[1..8]={7,3,6,8,4,1,5,2}。货箱7,3,6,8,4,1的总重量为390个单位且已被装载,剩下的装载能力为10,小于任意货箱.所以得到解[x1,...x8]=[1,0,1,1,0,1,1,1][算法思路]将装船过程划为多步选择，每步装一个货箱，每次从剩下的货箱中选择重量最轻的货箱.如此下去直到所有货箱均装上船或船上不能再容纳其他任何一个货箱。283.3最优装载算法描述最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略，可产生最优解。voidLoading(intx[],Typew[],Typec,intn){int*t=newint[n+1];Sort(w,t,n);//按货箱重量排序O(nlogn)for(inti=1;i<=n;i++)x[i]=0;//O(n)for(inti=1;i<=n&&w[t[i]]<=c;i++){x[t[i]]=1;c-=w[t[i]];}//调整剩余空间}29思考设N=8,[w1，…w8]=[100,200,50,90,150,50,20,80]，C=400。编程求t[1..8].303.4哈夫曼编码哈夫曼编码是用于数据文件压缩的十分有效的编码方法。哈夫曼编码压缩率通常在20%～90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长。313.4哈夫曼编码例如一个包含100,000个字符的文件，各字符出现频率不同，如下表所示。abcdef频率(千次)fc4513121695定长码000001010011100101变长码010110011111011100定长编码需要300,000位按表中变长编码方案，文件的总码长为：（45×1+13×3+12×3+16×3+9×4+5×4）×1000=224,000比定长码方案总码长少约25%。321.前缀码对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其它字符代码的前缀。这种编码称为前缀码。编码的前缀性质可以使译码方法非常简单。表示最优前缀码的二叉树总是一棵完全二叉树，即树中任一结点都有2个儿子结点。平均码长定义为：使平均码长达到最小的前缀码编码方案称为给定编码字符集C的最优前缀码。332.构造哈夫曼编码哈夫曼提出构造最优前缀码的贪心算法哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。算法以|C|个叶结点开始，执行|C|－1次的“合并”运算后产生最终所要求的树T。343.构造哈夫曼树构造最优二叉树的具体算法如下：与n个权值{w1,w2,...,wn}对应的n个结点构成n棵二叉树组成的森林F={T1,T2,...,Tn},其中每棵二叉树Ti(1<=i<=n)都有一个权值为wi的根结点，其左右子树均为空；在森林F中选出两棵根结点的权值最小的树作为一棵新树的左右子树，且置新树的附加根结点的权值为其左右子树上根结点的权值之和；从F中删除这两棵树，同时把新树加入F中；重复(2)和(3)，直到F中只含有一棵树为止。此树便是哈夫曼树。3536算法说明huffmanTree中，编码字符集中每一字符c的频率是f(c)。以f为键值的优先队列Q用在贪心选择时有效地确定算法当前要合并的2棵具有最小频率的树。一旦2棵具有最小频率的树合并后，产生一棵新的树，其频率为合并的2棵树的频率之和，并将新树插入优先队列Q。经过n－1次的合并后，优先队列中只剩下一棵树，即所要求的树T。算法huffmanTree用最小堆实现优先队列Q。初始化优先队列需要O(n)计算时间，由于最小堆的removeMin和put运算均需O(logn)时间，n－1次的合并总共需要O(nlogn)计算时间。因此，关于n个字符的哈夫曼算法的计算时间为O(nlogn)

。373.5单源最短路径(Single-SourceShortest-PathsProblem)给定带权有向图G=(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。单源最短路径问题：已知图G＝（V，E），找出从某给定的源结点S∈V到V中的每个结点的最短路径。383.5单源最短路径393.5.1Dijkstra算法Dijkstra算法是解单源最短路径问题的贪心算法。基本思想：设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。特殊路径设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，用数组D[i]记录顶点i当前所对应的最短特殊路径长度。401、Dijkstra算法的基本思想设S为最短距离已确定的顶点集（红点集）V-S是最短距离尚未确定的顶点集（蓝点集）。

①初始化

最初只有源点s的最短距离是已知的(D(s)=0)，故红点集S={s}。

②重复以下工作，按路径长度递增次序产生各顶点最短路径

在当前蓝点集中选择一个D[i]最小的蓝点扩充到红点集，更新其余蓝点集D[]值。

③当蓝点集中仅剩下最短距离为∞的蓝点，或者所有蓝点已扩充到红点集时，s到所有顶点的最短路径就求出来了。41一个实例Dijkstra(G，D，s)

//Dijkstra算法O(V2){//初始化操作

S={s}；D[s]=0；

for(alli∈V-S)D[i]=G[s][i]；//O(V)

//扩充红点集

for(i=1;i<V;i++)

{

D[k]=min{D[i]：alli∈V-S}；

if(D[k]==∞)return；

S=S∪{k}；

for(allj∈V-S)

if(D[j]>D[k]+G[k][j])D[j]=D[k]+G[k][j]；

}}//设置初始的红点集及最短距离//最多扩充V-1个蓝点到红点集//O(V)

//在蓝点集找特殊距离最小的顶点k//蓝点集中所有点的特殊距离均为∞,表示这些顶点的最短路径不存在//将蓝点k扩充到红点集//调整剩余蓝点的特殊距离//O(V)#defineVEX5//定义结点的个数#definemaxpoint100doublegraph[][maxpoint]={{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代表节点间无边相连intR[maxpoint]={0},B[maxpoint];intD[VEX],P[VEX];//定义数组D用来存放结点特殊距离，P数组存放父亲结点//初始时，红点集中仅有源结点0R[0]=1;B[0]=0;for(inti=1;i<VEX;i++)//初始化蓝点集节点B[i]=1;//对数组D、P进行初始化for(i=0;i<VEX;i++){D[i]=graph[0][i];if(D[i]!=-1)P[i]=0;elseP[i]=-1;}for(intk=1;k<VEX;k++)//每次从蓝点集中取出具有最短特殊路长度的结点min{for(intmin=0;B[min]==0;)min++;for(intj=min;j<VEX;j++)//求蓝点集结点最小下标元素

if(D[j]!=-1&&D[j]<D[min]&&B[j]==1)min=j;cout<<"min="<<min<<"";

//将具有最短特殊路长度的结点min添加到红点集中

R[min]=1;B[min]=0;

//对数组D作必要的修改

for(j=1;j<VEX;j++)if(graph[min][j]!=-1&&min!=j)//结点min到j间有路

if(D[j]>D[min]+graph[min][j]||D[j]==-1) {D[j]=D[min]+graph[min][j];//每次迭代求最小值，最后一次即为到源点的最短路径

P[j]=min; }}463.5.2Dijkstra算法Relax描述d[u]:su的距离p[u]:记录前一节点Relax松弛算法Init-single-source(G,s)foreachv∈V[G]do{d[v]=∞p[v]=NIL}d[s]=0,p[s]=NILRelax(u,v,w)ifd[v]>d[u]+w(u,v)then{d[v]=d[u]+w[u,v]p[v]=u}

47算法描述dijkstra(G,w,s)1.Init-single-source(G,s)//O(v)2.S=s3.Q=V[G]-S4.whileQ<>Φdou=min(Q)//用数组O(V)S=S∪{u}Q=V[G]-S

foreachv∈adj[u]&&v∈Q

//O(E)doRelax(u,v,w)483.5.3Bellman-Ford算法dijkstra算法的前提是所有边是正的Bellman-Ford算法允许负边Bellman-Ford算法的限制条件：不能包含权值总和为负值回路(负权值回路)，如下图所示。20117-2(c)493.5.3Bellman-Ford算法dijkstra算法的前提是所有边是正的Bellman-Ford算法允许负边初始化：将除源点外的所有顶点的最短距离估计值d[v]←+∞,d[s]←0;

迭代求解：反复对边集E中的每条边进行松弛操作，使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离；（运行|v|-1次）检验负权回路：如果存在负环，则算法返回false，表明问题无解；否则算法返回true，并且从源点可达的顶点v的最短距离保存在d[v]中。503.5.3Bellman-Ford算法思想dijkstra算法的前提是所有边是正的Bellman-Ford算法允许负边

Init-single-source(G,s)for

i←1to|V[G]|-1//O(V)

3.doforeachedge(u,v)∈E[G]//O(E)

4.doRELAX(u,v,w)

5.foreachedge(u,v)∈E[G]//O(E)6.doif

d[u]+w(u,v)<d[v]

7.thenreturnFALSE//存在负环

8.returnTRUE存在负权回路的图是不能求两点间最短路径，因为只要在负权回路上不断兜圈子，所得的最短路长度可以任意小。51d1

[u]为从源点v到终点u的只经过一条边的最短路径长度，并有dist1[u]=Edge[v][u]；d2

[u]为从源点v最多经过两条边到达终点u的最短路径长度；d3

[u]为从源点v出发最多经过不构成负权值回路的三条边到达终点u的最短路径长度；……dn-1[u]为从源点v出发最多经过不构成负权值回路的n-1条边到达终点u的最短路径长度；算法的最终目的是计算出dn-1

[u]，为源点v到顶点u的最短路径长度。52递推公式(求顶点u到源点v的最短路径)：d1

[u]=Edge[v][u]dk

[u]=min{dk-1

[u],min{dk-1

[j]+Edge[j][u]}},j=0,1,…,n-1,j≠u461230565-2-25-1-1133(c)kdk[0]dk[1]dk[2]dk[3]dk[4]dk[5]dk[6]10655∞∞∞2033554∞301352474013504550135043601350436/3/15/35∞/5/2/0∞/7/5/3∞/4无负环312056-2-11kdk[0]dk[1]dk[2]dk[3]1065∞2035230332验证负环0130有负环55Dijkstra算法与Bellman算法的区别Dijkstra算法在求解过程中，源点到集合S内各顶点的最短路径一旦求出，则之后不变了，修改的仅仅是源点到T集合中各顶点的最短路径长度。Bellman算法在求解过程中，每次循环都要修改所有顶点的d[]，也就是说源点到各顶点最短路径长度一直要到Bellman算法结束才确定下来。563.5.4其他最短路径问题①单目标最短路径问题(Single-DestinationShortest-PathsProblem)：找出图中每一顶点v到某指定顶点u的最短路径。只需将图中每条边反向，就可将这一问题变为单源最短路径问题，单目标u变为单源点u。②单顶点对间最短路径问题(Single-PairShortest-PathsProblem)：对于某对顶点u和v，找出从u到v的一条最短路径。显然，若解决了以u为源点的单源最短路径问题，则上述问题亦迎刃而解。而且从数量级来说，两问题的时间复杂度相同。③所有顶点对间最短路径问题(All-PairsShortest-PathsProblem)：对图中每对顶点u和v，找出u到v的最短路径问题。这一问题可用每个顶点作为源点调用一次单源最短路径问题算法予以解决。573.6最小生成树设G=(V,E)是无向连通带权图，即一个网络。E中每条边(v,w)的权为c[v][w]。如果G的子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树。生成树上各边权的总和称为该生成树的耗费。在G的所有生成树中，耗费最小的生成树称为G的最小生成树。网络的最小生成树在实际中有广泛应用。例如，在设计通信网络时，用图的顶点表示城市，用边(v,w)的权c[v][w]表示建立城市v和城市w之间的通信线路所需的费用，则最小生成树就给出了建立通信网络的最经济的方案。581、最小生成树性质用贪心算法设计策略可以设计出构造最小生成树的有效算法。Prim算法和Kruskal算法2个算法都利用了最小生成树性质：最小生成树性质：设G=(V，E)是一个连通网络，U是顶点集V的一个真子集。若(u，v)是G中所有的一个端点在U(u∈U)里、另一个端点不在U(即v∈V-U)里的边中，具有最小权值的一条边，则一定存在G的一棵最小生成树包括此边(u，v)。这个性质称为MST（MinimumSpanningTree）性质。591、最小生成树性质MST性质的证明：

约定：①集合U中的顶点——红色顶点②V-U中的顶点——蓝色顶点③连接红点和蓝点的边——紫色边④权最小的紫边称为轻边(即权重最“轻”的边)。用反证法证明MST性质601、最小生成树性质假设G中任何一棵MST都不含轻边(u，v)。则若T是G的一棵MST，则它不含此轻边。由于T是包含了G中所有顶点的连通图，所以T中必有一条从红点u到蓝点v的路径P，且P上必有一条紫边(u′

，v′)连接红点集和蓝点集，否则u和v不连通。当把轻边(u，v)加入树T时，该轻边和P必构成了一个回路。删去紫边(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性质成立。612、Prim（普里姆）算法设G=(V,E)是连通带权图，V={1,2,…,n}。Prim算法构造G的最小生成树基本思想：初始U={1}只要U是V的真子集，就作如下的贪心选择：选取满足条件i∈U，j∈V-U，且c[i][j]最小的边，将顶点j添加到U中。这个过程一直进行到U=V时为止。在这个过程中选取到的所有边恰好构成G的一棵最小生成树。622、Prim（普里姆）算法关键点思想是：将定点集合分成两个U，V-U（初始状态U中只有一个Uo），再加上一个TE集合来表示最小生成树边的集合。632、Prim（普里姆）算法例如，对于右图中的带权图，按Prim算法选取边的过程如图所示。642、Prim（普里姆）算法PrimMST(G，T，r)//求图G的以r为根的MST，结果放在T中{T=φ；U={1};

while(U!=V)//O(V){(i,j)=i∈U，j∈V-U，且c[i][j]最小的边//O(V)

T=T∪(i，j)//轻边(i，j)加入T

U=U∪

{j};//节点j加入U，变为红点

}

}/course_ware/data_structure/web/flashhtml/prim.htm652、Prim（普里姆）算法若候选轻边集中的轻边不止一条，可任选其中的一条扩充到T中。若一个蓝点与多个红点有边相接，选权最小的边做紫边。连通网的最小生成树不一定是惟一的，但它们的权相等。用这个办法实现的Prim算法所需的计算时间为O(V2)，与图中边数无关，该算法适合于稠密图。

662、Prim（普里姆）算法如何有效地找出满足条件i∈U,j∈V-U，且权c[i][j]最小的边(i,j)？较简单的办法是设置2个数组closest和lowcost。在Prim算法执行过程中，先找出V-U中使lowcost值最小的顶点j，然后根据数组closest选取边(j,closest[j］)，将j添加到U中，并对closest和lowcost作必要的修改。673、Kruskal（克鲁斯卡尔）算法Kruskal算法构造最小生成树的基本思想：(1)新建图G，G中拥有原图中相同的节点，但没有边(2)将原图中所有的边按权值从小到大排序(3）从权值最小的边开始，如果这条边连接的两个节点于图G中不在同一个连通分量中，则添加这条边到图G中(4)重复(3)，直至图G中所有的节点都在同一个连通分量中683、Kruskal（克鲁斯卡尔）算法例如，对前面的连通带权图，按Kruskal算法顺序得到的最小生成树上的边如图所示。693、Kruskal（克鲁斯卡尔）算法（1）算法思想

①T的初始状态

只有n个顶点而无边的森林T=(V，￠)

②按边长递增的顺序选择E中的n-1安全边(u，v)并加入T，生成MST

注意：

安全边指两个端点分别是森林T里两棵树中的顶点的边。加入安全边，可将森林中的两棵树连接成一棵更大的树

因为每一次添加到T中的边均是当前权值最小的安全边，MST性质也能保证最终的T是一棵最小生成树703、Kruskal（克鲁斯卡尔）算法MST-Kruskal(G)//求连通网G的一棵MST{T=(V，￠)；//初始化，T是只含n个顶点不包含边的森林//依权值递增序对E(G)中的边排序，并设结果在E[0..e-1]中O(Elog(E)

sorttheedgesofEbynon-decreasingweightw

for(i=0;i<e;i++)//e为图中边总数，O(E){

取第i条边（u,v）

ifu和v分别属于T中两棵不同的树

T=T∪{(u，v)}；//(u，v)是安全边，将其加入T中

}

returnT；}71说明有关说明：该算法的时间复杂度为O(ElogE)。

Kruskal算法的时间主要取决于边数。它较适合于稀疏图。723.7多机调度问题设有n个独立的作业{1,2,..,n}，由m台相同的机器进行加工处理。作业i所需的处理时间为ti。约定：任何作业可以在任何一台机器上加工处理，但未完工前不允许中断处理。任何作业不能拆分成更小的作业。多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。733.7多机调度问题这个问题是NP完全问题(Non-deterministicPolynomialCompleteProblem)，也即是多项式复杂程度的非确定性问题，到目前为止还没有有效的解法。对于这一类问题,用贪心选择策略有时可以设计出较好的近似算法。非确定性问题:无法按部就班直接地计算出来。找大质数的问题。没有一个公式，一套公式，就可以一步步推算出来，下一个质数应该是多少呢？大的合数分解质因数的问题，有没有一个公式，把合数代进去，就直接可以算出，它的因子各自是多少？也没有这样的公式。743.7多机调度问题采用最长处理时间作业优先的贪心选择策略可以设计出解多机调度问题的较好的近似算法。按此策略，当n≤m时(作业数<=机器数)，只要将机器i的[0,ti]时间区间分配给作业i即可，算法只需要O(1)时间。当n>m时，首先将n个作业依其所需的处理时间从大到小排序。然后依此顺序将作业分配给空闲的处理机。算法所需的计算时间为O(nlogn)。75一个实例例如，设7个独立作业{1,2,3,4,5,6,7}由3台机器M1，M2和M3加工处理。各作业所需的处理时间分别为{2,14,4,16,6,5,3}。按算法greedy产生的作业调度如下图所示，所需的总加工时间为17。作业编号数据输入：首先输入2个正整数n和m，分别表示有n个作业和m台相同的机器。然后输入n个正整数，第i个数表示作业i所需的处理时间。#def