拉斯维加斯算法与蒙特卡罗算法是什么?有什么区别?
0 1241
0
该提问暂无详细描述
收藏
2021-02-01 19:35 更新 空心人 •  3374
共 1 个回答
高赞 时间
0

蒙特卡罗算法和拉斯维加斯算法并不是算法的名称,而是对一类随机算法的特性的概括。 那么“蒙特卡罗”是一种什么特性呢?我们知道,既然是随机算法,在采样不全时,通常不能保证找到最优解,只能说是尽量找。那么根据怎么个“尽量”法,我们把随机算法分成两类: ** •蒙特卡罗算法:采样越多,越近似最优解; •拉斯维加斯算法:采样越多,越有机会找到最优解;**

蒙特卡罗算法

举个例子:假如筐里有100个苹果,让我每次闭眼拿1个,挑出最大的。于是我随机拿1个,再随机拿1个跟它比,留下大的,再随机拿1个……我每拿一次,留下的苹果都至少不比上次的小。拿的次数越多,挑出的苹果就越大,但我除非拿100次,否则无法肯定挑出了最大的。这个挑苹果的算法,就属于蒙特卡罗算法——尽量找好的,但不保证是最好的

拉斯维加斯算法

而拉斯维加斯算法,则是另一种情况。假如有一把锁,给我100把钥匙,只有1把是对的。于是我每次随机拿1把钥匙去试,打不开就再换1把。我试的次数越多,打开(最优解)的机会就越大,但在打开之前,那些错的钥匙都是没有用的。这个试钥匙的算法,就是拉斯维加斯的——尽量找最好的,但不保证能找到 所以你看,这两个词并不深奥,它只是概括了随机算法的特性,算法本身可能复杂,也可能简单。这两个词本身是两座著名赌城,因为赌博中体现了许多随机算法,所以借过来命名。 这两类随机算法之间的选择,往往受到问题的局限。如果问题要求在有限采样内,必须给出一个解,但不要求是最优解,那就要用蒙特卡罗算法。反之,如果问题要求必须给出最优解,但对采样没有限制,那就要用拉斯维加斯算法。 参考:https://www.zhihu.com/question/20254139/answer/33572009

收藏
2021-02-01 19:39 更新 小眼的铁板烧 •  3526