《高级算法设计》课件 第6章 在线算法

高级算法设计与分析在线算法林海lin.hai@B站：foretmer目录基本概念确定性在线算法在线最小生成树时间序列搜索随机在线算法租买问题在线二分图最大匹配概述离线算法在前面讨论的算法中，问题实例的所有数据在计算时，都是已知的，称为离线算法在线算法问题实例的数据是逐渐到来的，但是又需要对已经到来的数据进行计算，也就是说算法必须在输入数据不是很完全可知的情况下，完成相应的计算并输出结果如股票买卖、物流中的装车问题在线算法是近似算法概述人工智能算法试图从以往的数据中寻找出规律，并根据目前的分配状态，来智能的分配目前到达的任务在线算法数据完全未知假设存在一个对手(adversary)：这个对手对设计的算法了如指掌，所以能够针对算法给出最坏数据到达实例(称为最坏实例)，来使得算法的效率最低，所以设计在线算法时，通常需要分析在最坏实例下算法的性能。概述：流程股票买卖为例概述：定义竞争度ρ概述：定义在线算法的下界下界表达式给出了在最差实例下，任意在线算法ALG和OPT存在大于等于的关系，如果某算法ALG′的ρ=α，且c=0,b=0，说明在线算法ALG′的性能已经最优，因为所有在线算法在最坏实例下都是大于等于竞争度ρ的，当在线算法ALG′的竞争度是小于等于ρ，显然ALG′已经最优。确定性在线算法：在线最小生成树在线最小生成树图中的顶点不是一开始就已知，而是逐个到达，并要求一旦一个顶点到达就需要加入到树中，且让生成的树总代价尽量小。一个比较简单的在线算法是让到达的顶点通过离树内最近的顶点加入到树中。如，在第k个顶点到达时，选取前面k−1个顶点中和第k个顶点距离最近的顶点，通过此顶点将第k个顶点加入到树中。我们把这种算法称为最小生成树的贪心在线算法。确定性在线算法：在线最小生成树在线最小生成树确定性在线算法：在线最小生成树确定性在线算法：在线最小生成树确定性在线算法：在线最小生成树确定性在线算法：时间序列搜索确定性在线算法：时间序列搜索确定性在线算法：时间序列搜索确定性在线算法：时间序列搜索确定性在线算法：时间序列搜索确定性在线算法：时间序列搜索确定性在线算法：时间序列搜索确定性在线算法：时间序列搜索确定性在线算法：时间序列搜索确定性在线算法：时间序列搜索目录基本概念确定性在线算法在线最小生成树时间序列搜索随机在线算法租买问题在线二分图最大匹配随机在线算法策略的做出是随机性，形成随机在线算法，随机在线算法的好处是，假设的对手无法猜测算法的策略。随机在线算法：租买问题随机在线算法：租买问题随机在线算法：租买问题随机在线算法：租买问题随机在线算法：租买问题随机在线算法：租买问题随机在线算法：租买问题回到上面租买问题的例子ρ=4/3

的竞争度，这个竞争度比任意的确定性算法都要好，但这个竞争度是实例{I1,I2,I3}下的最优竞争度吗随机在线算法：租买问题随机实例下确定性算法费用和竞争度的计算随机在线算法：租买问题随机在线算法：租买问题随机在线算法：租买问题随机在线算法：在线二分图最大匹配随机在线算法：在线二分图最大匹配按秩进行贪心匹配的确定性算法随机在线算法：在线二分图最大匹配随机在线算法：在线二分图最大匹配在小数二分图匹配中，一个到达的顶点(a∈A)可以和B中的顶点(可以有多个)部分匹配随机在线算法：在线二分图最大匹配一个非常简单的算法是:当一个顶点ai到达时，和所有可匹配的顶点进行均匀匹配水位算法(waterlevelalgorithm)是一个非常著名的确定性在线算法，当A中的一个顶点a到达时，算法依据顶点a所有邻顶点的匹配状态，将a的匹配分配到这些邻顶点中，使得分配后，所有的邻顶点的匹配总量相似随机在线算法：在线二分图最大匹配随机在线算法：在线二分图最大匹配随机在线算法：在线二分图最大匹配随机在线算法：在线二分图最大匹配随机在线算法：在线二分图最大匹配随机在线算法：在