《高级算法设计》课件 第5章 随机算法

高级算法设计与分析随机算法林海lin.hai@B站：foretmer目录概述随机快速排序最小圆覆盖弗里瓦德算法集合覆盖最小割概述概述此算法可能返回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

个割，但如果进行