转载需注明出处:https://www.codelast.com/

查看本系列文章合集,请点击这里

  • 区别

讲到这里,稍微提一下,随机算法可以分为两类:蒙特卡洛算法 & 拉斯维加斯算法。
对蒙特卡洛算法来说,采样越多,越近似最优解
对拉斯维加斯算法来说,它永远给出正确解的随机化算法,总是给出正确结果,或是返回失败。

在固定的计算资源下,蒙特卡洛一定可以得到一个解,但拉斯维加斯不一定。
文章来源:https://www.codelast.com/

  • 拉斯维加斯算法实例

这里有一个很无趣的拉斯维加斯算法的例子:有10把钥匙,每次随机地取一把钥匙来开门,直到把门打开。如果只给你5次尝试的机会(在固定的计算资源下),那么可能能打开门(给出正确结果),也可能无法打开门(返回失败)。

当然,这个例子可能不能拿来套在蒙特卡罗算法身上,但这并不妨碍我们理解拉斯维加斯算法。

  • 参考文献

► 维基百科:拉斯维加斯算法

[原创] 蒙特卡罗算法 对比 拉斯维加斯算法

发表评论

电子邮件地址不会被公开。 必填项已用*标注