概率算法

2018-03-24 14:50:24

概率算法也叫随机化算法。概率算法允许算法在执行过程中随机地选择下一个计算步骤。在很多情况下，算法在执行过程中面临选择时，随机性选择比最优选择省时，因此概率算法可以在很大程度上降低算法的复杂度。

概率算法的一个基本特征是对所求解问题的同一实例用同一概率算法求解两次可能得到完全不同的效果。这两次求解问题所需的时间甚至所得到的结果可能会有相当大的差别。

一、拉斯维加斯算法

拉斯维加斯（Las Vegas）算法能显著的改进算法的有效性，甚至对某些迄今没有找到有效算法的问题，也能得到满意的算法。

拉斯维加斯算法的一个显著特征是它所做的随机性决策很可能导致算法找不到所需的解。因此通常使用一个boolean类型的方法表示Las Vegas算法。当算法找到了一个解时返回true，否则返回false。

    public static void obstinate(Object x, Object y) {
        // 反复调用拉斯维加斯算法LV(x, y),直到找到问题的一个解,其中x为输入参数，y为问题的解
        boolean success = false;
        while (!success) success = LV(x, y);
    }

二、蒙特卡罗算法

蒙特卡罗算法和拉斯维加斯算法不同的是蒙特卡罗算法是调用有限次算法，并且大概率给出一个正确解。

比如调用一次蒙特卡罗算法得到正确解概率为p，那么连续调用n次该算法都得到错误解的概率是 (1 - p) ^ n，如果p大于0.5，则该式会急剧下降到可以忽略不记。

例如主元素问题中，我们可以每次随机选择一个数来判断其是否为主元素，为真的概率大于0.5，如果我们反复调用这个函数k次，那么k次中全部选错的概率就会非常小，可以到忽略不记的地步。