概率算法(新)

1算法设计与分析黄刘生中国科学技术大学计算机系国家高性能计算中心（合肥）2008.8.192第一部分概率算法3Ch.1绪论1.故事：想象自己是神化故事的主人公，你有一张不易懂的地图，上面描述了一处宝藏的藏宝地点。经分析你能确定最有可能的两个地点是藏宝地点，但二者相距甚远。假设你如果已到达其中一处，就立即知道该处是否为藏宝地点。你到达两处之一地点及从其中一处到另一处的距离是5天的行程。进一步假设有一条恶龙，每晚光顾宝藏并从中拿走一部分财宝。假设你取宝藏的方案有两种：§1.1引言地点1地点2你5天5天5天4方案1.花4天的时间计算出准确的藏宝地点，然后出发寻宝，一旦出发不能重新计算方案2.有一个小精灵告诉你地图的秘密，但你必须付给他报酬，相当于龙3晚上拿走的财宝Prob1.1.1若忽略可能的冒险和出发寻宝的代价，你是否接受小精灵的帮助？显然，应该接受小精灵的帮助，因为你只需给出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引言}期望赢利：x-7.5y62.意义该故事告诉我们：当一个算法面临某种选择时，有时随机选择比耗时做最优选择更好，尤其是当最优选择所花的时间大于随机选择的平均时间的时侯显然，概率算法只能是期望的时间更有效，但它有可能遭受到最坏的可能性。73.期望时间和平均时间的区别确定算法的平均执行时间输入规模一定的所有输入实例是等概率出现时，算法的平均执行时间。概率算法的期望执行时间反复解同一个输入实例所花的平均执行时间。因此，对概率算法可以讨论如下两种期望时间①平均的期望时间：所有输入实例上平均的期望执行时间②最坏的期望时间：最坏的输入实例上的期望执行时间84.例子①快速排序中的随机划分要求学生写一算法，由老师给出输入实例，按运行时间打分，大部分学生均不敢用简单的划分，运行时间在1500-2600ms，三个学生用概率的方法划分，运行时间平均为300ms。②8皇后问题系统的方法放置皇后(回溯法)较合适，找出所有92个解O(2n)，若只找92个其中的任何一个解可在线性时间内完成O(n)。随机法：随机地放置若干皇后能够改进回溯法，特别是当n较大时③判断大整数是否为素数确定算法无法在可行的时间内判断一个数百位十进制数是否素数，否则密码就不安全。概率算法将有所作为：若能接受一个任意小的错误的概率95.概率算法的特点(1)不可再现性在同一个输入实例上，每次执行结果不尽相同，例如①N-皇后问题概率算法运行不同次将会找到不同的正确解②找一给定合数的非平凡因子每次运行的结果不尽相同，但确定算法每次运行结果必定相同(2)分析困难要求有概率论，统计学和数论的知识106.约定随机函数uniform：随机，均匀，独立①设a，b为实数，ab,uniform(a,b)返回x，a≤xb②设i，j为整数，i≤j,uniform(i..j)=k,i≤k≤j③设X是非空有限集，uniform(X)∈X11例1：设p是一个素数，a是一个整数满足1≤ap，a模除p的指数(index)是满足ai≡1(modp)的最小正整数i。它等于集合X={ajmodp|j≥1}的势，即i=|X|。例如，2模除31的指数等于5：25mod31=1,X={21mod31,22mod31,23mod31,24mod31,25mod31};5模除31的指数是3，即53mod31=1,3模除31的指数是30。由费马(Fermat)定理(ap-1≡1(modp))可知，a模p的指数总是恰好整除p-1.例如，设p=31，若a=2，则30÷5=6；若a=5，则30÷3=10。因此，X中的j至多为p-1，由此可得一种在X中随机，均匀和独立地取一个元素的算法。12ModularExponent(a,j,p){//求方幂模s=ajmodp,注意先求aj可能会溢出s←1;whilej0do{if(jisodd)s←s·amodp;a←a2modp;j←jdiv2;}returns;}Draw(a,p){//在X中随机取一元素j←uniform(1..p-1);returnModularExponent(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选的合适，该周期长度会非常长。TC中可用rand()和srand(time),用GNUC更好141.基本特征随机决策在同一实例上执行两次其结果可能不同在同一实例上执行两次的时间亦可能不太相同2.分类Numerical,MonteCarlo,LasVegas,Sherwood.很多人将所有概率算法(尤其是数字的概率算法)称为MonteCarlo算法§1.2概率算法的分类15①数字算法随机性被最早用于求数字问题的近似解例如，求一个系统中队列的平均长度的问题，确定算法很难得到答案概率算法获得的答案一般是近似的，但通常算法执行的时间越长，精度就越高，误差就越小使用的理由–现实世界中的问题在原理上可能就不存在精确解例如，实验数据本身就是近似的，一个无理数在计算机中只能近似地表示–精确解存在但无法在可行的时间内求得有时答案是以置信区间的形式给出的§1.2概率算法的分类16②MonteCarlo算法(MC算法)蒙特卡洛算法1945年由J.VonNeumann进行核武模拟提出的。它是以概率和统计的理论与方法为基础的一种数值计算方法，它是双重近似：一是用概率模型模拟近似的数值计算，二是用伪随机数模拟真正的随机变量的样本。这里我们指的MC算法是：若问题只有1个正确的解，而无近似解的可能时使用MC算法例如，判定问题只有真或假两种可能性，没有近似解因式分解，我们不能说某数几乎是一个因子特点：MC算法总是给出一个答案，但该答案未必正确，成功(即答案是正确的)的概率正比于算法执行的时间缺点：一般不能有效地确定算法的答案是否正确§1.2概率算法的分类17③LasVegas算法(LV算法)LV算法绝不返回错误的答案。特点：获得的答案必定正确，但有时它仍根本就找不到答案。和MC算法一样，成功的概率亦随算法执行时间增加而增加。无论输入何种实例，只要算法在该实例上运行足够的次数，则算法失败的概率就任意小。④Sherwood算法Sherwood算法总是给出正确的答案。当某些确定算法解决一个特殊问题平均的时间比最坏时间快得多时，我们可以使用Sherwood算法来减少，甚至是消除好的和坏的实例之间的差别。§1.2概率算法的分类18这类算法主要用于找到一个数字问题的近似解§2.1π值计算实验：将n根飞镖随机投向一正方形的靶子，计算落入此正方形的内切圆中的飞镖数目k。假定飞镖击中方形靶子任一点的概率相等(用计算机模拟比任一飞镖高手更能保证此假设成立)设圆的半径为r，面积s1=πr2；方靶面积s2=4r2由等概率假设可知落入圆中的飞镖和正方形内的飞镖平均比为：由此知：Ch.2数字概率算法2244krnr4/4nknk19求π近似值的算法为简单起见，只以上图的右上1/4象限为样本Darts(n){k←0;fori←1tondo{x←uniform(0,1);y←uniform(0,1);//随机产生点(x,y)if(x2+y2≤1)thenk++;//圆内}return4k/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π值计算21MonteCarlo积分(但不是指我们定义的MC算法)1、概率算法1设f:[0,1]→[0,1]是一个连续函数，则由曲线y=f(x),x轴,y轴和直线x=1围成的面积由下述积分给出：向单位面积的正方形内投镖n次，落入阴影部分的镖的数目为k，则显然，只要n足够大§2.2数字积分(计算定积分的值)10()Sfxdx/1kSSknn/Skn1xy1221.概率算法1HitorMiss(f,n){k←0;fori←1tondo{x←uniform(0,1);y←uniform(0,1);ify≤f(x)thenk++;}returnk/n;}Note:是S/4的面积，∵π=S,∴§2.2数字积分(计算定积分的值)1201xdx12041xdx231.概率算法1Ex2.在机器上用估计π值，给出不同的n值及精度。Ex3.设a,b,c和d是实数，且a≤b,c≤d,f:[a,b]→[c,d]是一个连续函数，写一概率算法计算积分：注意，函数的参数是a,b,c,d,n和f,其中f用函数指针实现，请选一连续函数做实验，并给出实验结果。§2.2数字积分(计算定积分的值)12041xdx()bafxdx241.概率算法1*Ex4.设ε,δ是(0,1)之间的常数，证明：若I是的正确值，h是由HitorHiss算法返回的值，则当n≥I(1-I)/ε2δ时有：Prob[|h-I|ε]≥1–δ上述的意义告诉我们：Prob[|h-I|≥ε]≤δ,即：当n≥I(1-I)/ε2δ时，算法的计算结果的绝对误差超过ε的概率不超过δ，因此我们根据给定ε和δ可以确定算法迭代的次数解此问题时可用切比雪夫不等式，将I看作是数学期望。§2.2数字积分(计算定积分的值)10()fxdx22(1)11((1))44IInII252.概率算法2更有效的概率算法是：在积分区间上随机均匀地产生点，求出这些点上的函数值的算术平均值，再乘以区间的宽度：Crude(f,n,a,b){sum←0;fori←1tondo{x←uniform(a,b);sum←sum+f(x);}return(b-a)sum/n;}§2.2数字积分(计算定积分的值)11()()(),nbiiaifxdxbafxaxbn262.概率算法2用HitorMiss和Crude运行三次的结果为：假定和存在，由算法求得的估算值的方差反比于点数n。当n足够大时，估计的分布近似为正态分布。对于给定的迭代次数n，Crude算法的方差不会大于HitorMiss的方差。但不能说，Crude算法总是优于HitorMiss。因为后者在给定的时间内能迭代的次数更多。例如，计算π值时，Crude需计算平方根，而用投镖算法darts时无需计算平方根。§2.2数字积分(计算定积分的值)3.141855,3.141422,3.14143413.141662,3.141486,3.141527hitncrude亿()bafxdx2()bafxdx273.确定的算法梯形算法将区间分为n-1个子区间，每个子区间内的长度为δ，Trapezoid(f,n,a,b){//假设n≥2delta←(b-a)/(n-1);sum←(f(a)+f(b))/2;forx←a+deltastepdeltatob–deltadosum←sum+f(x)returnsum×delta;}§2.2数字积分(计算定积分的值)f(a)f(b)=fafa22积分值((+)+(+)+...+)