算法设计与分析ch10online算法课件

第十章第十章 On-line Algorithms第十章10.1 Introduction to On-line Algorithms 10.1 Introduction to On-line前九章介绍的算法设计的条件前九章介绍的算法设计的条件在算法执行之前整个输入数据的细节都很清楚在算法执行之前整个输入数据的细节都很清楚问题是在完全了解输入数据信息条件下解决的问题是在完全了解输入数据信息条件下解决的实际应用存在不满足上述条件的情况实际应用存在不满足上述条件的情况磁盘调度问题磁盘调度问题操作系统的页面调度问题操作系统的页面调度问题 Data streams前九章介绍的算法设计的条件On-line算法算法在算法设计阶段或执行之前无完全信息可用在算法设计阶段或执行之前无完全信息可用,输入数据往往是实时到达的输入数据往往是实时到达的.算法时而正确时而错误算法时而正确时而错误.实时算法难以给出正确解实时算法难以给出正确解,一般是近似算法一般是近似算法.实时最小生成树问题实时最小生成树问题难难以以给给出出优优化化解解,“最最小小”需需要要放放弃弃或或改改为为“小小”.On-line算法可能如下工作算法可能如下工作:当每次一个数据到达时当每次一个数据到达时当每次一个数据到达时当每次一个数据到达时,将其连接到最近的邻居节点将其连接到最近的邻居节点将其连接到最近的邻居节点将其连接到最近的邻居节点.下边是一个六个实时到达节点的例子下边是一个六个实时到达节点的例子下边是一个六个实时到达节点的例子下边是一个六个实时到达节点的例子.On-line算法1 13 35 52 26 64 4算法工作过程算法工作过程优化解优化解1 13 35 52 26 64 4135264算法工作过程优化解135264On-line算法的性能算法的性能令令Con表示表示On-line算法解的代价算法解的代价令令Coff表示表示Off-line算法解的代价算法解的代价若若Con f(n)Coff+c,c是是常常数数,则则称称On-line算算法法的的近近似比为似比为 f(n).这个算法称为这个算法称为f(n)-competitiveOn-line算法的性能10.2 On-line Euclidean Spanning Tree Probleml问题的定义问题的定义l实时算法设计实时算法设计l算法性能分析算法性能分析10.2 On-line Euclidean Spanni问题的定义问题的定义 输入输入:S=v1,v2,vn是平面上的是平面上的n个点的集合个点的集合 这这n个点并非一次给定个点并非一次给定,是逐个出现的是逐个出现的l l 输出输出l l 一个一个”最小最小”生成树生成树求解最小生成树问题的求解最小生成树问题的On-line算法算法只能是近似算法只能是近似算法问题的定义 输入:求解最小生成树问题的On-line算法Greedy-On-line-ST(S)1.n=|S|;2.T=0;3.While n 0 Do4.Input(v);5.把把v与与V(T)之间最短边加入之间最短边加入T;/*/*V(T)V(T)是是是是T T节点集合节点集合节点集合节点集合*/6.Endwhile6.EndwhileOn-Line算法算法Greedy-On-line-ST(S)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.证证.令令令令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中每个点对之间的距离必中每个点对之间的距离必中每个点对之间的距离必中每个点对之间的距离必大于大于大于大于2l/k2l/k.若不然若不然若不然若不然,设设设设u u和和和和v v之间距离小于之间距离小于之间距离小于之间距离小于2l/k2l/k,则加入则加入则加入则加入u u(或或或或v v)以后以后以后以后,再加再加再加再加入入入入v v(或或或或u u)时时时时,不会产生大于不会产生大于不会产生大于不会产生大于2l/k2l/k的边的边的边的边.引理1.Tonl中第k最长边的长度最多为2l/k,1 于是于是于是于是,S Sk k上上上上TSPTSP的优化解的长度大于的优化解的长度大于的优化解的长度大于的优化解的长度大于|S Sk k|2l/k 2l/k.由于任意点集上的由于任意点集上的由于任意点集上的由于任意点集上的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,即即即即|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/l O(O(loglogn).n).于是,Sk上TSP的优化解的长度大于|Sk|2l10.3 On-line Algorithm for Convex hull problemsl 问题的定义问题的定义l On-line算法的基本思想算法的基本思想l On-line算法算法l算法的性能分析算法的性能分析 10.3 On-line Algorithm for Co问题定义问题定义输入输入平面上的平面上的n个点的集合个点的集合Q n个点逐个到达个点逐个到达,并非同时出现并非同时出现输出输出CH(Q):Q的的convex hull Q的的convex hull是一个凸多边形是一个凸多边形P，Q的点或者在的点或者在P上或者在上或者在P内内凸多边形凸多边形P是具有如下性质多边形是具有如下性质多边形:连接连接P内任意两点的边都在内任意两点的边都在P内内问题定义输入凸多边形P是具有如下性质多边形:基本思想基本思想当当k个节点已经到达后个节点已经到达后,我们得到一个部分我们得到一个部分CHOn-line算法的思想算法的思想当第当第k+1个节点个节点v到达时到达时如果如果如果如果v v落在落在落在落在CHCH内部内部内部内部,不需做任何事不需做任何事不需做任何事不需做任何事如果如果如果如果v v落在落在落在落在CHCH外部外部外部外部,需要调整需要调整需要调整需要调整CHCH的边界的边界的边界的边界关键是关键是关键是关键是:记住和调整部分记住和调整部分记住和调整部分记住和调整部分CHCH边界边界边界边界基本思想On-line算法的思想当第k+1个节点v到达时 平行线近似法平行线近似法 用一组并行线记录、调整、近似用一组并行线记录、调整、近似CH需要平行移动这需要平行移动这需要平行移动这需要平行移动这条线条线条线条线,不改变其不改变其不改变其不改变其斜率斜率斜率斜率近似解近似解近似解近似解 平行线近似法需要平行移动这条线,不改变其斜率近似解平行线的一般形式平行线的一般形式取取m对平行线对平行线,其斜率分别为其斜率分别为:0,tan(/m),tan(2/m),tan(m-1)/m).这这m对平行线必须满足对平行线必须满足:每个输入节点必须在所有平行线对内每个输入节点必须在所有平行线对内每个输入节点必须在所有平行线对内每个输入节点必须在所有平行线对内;每对平行线必须尽可能的靠近每对平行线必须尽可能的靠近每对平行线必须尽可能的靠近每对平行线必须尽可能的靠近平行线的一般形式输入输入节点序列节点序列 p1,p2,满足前面条件的满足前面条件的m对平行线对平行线输出输出 近似近似convex hull序列序列 a1,a2,ai是覆盖是覆盖p1,p2,pi的近似的近似convex hullOn-line算法算法输入On-line算法算法算法A初始化初始化初始化初始化:构造构造构造构造mm对平行线对平行线对平行线对平行线,斜率为斜率为斜率为斜率为0,tan(0,tan(/m),tan(m-/m),tan(m-1)1)/m);/m);搜索平行线相交在第一个点搜索平行线相交在第一个点搜索平行线相交在第一个点搜索平行线相交在第一个点p p1 1.第一步第一步第一步第一步:对于任意一个新到达点对于任意一个新到达点对于任意一个新到达点对于任意一个新到达点p pi i,如果如果如果如果p pi i落在所有平行线对落在所有平行线对落在所有平行线对落在所有平行线对 之间之间之间之间,不执行任何操作不执行任何操作不执行任何操作不执行任何操作;否则否则否则否则,平移最接近平移最接近平移最接近平移最接近p pi i的线到的线到的线到的线到p pi i,不改变其斜率不改变其斜率不改变其斜率不改变其斜率,使使使使p pi i成为该线的标记成为该线的标记成为该线的标记成为该线的标记.第二步第二步第二步第二步:沿逆时针方向连接每条平行线上的输入点沿逆时针方向连接每条平行线上的输入点沿逆时针方向连接每条平行线上的输入点沿逆时针方向连接每条平行线上的输入点,形成近似形成近似形成近似形成近似 convex hull convex hull a ai i.第三步第三步第三步第三步:如果不再有点输入如果不再有点输入如果不再有点输入如果不再有点输入 ,则停止则停止则停止则停止;否则令否则令否则令否则令i=i+1i=i+1,接受下一接受下一接受下一接受下一 个点个点个点个点p pi i,goto,goto 第一步第一步第一步第一步.算法A时间复杂性时间复杂性O(mn)=O(n)(因为因为m是常数是常数)近似解精度近似解精度三种三种相关的多边形相关的多边形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 P2m2mP P2m-12m-1P P1 1P P2 2P P3 3P P4 4A A2m2mA A1 1A A2 2A A3 3A A4 4时间复杂性算法的性能分析P2mP2m-1P1P2P3P4A2定理定理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 A2m2mA A1 1A A2 2A A3 3A A4 4定理1.ERR(A)sec(/2m)-1.BACab 考虑下图考虑下图考虑下图考虑下图,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(=sec(/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 考虑下图,P2mP2m-1P1P2P3P4A2mA 10.4 Randomized On-line Algorithm for MST 问题的定义问题的定义 随机随机On-line算法算法 算法的性能分析算法的性能分析 10.4 Randomized On-line Alg问题的定义问题的定义输入输入l l Euclidean空间上的空间上的n个点个点:v1,v2,vnl l n个逐个出现个逐个出现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)是一个确定的贪心算法是一个确定的贪心算法Algoritm R(m)随机On-line算法R(n-1)算法的时间复杂性算法的时间复杂性 时间复杂性时间复杂性 每次考察需要每次考察需要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,则比是则比是(n).证证.近似解的精确度定义1.随机On-line算法A称为c-c 我们首先定义一组记号我们首先定义一组记号我们首先定义一组记号我们首先定义一组记号:=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)产生的树的期望长度产生的树的期望长度产生的树的期望长度产生的树的期望长度.假定算法收到第假定算法收到第假定算法收到第假定算法收到第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(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).我们来计算E(LR(m)()/L()的下界.算法设计与分析ch10online算法课件30