算法设计 郑宇军 石海鹤 陈胜勇 算法设计（第12章）

《算法设计 郑宇军 石海鹤 陈胜勇 算法设计（第12章）》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第12章随机算法基本概念舍伍德算法蒙特卡洛算法拉斯维加斯算法12.1基本概念NP完全问题：很难在短时间内求出问题的精确解近似算法：在可接受的时间内求出问题的近似解参数化算法：在特定的参数范围内对问题进行精确求解随机算法:以一定的概率对问题进行求解总是能够计算出一个解，但不一定保证解的正确性求解不一定成功；但只要成功，就能得到一个正确的12.1基本概念近似计算圆周率xy12.1基本概念近似计算圆周率向方框内随机掷点x=r(0,1),y=r(0,1)落在圆内概率π/4近似值≈圆内点数c/总点数nxyn越大，近似度越高12.1基本概念随机数的生成

2、0～1随机数：线性同余法伪随机数12.1基本概念抛硬币问题输入：一次事件中抛硬币次数m，以及事件的模拟次数n一个数组H，其中H[0],H[1],H[2],…,H[m]分别表示硬币正面朝上的次数为0,1,2,…,m的事件概率12.1基本概念抛硬币问题的模拟算法AlgorithmTossCoins(m,n:int)beginletH=newint[m+1];fori=0ton-1doletcount=0;forj=0tomdocountcount+Random(2);H[count]H[count]+1;forj=0tomdoH[j]H[

3、j]/n;returnH;end1/0分别表示正/反面12.2舍伍德算法一些算法有着比较好的平均时间性能，但在个别特殊实例上的效率很差。此时可考虑在算法中引入随机性，减少或消除这种最坏情形12.2舍伍德算法随机化快速排序每次随机地从待排序数组区间[left..right]中选择一个下标v，并将A[v]与A[left]交换，然后按照快速排序算法继续子问题的划分和排序12.2舍伍德算法随机化快速排序AlgorithmRandomizedQuickSort(A:int[];left,right:int)beginif(left

4、nletv=left+Random(right–left+1);(A[v],A[left])(A[left],A[v]);letp=Partition(A,left,right);RandomizedQuickSort(A,left,p-1);RandomizedQuickSort(A,p+1,right);end12.2舍伍德算法有序链表搜索问题输入：有序链表S，以及待搜索的元素x输出：x在S中的位置index，未找到则返回−112.2舍伍德算法有序链表搜索问题随机选择数组元素若干次，从较接近搜索元素x的位置开始进行顺序查找12.2舍伍

5、德算法有序链表搜索问题AlgorithmRandomizedSearch(S:OrderedList();x:int)beginletindex=0,vmax=S.Small,m=floor(sqrt(S.count));fori=1tomdoletj=Random(S.count)+1,y=S.value[j];if(vmax

6、]=x)thenreturnindex;elsereturn-1;end12.3蒙特卡洛算法众数问题设选举中每名参选人只能投一票；如果某个候选人的得票数超过一半，则该候选人赢得了选举若T是一个含有n个元素的数组，当T中等于x的元素个数超过一半时，称x是T的众数12.3蒙特卡洛算法众数问题输入：含有n个元素的数组T输出：判断T中是否存在众数12.3蒙特卡洛算法众数问题排序，而后统计其中相同元素出现的次数中位数(第n/2小的数)查找，如果众数存在，它肯定等于中位数随机选取一个数x作为候选众数，然后统计x在数组中出现的次数易证x是否为众数，但无法

7、证明众数不存在12.3蒙特卡洛算法众数问题AlgorithmMajority(T:int[])beginletn=

8、T

9、,k=0;letx=T[Random(n)];fori=0ton-1doif(T[i]=x)thenkk+1;return(k>n/2);//k>n/2时T含有众数end12.3蒙特卡洛算法对于解某个判定问题的蒙特卡洛算法，当它返回true时解总是正确的，仅当它返回false时有可能产生错误的解，称这类蒙特卡洛算法为偏真算法如果一个蒙特卡洛算法对于问题的任一实例得到正确解的概率不小于p(1/2

10、法是p正确的，并称(p−1/2)是该算法的优势对于任一问题实例，如果蒙特卡洛算法不会给出2个不同的解，那么称蒙特卡洛算法是一致的12.3蒙特卡洛算法素数判定问题输入：一个大于1的