《概率算法新》PPT课件.ppt
《《概率算法新》PPT课件.ppt》由会员分享,可在线阅读,更多相关《《概率算法新》PPT课件.ppt(147页珍藏版)》请在三一办公上搜索。
1、,1,算法设计与分析黄刘生中国科学技术大学计算机系 国家高性能计算中心(合肥),2,第一部分概率算法,3,Ch.1 绪论,1.故事:想象自己是神化故事的主人公,你有一张不易懂的地图,上面描述了一处宝藏的藏宝地点。经分析你能确定最有可能的两个地点是藏宝地点,但二者相距甚远。假设你如果已到达其中一处,就立即知道该处是否为藏宝地点。你到达两处之一地点及从其中一处到另一处的距离是5天的行程。进一步假设有一条恶龙,每晚光顾宝藏并从中拿走一部分财宝。假设你取宝藏的方案有两种:,1.1 引言,4,方案1.花4天的时间计算出准确的藏宝地点,然后出发寻宝,一旦出发不能重新计算 方案2.有一个小精灵告诉你地图的秘
2、密,但你必须付给他报酬,相当于龙3晚上拿走的财宝 若忽略可能的冒险和出发寻宝的代价,你是否接受小精灵的帮助?显然,应该接受小精灵的帮助,因为你只需给出3晚上被盗窃的财宝量,否则你将失去4晚被盗财宝量。但是,若冒险,你可能做得更好!,1.1 引言,5,设x是你决定之前当日的宝藏价值,设y是恶龙每晚盗走的宝藏价值,并设x9y 方案1:4天计算确定地址,行程5天,你得到的宝藏价值为:x-9y 方案2:3y付给精灵,行程5天失去5y,你得到的宝藏价值为:x-8y 方案3:投硬币决定先到一处,失败后到另一处(冒险方案)一次成功所得:x-5y,机会1/2 二次成功所得:x-10y,机会1/2,1.1 引言
3、,期望赢利:x-7.5y,6,2.意义 该故事告诉我们:当一个算法面临某种选择时,有时随机选择比耗时做最优选择更好,尤其是当最优选择所花的时间大于随机选择的平均时间的时侯 显然,概率算法只能是期望的时间更有效,但它有可能遭受到最坏的可能性。,7,3.期望时间和平均时间的区别确定算法的平均执行时间 输入规模一定的所有输入实例是等概率出现时,算法的平均执行时间。概率算法的期望执行时间 反复解同一个输入实例所花的平均执行时间。因此,对概率算法可以讨论如下两种期望时间平均的期望时间:所有输入实例上平均的期望执行时间最坏的期望时间:最坏的输入实例上的期望执行时间,8,4.例子快速排序中的随机划分要求学生
4、写一算法,由老师给出输入实例,按运行时间打分,大部分学生均不敢用简单的划分,运行时间在1500-2600ms,三个学生用概率的方法划分,运行时间平均为300ms。8皇后问题系统的方法放置皇后(回溯法)较合适,找出所有92个解 O(2n),若只找92个其中的任何一个解可在线性时间内完成O(n)。随机法:随机地放置若干皇后能够改进回溯法,特别是当n较大时判断大整数是否为素数确定算法无法在可行的时间内判断一个数百位十进制数是否素数,否则密码就不安全。概率算法将有所作为:若能接受一个任意小的错误的概率,9,5.概率算法的特点(1)不可再现性 在同一个输入实例上,每次执行结果不尽相同,例如N-皇后问题概
5、率算法运行不同次将会找到不同的正确解找一给定合数的非平凡因子每次运行的结果不尽相同,但确定算法每次运行结果必定相同(2)分析困难 要求有概率论,统计学和数论的知识,10,6.约定 随机函数uniform:随机,均匀,独立设a,b为实数,ab,uniform(a,b)返回x,a x b 设i,j为整数,ij,uniform(i.j)=k,i k j 设X是非空有限集,uniform(X)X,11,例1:设p是一个素数,a是一个整数满足1ap,a模除p的指数(index)是满足ai1(mod p)的最小正整数i。它等于集合X=aj mod p|j 1的势,即i=|X|。例如,2模除31的指数等于5
6、:25 mod 31=1,X=21 mod 31,22 mod 31,23 mod 31,24 mod 31,25 mod 31;5模除31的指数是3,即53 mod 31=1,3模除31的指数是30。由费马(Fermat)定理(ap-1 1(mod p)可知,a模p的指数总是恰好整除p-1.例如,设p=31,若a=2,则305=6;若a=5,则303=10。因此,X中的j至多为p-1,由此可得一种在X中随机,均匀和独立地取一个元素的算法。,12,ModularExponent(a,j,p)/求方幂模s=aj mod p,注意先求aj可能会溢出s 1;while j0 do if(j is o
7、dd)s sa mod p;a a2 mod p;j j div 2;return s;Draw(a,p)/在X中随机取一元素j uniform(1.p-1);return ModularExponent(a,j,p);/在X中随机取一元素,13,伪随机数发生器在实用中不可能有真正的随机数发生器,多数情况下是用伪随机数发生器代替。大多数伪随机数发生器是基于一对函数:S:X X,这里X足够大,它是种子的值域R:X Y,Y是伪随机数函数的值域使用S获得种子序列:x0=g,xi=S(xi-1),i0然后使用R获得伪随机序列:yi=R(xi),i 0该序列必然是周期性的,但只要S和R选的合适,该周期长
8、度会非常长。TC中可用rand()和srand(time),用GNU C更好,14,基本特征随机决策在同一实例上执行两次其结果可能不同在同一实例上执行两次的时间亦可能不太相同分类Numerical,Monte Carlo,Las Vegas,Sherwood.很多人将所有概率算法(尤其是数字的概率算法)称为Monte Carlo算法,1.2 概率算法的分类,15,数字算法随机性被最早用于求数字问题的近似解例如,求一个系统中队列的平均长度的问题,确定算法很难得到答案概率算法获得的答案一般是近似的,但通常算法执行的时间越长,精度就越高,误差就越小使用的理由现实世界中的问题在原理上可能就不存在精确解
9、例如,实验数据本身就是近似的,一个无理数在计算机中只能近似地表示精确解存在但无法在可行的时间内求得有时答案是以置信区间的形式给出的,1.2 概率算法的分类,16,Monte Carlo算法(MC算法)蒙特卡洛算法1945年由J.Von Neumann进行核武模拟提出的。它是以概率和统计的理论与方法为基础的一种数值计算方法,它是双重近似:一是用概率模型模拟近似的数值计算,二是用伪随机数模拟真正的随机变量的样本。这里我们指的MC算法是:若问题只有1个正确的解,而无近似解的可能时使用MC算法例如,判定问题只有真或假两种可能性,没有近似解 因式分解,我们不能说某数几乎是一个因子特点:MC算法总是给出一
10、个答案,但该答案未必正确,成功(即答案是正确的)的概率正比于算法执行的时间缺点:一般不能有效地确定算法的答案是否正确,1.2 概率算法的分类,17,Las Vegas算法(LV算法)LV算法绝不返回错误的答案。特点:获得的答案必定正确,但有时它仍根本就找不到答案。和MC算法一样,成功的概率亦随算法执行时间增加而增加。无论输入何种实例,只要算法在该实例上运行足够的次数,则算法失败的概率就任意小。Sherwood算法Sherwood算法总是给出正确的答案。当某些确定算法解决一个特殊问题平均的时间比最坏时间快得多时,我们可以使用Sherwood算法来减少,甚至是消除好的和坏的实例之间的差别。,1.2
11、 概率算法的分类,18,这类算法主要用于找到一个数字问题的近似解2.1 值计算实验:将n根飞镖随机投向一正方形的靶子,计算落入此正方形的内切圆中的飞镖数目k。假定飞镖击中方形靶子任一点的概率相等(用计算机模拟比任一飞镖高手更能保证此假设成立)设圆的半径为r,面积s1=r2;方靶面积s2=4r2由等概率假设可知落入圆中的飞镖和正方形内的飞镖平均比为:由此知:,Ch.2 数字概率算法,19,求近似值的算法为简单起见,只以上图的右上1/4象限为样本Darts(n)k 0;for i 1 to n do x uniform(0,1);y uniform(0,1);/随机产生点(x,y)if(x2+y2
12、 1)then k+;/圆内return 4k/n;实验结果:=3.141592654n=1000万:3.140740,3.142568(2位精确)n=1亿:3.141691,3.141363(3位精确)n=10亿:3.141527,3.141507(4位精确),2.1 值计算,20,求近似值的算法Ex.1 若将y uniform(0,1)改为 y x,则上述的算法估计的值是什么?,2.1 值计算,21,Monte Carlo积分(但不是指我们定义的MC算法)1、概率算法1设f:0,1 0,1是一个连续函数,则由曲线y=f(x),x轴,y轴和直线x=1围成的面积由下述积分给出:向单位面积的正方
13、形内投镖n次,落入阴影部分的镖的数目为k,则显然,只要n足够大,2.2 数字积分(计算定积分的值),22,概率算法1HitorMiss(f,n)k 0;for i 1 to n do x uniform(0,1);y uniform(0,1);if y f(x)then k+;return k/n;Note:是S/4的面积,=S,2.2 数字积分(计算定积分的值),23,概率算法1Ex2.在机器上用 估计值,给出不同的n值及精度。Ex3.设a,b,c和d是实数,且a b,c d,f:a,b c,d是一个连续函数,写一概率算法计算积分:注意,函数的参数是a,b,c,d,n和f,其中f用函数指针实
14、现,请选一连续函数做实验,并给出实验结果。,2.2 数字积分(计算定积分的值),24,概率算法1*Ex4.设,是(0,1)之间的常数,证明:若I是 的正确值,h是由HitorMiss算法返回的值,则当n I(1-I)/2时有:Prob|h-I|1 上述的意义告诉我们:Prob|h-I|,即:当n I(1-I)/2时,算法的计算结果的绝对误差超过的概率不超过,因此我们根据给定和可以确定算法迭代的次数解此问题时可用切比雪夫不等式,将I看作是数学期望。,2.2 数字积分(计算定积分的值),25,概率算法2更有效的概率算法是:在积分区间上随机均匀地产生点,求出这些点上的函数值的算术平均值,再乘以区间的
15、宽度:Crude(f,n,a,b)sum 0;for i 1 to n do x uniform(a,b);sum sum+f(x);return(b-a)sum/n;,2.2 数字积分(计算定积分的值),26,概率算法2用HitorMiss和Crude运行三次的结果为:假定 和 存在,由算法求得的估算值的方差反比于点数n。当n足够大时,估计的分布近似为正态分布。对于给定的迭代次数n,Crude算法的方差不会大于HitorMiss的方差。但不能说,Crude算法总是优于HitorMiss。因为后者在给定的时间内能迭代的次数更多。例如,计算值时,Crude需计算平方根,而用投镖算法darts时无
16、需计算平方根。,2.2 数字积分(计算定积分的值),27,确定的算法梯形算法将区间分为n-1个子区间,每个子区间内的长度为,Trapezoid(f,n,a,b)/假设 n 2delta(b-a)/(n-1);sum(f(a)+f(b)/2;for x a+delta step delta to b delta dosum sum+f(x)return sum delta;,2.2 数字积分(计算定积分的值),28,确定的算法 当n=100,=3.140399 当n=1,000,=3.141555 当n=10,000,=3.141586 当n=100,000,=3.141593一般地,在同样的精
17、度下,梯形算法的迭代次数少于MC积分,但是有时确定型积分算法求不出解:例如,f(x)=sin2(100)!x),。但是用梯形算法时,当2 n101时,返回值是0。若用MC积分则不会发生该类问题,或虽然发生,但概率小得多。,2.2 数字积分(计算定积分的值),29,多重积分 在确定算法中,为了达到一定的精度,采样点的数目随着积分维数成指数增长,例如,一维积分若有100个点可达到一定的精度,则二维积分可能要计算1002个点才能达到同样的精度,三维积分则需计算1003个点。(系统的方法)但概率算法对维数的敏感度不大,仅是每次迭代中计算的量稍增一点,实际上,MC积分特别适合用于计算4或更高维数的定积分
18、。若要提高精度,则可用混合技术:部分采用系统的方法,部分采用概率的方法,2.2 数字积分(计算定积分的值),30,上一节可以认为,数字概率算法被用来近似一个实数,本节可用它们来估计一个整数值。例如,设X为有限集,若要求X的势|X|,则当X较大时,枚举显然不现实。问题:随机选出25人,你是否愿意赌其中至少有两个人生日相同吗?直觉告诉我们,一般人都不愿意赌其成立,但实际上成立的概率大于50%。,2.3 概率计数,31,一般地,从n个对象中选出k个互不相同的对象,若考虑 选择的次序,则不同的选择有 种;若允许重复选取同 一对象,则不同的选法共有 种。因此,从n个对象(允许同一对象重复取多次)中随机均
19、匀地选择出的k个对象互不相同的概率是:,注意a,b和b,a是不同的取法。由此可知,上述问题中,25个人生日互不相同的概率是:这里假设:不考虑润年,一年中人的生日是均匀分布的。,2.3 概率计数,32,由Stirling公式知:可得 假定 近似地 实际上,若,2.3 概率计数,33,因此,随机选出25个人中生日互不相同的概率约43%,由此可知至少有两人生日相同的概率约为57%。此例提示:有回放抽样,大集合通过第一次重复来估计集合大小。,2.3 概率计数,34,求集合X的势 设X是具有n个元素的集合,我们有回放地随机,均匀和独立地从X中选取元素,设k是出现第1次重复之前所选出的元素数目,则当n足够
20、大时,k的期望值趋近为,这里利用此结论可以得出估计|X|的概率算法:,2.3 概率计数,35,求集合X的势SetCount(X)k 0;S;a uniform(X);do k+;S Sa;a uniform(X);while(a S)return 2k2/注意:k的期望值是,上述算法n需足够大,且运行多次后才能确定n=|X|,即取多次运行后的平均值才能是n。该算法的时间和空间均为,因为,36,EX.用上述算法,估计整数子集1n的大小,并分析n对估计值的影响。,2.3 概率计数,37,多重集合中不同对象数目的估计 假设磁带上记录有Shakespeare全集,如何统计其中使用了多少个不同的单词?为
21、简单起见,同一词的复数,被动语态等可作为不同项。设N是磁带上总的单词数,n是其中不同词的数目方法一:对磁带上的单词进行外部排序,时间(NlgN),空间需求较大方法二:在内存中建一散列表,表中只存储首次出现的单词,平均时间O(N),空间(n),2.3 概率计数,38,多重集合中不同对象数目的估计方法三:若能忍受某种误差及已知n或N的上界M,则存在一个时空性能更好的概率算法解此问题。设U是单词序列的集合,设参数m稍大于lgM,可令:设h:U 0,1m 是一个散列函数,它用伪随机数的方法将U中的单词映射为长度为m的位串。(目的,减少存储量)若y是一个长度为k的位串,用yi表示y的第i位,1ik;用(
22、y,b),b 0,1来表示满足yi=b的最小的i,若y的位中没有哪一位等于b,则=k+1,2.3 概率计数,39,多重集合中不同对象数目的估计WordCount()y1.m+1 0;/初始化 for 磁带上每个单词x do/顺序读磁带i(h(x),1);/x的散列值中等于1的最小位置,表示x是/以 打头的yi 1;/将该位置置为1return(y,0);/返回y中等于0的最小位置,40,多重集合中不同对象数目的估计上界估计 例,不妨设m=4,h(x1)=0011,h(x2)=1010,h(x3)=0110,h(x4)=0010,算法返回:k=4也就是说,若算法返回4,说明磁带上至少有3个单词的
23、散列地址是以1,01,001打头的,但绝没有以0001打头的单词。一个以0001开始的随机二进制串的概率是2-4=1/16磁带上不太可能有多于16个互不相同的单词,即:互异单词的上界2k 因为只要h的随机性好,则对16个不同的单词xi,(h(xi),1)4(这些单词的散列值等于1的最小位置均不为4)的概率是(15/16)16 35.6%e-1(每个xi不等于0001的概率的15/16,16个单词均不以0001开头的概率为35.6%),只有此时算法才可能返回4。,2.3 概率计数,41,多重集合中不同对象数目的估计实际上,若算法的返回值k为4,则n=16的概率为:Probk=4|n=16=31.
24、75%下界估计 一个以001开始的随机二进制串的概率是2-3在磁带上互不相同的单词数目少于4的可能性不大,即:互不相同单词的下界2k-2 因为,对4个互不相同的单词中,至少有一个是以001打头的概率为1-(7/8)441.4%。实际上,若算法的返回值k为4,则n=4的概率为:Probk=4|n=4=18.75%粗略的分析告诉我们:磁带上互不相同的单词数目为:2k-22k实际上,算法WordCount估计的n应等于2k/1.54703性能:时间O(N),空间:O(lgN),2.3 概率计数,42,例如,矩阵乘法,求逆,计算特征值和特征向量只有一些特殊的应用,概率算法会执行得比确定性算法要好。,2
25、.4 线性代数中的数字问题,43,Sherwood算法能够平滑不同输入实例的执行时间设A是一个确定算法,tA(x)是解某个实例x的执行时间,设n是一整数,Xn是大小为n的实例的集合假定Xn中每一个实例是等可能出现的,则算法A解一个大小为n的实例的平均执行时间是:这里无法消除这样的可能性,存在一个size为n的实例x使得:设B是一个概率算法,对每个size为n的实例x满足:这里tB(x)是算法B在实例x上的期望值,s(n)是概率算法B为了取得均匀性所付出的成本。,Ch.3 Sherwood算法,44,虽然算法B的执行时间也可能偶然地在某一个实例x上大于,但这种偶然性行为只是由于算法所做的概率选择
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 概率算法新 概率 算法 PPT 课件
链接地址:https://www.31ppt.com/p-5536278.html