文档介绍：随机算法(suàn fǎ)引言
随机(suí jī)算法的优点：
1、执行时间和空间，小于同一问题的已知最好的确定性算法；
2、实现比较简单，容易理解。
很多确定性的算法，其性能很坏。可用随机(suí jī)选择的方法来改善算法的性能。
某些方面可能不正确，对特定的输入，算法的每一次运行不一定得到相同结果。出现这种不正确的可能性很小，以致可以安全地不予理睬。
第1页/共39页
第一页，共40页。
随机算法(suàn fǎ)的类型
数值概率(gàilǜ)算法
拉斯维加斯（Las Vegas）算法
蒙特卡罗（Monte Carlo）算法
舍伍德（Sherwood）算法。
第2页/共39页
第二页，共40页。
随机(suí jī)算法的类型
1、数值概率算法：用于数值问题的求解。所得到的解几乎都是近似解，近似解的精度随着计算时间的增加而不断地提高。
2、舍伍德（Sherwood）算法：很多具有很好的平均运行(yùnxíng)时间的确定性算法，在最坏的情况下性能很坏。引入随机性加以改造，可以消除或减少一般情况和最坏情况的差别。
第3页/共39页
第三页，共40页。
随机(suí jī)算法的类型
3、拉斯维加斯（Las Vegas）算法：要么给出问题的正确答案，要么得不到答案。反复求解多次，可使失效的概率任意(rènyì)小。
4、蒙特卡罗（Monte Carlo）算法：总能得到问题的答案，偶然产生不正确的答案。重复运行，每一次都进行随机选择，可使不正确答案的概率变得任意(rènyì)小。
第4页/共39页
第四页，共40页。
随机数发生器
产生随机数的公式：
产生0~65535的随机数 序列(xùliè)，
b、c、d为正整数，称为所产生的随机序列(xùliè)的种子。
常数b、c，对所产生的随机序列(xùliè)的随机性能有很大的关系，b通常取一素数。
第5页/共39页
第五页，共40页。
随机数发生器
#define MULTIPLIER 0x015A4E35L;
#define INCREMENT 1;
static unsigned long seed;
void random_seed(unsigned long d)
{
if (d==0)
seed = time(0);
else
seed = d;
}
unsigned int random(unsigned long low,unsigned long high)
{
seed = MULTIPLIER * seed + INCREMENT;
return ((seed >> 16) % (high – low) + low);
}
第6页/共39页
第六页，共40页。
数值(shùzí)概率算法
例：用随机投点法计算值
设有一半径为r的圆及其外切四边形。向该正方形随机地投掷n个点。设落入圆内的点数为k。由于所投入(tóurù)的点在正方形上均匀分布，因而所投入(tóurù)的点落入圆内的概率为 。所以当n足够大时，k与n之比就逼近这一概率。从而
第7页/共39页
第七页，共40页。
数值概率(gàilǜ)算法
public double darts(int n)
{ // 用随机(suí jī)投点法计算值
int k=0;
for (int i=1;i <=n;i++) {
double x=();
double y=();
if ((x*x+y*y)<=1) k++;
}
return 4*k/(double)n;
}
第8页/共39页
第八页，共40页。
舍伍德(Sherwood)算法(suàn fǎ)
一、确定性算法的平均运行时间
TA(x) ：确定性算法对输入实例的运行时间。
Xn ：规模为的所有输入实例全体。
算法的平均运行时间：
存在实例 ， 。
例：快速排序算法
当输入数据(shùjù)均匀分布时，运行时间是 。
当输入数据(shùjù)按递增或递减顺序排列时，算法的运行时间变坏
第9页/共39页
第九页，共40页。
舍伍德(Sherwood)算法(suàn fǎ)