隨機(jī)算法肄渗，顧名思義至会，就是在算法的運(yùn)行過(guò)程中引入了隨機(jī)機(jī)制，因此每次運(yùn)行得到的結(jié)果和運(yùn)行時(shí)間不一樣浑吟。常見(jiàn)的隨機(jī)算法有兩種Monte Carlo算法 和 Las Vegas算法。

Monte Carlo 算法耗溜。算法總能夠給出一個(gè)結(jié)果组力，不過(guò)這個(gè)結(jié)果是一個(gè)隨機(jī)變量，有一定概率是正確的抖拴。其中燎字，給出正確結(jié)果的概率是一個(gè)大于1/2的數(shù)腥椒。

Las Vegas算法。算法不一定能在有限時(shí)間內(nèi)給出結(jié)果候衍，不過(guò)一旦它給出了結(jié)果笼蛛，就一定是正確的。其中蛉鹿，給出結(jié)果的概率是一個(gè)任意大于0的數(shù)滨砍。

容易證明，上述兩類算法雖然只是以一定概率的到正確結(jié)果妖异，但是可以通過(guò)運(yùn)行多次惋戏，使得成功概率無(wú)限逼近1。

案例1 Ramsey Numbers

“任意6個(gè)人的聚會(huì)他膳，總能夠找出3個(gè)互相認(rèn)識(shí)的或者互相不認(rèn)識(shí)的”响逢。相信大家對(duì)這個(gè)表述并不陌生。歸結(jié)到數(shù)學(xué)表示上棕孙，它實(shí)際上說(shuō)的是舔亭，對(duì)于一個(gè)有6個(gè)頂點(diǎn)的無(wú)向圖，我們總能找到size為3的獨(dú)立集(任意兩點(diǎn)不相連)或者最大團(tuán)（任意兩點(diǎn)之間均相連）蟀俊。特別的钦铺，我們還有一個(gè)數(shù)Ramsey Number來(lái)表述這一數(shù)學(xué)問(wèn)題：

根據(jù)對(duì)稱性，容易得到误甚。一般的，我們可以給出R(k,l)的一個(gè)上界的估計(jì): （還沒(méi)有搞懂）谱净。我們也希望得到它的一個(gè)下界窑邦。思路也很簡(jiǎn)單，考慮一個(gè)含有n個(gè)頂點(diǎn)的隨機(jī)圖壕探。每?jī)蓚€(gè)點(diǎn)之間都有的幾率有邊相連冈钦。我們考察這個(gè)時(shí)候圖中找不到size為k的monotone set的概率P(n)。如果概率大于0李请，那么就說(shuō)明實(shí)際的要比n要大瞧筛。記V 的導(dǎo)出子圖X中找不到monotone set為事件。

案例2 Satisfiability of Boolean Formulas (SAT)

布爾可滿足性問(wèn)題导盅，指給定一個(gè)合取范式(conjunctive norm form)较幌，如果能夠找到一組變量賦值，使得最后表達(dá)式的結(jié)果為真白翻，我們則說(shuō)這個(gè)式子是可滿足的乍炉。

一般來(lái)說(shuō)绢片，這是一個(gè)NP問(wèn)題。但是當(dāng)給定的式子滿足一定條件時(shí)岛琼，我們能夠很輕易得判斷他們是否是可滿足的底循。

證明思路其實(shí)很簡(jiǎn)單。我們一共有種賦值方法槐瑞。對(duì)于子表達(dá)式熙涤，有種賦值方法使得子表達(dá)式不滿足。因此困檩，所有的不滿足的賦值最多有

所以我們至少能夠找到一組賦值祠挫，使得給定的合取范式為真。

下面我們可以給出找到這個(gè)賦值的方法窗看。思路也很簡(jiǎn)單茸歧，對(duì)變量一個(gè)一個(gè)賦值。比如說(shuō)显沈，首先對(duì)賦值软瞎。按照子式中包含的還是，或者不包含拉讯，我們將整個(gè)合取范式分成三部分A,B,C涤浇。當(dāng)給賦值為0的時(shí)候，表達(dá)式剩下A'和C魔慷；給賦值為1的時(shí)候只锭，表達(dá)式剩下B'和C。其中A'的子式長(zhǎng)度指數(shù)和為. B'為.因此院尔，表達(dá)式1的指數(shù)和為蜻展；表達(dá)式2的指數(shù)和為。將兩個(gè)式子相加邀摆，得到

image.png

兩個(gè)數(shù)相加小于2纵顾，其中必有一個(gè)數(shù)小于1。我們只要選擇那個(gè)小于1的取值就行栋盹。

案例3 Long Path in Graph

在給定的無(wú)向圖中找到最長(zhǎng)路徑是一個(gè)NP-hard問(wèn)題施逾。因?yàn)樵跓o(wú)向圖中找到一個(gè)Hamiton回路就已經(jīng)是一個(gè)NP-complete問(wèn)題。我們把要求降低一些例获，在hamiton圖中找到一個(gè)長(zhǎng)度的路徑汉额。下面我們證明，將有一個(gè)關(guān)于n的多項(xiàng)式時(shí)間的算法能夠解決這個(gè)問(wèn)題榨汤。不過(guò)蠕搜，我們稍微修改一下問(wèn)題：給定圖一種涂色coloring。如果給定路徑中每個(gè)點(diǎn)的顏色都不相同件余，我們就說(shuō)這是一條彩虹路徑讥脐。問(wèn)題轉(zhuǎn)變?yōu)椋航o定一個(gè)染色圖遭居，找到最長(zhǎng)的彩虹路徑。

首先旬渠，我們給出一個(gè)算法俱萍，它能夠在多項(xiàng)式時(shí)間內(nèi)解決上述問(wèn)題，用到的思想是動(dòng)態(tài)規(guī)劃告丢。定義:

需要注意的是枪蘑，是一個(gè)集合的集合。其中的元素是集合岖免，是以結(jié)尾長(zhǎng)度為i的彩虹路徑的點(diǎn)的顏色集合岳颇。我們希望從中推出。思路也很清楚颅湘，我們找到的鄰域點(diǎn)集话侧。對(duì)于， 考察中每一個(gè)元素闯参，也即顏色序列瞻鹏，如果序列中不含有，那么我們可以將和color of v同時(shí)加入鹿寨。以此類推新博。

算法如下：

對(duì)于給定的長(zhǎng)度，最內(nèi)層循環(huán)最大值是.外層兩個(gè)循環(huán)的值為脚草，是圖G的邊的個(gè)數(shù)赫悄。得到復(fù)雜度是,當(dāng)我們有的時(shí)候，復(fù)雜度顯然是關(guān)于n的多項(xiàng)式馏慨。（此處有疑問(wèn)）

接下來(lái)回到原來(lái)的問(wèn)題：給定無(wú)向圖埂淮，如何找到長(zhǎng)度為的路徑。首先写隶，我們分情況討論：如果不存在同诫，那么顯然找不到。如果存在樟澜，那么我們可以隨機(jī)給圖上色，然后用上述算法進(jìn)行求解叮盘。如果找到秩贰，則問(wèn)題解決；如果沒(méi)有找到柔吼，并不代表不存在毒费，有可能只是這個(gè)涂色方案不合適。我們固定一條路徑P愈魏，有如下的遞推關(guān)系: