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

最近更新

一轴晶矿物光轴与镜轴夹角的测定方法 2页

《土力学》课件赵树德版 75页

一种综合的地质统计学评价方法 2页

一种用于SHDT测井资料处理的拟合平面方法 2页

一种无需振荡器的数字频率抖动电路及其应用 2页

一种新型涡街式流量计的实验研究 2页

2023年人教版六年级语文下册第一次月考考试卷.. 7页

二年级数学上册期末试卷及答案(下载) 7页

机械制造厂车间翻新合同3篇 51页

木材临时仓储运输合同样本3篇 52页

服装行业融资居间协议3篇 49页

服装店装修拆旧协议模板3篇 47页

服装厂办公区改造装修合同3篇 45页

智能化停车场装修合同样本3篇 52页

昌平区KTV装修合同3篇 53页

时尚产业融资居间协议范例3篇 54页

2023年部编版五年级语文下册第一次月考试卷(汇.. 7页

旅游度假村水电装修样本3篇 45页

文物建筑内部修复合同3篇 54页

人教版六年级语文上册期末考试卷 7页

apqp产品质量先期策划(ppt-99页) 97页

2025年工程竣工自评报告三篇 19页

XX学校义务教育优质均衡发展创建实施方案范文.. 8页

顺丁烯二酸酐工艺规程 25页

水土保持方案范文5篇 16页

现场5S管理考核办法 5页

最新TSG-D0001-2022-压力管道安全技术监察规程.. 43页

苹果采摘机械手设计【水果采摘机】(含CAD图纸.. 38页

旋刀式割草机的改进设计【旋刀式割草机的设计.. 19页

《生育制度》全书概要 27页