The General Principles of Randomized Algorithms
随机算法的一般性原理

最近十几年来,国际上对随机算法(randomized algo-rithm)的研究有了巨大进展。在此期间,随机算法从一个计数理论的工具发展到今天在许多类型的算法中都得到了广泛应用,显示了随机算法本身强大的生命力。所谓随机算法,就是在执行过程中要做出随机选择的算法。随机算法有两种不同类型:其一是总能给出正确的解,两次运行之间唯一的区别是运行时间不同,我们把这种随机算法叫做Las Vegas算法;其二是有时会产生不正确解的算法,然而我们能够界定产生不正确解的概率,我们把这种随机算法叫做Monte Carlo算法。这两种算法哪种更好些,要看它应用于哪类问题,Las Vegas算法可以看成是Monte Carlo算法当错误的概率为零的情况。