[工学]算法设计 随机算法np问题

《[工学]算法设计 随机算法np问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、凸包问题简介凸包（convexhull）8/27/20212随机算法简介定义：在算法中引入随机因素,即通过随机数选择算法的下一步操作。特点：简单、快速一种平衡：随机算法可以理解为在时间、空间和随机三大计算资源中的平衡8/27/20214计算机产生随机数的方法d0=ddn=bdn-1+can=dn%655368/27/202151、数值概率算法：用于数值问题的求解2、Sherwood算法一定能得到问题的正确解常见的四类随机算法：8/27/202163、LasVegas算法或者得到正确的解，或者得不到解。4、MonteCarlo算法一定能得到解，但是得到的解可能不正确

2、，然而这种概率是小的且有界的。常见的四类随机算法：8/27/20217重复性定律设是一次随机试验的成功概率，则N次独立随机试验的成功概率为P=1-(1-)NN例如：=0.05,N=20,P18/27/20218一种重要让步策略：传统算法:以100％成功概率求解确定的问题的最优解近似算法:一种对解质量的让步算法随机算法:一种对求解成功概率和非确定的解质量的让步智能算法:遗传算法、模拟退火法、拟人拟物算法等8/27/20219用随机投点法计算值设有一半径为r的圆及其外切四边形。向该正方形随机地投掷n个点。设落入圆内的点数为k。由于所投入的点在正方形上均匀

3、分布，因而所投入的点落入圆内的概率为。所以当n足够大时，k与n之比就逼近这一概率。从而。doubledarts(intn){//用随机投点法计算值intk=0;for(inti=1;i<=n;i++){doublex=Random();doubley=Random();if((x*x+y*y)<=1)k++;}return4*k/(double)n;}8/27/202110举例:QuickSort传统的快排序算法-总是取第一个元素作为划分元；-算法的最坏运行时间是O(n2)，平均时间是O(nlogn)；-因此存在一些输入实例，使得算法达到最长运行时间，如：降序的

4、序列；随机快排序算法-随机选择一个元素作为划分元；-任何一个输入的期望时间是O(nlogn)；-是一个舍伍德算法；8/27/202111举例:八后问题对于大部分解，八后的位置并不具有系统性-因此可以随机地把它们放在连续的行上，只要注意不要互相威胁。但是可能会失败。解决方案：随机+回溯stopVegaspset01.0000262.00--262.0050.503933.8847.2380.39120.046513.0010.20222.118/27/202112主元素问题设T[1…n]是一个含有n个元素的数组。当

5、{i

6、{T[i]=x}}

7、>n/2时，称元素x为数

8、组T的主元素。majority(intt[],intn){随机产生整数i；intx=t[i];intk=0;for(intj=1;j<=n;j++)if(t[j]==x)k++;return(k>n/2);}8/27/202113主元素问题majority2返回true的概率是p+(1-p)p=1-(1-p)2>3/4majority2(intt[],intn){if(majority(t,n))returntrue;elsereturnmajority(t,n);}8/27/202114主元素问题8/27/202115最小截问题定义：给定一个无向图G(V,E

9、)，找一个截(V1,V2)使得V1和V2间的连边数最小。注：该问题可以用确定性算法（max-flowmin-cutalgorithm）在O(n2)时间内完成。8/27/202116随机算法随机选一条边，将两顶点合一并除去顶点上的环；直到图中只剩下两个顶点；返回剩下两顶点间的连边数；重复版本重复执行算法k次，取返回连边数最小数作为解。8/27/202117示例：#cut=215423541,234,51,234,51,2,3出错概率重复k次出错概率为本算法是一个MonteCarlo型算法8/27/202118模运算同余有以下性质：①若n

10、(a-b)，则a≡b(mod

11、n)。②amodn＝bmodn，则a≡b(modn)。③a≡b(modn),则b≡a(modn)。④a≡b(modn),b≡c(modn),则a≡c(modn)。从以上性质易知，同余类中的每一元素都可作为这个同余类的表示元素。8/27/202119模运算求余数运算（简称求余运算）amodn将整数a映射到集合{0,1,…,n-1}，称求余运算在这个集合上的算术运算为模运算，模运算有以下性质：①[(amodn)+(bmodn)]modn=(a+b)modn。②[(amodn)-(bmodn)]modn=(a-b)modn。③[(amodn)×(bmodn)]modn=

12、(a×b)