一、定義：

特卡羅是一類隨機(jī)方法的統(tǒng)稱。這類方法的特點(diǎn)是，可以在隨機(jī)采樣上計(jì)算得到近似結(jié)果，隨著采樣的增多，得到的結(jié)果是正確結(jié)果的概率逐漸加大，但在（放棄隨機(jī)采樣，而采用類似全采樣這樣的確定性方法）獲得真正的結(jié)果之前，無(wú)法知道目前得到的結(jié)果是不是真正的結(jié)果。?

拉斯維加斯方法是另一類隨機(jī)方法的統(tǒng)稱。這類方法的特點(diǎn)是，隨著采樣次數(shù)的增多，得到的正確結(jié)果的概率逐漸加大，如果隨機(jī)采樣過(guò)程中已經(jīng)找到了正確結(jié)果，該方法可以判別并報(bào)告，但在但在放棄隨機(jī)采樣，而采用類似全采樣這樣的確定性方法之前，不保證能找到任何結(jié)果（包括近似結(jié)果）?

二、場(chǎng)景舉例?

假如筐里有100個(gè)蘋果，讓我每次閉眼拿1個(gè)，挑出最大的。于是我隨機(jī)拿1個(gè)，再隨機(jī)拿1個(gè)跟它比，留下大的，再隨機(jī)拿1個(gè)……我每拿一次，留下的蘋果都至少不比上次的小。拿的次數(shù)越多，挑出的蘋果就越大，但我除非拿100次，否則無(wú)法肯定挑出了最大的。這個(gè)挑蘋果的算法，就屬于蒙特卡羅算法——盡量找好的，但不保證是最好的。

而拉斯維加斯算法，則是另一種情況。假如有一把鎖，給我100把鑰匙，只有1把是對(duì)的。于是我每次隨機(jī)拿1把鑰匙去試，打不開就再換1把。我試的次數(shù)越多，打開（最優(yōu)解）的機(jī)會(huì)就越大，但在打開之前，那些錯(cuò)的鑰匙都是沒有用的。這個(gè)試鑰匙的算法，就是拉斯維加斯的——盡量找最好的，但不保證能找到。?

三、結(jié)論?

?蒙特卡羅算法???

：采樣越多，越近似最優(yōu)解；

?拉斯維加斯算法：采樣越多，越有機(jī)會(huì)找到最優(yōu)解；?

這兩類隨機(jī)算法之間的選擇，往往受到問題的局限。如果問題要求在有限采樣內(nèi)，必須給出一個(gè)解，但不要求是最優(yōu)解，那就要用蒙特卡羅算法。反之，如果問題要求必須給出最優(yōu)解，但對(duì)采樣沒有限制，那就要用拉斯維加斯算法。?