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页

淘宝店铺转让合同标准文本示例 5页

介绍几种新的低给液工艺和设备 2页

介电矿物摩擦静电选矿的理论基础及应用 2页

人民币贬值对我国进出口贸易的影响与对策 2页

人参季节性吸收根发育形态学研究(英文) 2页

产生二羧酸的耐高温酵母菌的研究 2页

交流立柱式电风扇风量测试方法探讨 2页

亚太地区城市技术合作网在沪成立 2页

《空气的性质》ppt课件 35页

《短歌行》公开课优秀课件 28页

二烷基亚磷酸酯与硫脲反应产物的探讨 2页

污水处理服务合同 7页

乙酰胆碱酯酶两个酶解肽片氨基酸序列分析 2页

水利工程建设项目合同基本条款 6页

民间融资抵押保证合同标准文本 6页

民政局简易离婚合同范文 5页

中短波发射台对变电站二次系统影响分析 2页

中小企业会计文化现状、成因及对策初探 2页

中国铲土运输机械研究会召开年会 2页

橱柜采购合同协议书 7页

棋牌室加盟承包合同 6页

中国封建社会中资本主义萌芽问题之研究 2页

中国农村金融学会一九八八年课题研究会研究规.. 2页

两种凸轮机构的压力角分析和优化研究 2页

东方杯叶吸虫囊蚴的体外培养和发育的研究 2页

世界排球发展动态与我国进攻技术、战术的发展.. 2页

不断探索与国际金融组织合作的新思路 2页

不同三轴应力条件下岩石电阻率变化的试验研究.. 2页

上海市科学学研究会民主选出第一届理事会成员.. 2页