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