拉斯维加斯算法和回溯算法解决问题的区别

Question

如题所述

Answer 1

　　一旦用拉斯维加斯算法找到一个解，这个解就一定是正确解。
　　但有时用拉斯维加斯算法找不到解。与蒙特卡罗算法类似，拉斯维加斯算法找到正确解的概率随着它所用的计算时间的增加而提高。
　　对于所求解问题的任一实例，用同一拉斯维加斯算法反复对该实例求解足够多次，可使求解失败的概率任意小。
　　拉斯维加斯算法的一个显著特征是它所作的随机性决策有可能导致算法找不到所需的解。