算法设计与分析-4.ppt

S={1,3,6,4,2} S={1,3,6,4,2, 5} 实现Prim算法时，应当考虑如何有效地找出满足条件i?S, j?V-S，且权c[i][j]最小的边(i,j)。 方法：设置2个数组closest和lowcost。 在Prim算法执行过程中，先找出V-S中使lowcost值最小的顶点j，然后根据数组closest选取边(j,closest[j］)，最后将j添加到S中，并对closest和lowcost作必要的修改。 用这个办法实现的Prim算法所需的计算时间为 Kruskal算法 基本原理： Step1. 将G的n个顶点看成n个孤立的连通分支 Step2. 将所有的边按权从小到大排序 Step3. 从权最小的第一条边开始，依边权递增的顺序查看每一条边v,w，并按下述方法连接2个不同的连通分支：当查看到第k条边(v,w)时， 1) 如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时，用边(v,w)将T1和T2合并成一个连通分支，然后继续查看后续第k+1条边 2) 如果端点v和w已经属于当前的同一个连通分支中，不允许将(v,w)加入，否则会产生回路。 此时，直接再查看后续第k+1条边 Kruskal算法 Step4. 持续上述过程，直到只剩下一个连通分支——最小生成树 E.g. 5 6 3 2 4 1 Step1. Step2. 边排序 3 1 1 6 4 2 5 2 3 6 3 4 4 1 5 3 2 5 4 3 5 5 3 6 6 5 6 3 1 1 6 4 2 5 2 3 边排序： 6 3 4 4 1 5 3 2 5 4 3 5 说明： 1）节点1与4、3与4已经在同一连通分量中 2）节点2、3分属于不同连通分量 Kruskal算法时间复杂性当图的边数为e时，Kruskal算法所需的计算时间 与Prim算法比较 当时，Kruskal算法比Prim算法差， 当时，Kruskal算法比Prim算法好得多 * 应用：TD-LTE网络小区/基站PCI资源分配顺序，K算法 4.7 多机调度问题 多机调度问题:n个作业组成的作业集，可由m台机器加工处理。给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。 约定： 1）作业不能拆分成更小的子作业 2）每个作业均可在任何一台机器上加工处理 问题性质： 这个问题是NP完全问题，还没有有效的解法（求最优解）。 用贪心选择策略设计出较好的近似算法（求次优解）。 贪心选择策略：采用最长处理时间作业优先的，即：1）将n个作业按照所需完成时间由大到小排序2）依此顺序将作业分配给空闲的m台处理机 问：为何不是由小到大排列？！ 求解过程： 1）当n≤m 时，即机器数目m不小于待加工的作业数目n，无作业等待。此时，将机器i的[0, ti]时间区间分配给作业i。算法需要O(1)时间 当nm时，将n个作业依其所需的处理时间从大到小排序，然后依此顺序将作业分配给空闲的处理机。所需计算时间为O(nlogn)——排序耗费 贪心选择求解次优解 E.g. 设7个独立作业{1, 2, 3, 4, 5, 6, 7}，由3台机器M1，M2和M3加工处理。作业调度如下图所示，所需的加工时间为17。作业排序：4, 2, 5, 6, 3, 1 作业 1 2 3 4 5 6 7 加工时间 2 14 4 16 6 5 3 * 问题：为何不是由小到大排列——最短处理时间作业优先？！ 贪心选择策略：采用最长处理时间作业优先的，即：1）将n个作业按照所需完成时间由大到小排序2）依此顺序将作业分配给空闲的m台处理机 操作系统作业/进程调度：最短作业优先调度SJF(Shortest Job First) ，可以保证作业平均等待时间最短 * 欢迎辞 * 55 * a：45 x：12 b：13 f：5 e：9 y：16 100 0 1 58 0 1 Z:28 0 1 14 0 1 86 0 1 14 0 子树T’, B(T’) e.g. 子问题 C’={a,b,z,e,f} 证明关键点： 1）T的平均码长B(T)可用子树T‘的平均码长B(T’) 表示B(T) = B(T’) + 1*f(x) + 1*f(y) 上式：递推表达式，表示原问题最优值与子问题最优值之间的关系 T’所表示的C‘的前缀码的码长B(T’)是最短/最优的 反证法证明：假设有另一个T’’，是子问题C’的最优前缀码，即B(T’)B(T’’)。 节点z在T’’还是一个叶节点，在T’’ 中将z替换为其子节点x、y，得到T’’’。 e.g 见下页：* b：13 a：45 f：5 e：9 100 0 1 58 0 1 Z:28 14 0 1 86 0 1 14 0