1 / 38
文档名称:

第九章概率算法 (2).ppt

格式:ppt   大小:1,817KB   页数:38页
下载后只包含 1 个 PPT 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

第九章概率算法 (2).ppt

上传人:石角利妹 2022/4/15 文件大小:1.77 MB

下载得到文件列表

第九章概率算法 (2).ppt

相关文档

文档介绍

文档介绍:第九章概率算法
*
计算机算法设计与分析
*
本讲稿第一页,共三十八页
概率计算
概率计算就是在算法中可采用随机选择计算的步骤、元素或参数等。
它的基本特征是计算具有不确定性。
它的解也不一定是最优解。
它在很大程度上能er /= 2; a = a * a % n;}
if (a * other % n == 1) return True;
return False;
}
本讲稿第十一页,共三十八页
合数的见证者
设n为测试的自然数,不妨设n是大于2的奇数,则有n – 1 = 2im,其中i是非负整数,m是正奇数。取一自然数b,1 < b < n,记W(b)为条件:
① bn–1 ≠ 1 (mod n) 或
②i,使得m = (n–1)/2i 且 1 < gcd(bm–1, n) < b。
若①或②中有一个为真,就认为W(b)满足,则n必定是合数,我们称b是n为合数的见证者。
若n有见证者,则n必定为合数。
本讲稿第十二页,共三十八页
合数的见证者多于一半
Miller已经证明,存在常数c,使得当n为合数时,在[1, c(log n)2]范围内有见证者。
Rabin证明了:如果n是合数,则
|{b|1<b<n,W(b)满足}|≥(n–1)/2
即,在小于n的自然数中有多半是n的见证者。
任取一个自然数b < n,若b不是n的见证者,则n是合数的概率小于1/2。若随机取m个数都不是见证者,则n是合数的概率小于1/2m。
本讲稿第十三页,共三十八页
Miller-Rabin素数判定概率算法
Bool Miller_Rabin_Prime(int n){
b[1 .. m] = RandomSampling(n, m);
/*随机选取m个大于1小于n的无重复的自然数
for (j = 1; j <= m; j++)
if (W(b[j]) 满足) return False;
return True;
}
若m = 100,则n不是素数的概率小于1/2100。
本讲稿第十四页,共三十八页
Las Vegas算法
Las Vegas算法的特点是随机性地进行决策。
例如对n后问题,Las Vegas算法是随机地产生一组王后放置的位置。若成功了,便找到了一个解;若失败了,就整个重来,再随机产生另外一组王后的位置。这样作,直至找到解。
此算法能显著地改进算法的有效性,甚至对迄今为止找不到有效算法的问题,也能得到满意的结果。
本讲稿第十五页,共三十八页
瞎子爬山法与局部最优
更一般的求解问题的方法是瞎子爬山法。
一个瞎子从山脚开始,试探着一步一步向上爬,就可以一直爬到山顶。
可是,他爬上的可能只是个小山头,更高的山还在后面。而他无法从小山头下来,也就无法爬到更高的山头了。
这种情形就被称为陷入了局部最优。
如何避免陷入局部最优是求解问题中要注意的一个重要问题。
本讲稿第十六页,共三十八页
进化算法(Evolutionary Algorithm)
达尔文的进化论:适者生存,优胜劣汰。
1975年霍兰(Holland)提出了遗传算法,通过模拟生物进化的过程概率搜索最优解。
遗传算法首先产生所谓的个体种群,每个个体是编码的二进制串(又称为染色体)。
然后对个体进行随机的选择,再经过复制、交叉和变异产生下一代的种群。
就这样经过一代一代的进化,最终获得满意的个体(即问题的解)。
本讲稿第十七页,共三十八页
进化计算中的基本算子
适应值f(xi):给出个体xi优劣;
选择算子:对个体进行概率选择。
个体的概率为p(xi) = f(xi) / ∑f(xj),优秀的个体具有较高的概率。
最常用的选择算子为轮盘赌的方法。这样优秀个体具有较高的被选中的概率。同时差的个体也有被选中的可能。
复制算子copy:对选中的个体进行复制。
交叉算子:将两个个体染色体中的某个位彼此交换,从而形成两个新的个体。
变异算子m:改变一个个体的染色体的某些位,得到一个新的个体。
停止准则:决定算法停止的准则
本讲稿第十八页,共三十八页
进化算法的基本框架
t = 0 // t为代数;
初始化:P(0)={a1(0), …, an(0)}//初始种群P(0)
度量:P(0): {f(a1(0)), …, f(an(0))};
while (P(t)不满足停止准则) {
交叉:P’(t) = (P(t));
变异:P’’(t) = m(P’(t));
度量:P’’(t):{f(a1’’(t)), …, f(an’’(t)));
选择:P(t+1) = P’’(t) ∪Q;
t = t +1; }

最近更新

2025年贵州工贸职业学院单招综合素质考试题库.. 73页

2025年幼儿园语言教学说课稿 24页

2025年贵州文化旅游职业学院单招职业技能测试.. 74页

基于CUDA的数控仿真加工面显示算法的研究 3页

基于CREAM的电网人为可靠性定量分析方法 3页

2025年神木职业技术学院单招职业适应性考试题.. 72页

2025年贵州盛华职业学院单招职业倾向性测试题.. 75页

2025年贵州省毕节地区单招职业适应性测试题库.. 72页

2025年贵州省黔西南布依族苗族自治州单招职业.. 74页

2025年福建农林大学金山学院单招职业适应性考.. 73页

2025年贵州职业技术学院单招职业适应性测试题.. 72页

2025年福建林业职业技术学院单招职业技能测试.. 74页

2025年贵州轻工职业技术学院单招职业倾向性考.. 75页

幼儿园中班十月份计划报告 4页

基于BOPPPS教学模式的“基础会计”课程教学设.. 3页

2025年赤峰工业职业技术学院单招职业倾向性测.. 72页

2025年绍兴文理学院元培学院单招职业技能测试.. 74页

2025年绍兴职业技术学院单招综合素质考试题库.. 73页

2025年幼儿园春季开学典礼活动方案主题 27页

2025年苏州健雄职业技术学院单招职业适应性测.. 74页

2025年幼儿园教育讲座的心得体会 4页

相机租赁合同 4页

菜鸟驿站员工工作合同 5页

学徒工聘用劳动协议汇编3篇 10页

电梯质量手册程序文件 49页

钢结构厂房施工合同范本 11页

员工入职健康体检表健康证明 2页

基地种植主管岗位职责(共8篇) 14页

《基本要道》 187页

《GJB2650-1996 微波元器件性能测试方法》.pd.. 68页