說(shuō)透游戲中常用的兩種隨機(jī)算法

沒(méi)事兒的時(shí)候我喜歡玩玩那些經(jīng)典的 2D 網(wǎng)頁(yè)小游戲，我發(fā)現(xiàn)很多游戲都要涉及地圖的隨機(jī)生成，比如掃雷游戲中地雷的位置應(yīng)該是隨機(jī)分布的：

再比如經(jīng)典炸彈人游戲，障礙物的位置也是有一定隨機(jī)性的：

這些 2D 游戲相較現(xiàn)在的大型 3D 游戲雖然看起來(lái)有些簡(jiǎn)陋，但依然用到很多有趣算法技巧，本文就來(lái)深入研究一下地圖的隨機(jī)生成算法。

2D 游戲的地圖肯定可以抽象成一個(gè)二維矩陣，就拿掃雷舉例吧，我們可以用下面這個(gè)類表示掃雷的棋盤：

classGame{
intm,n;
//大小為m*n的二維棋盤
//值為true的地方代表有雷，false代表沒(méi)有雷
boolean[][]board;
}

如果你想在棋盤中隨機(jī)生成k個(gè)地雷，也就是說(shuō)你需要在board中生成k個(gè)不同的(x, y)坐標(biāo)，且這里面x, y都是隨機(jī)生成的。

對(duì)于這個(gè)需求，首先一個(gè)優(yōu)化就是對(duì)二維矩陣進(jìn)行「降維打擊」，把二維數(shù)組轉(zhuǎn)化成一維數(shù)組：

classGame{
intm,n;
//長(zhǎng)度為m*n的一維棋盤
//值為true的地方代表有雷，false代表沒(méi)有雷
boolean[]board;

//將二維數(shù)組中的坐標(biāo)(x,y)轉(zhuǎn)化為一維數(shù)組中的索引
intencode(intx,inty){
returnx*n+y;
}

//將一維數(shù)組中的索引轉(zhuǎn)化為二維數(shù)組中的坐標(biāo)(x,y)
int[]decode(intindex){
returnnewint[]{index/n,index%n};
}
}

這樣，我們只要在[0, m * n)中選取一個(gè)隨機(jī)數(shù)，就相當(dāng)于在二維數(shù)組中隨機(jī)選取了一個(gè)元素。

但問(wèn)題是，我們現(xiàn)在需要隨機(jī)選出k個(gè)不同的位置放地雷。你可能說(shuō)，那在[0, m * n)中選出來(lái)k個(gè)隨機(jī)數(shù)不就行了？

是的，但實(shí)際操作起來(lái)有些麻煩，因?yàn)槟愫茈y保證隨機(jī)數(shù)不重復(fù)。如果出現(xiàn)重復(fù)的隨機(jī)數(shù)，你就得再隨機(jī)選一次，直到找到k個(gè)不同的隨機(jī)數(shù)。

如果k比較小m * n比較大，那出現(xiàn)重復(fù)隨機(jī)數(shù)的概率還比較低，但如果k和m * n的大小接近，那么出現(xiàn)重復(fù)隨機(jī)數(shù)的概率非常高，算法的效率就會(huì)大幅下降。

那么，我們有沒(méi)有更好的辦法能夠在線性的時(shí)間復(fù)雜度解決這個(gè)問(wèn)題？其實(shí)是有的，而且有很多種解決方案。

洗牌算法

第一個(gè)解決方案，我們可以換個(gè)思路，避開(kāi)「在數(shù)組中隨機(jī)選擇k個(gè)元素」這個(gè)問(wèn)題，把問(wèn)題轉(zhuǎn)化成「如何隨機(jī)打亂一個(gè)數(shù)組」。

現(xiàn)在想隨機(jī)初始化k顆地雷的位置，你可以先把這k顆地雷放在board開(kāi)頭，然后把board數(shù)組隨機(jī)打亂，這樣地雷不就隨機(jī)分布到board數(shù)組的各個(gè)地方了嗎？

洗牌算法，或者叫隨機(jī)亂置算法就是專門解決這個(gè)問(wèn)題的，我們可以看下力扣第 384 題「打亂數(shù)組」：

這個(gè)shuffle函數(shù)是算法的關(guān)鍵，直接看解法代碼吧：

classSolution{
privateint[]nums;
privateRandomrand=newRandom();

publicSolution(int[]nums){
this.nums=nums;
}

publicint[]reset(){
returnnums;
}

//洗牌算法
publicint[]shuffle(){
intn=nums.length;
int[]copy=Arrays.copyOf(nums,n);
for(inti=0;i//生成一個(gè)[i,n-1]區(qū)間內(nèi)的隨機(jī)數(shù)
intr=i+rand.nextInt(n-i);
//交換nums[i]和nums[r]
swap(copy,i,r);
}
returncopy;
}

privatevoidswap(int[]nums,inti,intj){
inttemp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
}

洗牌算法的時(shí)間復(fù)雜度是 O(N)，而且邏輯很簡(jiǎn)單，關(guān)鍵在于讓你證明為什么這樣做是正確的。排序算法的結(jié)果是唯一可以很容易檢驗(yàn)的，但隨機(jī)亂置算法不一樣，亂可以有很多種，你怎么能證明你的算法是「真的亂」呢？

分析洗牌算法正確性的準(zhǔn)則：產(chǎn)生的結(jié)果必須有n!種可能。這個(gè)很好解釋，因?yàn)橐粋€(gè)長(zhǎng)度為n的數(shù)組的全排列就有n!種，也就是說(shuō)打亂結(jié)果總共有n!種。算法必須能夠反映這個(gè)事實(shí)，才是正確的。

有了這個(gè)原則再看代碼應(yīng)該就容易理解了：

對(duì)于nums[0]，我們把它隨機(jī)換到了索引[0, n)上，共有n種可能性；

對(duì)于nums[1]，我們把它隨機(jī)換到了索引[1, n)上，共有n - 1種可能性；

對(duì)于nums[2]，我們把它隨機(jī)換到了索引[2, n)上，共有n - 2種可能性；

以此類推，該算法可以生成n!種可能的結(jié)果，所以這個(gè)算法是正確的，能夠保證隨機(jī)性。

水塘抽樣算法

學(xué)會(huì)了洗牌算法，掃雷游戲的地雷隨機(jī)初始化問(wèn)題就解決了。不過(guò)別忘了，洗牌算法只是一個(gè)取巧方案，我們還是得面對(duì)「在若干元素中隨機(jī)選擇k個(gè)元素」這個(gè)終極問(wèn)題。

要知道洗牌算法能夠生效的前提是你使用數(shù)組這種數(shù)據(jù)結(jié)構(gòu)，如果讓你在一條鏈表中隨機(jī)選擇k個(gè)元素，肯定不能再用洗牌算法來(lái)蒙混過(guò)關(guān)了。

再比如，假設(shè)我們的掃雷游戲中棋盤的長(zhǎng)和寬非常大，已經(jīng)不能在內(nèi)存中裝下一個(gè)大小為m * n的board數(shù)組了，我們只能維護(hù)一個(gè)大小為k的數(shù)組記錄地雷的位置：

classGame{
//棋盤的行數(shù)和列數(shù)（非常大）
intm,n;
//長(zhǎng)度為k的數(shù)組，記錄k個(gè)地雷的一維索引
int[]mines;

//將二維數(shù)組中的坐標(biāo)(x,y)轉(zhuǎn)化為一維數(shù)組中的索引
intencode(intx,inty){
returnx*n+y;
}

//將一維數(shù)組中的索引轉(zhuǎn)化為二維數(shù)組中的坐標(biāo)(x,y)
int[]decode(intindex){
returnnewint[]{index/n,index%n};
}
}

這樣的話，我們必須想辦法在[0, m*n)中隨機(jī)選取k個(gè)不同的數(shù)字了。

這就是常見(jiàn)的隨機(jī)抽樣場(chǎng)景，常用的解法是水塘抽樣算法（Reservoir Sampling）。水塘抽樣算法是一種隨機(jī)概率算法，會(huì)者不難，難者不會(huì)。

我第一次見(jiàn)到這個(gè)算法問(wèn)題是谷歌的一道算法題：給你一個(gè)未知長(zhǎng)度的單鏈表，請(qǐng)你設(shè)計(jì)一個(gè)算法，只能遍歷一次，隨機(jī)地返回鏈表中的一個(gè)節(jié)點(diǎn)。

這里說(shuō)的隨機(jī)是均勻隨機(jī)（uniform random），也就是說(shuō)，如果有n個(gè)元素，每個(gè)元素被選中的概率都是1/n，不可以有統(tǒng)計(jì)意義上的偏差。

一般的想法就是，我先遍歷一遍鏈表，得到鏈表的總長(zhǎng)度n，再生成一個(gè)[0,n-1)之間的隨機(jī)數(shù)為索引，然后找到索引對(duì)應(yīng)的節(jié)點(diǎn)。但這不符合只能遍歷一次鏈表的要求。

這個(gè)問(wèn)題的難點(diǎn)在于隨機(jī)選擇是「動(dòng)態(tài)」的，比如說(shuō)你現(xiàn)在你已經(jīng)遍歷了 5 個(gè)元素，你已經(jīng)隨機(jī)選取了其中的某個(gè)元素a作為結(jié)果，但是現(xiàn)在再給你一個(gè)新元素b，你應(yīng)該留著a還是將b作為結(jié)果呢？以什么邏輯做出的選擇，才能保證你的選擇方法在概率上是公平的呢？

先說(shuō)結(jié)論，當(dāng)你遇到第i個(gè)元素時(shí)，應(yīng)該有1/i的概率選擇該元素，1 - 1/i的概率保持原有的選擇。看代碼容易理解這個(gè)思路：

/*返回鏈表中一個(gè)隨機(jī)節(jié)點(diǎn)的值*/
intgetRandom(ListNodehead){
Randomr=newRandom();
inti=0,res=0;
ListNodep=head;
//while循環(huán)遍歷鏈表
while(p!=null){
i++;
//生成一個(gè)[0,i)之間的整數(shù)
//這個(gè)整數(shù)等于0的概率就是1/i
if(0==r.nextInt(i)){
res=p.val;
}
p=p.next;
}
returnres;
}

對(duì)于概率算法，代碼往往都是很淺顯的，但是這種問(wèn)題的關(guān)鍵在于證明，你的算法為什么是對(duì)的？為什么每次以1/i的概率更新結(jié)果就可以保證結(jié)果是平均隨機(jī)的？

我們來(lái)證明一下，假設(shè)總共有n個(gè)元素，我們要的隨機(jī)性無(wú)非就是每個(gè)元素被選擇的概率都是1/n對(duì)吧，那么對(duì)于第i個(gè)元素，它被選擇的概率就是：

第i個(gè)元素被選擇的概率是1/i，在第i+1次不被替換的概率是1 - 1/(i+1)，在第i+2次不被替換的概率是1 - 1/(i+2)，以此類推，相乘的結(jié)果是第i個(gè)元素最終被選中的概率，也就是1/n。因此，該算法的邏輯是正確的。

同理，如果要在單鏈表中隨機(jī)選擇k個(gè)數(shù)，只要在第i個(gè)元素處以k/i的概率選擇該元素，以1 - k/i的概率保持原有選擇即可。代碼如下：

/*返回鏈表中k個(gè)隨機(jī)節(jié)點(diǎn)的值*/
int[]getRandom(ListNodehead,intk){
Randomr=newRandom();
int[]res=newint[k];
ListNodep=head;

//前k個(gè)元素先默認(rèn)選上
for(inti=0;inull;i++){
res[i]=p.val;
p=p.next;
}

inti=k;
//while循環(huán)遍歷鏈表
while(p!=null){
i++;
//生成一個(gè)[0,i)之間的整數(shù)
intj=r.nextInt(i);
//這個(gè)整數(shù)小于k的概率就是k/i
if(jreturnres;
}

對(duì)于數(shù)學(xué)證明，和上面區(qū)別不大：

雖然每次更新選擇的概率增大了k倍，但是選到具體第i個(gè)元素的概率還是要乘1/k，也就回到了上一個(gè)推導(dǎo)。

類似的，回到掃雷游戲的隨機(jī)初始化問(wèn)題，我們可以寫一個(gè)這樣的sample抽樣函數(shù)：

//在區(qū)間[lo,hi)中隨機(jī)抽取k個(gè)數(shù)字
int[]sample(intlo,inthi,intk){
Randomr=newRandom();
int[]res=newint[k];

//前k個(gè)元素先默認(rèn)選上
for(inti=0;iinti=k;
//while循環(huán)遍歷數(shù)字區(qū)間
while(i//生成一個(gè)[0,i)之間的整數(shù)
intj=r.nextInt(i);
//這個(gè)整數(shù)小于k的概率就是k/i
if(j1;
}
}
returnres;
}

這個(gè)函數(shù)能夠在一定的區(qū)間內(nèi)隨機(jī)選擇k個(gè)數(shù)字，確保抽樣結(jié)果是均勻隨機(jī)的且只需要 O(N) 的時(shí)間復(fù)雜度。

蒙特卡洛驗(yàn)證法

上面講到的洗牌算法和水塘抽樣算法都屬于隨機(jī)概率算法，雖然從數(shù)學(xué)上推導(dǎo)上可以證明算法的思路是正確的，但如果你筆誤寫出 bug，就會(huì)導(dǎo)致概率上的不均等。更神奇的是，力扣的判題機(jī)制能夠檢測(cè)出這種概率錯(cuò)誤。

那么最后我就來(lái)介紹一種方法檢測(cè)隨機(jī)算法的正確性：蒙特卡洛方法。我猜測(cè)力扣的判題系統(tǒng)也是利用這個(gè)方法來(lái)判斷隨機(jī)算法的正確性的。

記得高中有道數(shù)學(xué)題：往一個(gè)正方形里面隨機(jī)打點(diǎn)，這個(gè)正方形里緊貼著一個(gè)圓，告訴你打點(diǎn)的總數(shù)和落在圓里的點(diǎn)的數(shù)量，讓你計(jì)算圓周率。

這其實(shí)就是利用了蒙特卡羅方法：當(dāng)打的點(diǎn)足夠多的時(shí)候，點(diǎn)的數(shù)量就可以近似代表圖形的面積。結(jié)合面積公式，可以很容易通過(guò)正方形和圓中點(diǎn)的數(shù)量比值推出圓周率的。

當(dāng)然，打的點(diǎn)越多，算出的圓周率越準(zhǔn)確，充分體現(xiàn)了大力出奇跡的道理。

比如，我們可以這樣檢驗(yàn)水塘抽樣算法sample函數(shù)的正確性：

publicstaticvoidmain(String[]args){
//在[12,22)中隨機(jī)選3個(gè)數(shù)
intlo=12,hi=22,k=3;
//記錄每個(gè)元素被選中的次數(shù)
int[]count=newint[hi-lo];
//重復(fù)10萬(wàn)次
intN=1000000;
for(inti=0;iint[]res=sample(lo,hi,k);
for(intelem:res){
//對(duì)隨機(jī)選取的元素進(jìn)行記錄
count[elem-lo]++;
}
}
System.out.println(Arrays.toString(count));
}

這段代碼的輸出如下：

[300821,299598,299792,299198,299510,300789,300022,300326,299362,300582]

當(dāng)然你可以做更細(xì)致的檢查，不過(guò)粗略看看，各個(gè)元素被選中的次數(shù)大致是相同的，這個(gè)算法實(shí)現(xiàn)的應(yīng)該沒(méi)啥問(wèn)題。

對(duì)于洗牌算法中的shuffle函數(shù)也可以采取類似的驗(yàn)證方法，我們可以跟蹤某一個(gè)元素x被打亂后的索引位置，如果x落在各個(gè)索引的次數(shù)基本相同，則說(shuō)明算法正確，你可以自己嘗試實(shí)現(xiàn)，我就不貼代碼驗(yàn)證了。

拓展延伸

到這里，常見(jiàn)的隨機(jī)算法就講完了，簡(jiǎn)單總結(jié)下吧。

洗牌算法主要用于打亂數(shù)組，比如我們?cè)?/span>快速排序詳解及運(yùn)用中就用到了洗牌算法保證快速排序的效率。

水塘抽樣算法的運(yùn)用更加廣泛，可以在序列中隨機(jī)選擇若干元素，且能保證每個(gè)元素被選中的概率均等。

對(duì)于這些隨機(jī)概率算法，我們可以用蒙特卡洛方法檢驗(yàn)其正確性。

最后留幾個(gè)拓展題目：

1、本文開(kāi)頭講到了將二維數(shù)組坐標(biāo)(x, y)轉(zhuǎn)化成一維數(shù)組索引的技巧，那么你是否有辦法把三維坐標(biāo)(x, y, z)轉(zhuǎn)化成一維數(shù)組的索引呢？

2、如何對(duì)帶有權(quán)重的樣本進(jìn)行加權(quán)隨機(jī)抽?。勘热缃o你一個(gè)數(shù)組w，每個(gè)元素w[i]代表權(quán)重，請(qǐng)你寫一個(gè)算法，按照權(quán)重隨機(jī)抽取索引。比如w = [1,99]，算法抽到索引 0 的概率是 1%，抽到索引 1 的概率是 99%，答案見(jiàn)我的這篇文章。

3、實(shí)現(xiàn)一個(gè)生成器類，構(gòu)造函數(shù)傳入一個(gè)很長(zhǎng)的數(shù)組，請(qǐng)你實(shí)現(xiàn)randomGet方法，每次調(diào)用隨機(jī)返回?cái)?shù)組中的一個(gè)元素，多次調(diào)用不能重復(fù)返回相同索引的元素。要求不能對(duì)該數(shù)組進(jìn)行任何形式的修改，且操作的時(shí)間復(fù)雜度是 O(1)，答案見(jiàn)我的這篇文章