随机算法比较

《随机算法比较》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

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

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

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

5、符串匹配基于哈希计算的字符串匹配算法是拉斯维加斯型概率算法，母串的子串与模式串的哈希值相等时并不能保证匹配成功，而需要用朴素的方式进行验证三、蒙特卡罗算法：l特点：蒙特卡罗算法总能得到问题的答案，但偶尔会产生不正确的答案。有时并不能判断给出的答案是否正确。不存在任何近似解答。重复运行算法使得产生不正确解的概率任意小。在实际应用中，我们常会遇到一些问题，不论是采用确定性的算法亦或者是随机算法都无法保证每次都能得到正确的解。蒙特卡罗算法则在一般情况下可以保证对问题的所有实例都以高概率给出正确的解，但是通常无法判断一个具体解是否正确。设p是实数，且。如果一个蒙特卡罗算法对于问题的任意实例得到

6、正确解的概率不小于p，则称该蒙特卡罗算法是p正确的。且称是该算法的优势。如果对同一实例，蒙特卡罗算法不会给出两个不同的正确答案，则称该蒙特卡罗算法是一致的。对于一致的p正确的蒙特卡罗算法，要提高获得正确解的概率，只要执行该算法若干次，并选择出频次最高的解即可。l适用范围：1.主元素问题2.素数测试3.二次探测4.费马定理舍伍德算法拉斯维加斯算法蒙特卡罗算法优点①一个正确解②尽量消除这种最坏情形与特定实例之间的关联性③对实例的计算时间复杂性均匀①找到的解一定是正确解②显著改善算法的有效性①用于求问题的准确解②算法耗时越多，正确解概率越高缺点①不会改善整体平均时间复杂度①可能找不到解①得到

7、的解可能不正确