0041算法笔记——介绍随机化算法及其与随机数问题的关系

1、随机化算法

(1)描述 ：随机化算法是这样一种算法，在算法中使用了随机函数，且随机函数的返回值直接或者间接的影响了算法的执行流程或执行结果。随机化算法基于随机方法，依赖于概率大小。

(2)****分类 ：通常情况下，在处理概率（随机化）算法时通常会将其主要分为四类：数值概率方法、蒙特卡罗方法、拉斯维加斯方法以及舍伍德方法。

数值随机化算法 ：数值概率算法常用于数值问题的求解。这类算法所得到的往往是近似解。而且近似解的精度随计算时间的增加不断提高。在许多情况下，要计算出问题的精确解是不可能或没有必要的，因此用数值概率算法可得到相当满意的解。

蒙特卡罗（Monte Carlo）算法 ：被用来求问题的准确解。通过使用蒙特卡罗算法可以获得问题的一个解；然而这个解未必是正确的；其获得正确解的概率受所使用时间的影响；当所花费的时间越长时；得到正确解的概率就会越高；该算法的主要缺点就在于此；一般情况下；难以准确判断所得结果是否可靠。

拉斯维加斯（Las Vegas） 算法：它不会有错误的结果；只要找到了一个结果，则必定是正确的答案；然而，在某些情况下，则有可能无法找到任何结果。与蒙特卡罗方法相似的是其行为特征。通过反复运行同一拉斯维加斯算法于同一问题实例足够多的次数后，则该问题实例求解失败的概率可降至任意低水平。

_