概述
隨機(jī)算法是當(dāng)前工業(yè)界和學(xué)術(shù)界都比較熱的一個(gè)話題吆豹，從機(jī)器學(xué)習(xí)显歧、數(shù)據(jù)挖掘到現(xiàn)在熱得發(fā)燙的深度學(xué)習(xí)蒙挑，無一沒有隨機(jī)算法的影子。隨機(jī)算法起源于人類天性：賭博肾扰，最初用來解決一些不確定問題畴嘶，現(xiàn)在已逐漸發(fā)展為一門獨(dú)立的學(xué)科，深入到工程領(lǐng)域各學(xué)科集晚。本文以一個(gè)簡(jiǎn)單的例子對(duì)基本的隨機(jī)算法作簡(jiǎn)單介紹，深入了解請(qǐng)研讀隨機(jī)算法
尋寶問題
尋寶問題描述如下：
假設(shè)有10個(gè)山頭区匣，其中3個(gè)山頭里面分別有價(jià)值10個(gè)金幣寶藏偷拔，每個(gè)山頭都有1個(gè)精靈守護(hù)蒋院，要進(jìn)山尋寶，必須給精靈3個(gè)金幣莲绰，當(dāng)在一個(gè)山頭找到寶藏后欺旧，精靈不允許繼續(xù)再尋寶，哪個(gè)山頭有寶藏未知蛤签，是否應(yīng)該尋寶辞友，采用何種策略尋寶？
因?yàn)槊總€(gè)山里面是否有寶藏是未知的震肮，不妨對(duì)這10個(gè)山里面是否有寶藏進(jìn)行編號(hào)称龙，設(shè)為{0, 0, 0, 1, 0, 0, 1, 0, 0, 1}，其中的0表示沒有寶藏戳晌，1表示有寶藏鲫尊。
因?yàn)閷毑匚粗凑帐裁礃拥捻樞蛟L問山頭也是未知的沦偎。在這種情況下疫向，有兩種方案：
- 情況1: 給山頭排個(gè)序，然后依次訪問豪嚎；
- 情況2: 隨機(jī)訪問搔驼；
對(duì)于情況1，假設(shè)排序?yàn)閜=<0, 0, 0, 1, 0, 0, 1, 0, 0, 1>侈询，則挖到寶藏會(huì)虧本2個(gè)金幣舌涨。也就是說，一旦確定了訪問山頭的次序妄荔，并且這個(gè)次序是一個(gè)虧本的次序泼菌，則必然虧本。
對(duì)于情況2啦租，隨機(jī)訪問有是什么樣子呢哗伯？在這里不作具體的數(shù)學(xué)分析（分析也比較簡(jiǎn)單，利用離散均勻分布篷角，計(jì)算期望）焊刹。隨機(jī)訪問一般有兩種算法，一種是lasvegas算法恳蹲，一種是monter carlo算法虐块，隨機(jī)算法的本質(zhì)是算法的某一步驟中引入隨機(jī)函數(shù)確定的某個(gè)值，從而導(dǎo)致不同相同的輸入可能得到不同的結(jié)果嘉蕾。
lasvegas算法針對(duì)尋寶問題的代碼為：
func LasVegas(input []int, key int) int {
retCount := 0
r := rand.New(rand.NewSource(time.Now().UnixNano()))
idxs := make([]int, 0)
for i, _ := range input {
idxs = append(idxs, i)
}
for count := 0; count < len(input); count++ {
// 從未選擇的山頭中選擇一個(gè)
i := r.Intn(len(idxs))
retCount++
if input[idxs[i]] == key {
fmt.Println("===========")
return 10 - 3*retCount
}
idxs = lefts(idxs, idxs[i])
}
return 0 - 3*retCount
}
分析上面的代碼贺奠，lasvegas算法的本質(zhì)是只要存在解（在本例的尋寶中），會(huì)一直嘗試错忱，直到得到正確解儡率。也就是：只要存在解挂据，lasvegas算法最終一定會(huì)得到解。
如果尋寶問題中儿普，山頭數(shù)量足夠多崎逃，而寶藏山頭特別少，則按照lasvegas算法可能會(huì)虧損特別嚴(yán)重眉孩，得不償失个绍，因此，monter carlo算法對(duì)嘗試的次數(shù)作了限制浪汪，這本質(zhì)上就是一種嘗試-止損原則巴柿，即先確定一個(gè)止損位，按照在止損范圍內(nèi)嘗試獲利吟宦。其代碼為：
func MC(input []int, upperTryNum int, key int) int {
retCount := 0
r := rand.New(rand.NewSource(time.Now().UnixNano()))
idxs := make([]int, 0)
for i, _ := range input {
idxs = append(idxs, i)
}
for count := 0; count < len(input); count++ {
if retCount <= upperTryNum {
retCount++
i := r.Intn(len(idxs))
if input[i] == key {
return 10 - 3*retCount
}
idxs = lefts(idxs, idxs[i])
}
}
return 0 - upperTryNum
}
其中的upperTryNum就是嘗試的次數(shù)篮洁。
通常情況下，Monte Carlo不一定會(huì)得到解殃姓，但是其損失是可以預(yù)見袁波。針對(duì)尋寶這個(gè)例子，在本人機(jī)器上分別運(yùn)行10次蜗侈，其獲益金幣數(shù)結(jié)果為（每次運(yùn)行結(jié)果都不同）：
lvs（lasvegas）: [4 1 -2 4 -8 7 7 7 4 1] , mcs（monter carlo）: [4 7 7 7 7 7 7 1 7 7]
大家可以在自己的機(jī)器上觀測(cè)運(yùn)行結(jié)果（ https://github.com/bjutJohnson/Algorithms/tree/master/src/probabilistic ） 篷牌，可以把嘗試次數(shù)設(shè)置得更多一些，然后結(jié)合數(shù)學(xué)期望進(jìn)行分析踏幻。
小結(jié)
隨機(jī)算法雖然起源于不確定性問題枷颊，但是對(duì)于規(guī)模龐大的確定性問題如圍棋、解密度空間稀疏等该面，都有與之相應(yīng)的解決方案夭苗，特別是求解次優(yōu)解的情況。
