算法设计与分析ch10on-line算法.ppt

《算法设计与分析ch10on-line算法.ppt》由会员分享，可在线阅读，更多相关《算法设计与分析ch10on-line算法.ppt（29页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第十章第十章 On-line Algorithms10.1 Introduction to On-line Introduction to On-line AlgorithmsAlgorithms 前九章介绍的算法设计的条件前九章介绍的算法设计的条件在算法执行之前整个输入数据的细节都很清楚在算法执行之前整个输入数据的细节都很清楚问题是在完全了解输入数据信息条件下解决的问题是在完全了解输入数据信息条件下解决的实际应用存在不满足上述条件的情况实际应用存在不满足上述条件的情况磁盘调度问题磁盘调度问题操作系统的页面调度问题操作系统的页面调度问题 Data streamsOn-line算法算法在算法设计

2、阶段或执行之前无完全信息可用在算法设计阶段或执行之前无完全信息可用,输入数据往往是实时到达的输入数据往往是实时到达的.算法时而正确时而错误算法时而正确时而错误.实时算法难以给出正确解实时算法难以给出正确解,一般是近似算法一般是近似算法.实时最小生成树问题实时最小生成树问题难以给出优化解难以给出优化解,“最小最小”需要放弃或改为需要放弃或改为“小小”.On-line算法可能如下工作算法可能如下工作:当每次一个数据到达时当每次一个数据到达时当每次一个数据到达时当每次一个数据到达时,将其连接到最近的邻居节点将其连接到最近的邻居节点将其连接到最近的邻居节点将其连接到最近的邻居节点.下边是一个六个实时到

3、达节点的例子下边是一个六个实时到达节点的例子下边是一个六个实时到达节点的例子下边是一个六个实时到达节点的例子.1 13 35 52 26 64 4算法工作过程算法工作过程优化解优化解1 13 35 52 26 64 4On-line算法的性能算法的性能令令Con表示表示On-line算法解的代价算法解的代价令令Coff表示表示Off-line算法解的代价算法解的代价若若Con f(n)Coff+c,c是是常常数数,则则称称On-line算算法法的的近近似比为似比为 f(n).这个算法称为这个算法称为f(n)-competitive10.2 On-line Euclidean Spanning

4、On-line Euclidean Spanning Tree ProblemTree Probleml问题的定义问题的定义l实时算法设计实时算法设计l算法性能分析算法性能分析问题的定义问题的定义 输入输入:S=v1,v2,vn是平面上的是平面上的n个点的集合个点的集合 这这n个点并非一次给定个点并非一次给定,是逐个出现的是逐个出现的l l 输出输出l l 一个一个”最小最小”生成树生成树求解最小生成树问题的求解最小生成树问题的On-line算法算法只能是近似算法只能是近似算法Greedy-On-line-ST(S)1.n=|S|;2.T=0;3.While n 0 Do4.Input(v);

5、5.把把v与与V(T)之间最短边加入之间最短边加入T;/*/*V(T)V(T)是是是是T T节点集合节点集合节点集合节点集合*/6.Endwhile6.EndwhileOn-Line算法算法算法的时间复杂性算法的时间复杂性3-6步需要的比较次数步需要的比较次数=1+2+(n-1)T(n)=O(n2)解的精确度解的精确度Greedy-On-line-ST算法的近似比是算法的近似比是O(logn)设设Tonl是算法产生的生成树是算法产生的生成树,l是优化生成树的代价或长度是优化生成树的代价或长度,下边我们来证明这个结论下边我们来证明这个结论算法的性能分析算法的性能分析引理引理1.Tonl中第中第k

6、最长边的长度最多为最长边的长度最多为2l/k,1 k n-1.证证.令令令令S Sk k=v v|v v加入加入加入加入T Tonlonl后后后后,T Tonlonl中出现长度大于中出现长度大于中出现长度大于中出现长度大于2l/k2l/k的边的边的边的边.如果如果如果如果|S|Sk k|k|k,则则则则Tonl中至多中至多k-1条边的长度大于条边的长度大于2l/k,即即Tonl中第中第k最长边的长度最多为最长边的长度最多为2l/k.往证往证|S|Sk k|k.|k.由算法的由算法的由算法的由算法的GreedyGreedy方法可知方法可知方法可知方法可知,S Sk k中每个点对之间的距离必中每个

7、点对之间的距离必中每个点对之间的距离必中每个点对之间的距离必大于大于大于大于2l/k2l/k.若不然若不然若不然若不然,设设设设u u和和和和v v之间距离小于之间距离小于之间距离小于之间距离小于2l/k2l/k,则加入则加入则加入则加入u u(或或或或v v)以后以后以后以后,再加再加再加再加入入入入v v(或或或或u u)时时时时,不会产生大于不会产生大于不会产生大于不会产生大于2l/k2l/k的边的边的边的边.于是于是于是于是,S Sk k上上上上TSPTSP的优化解的长度大于的优化解的长度大于的优化解的长度大于的优化解的长度大于|S Sk k|2l/k 2l/k.由于任意点集上的由于任

8、意点集上的由于任意点集上的由于任意点集上的TSPTSP优化解的长度是其最小生成树长度优化解的长度是其最小生成树长度优化解的长度是其最小生成树长度优化解的长度是其最小生成树长度的的的的2 2倍倍倍倍,S Sk k的最小生成树的长度大于的最小生成树的长度大于的最小生成树的长度大于的最小生成树的长度大于|S Sk k|l/k l/k.因为因为因为因为S Sk k上最小生成树长度上最小生成树长度上最小生成树长度上最小生成树长度l l不小于不小于不小于不小于S S上最小生成树长度上最小生成树长度上最小生成树长度上最小生成树长度,我们我们我们我们有有有有,|S Sk k|l/k l/k l l l l,即

9、即即即|S Sk k|l/k l/k l,l,或或或或|S Sk k|k k.于是于是于是于是,Tonl中第中第k最长边的长度最多为最长边的长度最多为2l/k.定理定理1.Greedy-On-line-ST算法的近似比是算法的近似比是O(logn).证证.由引理由引理由引理由引理1,1,T Tonlonl的长度的长度的长度的长度L L 1 1 k k n-1n-12l/k2l/k =2l =2l 1 1 k k n-1n-11/k 1/k =2l =2l H(n-1)H(n-1)=O(O(loglogn).n).于是于是于是于是,算法的近似比为算法的近似比为算法的近似比为算法的近似比为L/lL

10、/l O(O(loglogn).n).10.3 On-line Algorithm for Convex On-line Algorithm for Convex hull problemshull problemsl 问题的定义问题的定义l On-line算法的基本思想算法的基本思想l On-line算法算法l算法的性能分析算法的性能分析 问题定义问题定义输入输入平面上的平面上的n个点的集合个点的集合Q n个点逐个到达个点逐个到达,并非同时出现并非同时出现输出输出CH(Q):Q的的convex hull Q的的convex hull是一个凸多边形是一个凸多边形P，Q的点或者在的点或者在P上或

11、者在上或者在P内内凸多边形凸多边形P是具有如下性质多边形是具有如下性质多边形:连接连接P内任意两点的边都在内任意两点的边都在P内内基本思想基本思想当当k个节点已经到达后个节点已经到达后,我们得到一个部分我们得到一个部分CHOn-line算法的思想算法的思想当第当第k+1个节点个节点v到达时到达时如果如果如果如果v v落在落在落在落在CHCH内部内部内部内部,不需做任何事不需做任何事不需做任何事不需做任何事如果如果如果如果v v落在落在落在落在CHCH外部外部外部外部,需要调整需要调整需要调整需要调整CHCH的边界的边界的边界的边界关键是关键是关键是关键是:记住和调整部分记住和调整部分记住和调整

12、部分记住和调整部分CHCH边界边界边界边界 平行线近似法平行线近似法 用一组并行线记录、调整、近似用一组并行线记录、调整、近似CH需要平行移动这需要平行移动这需要平行移动这需要平行移动这条线条线条线条线,不改变其不改变其不改变其不改变其斜率斜率斜率斜率近似解近似解近似解近似解平行线的一般形式平行线的一般形式取取m对平行线对平行线,其斜率分别为其斜率分别为:0,tan(/m),tan(2/m),tan(m-1)/m).这这m对平行线必须满足对平行线必须满足:每个输入节点必须在所有平行线对内每个输入节点必须在所有平行线对内每个输入节点必须在所有平行线对内每个输入节点必须在所有平行线对内;每对平行线

13、必须尽可能的靠近每对平行线必须尽可能的靠近每对平行线必须尽可能的靠近每对平行线必须尽可能的靠近输入输入节点序列节点序列 p1,p2,满足前面条件的满足前面条件的m对平行线对平行线输出输出 近似近似convex hull序列序列 a1,a2,ai是覆盖是覆盖p1,p2,pi的近似的近似convex hullOn-line算法算法算法算法A初始化初始化初始化初始化:构造构造构造构造mm对平行线对平行线对平行线对平行线,斜率为斜率为斜率为斜率为0,tan(0,tan(/m),tan(m-/m),tan(m-1)1)/m);/m);搜索平行线相交在第一个点搜索平行线相交在第一个点搜索平行线相交在第一个

14、点搜索平行线相交在第一个点p p1 1.第一步第一步第一步第一步:对于任意一个新到达点对于任意一个新到达点对于任意一个新到达点对于任意一个新到达点p pi i,如果如果如果如果p pi i落在所有平行线对落在所有平行线对落在所有平行线对落在所有平行线对 之间之间之间之间,不执行任何操作不执行任何操作不执行任何操作不执行任何操作;否则否则否则否则,平移最接近平移最接近平移最接近平移最接近p pi i的线到的线到的线到的线到p pi i,不改变其斜率不改变其斜率不改变其斜率不改变其斜率,使使使使p pi i成为该线的标记成为该线的标记成为该线的标记成为该线的标记.第二步第二步第二步第二步:沿逆时针

15、方向连接每条平行线上的输入点沿逆时针方向连接每条平行线上的输入点沿逆时针方向连接每条平行线上的输入点沿逆时针方向连接每条平行线上的输入点,形成近似形成近似形成近似形成近似 convex hull convex hull a ai i.第三步第三步第三步第三步:如果不再有点输入如果不再有点输入如果不再有点输入如果不再有点输入 ,则停止则停止则停止则停止;否则令否则令否则令否则令i=i+1i=i+1,接受下一接受下一接受下一接受下一 个点个点个点个点p pi i,goto,goto 第一步第一步第一步第一步.时间复杂性时间复杂性O(mn)=O(n)(因为因为m是常数是常数)近似解精度近似解精度三种

16、三种相关的多边形相关的多边形E E:由由由由2m2m个平行线形成的多边形个平行线形成的多边形个平行线形成的多边形个平行线形成的多边形.C C:输入点集合的输入点集合的输入点集合的输入点集合的Convex hull,Convex hull,即准确解即准确解即准确解即准确解.A A:算法算法算法算法A A给出的近似给出的近似给出的近似给出的近似Convex hull.Convex hull.L(P)表表 示示 多多 边边 形形 P的的 总总 边边 长长,则则L(E)L(C)L(A).近似解近似解A的误差定义为的误差定义为 ERR(A)=(L(C)-L(A)/L(C)算法的性能分析算法的性能分析P

17、P2m2mP P2m-12m-1P P1 1P P2 2P P3 3P P4 4A A2m2mA A1 1A A2 2A A3 3A A4 4定理定理1.ERR(A)sec(/2m)-1.*定理定理定理定理1 1说明说明说明说明mm越大越大越大越大(即平行线对越多即平行线对越多即平行线对越多即平行线对越多),),错误越小错误越小错误越小错误越小.证证证证.考虑下图考虑下图考虑下图考虑下图:B BA AC Ca ab b 于是于是于是于是,AB+ACAB+AC BC sec(BC sec(/2)./2).P P2m2mP P2m-12m-1P P1 1P P2 2P P3 3P P4 4A A2

18、m2mA A1 1A A2 2A A3 3A A4 4 考虑下图考虑下图考虑下图考虑下图,P P2m2mP P2m-12m-1P P1 1P P2 2P P3 3P P4 4A A2m2mA A1 1A A2 2A A3 3A A4 4 由由AB+ACAB+AC BC sec(BC sec(/2)/2)，我们有我们有我们有我们有 L(E)L(E)=P P2m2mA A1 1+A A1 1P P1 1+P+P1 1A A2 2+A+A2m2mP P2m2m sec(sec(/2m)(P/2m)(P2m2mP P1 1+P+P1 1P P2 2+P+P2m-12m-1P P2m2m)=sec(=s

19、ec(/2m)L(A)./2m)L(A).于是于是于是于是,Err(A)=(L(C)-L(A)/L(C)Err(A)=(L(C)-L(A)/L(C)(L(E)-L(A)/L(A)(L(E)-L(A)/L(A)sec(sec(/2m)-1/2m)-1 10.4 Randomized On-line Algorithm for MST Randomized On-line Algorithm for MST 问题的定义问题的定义 随机随机On-line算法算法 算法的性能分析算法的性能分析 问题的定义问题的定义输入输入l l Euclidean空间上的空间上的n个点个点:v1,v2,vnl l n

20、个逐个出现个逐个出现l l 输出输出l l 由由v1,v2,vn构成的构成的最小生成树最小生成树Algoritm R(m)T=0;input(m);input(v1);input(v2);把边把边(v1,v2)添加到添加到T;For k=3 To n Do input(vk);If k m+1 Then 从从(vk,v1),(vk,vk-1)中选择最小边加入中选择最小边加入T;Else 从从(vk,v1),(vk,vk-1)中中随机地随机地选择选择m条边条边,把这把这m条边中最小边加入条边中最小边加入T;Return T.随机随机On-line算法算法R(n-1)是一个确定的贪心算法是一个确定

21、的贪心算法算法的时间复杂性算法的时间复杂性 时间复杂性时间复杂性 每次考察需要每次考察需要O(m)时间时间 需要需要O(n)次考察次考察 T(n)=O(nm)近似解的精确度近似解的精确度定义定义1.随机随机On-line算法算法A称为称为c-competitive,如果存如果存 在一个常数在一个常数b,使得使得 E(CA()c Copt()+b 其中其中,E(CA()是算法是算法A在问题实例在问题实例 上产生的上产生的 近似解的代价近似解的代价,Copt()是是 的优化解的代价的优化解的代价.定理定理1.如果如果m是固定常数是固定常数,算法算法R(m)的的competitive,则比是则比是(

22、n).证证.我们首先定义一组记号我们首先定义一组记号我们首先定义一组记号我们首先定义一组记号:=1,2,n1,2,n 输入点集合输入点集合输入点集合输入点集合,输入顺序为输入顺序为输入顺序为输入顺序为1 1、2 2、n.n.D(a,b)=D(a,b)=点点点点a a和和和和b b之间的距离之间的距离之间的距离之间的距离.N(a,k)=N(a,k)=在已经出现的点中在已经出现的点中在已经出现的点中在已经出现的点中点点点点a a的第的第的第的第k k最近点最近点最近点最近点.E(LE(LR(m)R(m)()=算法算法算法算法R(m)R(m)产生的树的期望长度产生的树的期望长度产生的树的期望长度产生

23、的树的期望长度.假定算法收到第假定算法收到第假定算法收到第假定算法收到第i i个输入点个输入点个输入点个输入点i i.如果如果如果如果2 2 i i m+1m+1,则则则则i i与前与前与前与前i-1i-1个点中最近点连接个点中最近点连接个点中最近点连接个点中最近点连接,加入树中加入树中加入树中加入树中.如果如果如果如果m+1m+1 i i n n,则则则则i i与与与与前前前前i-1i-1个点中个点中个点中个点中第第第第j j最近点连接的概率为最近点连接的概率为最近点连接的概率为最近点连接的概率为于是于是于是于是,我们有我们有我们有我们有我们来计算我们来计算我们来计算我们来计算E(LE(LR

24、(m)R(m)()/L(/L()的的的的下界下界下界下界.L(L()是输入点集合为是输入点集合为是输入点集合为是输入点集合为 时的最小生成树的长度时的最小生成树的长度时的最小生成树的长度时的最小生成树的长度.构造一个特殊输入序列构造一个特殊输入序列构造一个特殊输入序列构造一个特殊输入序列 *,使得使得使得使得 E(LE(LR(m)R(m)(*)/L()/L(*)=(n)(n)于是于是于是于是,E(LR(m)(E(LR(m)()/L()/L()=)=(n)(n)我们来计算我们来计算我们来计算我们来计算E(LE(LR(m)R(m)()/L(/L()的上界的上界的上界的上界.令令令令D D是是是是n n个输入点的直径个输入点的直径个输入点的直径个输入点的直径.最小生成树的长度最小生成树的长度最小生成树的长度最小生成树的长度 D D.因每条边的长度因每条边的长度因每条边的长度因每条边的长度 D D,任何任何任何任何On-lineOn-line算法产生的树的长度算法产生的树的长度算法产生的树的长度算法产生的树的长度 (n-1)D(n-1)D.我们有我们有我们有我们有,E(LE(LR(m)R(m)()/L()/L()(n-1)D/D=n-1(n-1)D/D=n-1.于是于是于是于是,R(m)R(m)的的的的competitivecompetitive比是比是比是比是 (n).(n).