概率算法简介
——————————————————————————————————
很多算法的每一个计算步骤都是固定的,而在下面我们要讨论的概率算法,允许算法在执行的过程中
随机选择下一个计算步骤。许多情况下,当算法在执行过程中面临一个选择时,随机性选择常比最优选择
省时。因此概率算法可在很大程度上降低算法的复杂度。
概率算法的一个基本特征是对所求解问题的同一实例用同一概率算法求解两次可能得到完全不同的效果。
这两次求解问题所需的时间甚至所得到的结果可能会有相当大的差别。一般情况下,可将概率算法大致分
为四类数值概率算法,蒙特卡罗()算法,拉斯维加斯()算法和舍伍德
()算法。
数值概率算法常用于数值问题的求解。这类算法所得到的往往是近似解。而且近似解的精度随计算时间的
增加不断提高。在许多情况下,要计算出问题的精确解是不可能或没有必要的,因此用数值概率算法可得
到相当满意的解。
蒙特卡罗算法用于求问题的准确解。对于许多问题来说,近似解毫无意义。例如,一个判定问题其解为
“是”或“否”,二者必居其一,不存在任何近似解答。又如,我们要求一个整数的因子时所给出的解答必须
是准确的,一个整数的近似因子没有任何意义。用蒙特卡罗算法能求得问题的一个解,但这个解未必是正
确的。求得正确解的概率依赖于算法所用的时间。算法所用的时间越多,得到正确解的概率就越高。蒙特
卡罗算法的主要缺点就在于此。一般情况下,无法有效判断得到的解是否肯定正确。
拉斯维加斯算法不会得到不正确的解,一旦用拉斯维加斯算法找到一个解,那么这个解肯定是正确的。但
是有时候用拉斯维加斯算法可能找不到解。与蒙特卡罗算法类似。拉斯维加斯算法得到正确解的概率随着
它用的计算时间的增加而提高。对于所求解问题的任一实例,用同一拉斯维加斯算法反复对该实例求解足
够多次,可使求解失效的概率任意小。
舍伍德算法总能求得问题的一个解,且所求得的解总是正确的。当一个确定性算法在最坏情况下的计算复
杂性与其在平均情况下的计算复杂性有较大差别时,可以在这个确定算法中引入随机性将它改造成一个舍
伍德算法,消除或减少问题的好坏实例间的这种差别。舍伍德算法精髓不是避免算法的最坏情况行为,而
是设法消除这种最坏行为与特定实例之间的关联性。
本文简要的介绍一下数值概率算法和舍伍德算法。
首先来谈谈随机数。随机数在概率算法设计中扮演着十分重要的角色。在现实计算机上无法产生真正的随
机数,因此在概率算法中使用的随机数都是一定程度上随机的,即伪随机数。
产生随机数最常用的方法是线性同余法。由线性同余法产生的随机序列 满足
其中!!! 。 称为该随机序列的种子。
下面我们建立一个随机数类 " #$ ,该类包含一个由用户初始化的种子 。给定种子之
后,既可产生与之相应的随机数序列。 是一个无符号长整型数,既可由用户指定也可由系统时间
自动产生。$% &'(()'*
$% $%+%,-',)*
$%)-(*
" #$
.////+%0