简档(randomized algorithm )是指需要利用随机数发生器的算法，其中算法所执行的一些选择取决于随机数发生器所生成的随机数。

随机化算法有时也称为概率算法，但如果以此方式区分两者： (例如果取得结果的途径)是随机的，那么在拉斯维加斯如果取得的解是否正确具有随机性，则称为概率算法，如蒙特卡罗算法。

分治、动态规划、贪婪算法、回溯和分支定界等算法的各个计算步骤已经确定，概率算法可以在运行中随机选择下一个计算步骤。 在许多情况下，当算法在运行中遇到一个选择时，概率算法可以大大降低算法的复杂性，因为随机选择往往比最优选择更为节省。 概率算法的基本特征之一是用相同的概率算法对所求解问题的相同实例进行两次求解可以获得完全不同的效果(所需时间或计算结果)。算法分类

求解数值随机化算法数值问题的近似解，精度随着计算时间的延长而提高。 消除舍伍德算法算法的最坏情况操作与特定实例的相关性并没有提高平均性能，也没有故意避免算法的最坏情况操作。拉斯维加斯算法是解决问题的正确答案，但可能找不到答案。蒙特卡罗算法求出问题的精确解，但该解未必准确，一般不能有效判定正确性。随机化算法的特点

1 .当执行算法时遇到选择时，概率算法通常比最优选择算法节省时间。

2 .用相同的概率算法对所求问题的同一事例进行两次求解，两次求解所需的时间和得到的结果可能有很大的差异。

舍伍德算法

总是求出问题的正确答案。 如果确定算法最坏情况下的计算复杂度和平均情况下的计算复杂度相差很大，则可以在确定算法中引入随机性，并将其改造成舍伍德算法，以消除或减少问题不同实例之间的计算时间差。 舍伍德算法的精髓所在——对等方试图消除这种最坏行为与特定实例的相关性，而不是避免算法最坏的情况行为。

蒙特卡罗算法：

该方法用于求解问题的精确解(或精确解而不是近似解)，但并不能保证求解的正确。 也就是说，有时根据蒙特卡罗算法求出的解是错误的。 但这类算法能控制得到错误解的概率，简单高效，是一种有价值的随机算法。

拉斯维加斯算法：

的解总是正确的，但拉斯维加斯的算法有时总是找不到解。 一般来说，求出正确解的概率随着计算时间的延长而变高。 因此，为了减少求解失败的概率，可以使用一个拉斯维加斯算法对同一实例多次重复执行该算法。

随机数

由于现实中的计算机无法产生真随机数，随机化算法中使用的随机数都在一定程度上是随机的，即伪随机数。 (线性同余) ) )。

例：

计算圆周率

doubledarts(intn )//随机投点法计算r值static RandomNumber dart； int k=0； for(intI=1； i=n； I ) { double x=dart.fRandom (； double y=dart.fRandom (； if(x*xy*y )=1) k； }return4*k/double(n； (计算定积分

doubledarts(intn )//随机投点法计算定积静态随机模型； int k=0； for(intI=1； i=n； I ) { double x=dart.fRandom (； double y=dart.fRandom (； if(y=f ) ) k； }returnk/double(n； 6求解非线性方程

函数极小值法：

在求解路线的区域d内，选定随机点x作为随机搜索的出发点。

1 .按照预先选定的分布(正态分布、均匀分布等)，逐个选择随机点x，计算目标函数，满足精度要求的随机点为近似解。

2 .算法搜索中，将步骤j的随机搜索中得到的随机搜索点设为x。 在步骤j 1中，生成随机搜索方向和步骤，计算下一步骤的增量Xi。 根据当前点Xix，获得步骤j 1的随机搜索点。 其中，作为所求韭菜线性方程的近似解。 否则，进行下一个新的随机搜索过程

while((minEpsilon ) ) /随机搜索步骤系数if ) FXmin )的计算成功，增大步骤系数min=fx； //fx是目标函数值，min是当前最佳值a*=k； //

a为步长因子 success = true; } else{/l搜索失败，减少步长因子 mm++; if(mm> M a/= k; success = false;} for(inti=1;i<n;i++)//计算随机搜索方向和增量 r[i]| = 2.0 * rnd.fRandom() – 1;/r为搜索方向向量 if (success) for(int i=1; i<= n; i++)dx[i]=a * r[i]; else for(int i=1;i <n; f+) dxi= a* r[i]; 舍伍德算法

设A是一个确定性算法，当它的输入实例为x时所需的计算时间记为tA(x)。设X，是算法A的输入规模为n的实例的全体，则当问题的输入规模为n时，算法A所需的平均时间为:

这显然不能排除存在x∈Xn使得tA(x)>>tA‘(n)的可能性。希望获得一个随机化算法B，使得对问题的输入规模为n的每个实例均有:
tB(x)=tA'(n)+ s(n)
这就是舍伍德算法设计的基本思想。
当s(n)与tA(n)相比可忽略时，舍伍德算法可获得很好的平均性能。

有时也会遇到这样的情况，即所给的确定性算法无法直接改造成舍伍德型算法。此时可借助于随机预处理技术，不改变原有的确定性算法，仅对其输入进行随机洗牌，同样可收到舍伍德算法的效果。
 

/*例如，对于确定性选择算法，可以用下面的洗牌算法shuffle将数组a中元素随机排列，然后用确定性选择算法求解。这样做所收到的效果与舍伍德型算法的效果是一样的。*/template<class Type>void Shuffle(Type a[], int n){//随机洗牌算法 static RandomNumber rnd; for (int i=0;i<n;i++) { int j=rnd.Random(n-i)+i; Swap(a[i], a[j]); }}

跳跃表

●舍伍德型算法的设计思想还可用于设计高效的数据结构。
●如果用有序链表来表示一个含有n个元素的有序集S，则在最坏情况下，搜索S中一个元素需要2(n)计算时间。
●提高有序链表效率的一个技巧是在有序链表的部分结点处增设附加指针以提高其搜索性能。在增设附加指针的有序链表中搜索一个元素时，可借助于附加指针跳过链表中若干结点，加快搜索速度。这种增加了向前附加指钍的有序链表称为跳跃表

完全跳跃表与完全二叉搜索树的情形非常类似。它虽然可以有效地支持成员搜索运算，但不适应于集合动态变化的情况。集合元素的插入和删除运算会破坏完全跳跃表原有的平衡状态，影响后继元素搜索的效率。
 

为了在动态变化中维持跳跃表中附加指针的平衡性，必须使跳跃表中k级结点数维持在总结点数的一定比例范围内。注意到在一个完全跳跃表中，50%的指针是0级指针;25%的指针是1级指针; … (100/2k+1)%的指针是k级指针。因此，在插入-一个元素时，以概率1/2引入一个0级结点，以概率1/4引入-一个1级结点，…以概率1/2k+1引入一个k级结点。

另一方面，二个i级结点指向下一个同级或更高级的结点，它所跳过的体点数不再准确地维持在2-1。经过这样的修改，就可以在插入或删除一个元素时，通过对跳跃表的局部修改来维持其平衡性。

在一个完全跳跃表中，具有i级指针的结点中有一半同时具有i+1级指针。为了维持跳跃表的平衡性，可以事先确定一个实0≤p<1,并要求在跳跃表中维持在具有i级指针的结点中同时具有计1级指针的结点所占比例约为p.为此目的，在插入一个新结点时，先将其结点级别初始化为0，然后用随机数生成器反复地产生一个[0，1]间的随机实数q。如果qsp，则使新结点级别增加1,直至q≥p。

拉斯维加斯算法： //拉斯维加斯算法的一个显著特征是它所作的随机性决策有可能导致算法找不到所需的解。void obstinate(Object x, Object y){//反复调用拉斯维加斯算法LV(x,y),直到找到问题的一个解y bool success= false; while (!success) success=lv(x,y);}