算法设计与分析 课件 许瑾晨 第九章 概率算法

算法设计与分析算法设计-概率算法信息工程大学国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版一二三算法引例算法基本思想算法分类随机函数典型应用快速排序N皇后求Pi主元素求解重点掌握：1.算法的基本思想2.不同概率算法的区别算法设计与分析概率算法-引例信息工程大学国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版求一串数中的主元素，即出现次数超过一半的数1,2,2,3,2,4,2,4,2,2假设一定存在主元素方法一：排序，位置5的数即为主元素1222222344求一串数中的主元素，即出现次数超过一半的数假设一定存在主元素1,2,2,3,2,4,2,4,2,2方法二：士兵守阵地，留下的士兵就是主元素1223242422VS求一串数中的主元素，即出现次数超过一半的数假设一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守阵地，留下的士兵就是主元素VS1223242422求一串数中的主元素，即出现次数超过一半的数假设一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守阵地，留下的士兵就是主元素VS1223242422求一串数中的主元素，即出现次数超过一半的数假设一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守阵地，留下的士兵就是主元素VS23242422求一串数中的主元素，即出现次数超过一半的数假设一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守阵地，留下的士兵就是主元素VS23242422求一串数中的主元素，即出现次数超过一半的数假设一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守阵地，留下的士兵就是主元素VS23242422求一串数中的主元素，即出现次数超过一半的数假设一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守阵地，留下的士兵就是主元素VS242422求一串数中的主元素，即出现次数超过一半的数假设一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守阵地，留下的士兵就是主元素VS242422求一串数中的主元素，即出现次数超过一半的数假设一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守阵地，留下的士兵就是主元素VS242422求一串数中的主元素，即出现次数超过一半的数假设一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守阵地，留下的士兵就是主元素VS2422求一串数中的主元素，即出现次数超过一半的数假设一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守阵地，留下的士兵就是主元素VS2422求一串数中的主元素，即出现次数超过一半的数假设一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守阵地，留下的士兵就是主元素VS2422求一串数中的主元素，即出现次数超过一半的数假设一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守阵地，留下的士兵就是主元素VS22求一串数中的主元素，即出现次数超过一半的数假设一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守阵地，留下的士兵就是主元素VS22求一串数中的主元素，即出现次数超过一半的数假设一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法二：士兵守阵地，留下的士兵就是主元素VS22求一串数中的主元素，即出现次数超过一半的数假设一定存在主元素1,2,2,3,2,4,2,4,2,2AB方法三：上帝扔骰子，选择后再判断1223242422123456789103求一串数中的主元素，即出现次数超过一半的数假设一定存在主元素1,2,2,3,2,4,2,4,2,2方法三：上帝扔骰子，选择后再判断1223242422123456789102求一串数中的主元素，即出现次数超过一半的数假设一定存在主元素1,2,2,3,2,4,2,4,2,2求一串数中的主元素，即出现次数超过一半的数方法三：上帝投色子方法二：士兵守阵地方法一：排序确定算法概率算法允许算法执行过程中随机地选择计算步骤，因此算法的每一次执行过程可能都不完全相同。算法的每一计算步骤都是确定的，在输入不变的情况下，不管重复执行算法多少次，其结果都完全相同。确定算法：递归、分治、动规、贪心、搜索概率算法测试选择题：本节课针对主元素求解问题给出的三种方法：排序法，士兵守阵地和概率算法，三种算法在平均情况下需要的计算次数分别表示为W1，W2和W3，三者从大到小排序正确的是（）A：W1，W2，W3B：W1，W3，W2C：W2，W3，W1D：W2，W1，W3E：W3，W2，W1F：W3，W1，W2算法设计与分析概率算法-舍伍德信息工程大学国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版当一个确定性算法的平均和最坏时间复杂度差别较大时，可在确定性算法中引入随机性将确定算法改造为概率算法。这类通过引入随机性减少算法的最坏情形对应输入的出现次数的算法称为舍伍德算法。

对确定性算法A，记输入实例I的计算时间为tA(I)。设Dn是算法A的输入规模为n的全体实例，可能存在I∈Dn使得。目标：实现概率算法B，使得对规模为n的问题的每个实例均有。其中，s(n)与相比可忽略。defkth_small(a,b,e,k):#在a[b]~a[e]中找第k小元素ifb>eork<1ork>e-b+1:return-1p=partition(a,b,e)m=p-bifk==m+1:returna[p]ifk<m+1:returnkth_small(a,b,p-1,k)returnkth_small(a,p+1,e,k-m-1)例：选择第k小元素defpartition(a,b,e):#将a[b]~a[e]以基准数为标准分为三部分i=bj=e

x=a[b]whilei<j:#从两边开始搜索与基准数进行比较whilei<janda[j]>=x:j-=1ifi<j:a[i]=a[j]i+=1whilei<janda[i]<x:i+=1ifi<j:a[j]=a[i]j-=1a[i]=xreturni舍伍德算法实现：选择第k小元素defpartition(a,b,e):#将a[b]~a[e]以基准数为标准分为三部分i=bj=ek=b+randint(0,e-b)#随机选择基准元素a[b],a[k]=a[k],a[b]#将随机选择的基准元素与首位元素互换x=a[b]whilei<j:whilei<janda[j]>=x:j-=1ifi<j:a[i]=a[j]i+=1whilei<janda[i]<x:i+=1ifi<j:a[j]=a[i]j-=1a[i]=xreturni优势：

对所有实例的计算时间相对均匀，计算总能求得问题的一个解，且求得的解总是正确的。关键：

与相应的确定算法相比，其时间复杂性并没有改进。测试判断题：舍伍德算法可以降低算法的最坏时间复杂度A：

正确B：错误算法设计与分析概率算法-拉斯维加斯信息工程大学国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版

拉斯维加斯算法可以显著地改进算法的有效性(得到正确解的可能性)，甚至对某些迄今为止找不到有效算法的问题，也能得到满意的结果。

特征:随机性决策有可能导致算法找不到所需的解。算法找到正确解的概率随所用计算时间的增加而提高，得到的解一定是正确解，但算法可能找不到解。对同一个问题，用拉斯维加斯算法反复求解多次，可使求解失败的概率任意小。

拉斯维加斯算法应用形式：反复调用拉斯维加斯算法LV(x,y)，直到找到问题的一个解。voidobstinate(Objectx,Objecty){booleansuccess=false;while(!success)success=lv(x,y);}n后问题：

在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。1234567812345678QQQQQQQQN皇后问题的拉斯维加斯算法实现：

算法是否得到正确解一方面取决于随机性，更重要的则取决于算法运行的时间，只要有足够的运行时间，就可以得到正确解。测试判断题：拉斯维加斯算法可能得不到问题的解，但若得到一个解，解一定是正确的。A：

正确B：错误算法设计与分析概率算法-蒙特卡罗信息工程大学国家级实验教学示范中心计算机学科组规划教材算法设计与分析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]上的连续函数，且0f(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+=1returnk>n/2#k>n/2时t含有主元素返回true时，一定含有主元素，但返回false时，数组未必不含主元素重复调用主元素蒙特卡罗算法boolmajority2(int[]t,intn){if(majority(t,n))returntrue;e