《算法设计与分析》第七章随机算法及计算复杂性

《《算法设计与分析》第七章随机算法及计算复杂性》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第七章随机算法及NP完全问题7.1随机算法引言7.2随机算法的类型7.3随机数发生器7.4数值概率算法7.5舍伍德(Sherwood)算法7.6拉斯维加斯（LasVegas）算法7.7蒙特卡罗（MonteCarlo）算法7.8NP完全问题7.1随机算法引言确定性的算法：算法的每一个计算步骤都是确定的，对于相同的输出，每一次执行过程都会产生相同的输出。随机算法：非形式描述随机算法为使用随机函数产生器的算法。算法中的一些判定依赖于随机函数产生器的输出。随机算法对于相同的输入，在不同的运行过程中会得到不同的输出。对于相同的输入，随机算法的执行时间也可能随不

2、同的运行过程而不同。8.1随机算法引言随机算法的优点：1、执行时间和空间，小于同一问题的已知最好的确定性算法；2、实现比较简单，容易理解。很多确定性的算法，其性能很坏。可用随机选择的方法来改善算法的性能。某些方面可能不正确，对特定的输入，算法的每一次运行不一定得到相同结果。出现这种不正确的可能性很小，以致可以安全地不予理睬。7.2随机算法的类型数值概率算法拉斯维加斯（LasVegas）算法蒙特卡罗（MonteCarlo）算法舍伍德（Sherwood）算法。7.2随机算法的类型1、数值概率算法：用于数值问题的求解。所得到的解几乎都是近似解，近似解的精度

3、随着计算时间的增加而不断地提高。2、舍伍德（Sherwood）算法：很多具有很好的平均运行时间的确定性算法，在最坏的情况下性能很坏。引入随机性加以改造，可以消除或减少一般情况和最坏情况的差别。7.2随机算法的类型3、拉斯维加斯（LasVegas）算法：要么给出问题的正确答案，要么得不到答案。反复求解多次，可使失效的概率任意小。4、蒙特卡罗（MonteCarlo）算法：总能得到问题的答案，偶然产生不正确的答案。重复运行，每一次都进行随机选择，可使不正确答案的概率变得任意小。7.3随机数发生器产生随机数的公式：产生0~65535的随机数序列，b、c、d为

4、正整数，称为所产生的随机序列的种子。常数b、c，对所产生的随机序列的随机性能有很大的关系，b通常取一素数。7.3随机数发生器#defineMULTIPLIER0x015A4E35L;#defineINCREMENT1;staticunsignedlongseed;voidrandom_seed(unsignedlongd){if(d==0)seed=time(0);elseseed=d;}unsignedintrandom(unsignedlonglow,unsignedlonghigh){seed=MULTIPLIER*seed+INCREMENT

5、;return((seed>>16)%(high–low)+low);}7.4数值概率算法例：用随机投点法计算值设有一半径为r的圆及其外切四边形。向该正方形随机地投掷n个点。设落入圆内的点数为k。由于所投入的点在正方形上均匀分布，因而所投入的点落入圆内的概率为。所以当n足够大时，k与n之比就逼近这一概率。从而7.4数值概率算法publicdoubledarts(intn){//用随机投点法计算值intk=0;for(inti=1;i<=n;i++){doublex=dart.fRandom();doubley=dart.fRandom();if(

6、(x*x+y*y)<=1)k++;}return4*k/(double)n;}7.5舍伍德(Sherwood)算法一、确定性算法的平均运行时间TA(x)：确定性算法对输入实例的运行时间。Xn：规模为的所有输入实例全体。算法的平均运行时间：存在实例，。例：快速排序算法当输入数据均匀分布时，运行时间是。当输入数据按递增或递减顺序排列时，算法的运行时间变坏7.5舍伍德(Sherwood)算法二、舍伍德算法的基本思想消除不同输入实例对算法性能的影响，使随机算法对规模为的每一个实例，都有：三、期望运行时间：当s(n)与相比很小可以忽略时，舍伍德算法有很好的性能

7、。对所有输入实例而言，运行时间相对均匀。时间复杂性与确定性算法的时间复杂性相当.7.5舍伍德(Sherwood)算法随机快速排序算法算法9.1随机选择枢点的快速排序算法输入：数组A,数组元素的的起始位置low,终止位置high输出：按非降顺序排序的数组A1.template2.voidquicksort_random(TypeA[],intlow,inthigh)3.{4.random_seed(0);/*选择系统当前时间作为随机数种子*/5.r_quicksort(A,low,high);/*递归调用随机快速排序算法*/6.}

8、7.5舍伍德(Sherwood)算法1.voidr_quicksort(TypeA[],intlow,int