算法设计与分析 课件 9.4-概率算法 - 蒙特卡罗算法.pptx

算法设计与分析概率算法-蒙特卡罗信息工程大学国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版

思政：国防--催生新技术的源动力“曼哈顿计划”摩纳哥蒙特卡罗冯·诺伊曼

目标： 求问题的准确解特征：求得的解不一定正确，且无法判定所得解是否肯定正确。设p是0.5到1间的实数。若算法得到正确解的概率不小于p，则称该蒙特卡罗算法是p正确的，且p-1/2是该算法的优势。求得正确解的概率依赖于算法所用时间，时间越多，得到正确解的概率越高此外，若对于同一问题，蒙特卡罗算法不会给出不同的正确解答，则称该蒙特卡罗算法是一致的。

应用：数值问题求解 求近似解 近似解精度随计算时间的增加而不断提高。例1：计算?值随机投点法半径为r的圆的外切四边形内投点?

defdarts(n):k=0foriinrange(1,n+1):x=random()#在[0，1)内随机选择一个数作为xy=random()#在[0，1)内随机选择一个数作为yifx**2+y**2=1:k+=1return4*k/n例1：计算?值测试判断题：针对计算Pi值的蒙特卡罗算法实现代码，当n=1000时，独立运行两次程序，会得到一样的结果。A：正确 B：错误

例2：计算定积分设f(x)是[0,1]上的连续函数，且0?f(x)?1。需要计算的积分为。假设向单位正方形内随机地投入n个点(xi,yi)。如果有m个点落入积分区域内，则

defdarts(n):k=0foriinrange(1,n+1):x=random()#在[0，1)内随机选择一个数作为xy=random()#在[0，1)内随机选择一个数作为yify=f(x):k+=1returnk/n例2：计算定积分

例3：主元素问题设数组T[1:n]含有n个元素。当|{i|T[i]=x}|n/2时，称元素x是数组T的主元素。defmajority(t):n=len(t)-1i=randint(1,n)x=t[i]#随机选择数组元素k=0forjinrange(1,n+1):ift[j]==x:k+=1returnkn/2#kn/2时t含有主元素返回true时，一定含有主元素，但返回false时，数组未必不含主元素

重复调用主元素蒙特卡罗算法boolmajority2(int[]t,intn){if(majority(t,n))returntrue;elsereturnmajority(t,n);}设p是算法返回true的概率，则算法可将错误率降低到(1-p)2(1/2)2=1/4。对于任何的?0，重复调用算法?log(1/?)?次，可使错误概率小于?。

测试判断题：蒙特卡罗算法随着执行次数的增多，获得正确解的概率越高A：正确B：错误