随机算法比较

1、对比舍伍德算法、拉斯维加斯算法、蒙特卡洛算法的适用范围以及它们 的优缺点。一、舍伍德算法：特点舍伍德算法总能求得问题的一个解，且所求得的解总是正确的。当一个确定性算 法在最坏情况下的计算复杂性与其在平均惜况下的计算复杂性有较大的差别时，可 在这个确定性算法中引入随机性将它改造成一个舍伍徳算法，消除或减少问题的好 坏实例间的这种差别。舍伍德算法的精髓不是避免算法的最坏悄形行为，而是设法 消除这种最坏悄形行为与特定实例之间的关联性。舍伍德算法不会从整体上或平均的改善问题求解的时间复杂度，但可以对一些特 别耗时的特定输入改善至较适中的时间复杂度。设A是一个确定性算法，当它的输入实例为x时所需的计算时

2、间记为tA(x)o设 Xn是算法A的输入规模为n的实例的全体，则当问题的输入规模为n时，算法A 所需的平均时间为_艺 © O)“小卞厂这显然不能排除存在xGXn使得tA(x)»tA(n)的可能性。希望获得一个概率算法B,使得对问题的输入规模为n的每一个实例均有心二几何+心)这就是舍伍德算法设计的基本思想。当s(n)与tA(n)相比可忽略时，舍伍德算法 可获得很好的平均性能。适用范围：1. 快速排序算法2. 线性时间选择算法上述两算法选择合适的划分基准，舍伍德算法随机地选择一个数组元素作为划分 基准，这样既能保证算法的线性时间平均性能，乂避免了计算拟中位数的麻烦。3. 搜索有

3、序表利用数组的小标的索引性质，可以设讣一个随机化搜索算法，以改进算法的搜索 时间复朵性。即随机抽取数组元素若干次，从较近搜索元素x的位置开始做顺序搜 索。4. 跳跃表在跳跃表中随机增加附加指针，以及在该结点处应随机增加指针。二、拉斯维加斯算法：特点：拉斯维加斯算法不会得到不正确的解。一旦用拉斯维加斯算法找到一个解，这个 解就一定是正确解。与蒙特卡罗算法类似，拉斯维加斯算法找到正确解的概率随着 它所用的计算时间的增加而提高。但对所求解的问题，用同一个拉斯维加斯算法反 复求解多次，可以使得求解失效的概率任意小。拉斯维加斯算法能显著改进算法的有效性。棋至于对某些迄今为止找不到有效算 法的问题，也能得

4、到满意的结果。拉斯维加斯算法的一个显著特征是它所做出的随 机性决策有可能导致算法找不到所需的解。因此通常用一个bool型函数来表示拉斯 维加斯型算法。当算法找到一个解时返回true,否则返回falseo拉斯维加斯算法的 典型调用形式为bool success=LV(x,y)：其中x是输入参数；当success的值为true时, y返回问题的解。当success的值为false时，算法未能找到问题的解。此时可以对同 一实例再次独立的调用相同的算法。适用范围：1. n后问题在棋盘上相继的各行中随机地放置皇后，并且注意使新放置的皇后与已放置的皇 后互不攻击，直至n个皇后均已经相容地放置好，或已没有下

5、一个皇后的可放置位 置为止。2. 整数因子分解3. 字符串匹配基于哈希计算的字符串匹配算法是拉斯维加斯型概率算法，母串的子串与模式串 的哈希值相等时并不能保证匹配成功，而需要用朴素的方式进行验证三、蒙特卡罗算法：特点：蒙特卡罗算法总能得到问题的答案，但偶尔会产生不正确的答案。有时并不能判 断给出的答案是否正确。不存在任何近似解答。重复运行算法使得产生不正确解的 概率任意小。在实际应用中，我们常会遇到一些问题，不论是釆用确定性的算法亦或者是随机 算法都无法保证每次都能得到正确的解。蒙特卡罗算法则在一般情况下可以保证对 问题的所有实例都以高概率给出正确的解，但是通常无法判断一个具体解是否正确。 设p是实数，且1/21。如果一个蒙特卡罗算法对于问题的任意实例得到正确解 的概率不小于P，则称该蒙特卡罗算法是p正确的。且称p-'R是该算法的优势。如 果对同一实例，蒙特卡罗算法不会给出两个不同的正确答案，则称该蒙特卡罗算法 是一致的。对于一致的p正确的蒙特卡罗算法，要提高获得正确解的概率，只要执 行该算法若干次，并选择出频次最高的解即可。适用范围：1. 主元素问题2. 素数测试3. 二次探测4. 费马定理舍伍徳算法拉斯维加斯算法蒙特卡罗算法优点 一个正确解 尽量消除这种最 坏情形与特泄实 例之间的关联性 对