第10章 概率算法(完).ppt

《第10章 概率算法(完).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第10章概率算法2021/7/21第10章概率算法Page210.1概述10.2舍伍德(Sherwood)型概率算法10.3拉斯维加斯(LasVegas)型概率算法10.4蒙特卡罗(MonteCarlo)型概率算法10.5实验项目——随机数发生器第10章概率算法2021/7/21第10章概率算法Page310.1.1概率算法的设计思想10.1.2随机数发生器10.1概述2021/7/21第10章概率算法Page4概率算法把“对于所有合理的输入都必须给出正确的输出”这一求解问题的条件放宽，把随机性的选择注入到算法中，在算法执行

2、某些步骤时，可以随机地选择下一步该如何进行，同时允许结果以较小的概率出现错误，并以此为代价，获得算法运行时间的大幅度减少。10.1.1概率算法的设计思想2021/7/21第10章概率算法Page5例如，判断表达式f(x1,x2,…,xn)是否恒等于0。概率算法首先生成一个随机n元向量(r1,r2,…,rn)，并计算f(r1,r2,…,rn)的值，如果f(r1,r2,…,rn)≠0，则f(x1,x2,…,xn)≠0；如果f(r1,r2,…,rn)＝0，则或者f(x1,x2,…,xn)恒等于0，或者是(r1,r2,…,rn)比较

3、特殊，如果这样重复几次，继续得到f(r1,r2,…,rn)＝0的结果，那么就可以得出f(x1,x2,…,xn)恒等于0的结论，并且测试的随机向量越多，这个结果出错的可能性就越小。2021/7/21第10章概率算法Page6一般情况下，概率算法具有以下基本特征：（1）概率算法的输入包括两部分，一部分是原问题的输入，另一部分是一个供算法进行随机选择的随机数序列；（2）概率算法在运行过程中，包括一处或若干处随机选择，根据随机值来决定算法的运行；（3）概率算法的结果不能保证一定是正确的，但可以限定其出错概率；（4）概率算法在不同的运

4、行中，对于相同的输入实例可以有不同的结果，因此，对于相同的输入实例，概率算法的执行时间可能不同。2021/7/21第10章概率算法Page7对于确定性算法，通常分析在平均情况下以及最坏情况下的时间复杂性。对于概率算法，通常分析在平均情况下以及最坏情况下的期望时间复杂性，即由概率算法反复运行同一输入实例所得的平均运行时间。概率算法的时间性能需要强调的是，“随机”并不意味着“随意”。2021/7/21第10章概率算法Page8目前，在计算机上产生随机数还是一个难题，因为在原理上，这个问题只能近似解决。计算机中产生随机数的方法通常

5、采用线性同余法，产生的随机数序列为a0,a1,…,an，满足：（式10.1）其中，b≥0，c≥0，m＞0，d≤m。d称为随机数发生器的随机种子（RandomSeed），当b、c和m的值确定后，给定一个随机种子，由式10.1产生的随机数序列也就确定了。10.1.2随机数发生器2021/7/21第10章概率算法Page9计算机语言提供的随机数发生器，一般会需要一个随机种子，这个随机种子可以是系统当前的日期或时间。下面给出利用C++语言中的随机函数rand产生的分布在任意区间[a,b)上的随机数算法。算法10.1——随机数发生器i

6、ntRandom(inta,intb){returnrand()%(b-a)+a;//rand()产生[a,b)之间的随机整数}C++描述2021/7/21第10章概率算法Page1010.2.1快速排序10.2.2选择问题10.2舍伍德(Sherwood)型概率算法2021/7/21第10章概率算法Page11舍伍德(Sherwood)型概率算法分析确定性算法在平均情况下的时间复杂性时，通常假定算法的输入实例满足某一特定的概率分布。事实上，很多算法对于不同的输入实例，其运行时间差别很大。例如快速排序算法，若输入实例是等概率

7、均匀分布，其时间复杂性是O(nlog2n)，若输入实例基本有序，其时间复杂度是O(n2)。因此，可以采用舍伍德型概率算法来消除算法的时间复杂性与输入实例间的这种联系。2021/7/21第10章概率算法Page12算法10.2——随机洗牌voidRandomShuffle(intn,intr[]){for(i=0;i

8、仅对其输入实例随机排列（称为洗牌）。假设输入实例为整型，下面的随机洗牌算法可在线性时间实现对输入实例的随机排列。2021/7/21第10章概率算法Page13舍伍德型概率算法总能求得问题的一个解，并且所求得的解总是正确的。但与其相对应的确定性算法相比，舍伍德型概率算法的平均时间复杂性没有改