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年重庆航天职业技术学院单招职业技能测试.. 74页

2025年年江苏高考英语作文范文 3页

2025年大学大二学生学年自我鉴定 15页

2025年重庆轻工职业学院单招职业技能测试题库.. 73页

高校校园记者新闻写作培训 37页

2025年重庆商务职业学院单招职业适应性测试题.. 75页

2025年年度培训计划表内容模板 60页

固定化光合细菌处理含氯酚废水的特性研究 3页

2025年重庆工贸职业技术学院单招职业倾向性测.. 75页

2025年重庆市内江市单招职业适应性测试题库审.. 74页

2025年重庆市宜宾市单招职业适应性测试题库最.. 74页

2025年重庆市泸州市单招职业倾向性考试题库及.. 75页

2025年长春医学高等专科学校单招职业倾向性考.. 76页

2025年长春汽车职业技术大学单招职业倾向性测.. 76页

2025年长春职业技术学院单招职业技能考试题库.. 74页

2025年长春金融高等专科学校单招职业适应性考.. 76页

2025年大学什么专业好就业 4页

2025年重庆机电职业技术大学单招职业技能考试.. 74页

2025年年事业单位年度总结工作报告 18页

2025年长沙文创艺术职业学院单招职业倾向性考.. 74页

2025年新课程理念下学生学习方式转变的研究【.. 8页

2025年重庆能源职业学院单招职业适应性考试题.. 73页

2025年长沙轨道交通职业学院单招职业倾向性测.. 73页

2025年新药研发的项目策划书3篇 6页

2025年平安夜圣诞节高级文案 17页

哈尔滨市汽车零部件产业国际科技合作状况研究.. 3页

创意英语数字教案:提升学生学习兴趣 9页

人教版一年级数学下册各单元知识点 14页

2024年小学生知识竞赛问答试题及答案(共44题).. 7页

plc1200六层三部电梯控制系统的设计模板 38页