算法设计与分析ch10 on-line算法.pptVIP

第十章 On-line Algorithms 10.1 Introduction to On-line Algorithms 前九章介绍的算法设计的条件 在算法执行之前整个输入数据的细节都很清楚 问题是在完全了解输入数据信息条件下解决的 实际应用存在不满足上述条件的情况 磁盘调度问题 操作系统的页面调度问题 Data streams On-line算法 在算法设计阶段或执行之前无完全信息可用, 输入数据往往是实时到达的. 算法时而正确时而错误. 实时算法难以给出正确解, 一般是近似算法. 实时最小生成树问题 难以给出优化解, “最小”需要放弃或改为“小”. On-line算法可能如下工作: 当每次一个数据到达时, 将其连接到最近的邻居节点. 下边是一个六个实时到达节点的例子. 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. 把v与V(T)之间最短边加入T; /*V(T)是T节点集合 */ 6. Endwhile 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的边. 于是, Sk上TSP的优化解的长度大于 |Sk|2l/k . 由于任意点集上的TSP优化解的长度是其最小生成树长度 的2倍, Sk的最小生成树的长度大于|Sk|l/k . 因为Sk上最小生成树长度l’不小于S上最小生成树长度, 我们 有, |Sk|l/k l’ ? l , 即|Sk|l/k l, 或 |Sk| k . 于是, Tonl中第k最长边的长度最多为2l/k. 定理1. Greedy-On-line-ST算法的近似比是O(logn). 证. 由引理1, Tonl的长度L ? ?1?k?n-12l/k =2l ?1?k?n-11/k =2l?H(n-1)=O(logn). 于是, 算法的近似比为L/l?O(logn). 10.3 On-line Algorithm for Convex hull problems 问题的定义 On-line算法的基本思想 On-line算法 算法的性能分析 问题定义 输入 平面上的n个点的集合Q n个点逐个到达, 并非同时出现 输出 CH(Q): Q的convex hull Q的convex hull是一个凸多边形P， Q的点或者在P上或者在P内 凸多边形P是具有如下性质多边形: 连接P内任意两点的边都在P内 基本思想 当k个节点已经到达后,