第三讲-贪心法.ppt

例3.1 已知n=3, M=20, p=(25, 24, 15), w=(18, 15, 10), 其中的四个可行解 例3.2 已知n=4, p=(100, 10, 15, 20), d=(2, 1, 2, 1), 其中的九个可行解： 算法与时间复杂度 FastGreedyJobScheduling(int *d, float *p, int *J, int n) { int k=min {n, max {d[i]}}, F[k+1]; ElemType set[k+1]; for (i=0; i=k; i++) {F[i]=i; set [i]. data=i; set [i]. tag=-1;} for (j=0; i=1; i=n; i++) { r = find ( min (n, d[i-1]) ); if (F[r]!=0){ J[j++]=i; m=find(F[r]-1); union (m, r); F[r]=F[m]; } } } 该算法的计算时间为O(nα(2n,n))≈O(n) 3.5 最优归并模式 已知两个已分类文件: (F1, L1), (F2, L2), 归并的时间复杂度为O(L1+L2). 确定将n个长度不同的已分类文件归并在一起的最优方法(时间复杂度最低). 60 F2+ F3+F1 90 30 F2+ F3 方案3 60 F1+ F3+F2 100 40 F1+ F3 方案2 60 F1+ F2+F3 110 50 F1+ F2 方案1 10 20 30 总次数 记录移 动次数 F3 F2 F1 文件 对于不同的归并方案, 其总的记录移动次数不同. 两两归并时, 每次都选择长度最短的两个文件, 以使文件移动总次数增量最小 struct NODE { unsigned char *file; unsigned int length; unsigned tag; struct NODE *parent1; struct NODE *parent2; } L[2n-1]; 数据结构 file= length= tag=0 parent1=NULL parent2=NULL 元素初值 struct NODE * GreedyBinMerging(struct NODE * L, int n) { for(next=n; j=1; j=n-1; j++, next++) { k1=Least(L); L[k1].tag=1; k2=Least(L); L[k2].tag=1; L[next].parent1=L[k1]; L[next].parent2=L[k2]; L[next].length= L[next].parent1-length+ L[next].parent2-length; L[next].file=Merge(L[next].lch-file, L[next].rch-file); } return L[2n-1]; } 3.6 最小生成树 连通图与生成树 生成树的定义 生成树的应用举例 最小成本生成树 最小成本生成树构造方法 从空树开始，每次向树中加入一条不构成环的边 新加入的边应使生成树获得最小成本增量 PRIM 算法 Prim(float cost[n][n], int T[n-1][2], float *mincost) { int near[n], u, v; GetMincostEdge(u,v); T[1][1]=u; T[1][2]=v; *mincost=cost[u][v]; for(i=1; i=n; i++) if( cost[i][u]cost[i][v] ) near[i]=u; else near[i]=v; near[u]=near[v]=0; for(i=2; i=n-1; i++) { j=GetNode{ (near[j]!=0) Min{cost[j][near[j]] }; T[i][1]=j; T[i][2]=near[j]; *mincost=*mincost+cost[j][near[j]]; near[j]=0;