第九章概率算法.ppt
《第九章概率算法.ppt》由会员分享,可在线阅读,更多相关《第九章概率算法.ppt(38页珍藏版)》请在麦多课文档分享上搜索。
1、2018/10/9,计算机算法设计与分析,1,第九章 概率算法,2018/10/9,计算机算法设计与分析,2,概率计算,概率计算就是在算法中可采用随机选择计算的步骤、元素或参数等。 它的基本特征是计算具有不确定性。 它的解也不一定是最优解。 它在很大程度上能降低算法的复杂度。 在非标准算法中普遍了应用概率方法,主要有: (1)直接用概率进行数值计算; (2)用概率/随机进行选择; (3)利用概率加速搜索或避免陷于局部最优。,2018/10/9,计算机算法设计与分析,3,直接用概率进行数值计算,设f(x)是0, 1上的连续函数,求I = f(x)dx。,01,y = f(x),G,假设向单位正方
2、形内随机投入n个点(xi, yi),若有m个点落入G中,则Im/n。,double Darts (int n) double x, y; int k = 0; static RandomNumber dart;for (int i=1; i=n; i+) x=dart.fRandom(); y=dart.fRandom(); if (y=f(x) k+;return k/double(n); ,2018/10/9,计算机算法设计与分析,4,划分基准的随机选择,在快速排序算法中,若用拟中位数作为划分标准,可保证在线性时间内完成。但是确定拟中位数要付出额外开销。若选用第一个元素为划分基准,最坏时的
3、时间复杂性为O(n2)。 若在算法中采用随机选择一个元素作为划分标准,便可既保证算法的线性时间平均性能,又避免了计算拟中位数的麻烦。 也可先对数组进行“洗牌”,然后再进行确定的排序算法。这样依然可取得同样的效果。,2018/10/9,计算机算法设计与分析,5,“洗牌”后的快速排序,void Shuffle(Type a, int n) /随机洗牌算法static RandomNumber md;for (int i = 1; i n; i+) int j = md.Random(n i + 1) + i;Swap(ai, aj); Void QuiksortByShuffle(Type a,
4、int n) Shuffle(a, n); /将数组a洗牌Quiksort(a, n); ,2018/10/9,计算机算法设计与分析,6,随机抽样,在n个元素的集合中随机抽取m(0mn)个无重复的元素。为简单起见,假定所有元素的值都位于1至n之间。,2018/10/9,计算机算法设计与分析,7,随机抽样,我们采用下面的方法进行选择: 1、首先将n个元素都标记为“未选择”; 2、重复下列步骤直到抽取了m个不同的元素 产生一个1至n间的随机数r; 如果r标记为“未选择”,将它标记为“已选择”,并加入到抽样中。,2018/10/9,计算机算法设计与分析,8,随机抽样,int RandomSampli
5、ng(Sn, Am, m) mark1n = False; count=0;while(count m) r = random(1, n);if (markr = False) count+;Acount=Sr;markr=True; ,2018/10/9,计算机算法设计与分析,9,判定素数的概率算法,判定自然数是否是素数,不仅有重要理论意义,而且在密码学中具有重要实用价值。 最简单的素数判定方法是依次测定从2到n 中是否存在n的因子,该算法的复杂度为O(n )。 筛法:将小于n的合数预先筛掉,而不用判断其是否为n的因子。它虽然没有降低算法的复杂度,但实际运行速度比前者要快得多。 概率算法,保
6、证一定概率的前提下简单判断。,2018/10/9,计算机算法设计与分析,10,Fermat素数测试法,Fermat定理: 若p是素数,则对任意整数a,gcd(a, p) = 1,则有ap11 (mod p)。 显然,对素数p有pp1 1 (mod p)。 对于一般的整数n,满足nn11 (mod n)的数目很少。满足的称为伪素数。 就用是否满足nn11 (mod n)来判断n是否为素数。,2018/10/9,计算机算法设计与分析,11,Fermat素数测试法,Bool Fermat_Prime(int n) a = 2; power = n 1; other = 1;while(power 1
7、) if (power % 2 = = 1) other *= a; other %= n;power /= 2; a = a * a % n;if (a * other % n = 1) return True;return False; ,2018/10/9,计算机算法设计与分析,12,合数的见证者,设n为测试的自然数,不妨设n是大于2的奇数,则有n 1 = 2im,其中i是非负整数,m是正奇数。取一自然数b,1 b n,记W(b)为条件: bn1 1 (mod n) 或 i,使得m = (n1)/2i 且 1 gcd(bm1, n) b。 若或中有一个为真,就认为W(b)满足,则n必定是
8、合数,我们称b是n为合数的见证者。 若n有见证者,则n必定为合数。,2018/10/9,计算机算法设计与分析,13,合数的见证者多于一半,Miller已经证明,存在常数c,使得当n为合数时,在1, c(log n)2范围内有见证者。,Rabin证明了:如果n是合数,则 |b|1bn,W(b)满足|(n1)/2即,在小于n的自然数中有多半是n的见证者。,任取一个自然数b n,若b不是n的见证者,则n是合数的概率小于1/2。若随机取m个数都不是见证者,则n是合数的概率小于1/2m。,2018/10/9,计算机算法设计与分析,14,Miller-Rabin素数判定概率算法,Bool Miller_R
9、abin_Prime(int n)b1 m = RandomSampling(n, m); /*随机选取m个大于1小于n的无重复的自然数 for (j = 1; j = m; j+)if (W(bj) 满足) return False;return True; 若m = 100,则n不是素数的概率小于1/2100。,2018/10/9,计算机算法设计与分析,15,Las Vegas算法,Las Vegas算法的特点是随机性地进行决策。 例如对n后问题,Las Vegas算法是随机地产生一组王后放置的位置。若成功了,便找到了一个解;若失败了,就整个重来,再随机产生另外一组王后的位置。这样作,直至
10、找到解。 此算法能显著地改进算法的有效性,甚至对迄今为止找不到有效算法的问题,也能得到满意的结果。,2018/10/9,计算机算法设计与分析,16,瞎子爬山法与局部最优,更一般的求解问题的方法是瞎子爬山法。 一个瞎子从山脚开始,试探着一步一步向上爬,就可以一直爬到山顶。,可是,他爬上的可能只是个小山头,更高的山还在后面。而他无法从小山头下来,也就无法爬到更高的山头了。,这种情形就被称为陷入了局部最优。,如何避免陷入局部最优是求解问题中要注意的一个重要问题。,2018/10/9,计算机算法设计与分析,17,进化算法(Evolutionary Algorithm),达尔文的进化论:适者生存,优胜劣
11、汰。 1975年霍兰(Holland)提出了遗传算法,通过模拟生物进化的过程概率搜索最优解。 遗传算法首先产生所谓的个体种群,每个个体是编码的二进制串(又称为染色体)。 然后对个体进行随机的选择,再经过复制、交叉和变异产生下一代的种群。 就这样经过一代一代的进化,最终获得满意的个体(即问题的解)。,2018/10/9,计算机算法设计与分析,18,进化计算中的基本算子,适应值f(xi):给出个体xi优劣; 选择算子:对个体进行概率选择。,个体的概率为p(xi) = f(xi) / f(xj),优秀的个体具有较高的概率。 最常用的选择算子为轮盘赌的方法。这样优秀个体具有较高的被选中的概率。同时差的
- 1.请仔细阅读文档,确保文档完整性,对于不预览、不比对内容而直接下载带来的问题本站不予受理。
- 2.下载的文档,不会出现我们的网址水印。
- 3、该文档所得收入(下载+内容+预览)归上传者、原创作者;如果您是本文档原作者,请点此认领!既往收益都归您。
下载文档到电脑,查找使用更方便
2000 积分 0人已下载
下载 | 加入VIP,交流精品资源 |
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第九 概率 算法 PPT
