1 / 22
文档名称:

算法第7章概率算法.ppt

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

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

分享

预览

算法第7章概率算法.ppt

上传人:435638 2025/3/15 文件大小:3.07 MB

下载得到文件列表

算法第7章概率算法.ppt

相关文档

文档介绍

文档介绍:该【算法第7章概率算法 】是由【435638】上传分享,文档一共【22】页,该文档可以免费在线阅读,需要了解更多关于【算法第7章概率算法 】的内容,可以使用淘豆网的站内搜索功能,选择自己适合的文档,以下文字是截取该文章内的部分文字,如需要获得完整电子版,请下载此文档到您的设备,方便您编辑和打印。第7章 概率算法
2
理解产生伪随机数的算法
5
掌握拉斯维加斯算法的设计思想
3
掌握数值概率算法的设计思想
6
掌握舍伍德算法的设计思想
1
学习要点
4
掌握蒙特卡罗算法的设计思想
2
随机数
随机数在概率算法设计中扮演着十分重要的角色。在现实计算机上无法产生真正的随机数,因此在概率算法中使用的随机数都是一定程度上随机的,即伪随机数。
线性同余法是产生伪随机数的最常用的方法。由线性同余法产生的随机序列a0,a1,…,an满足
添加标题
其中b0,c0,dm。d称为该随机序列的种子。如何选取该方法中的常数b、c和m直接关系到所产生的随机序列的随机性能。这是随机性理论研究的内容,已超出本书讨论的范围。从直观上看,m应取得充分大,因此可取m为机器大数,另外应取gcd(m,b)=1,因此可取b为一素数。
添加标题
3
1
数值概率算法
Part One
用随机投点法计算值
设有一半径为r的圆及其外切四边形。向该正方形随机地投掷n个点。设落入圆内的点数为k。由于所投入的点在正方形上均匀分布,因而所投入的点落入圆内的概率为 。所以当n足够大
时,k与n之比就逼近这一概率。从而
double Darts(int n)
{ // 用随机投点法计算值
static RandomNumber dart;
int k=0;
for (int i=1;i <=n;i++) {
double x=();
double y=();
if ((x*x+y*y)<=1) k++;
}
return 4*k/double(n);
}
5
计算定积分
设f(x)是[0,1]上的连续函数,且0f(x)1。
需要计算的积分为 ,积分I等于图中的面积G。
在图所示单位正方形内均匀地作投点试验,则随机点落在曲线下面的概率为
假设向单位正方形内随机地投入n个点(xi,yi)。如果有m个点落入
G内,则随机点落入G内的概率
6
解非线性方程组
求解下面的非线性方程组
其中,x1,x2,…,xn是实变量,fi是未知量x1,x2,…,xn的非线性实函数。要求确定上述方程组在指定求根范围内的一组解
在指定求根区域D内,选定一个随机点x0作为随机搜索的出发点。在算法的搜索过程中,假设第j步随机搜索得到的随机搜索点为xj。在第j+1步,计算出下一步的随机搜索增量xj。从当前点xj依xj得到第j+1步的随机搜索点。当x<时,取为所求非线性方程组的近似解。否则进行下一步新的随机搜索过程。
01
03
02
7
舍伍德(Sherwood)算法
设A是一个确定性算法,当它的输入实例为x时所需的计算时间记为tA(x)。设Xn是算法A的输入规模为n的实例的全体,则当问题的输入规模为n时,算法A所需的平均时间为
这显然不能排除存在x∈Xn使得 的可能性。希望获得一个概率算法B,使得对问题的输入规模为n的每一个实例均有
这就是舍伍德算法设计的基本思想。当s(n)与tA(n)相比可忽略时,舍伍德算法可获得很好的平均性能。
8
舍伍德(Sherwood)算法
复习学过的Sherwood算法:
(1)线性时间选择算法
(2)快速排序算法
有时也会遇到这样的情况,即所给的确定性算法无法直接改造成舍伍德型算法。此时可借助于随机预处理技术,不改变原有的确定性算法,仅对其输入进行随机洗牌,同样可收到舍伍德算法的效果。例如,对于确定性选择算法,可以用下面的洗牌算法shuffle将数组a中元素随机排列,然后用确定性选择算法求解。这样做所收到的效果与舍伍德型算法的效果是一样的。
template<class Type>
void Shuffle(Type a[], int n)
{// 随机洗牌算法
static RandomNumber rnd;
for (int i=0;i<n;i++) {
int j=(n-i)+i;
Swap(a[i], a[j]);
}
}
9
跳跃表
01
02
03
04
舍伍德型算法的设计思想还可用于设计高效的数据结构。
提高有序链表效率的一个技巧是在有序链表的部分结点处增设附加指针以提高其搜索性能。在增设附加指针的有序链表中搜索一个元素时,可借助于附加指针跳过链表中若干结点,加快搜索速度。这种增加了向前附加指针的有序链表称为跳跃表。
如果用有序链表来表示一个含有n个元素的有序集S,则在最坏情况下,搜索S中一个元素需要(n)计算时间。
应在跳跃表的哪些结点增加附加指针以及在该结点处应增加多少指针完全采用随机化方法来确定。这使得跳跃表可在O(logn)平均时间内支持关于有序集的搜索、插入和删除等运算。
10

最近更新

物流公司驾驶员劳动合同范本(详尽版) 6页

2025年开学典礼话题作文合集 10页

2025年度绿色建筑办公室租赁合同 8页

2025年开学典礼新生发言稿精选 16页

2025年度绿色住宅小区树木移植与环保监测合同.. 9页

2025年开学作文优秀 13页

2025年急救四大核心技术培训精华 42页

物业管理清洁服务合同范本 6页

物业管理居间合同协议书范本 6页

2025年开业庆典总经理致辞范文 5页

2025年度精密仪器组装代加工服务合同范本 9页

2025年度稀有矿粉竞业禁止交易合同 9页

2025年建设单位承诺书8篇 15页

2025年建议书保护动物350字精选五篇范文 7页

2025年度科技项目居间合作佣金分配与知识产权.. 8页

2025年度科技教育培训机构教师聘用及科技创新.. 8页

2025年心脏CTO病变介入疗法实战解析 70页

2025年度科技博物馆设计与施工合同 9页

物业公司商铺租赁合同模板 6页

2025年建筑技术员本人工作述职报告 19页

2025年度离婚房产证更名及婚前财产协议执行合.. 9页

2025年建筑工地资料员岗位职责范本篇 10页

2025年度矿山安全生产承包经营责任书 9页

2025年度短期旅行保险理赔权益转让合同 7页

艺术舞蹈老师简历模板 1页

服装设计合作协议书 5页

煤炭资源地质勘查设计编写提纲 14页

硫酸铵生产硫酸钾的可行性方案 31页

2022年首都经济贸易大学工商管理专业《管理学.. 22页

学生5mm坐标纸(虚线 word版)直接打印 2页