算法
数值概率算法常用于数值问题的求解。这类算法所得到的往往是近似解。而且近似解的精度随计算时间的增加不断提高。在许多情况下，要计算出问题的精确解是不可能或没有必要的，因此用数值概率算法可得到满意的解。举个例子：计算的近似值时，我们可以在单位圆的外接正方形内随机撒
个点，设有k个点落在单位圆内，可以得到
4k。

数值概率算法不是本文的重点，这里仅作简单介绍。有兴趣的同学可自行研究。
12拉斯维加斯（LasVegas）算法
拉斯维加斯算法不会得到不正确的解，也就是说，一旦用拉斯维加斯算法找到一个解，那么这个解肯定是正确的。但是有时候用拉斯维加斯算法可能找不到解。算法所用的时间越多，得到解的概率就越高。
13蒙特卡罗（Mo
teCarlo）算法
又是一个以赌城命名的算法。通常所说的蒙特卡罗算法分为两类。1．蒙特卡罗判定：蒙特卡罗算法总是能给出问题的解，但是偶尔也可能会产生非正确
3
fIOI2008冬令营论文顾研
的解。求得正确解的概率依赖于算法所用的时间。蒙特卡罗判定的错误必须是“单边”的，即实际答案是YES（NO），算法给出的答案可能是NO（YES），但是实际答案是NO（YES），则算法给出的答案一定是NO（YES）。因此蒙特卡罗算法得到正确解的概率随着计算次数的增加而提高，即在时间和精度上的一种平衡。最常见的蒙特卡罗判定是众所周知的MillerRabi
素数测试字符串匹配的Rabi
Karp算法。2．蒙特卡罗抽样：它的基本思想是，对于所求的问题，通过试验的方法，通过大样本来模拟，得到这个随机变量的期望值，并用它作为问题的解。它是以一个概率模型为基础，按照这个模型所描绘的过程，通过模拟实验的结果，作为问题的近似解的过程。蒙特卡罗抽样的主要步骤可参考附录1。本文第三章的模拟退火算法就使用了蒙特卡罗抽样的思想。
14舍伍德（Sherwood）算法
舍伍德算法总能求得问题的一个解，且所求得的解总是正确的。当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时，可以在这个确定算法中引入随机性将它改造成一个舍伍德算法，消除或减少问题的好坏实例之间的这种差别。舍伍德算法精髓不是避免算法的最坏情况的发生，而是设法消除这种最坏行为与特定实例之间的关联性。舍伍德算法最广泛的一个应用就是快速排序的随机化实现。本文第二章的随机增量算法就是舍伍德算法的一种应用。
除了随机算法，国家集训队2006年论文：唐文斌《浅谈“调整”思想在信息学竞赛中的应用》中很多带r