算法第九章算法设计与分析ppt课件

算法设计与分析,郭丹 计算机与信息学院 guodan http: 2012年10月,1,课堂内容,2,算法分析篇,第七章 概率分析 第八章 摊销分析 第九章 竞争分析,3,第九章 竞争分析,9.1 什么是竞争分析？ 9.2 在线算法和离线算法 9.3 竞争力 9.4 线性表更新问题 9.5 聚类问题,4,第九章 竞争分析,9.1 什么是竞争分析？ 概率分析 VS. 摊销分析 VS. 竞争分析 概率分析：引入概率分布的平均情况分析 摊销分析：关注数据结构的平均最坏情况分析 竞争分析：比较算法和最优算法的差距,5,第九章 竞争分析,9.1 什么是竞争分析？ 竞争 5 年前，叶芙还是一个不为人所知的，没有申请过任何国家科研经费的研究人员。由于她对文学和哲学非常有兴趣，她用故事来讲述理论，提出的研究课题也经常与众不同。但是叶芙的这种研究风格并不被各种“专家们”所理解： 1、“研究的具体步骤是什么呢? “ 2、“所定义函数中的参数如何定义、度量没有阐述. 没有提出本项目的关键科学问题“ 3、“影响系统可靠性的最重要因素还是系统本身，与系统运行相关环境的研究对开发高可靠系统没有任何智助“,即便叶芙后来获得了成功！ 但她的事例也告诉我们： 要想快速获得成功，就得尽量按照最优标准答案来！,6,第九章 竞争分析,9.1 什么是竞争分析？ 竞争 这个世界里充满竞争。 各种评优、各种打分、各种奖励等层出不穷。 如果你申请项目未果，其给出的理由通常会包括一句类似“这次的项目评选竞争十分激烈“的话。,7,第九章 竞争分析,9.1 什么是竞争分析？ 竞争的目的是什么？ 评优。 那么如何评比才能是真正的选优呢? 当然是以最优的可能性或者“ 完美“为评判标准，井且达到这个最优标准的某一个程度(如百分比)才能被称为优秀。,两个普通算法不是竞争分析！ 一个算法和最优算法的比较才算竞争分析！,8,第九章 竞争分析,9.2 在线算法和离线算法 游戏俄罗斯方块：一块块不同形状的拼版从上面掉下，玩家需要将这些拼版尽量拼整齐， 目标是让每一行都尽量填满，不留空格。而填满的行就会销掉，从而腾出空间来接收后面的拼版。如果玩家来不及消除足够的行数而导致拼版累积到框顶，游戏便宜告结束。,9,第九章 竞争分析,9.2 在线算法和离线算法 提问：俄罗斯方块游戏是在线的还是离线的？ 在线算法（在线处理）：如果一个算法输入或请求是一个一个出砚，但每个请求和输入必须立即得到处理，且在处理一个输入请求的时候不知道后面的请求和 输入，这种处理算法就是在线算法。 离线算法：这种算法可以事先就得知所有的输入和请求， 这样就可以对所有的输入和请求进行最优的规划。,10,第九章 竞争分析,9.2 在线算法和离线算法 提问：俄罗斯方块游戏是在线的还是离线的？ 在线算法： 1、一次只提供操作序列 S 里面的一个操作. 2、对于每个操作，算法必须立即执行所需的操作(在不知道将来的操作是什么的情况下)。 离线算法： 离线算法可以事先看到整个操作序列 S。 提问：在线和离线，哪种方式更容易得到最优算法？ 在线算法不可能得到最优！ 离线算法有可能得到最优！,11,第九章 竞争分析,9.2 在线算法和离线算法 算法例子 很多人将人生比喻一个在线算法，从而判断人生无法活出最优! 操作系统里面的磁盘调度 ,12,第九章 竞争分析,9.2 在线算法和离线算法 算法例子 人生：一个在线算法，从而判断人生无法活出最优! 操作系统里面的磁盘调度（在线，离线，在线+离线） ,13,第九章 竞争分析,9.3 竞争力 竞争力（Competitive Ratio） 算法的成本除以最优离线算法的成本。如果设最优的离钱算法成本为o ，讨论中的在线算法成本为x 。 则该在线算法的竞争力CR = x/o 。 提问：CR的值是大好呢？还是小好？ 当然是小好，为什么？,14,第九章 竞争分析,9.3 竞争力,定义：一个在线算法A 如果满足下列条件，则被称为-竞争力的。 存在一个常数k ，对于任意一个操作序列S，有 CA(S) COPT(S) + k OPT 是我们的最优离线算法，也可称为上帝的算法.。,15,第九章 竞争分析,9.4 线性表更新问题 线性表更新问题衡量成本的例子 给定一个线性表和一组访问请求，如果访问位置靠前的元素比位置靠后的元素成本低。当然，在每次访问结束后，允许算法对线性表进行重新排列。 提问：如何设计算法使得访问线性表的成本最低? 提示：衣橱！ 衣橱里的衣服一件件叠放着( 一个线性表)。每天出门的时候我们从这摞衣服里面取出一套穿上(访问线性表)。晚上回来后再把衣服放回到衣橱(不用洗衣服)。,16,第九章 竞争分析,9.4 线性表更新问题 前置移动算法( Move-To-Front，MTF ) ： 1、将最常穿的衣服放在较上面的位置。 2、每次拿最上面的衣服。 3、回来脱下来的衣服也放在最上面。 提问：以前的分析能判断这个算法的总成本会是最低吗?,17,第九章 竞争分析,9.4 线性表更新问题 前置移动算法( Move-To-Front，MTF ) ： 定理：线性表的MTF 算法是 4-竞争力。 推论：如采我们把元素x 移动到表头的成本记为0 ，即我们能够用常数时间将x 从L 里面切割出来附加在头上(链表)，则MTF 算法就是 2-竞争力。 所以，我们宣称 MTF 算法是 O(1) -竞争力的。 证明：竞争分析怎么比较？ 选择最优算法-考量离线算法 （假设已经知道我们一生要穿什么衣服的算法）,18,第九章 竞争分析,9.4 线性表更新问题 前置移动算法( Move-To-Front，MTF ) ： 证明：一次操作成本就是移动元素的次数。 估算实际操作成本与离线成本的距离 借鉴势能分析来估算两者距离。,19,第九章 竞争分析,9.4 线性表更新问题 前置移动算法( Move-To-Front，MTF ) ： 证明： 势能分析得到范围值之后，再做一个换算，得如下结论。,因此， 线性表的MTF 算法是 4-竞争力。,20,第九章 竞争分析,9.5 聚类问题 聚类衡量结果的例子 聚类就是对大量未知标注的数据集，按数据的内在相似性将数据集划分为多个类别，使类别内的数据相似度较大而类别间的数据相似度较小。,21,第九章 竞争分析,9.5 聚类问题 聚类的应用例子,对相似的文档或超链接进行聚类，由于类别数远小于文档数，能够加快用户寻找相关信息的速度。,22,第九章 竞争分析,9.5 聚类问题 聚类的应用例子 采用网络数据集单个TCP连接的基本属性。 进行聚类分类: DOS拒绝服务攻击类型； U2R非授权得到超级用户权限； R2L从远程计算机进行非授权的访问； Probing扫描或者对其它系统漏洞的探测。,23,第九章 竞争分析,9.5 聚类问题 聚类的特点：无训练语料。 聚类的难度：即使离线，也无法判定什么是最优！,24,第九章 竞争分析,9.5 聚类问题 求解思想：在一片空间的所有数据点上划分出给定个数的区间，使得每个区间里面最远两点的距离最小。,25,第九章 竞争分析,9.5 聚类问题 聚类问题的次优解算法： CLUSTERJNG-LGORITHM (X)如下: 1、首先随机选择一个点u1作为第1 个区问C1 的中心。 2、接着按下面的规则依次选择u2, u3, , uk向分别作为区间C2, C3, , Ck 的中心: 对于2 m k，um是距离u1, u2, , um-1最远的点。 3、把其它每个点指派给距离它最近的区间，即点x 所属区问为Cy这里y=min d(x, uy) 。,26,第九章 竞争分析,9.5 聚类问题 求解思想：k=4 1、随机选一个类的中心点， 2、依次选择3个离已选择的点距离最远的点，作为新的类的中心点。 3、把其它点放入离四个类中心点最近的类别中。,27,第九章 竞争分析,9.5 聚类问题 CLUSTERING-ALGORITHM 算法的竞争分析 这个直径与最优划分的直径相比质量如何呢? 设x 为距离我们选出的k 个中心点 u1, u2, , uk 的最远的点， 设r 为 x 与离其最近的中心点的距离。 1、CA算法的直径 dCA 2r 2、最优算法的下限是 正好这两个点形成一个类 最优算法的直径 d最优 r 3、 dCA / d最优 2r/r =2 所以，CA算法是2-竞争力的算法。,r,28,谢谢！,29,