算法导论ch.pptVIP

10.1 Introduction to On-line Algorithms 10.2 On-line Euclidean Spanning Tree Problem 10.3 On-line Algorithm for Convex hull problems 10.4 Randomized On-line Algorithm for MST 10.1 Introduction to On-line Algorithms 前九章介绍的算法设计的条件 在算法执行之前整个输入数据的细节都很清楚 问题是在完全了解输入数据信息条件下解决的 实际应用存在不满足上述条件的情况 磁盘调度问题 操作系统的页面调度问题 Data streams On-line算法 在算法设计阶段或执行之前无完全信息可用, 输入数据往往是实时到达的. 算法时而正确时而错误. 实时算法难以给出正确解, 一般是近似算法. 实时最小生成树问题 难以给出优化解, “最小”需要放弃或改为“小”. On-line算法可能如下工作: 当每次一个数据到达时, 将其连接到最近的邻居节点. 下边是一个六个实时到达节点的例子. 问题的定义 算法的时间复杂性 3-6步需要的比较次数=1+2+…+(n-1) T(n)=O(n2) 解的精确度 Greedy-On-line-ST算法的近似比是O(logn) 设Tonl是算法产生的生成树, l是优化生成树的代价或长度, 下边我们来证明这个结论 引理1. Tonl中第k最长边的长度最多为2l/k, 1?k?n-1. 证. 令Sk={v | v加入Tonl后, Tonl中出现长度大于2l/k的边}. 如果|Sk|k, 则Tonl中至多k-1条边的长度大于2l/k, 即 Tonl中第k最长边的长度最多为2l/k. 往证|Sk|k. 由算法的Greedy方法可知, Sk中每个点对之间的距离必 大于2l/k. 若不然, 设u和v之间距离小于2l/k, 则加入u(或v)以后, 再加 入v(或u)时, 不会产生大于2l/k的边. 基本思想 当k个节点已经到达后, 我们得到一个部分CH 平行线的一般形式 取m对平行线, 其斜率分别为: 0, tan(?/m), tan(2?/m), …, tan((m-1)?/m). 这m对平行线必须满足: 每个输入节点必须在所有平行线对内; 每对平行线必须尽可能的靠近 On-line算法 输入 节点序列 p1, p2, … 满足前面条件的m对平行线 输出 近似convex hull序列 a1, a2, … ai是覆盖p1, p2, …, pi的近似convex hull 算法A 初始化: 构造m对平行线, 斜率为0, tan(?/m), …, tan((m-1)?/m); 有哪些信誉好的足球投注网站平行线相交在第一个点p1. 第一步: 对于任意一个新到达点pi, 如果pi落在所有平行线对 之间, 不执行任何操作; 否则, 平移最接近pi的线到pi, 不改变其斜率, 使pi成为该线的标记. 第二步: 沿逆时针方向连接每条平行线上的输入点, 形成近似 convex hull ai. 第三步: 如果不再有点输入 , 则停止; 否则令i=i+1, 接受下一 个点pi, goto 第一步. HITCSE 第十章 On-line Algorithms 李建中 计算机科学与工程系 提要 参考资料 《网站资料》 第十章 1 3 5 2 6 4 算法工作过程 优化解 1 3 5 2 6 4 On-line算法的性能 令Con表示On-line算法解的代价 令Coff表示Off-line算法解的代价 若Con?f(n)Coff+c, c是常数, 则称On-line算法的近似比为 f(n). 这个算法称为f(n)-competitive 10.2 On-line Euclidean Spanning Tree Problem 问题的定义 实时算法设计 算法性能分析 输入: S={v1, v2, …, vn}是平面上的n个点的集合 这n个点并非一次给定, 是逐个出现的 输出 一个”最小”生成树 求解最小生成树问题的On-line算法 只能是近似算法 Greedy-On-line-ST(S) 1. n=|S|; 2. T=0; 3. While n?0 Do 4. Input(v); 5. 把