随机算法.ppt

第9章随机算法 1. 随机算法引例 2. 随机算法的类型 3. 舍伍德算法 4. 拉斯维加斯算法 5. 蒙特卡罗算法 11. 随机算法引例 rr 4 4/ 2 2??????r r数落入左上角正方形的点落入扇形面积的点数??4?由此推导出: ??????????,...... 2,1 mod 1 0nmcba a da nn 22. 随机算法的类型?第1类算法:数值概率算法。用于数值问题求解,所得到的几乎都是近似解,但计算精度随着计算时间的增加而不断提高。引例中就是一个数值概率算法;在给定函数 f(x) 的定义域和 x 与 f(x) 之间的映射关系,求解 f(x) 的最值时,可以用数值概率算法。?第2类算法:舍伍德算法。舍伍德算法不会从整体上或平均的改善问题求解的时间复杂度, 但可以对一些特别耗时的特定输入改善至较适中的时间复杂度 3 ?第3类概率算法是拉斯维加斯算法。该算法可能给出问题的正确答案,也可能得不到问题的正确答案。但对所求解的问题,用同一个拉斯维加斯算法反复求解多次,可以使得求解失效的概率任意小?蒙特卡罗算法总能得到问题的答案,但偶尔会产生不正确的答案。有时并不能判断给出的答案是否正确。重复运行算法使得产生不正确解的概率任意小 43. 舍伍德算法 舍伍德算法概述 随机快速排序算法 随机选择算法 舍伍德算法概述假设 T A (x) 是确定性算法 A对一个输入实例 x的运行时间,则???? n Xx A AX xTnT n???上述算法可能存在某个 x使得 T A (x) 远远大于平均时间复杂度。舍伍德类型算法通过向确定性算法 A中加入随机因子,使得每一个输入实例与平均时间复杂度相差不大?????? nsnTxT AB?? 随机快速排序算法?快速排序的时间复杂度最好情况下是 O(nlogn) ,最坏情况下是 O(n 2),平均情况是 O(nlogn) 。最坏情况的出现原因是:待排序的对象已经基本上排序完毕,使得问题的中轴始终处于所有数据的某端或接近于某端?为了排除上述情况,可以在中轴选取时,引入随机因子:端点和某个随机位置的数据交换。这使得中轴不大可能是最小(最大)值,或接近最小(最大)值的数值?有没有更保险的算法? 随机选择算法?从n个元素中选择第 k小的元素,存在一个 O(n) 级别的算法,这个算法的时间复杂度上界是20n,具有一个较大的常数?上述算法最耗时的地方是:查找一个合适的中轴(把所有元素分成 n/5 组,每组 5个,找出每组中数,然后找出所有元素的近似中数) ?计算元素中数的过程可以省略,取而代之的是在所有元素中取得一个随机位置,然后让这个位置上的数作为中数?这个随机算法的时间复杂度小于 4n ?是否可以继续改进这个随机算法? 84. 拉斯维加斯算法 拉斯维加斯算法概述 八皇后问题 字符串匹配 9 ?拉斯维加斯型概率算法有时成功,有时失败?当出现失败时,只要在相同的输入实例上再次运行相同的拉斯维加斯概率算法,就又有成功的可能?假设 BOOL las_vegas(P(x)) 是针对问题 P的某个实例x的运行代码,则拉斯维加斯执行下面代码: ? while( !las_vegas(P(x)) ?假设 p(x) 是输入实例 x和运行成功的概率之间的关系,如果存在常数?,使得 p(x) ??,就认为该拉斯维加斯算法正确,随着时间增加,可以让算法的错误概率(1- ?) k任意小 拉斯维加斯算法概述 10