《高级算法设计》课件 第5、6章 随机算法；在线算法

高级算法设计与分析随机算法目录概述随机快速排序最小圆覆盖弗里瓦德算法集合覆盖最小割概述概述此算法可能返回0，也可能返回n∗a，算法复杂度可能为Θ(1)，也可能为Θ(n)概述：分类1拉斯维加斯算法(LasVegas)算法能够得到一个确定性的解决，但算法执行时间不确定例子:在有n个元素的数组A中，有一半的元素为0，另一半的元素为1(随机分布)，找到一个值为1元素的下标。概述：分类1蒙特卡洛算法(MonteCarlo)蒙特卡洛算法得出的解是不确定的，但是执行时间是确定的概述：分类1概述：分类2概述：分类2分类避免落入最坏情形降低算法复杂度避免落入最坏情形：随机快速排序快速排序的平均复杂度是O(nlogn)，但是在最坏的情况下，算法的复杂度为O(n2)。为了消除这种最差的情况，可以在快速排序引入一种随机因素随机快速排序在数组中随机的选择一个元素作为主元素Lomuto划分避免落入最坏情形：随机快速排序避免落入最坏情形：随机快速排序避免落入最坏情形：随机快速排序秩小于i和大于j的元素被选为主元，i和j的比较概率并不会受到影响如果i和j被选为主元，则i和j进行比较(共2个元素)大于i且小于j的元素被选为主元(共j−i−1个元素)，则i和j不会比较避免落入最坏情形：随机快速排序最小圆覆盖所有三个点形成的圆个数为O(n3)，判断每个圆是否包含所有其他点O(n)，暴力求解的总复杂度为O(n4)最小圆覆盖随机增量法(randomizedincrementalconstruction)增量:通过逐个的添加点，来计算每一步的最小覆盖圆，即计算一个点的最小圆覆盖，两个点的最小圆覆盖，···，直到n个点的最小圆覆盖;随机:通过一种随机的方式来添加点，避免算法跌入最坏情况。最小圆覆盖设目前新添加的点是pi，那么存在两种情况:如果添加的新点pi

已经被包含在Ci−1

内，那么Ci=Ci−1

添加的新点pi

没有被包含在Ci−1

内，此时需要增大圆，增大到什么时候为止?圆刚好能够包含pi

。最小圆覆盖假设结论不成立：最小圆覆盖pi在圆上，可以通过遍历{p1,p2,···,pi−1}上任意的两个点组合来确定Ci

p1

加入，这样p1

和pi

形成两个节点的最小圆，再依次加入{p2,···,pi−1}，直到找到第一个不被当前最小圆包含的点(设为pj)。pj和pi，它们是{p1,p2,···,pj,pi}这些点的最小圆边界上的点再次对{p1,p2,···,pj−1}这些点增量判断，得到{p1,p2,···,pj,

pi}这些点的最小圆重复上述流程，直到得到{p1,p2,···,pi−1,pi}所有这些点的最小圆最小圆覆盖最小圆覆盖最小圆覆盖算法复杂度最小圆覆盖算法复杂度主函数：因为点排列的随机性，第i个点在Ci

边界上的概率只有3/i（或者2/i）

最小圆覆盖算法复杂度MinDisc1Piont函数的复杂度最小圆覆盖算法复杂度MinDisc1Piont函数的复杂度最小圆覆盖算法复杂度主函数分类避免落入最坏情形降低算法复杂度弗里瓦德算法(Frievald’sAlgorithm)弗里瓦德算法(Frievald’sAlgorithm)弗里瓦德算法(Frievald’sAlgorithm)集合覆盖集合覆盖的随机算法基于IP建模，以及其对应的松弛LP问题假设已经求得LP问题的最优解x∗，在随机算法中，最优解x∗

看成子集S的选取概率集合覆盖某个元素ei通过随机算法没有被覆盖的概率集合覆盖抛k次硬币，只要出现一次硬币朝上，子集Sj被选中集合覆盖为了算法能够得出一个合法解，我们可以通过多次执行上面的抛硬币流程，直到得出合法解为止算法repeat期望执行次数为多少次？集合覆盖算法repeat期望执行次数为多少次？即求算法执行一次repeat，得出合法解，且代价（权重之和）小于4k·OPTLP

的概率集合覆盖集合覆盖集合覆盖最小割最小割最小割随机的方式得出一个最小割的概率是多少?最小割最小割最小割最小割最小割最小割最小割在得到一个收缩图G后，对图G应用两次随机收缩算法，并递归的应用以上方法通过7

次收缩，可随机得到4

个割，但如果进行独立的收缩，则需要4∗3=12次的收缩。最小割最小割最小割最小割递归收缩图的叶子层（也就是边界条件）看成是第0层，其上一层为第1层，以此类推，则第k+1层节点得出最小割概率p_{k+1}的递归式：高级算法设计与分析在线算法目录基本概念确定性在线算法在线最小生成树时间序列搜索随机在线算法租买问题在线二分图最大匹配概述离线算法在前面讨论的算法中，问题实例的所有数据在计算时，都是已知的，称为离线算法在线算法问题实例的数据是逐渐到来的，但是又需要对已经到来的数据进行计算，也就是说算法必须在输入数据不是很完全可知的情况下，完成相应的计算并输出结果如股票买卖、物流中的装车问题在线算法是近似算法概述人工智能算法试图从以往的数据中寻找出规律，并根据目前的分配状态，来智能的分配目前到达的任务在线算法数据完全未知假设存在一个对手(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的匹配分配到这些邻顶点中