動態規劃與數學方程法解決樓層扔雞蛋問題

1.問題描述

兩個軟硬程度一樣的雞蛋,它們有可能都在一樓就摔碎,也可能從一百層樓摔下來沒事。有座100層的建築,用這兩個雞蛋確定哪一層是雞蛋可以安全落下的最高位置,可以摔碎兩個雞蛋,求給出一個最佳策略,測出雞蛋恰好不會碎的樓層,最佳策略滿足的條件就是在最壞情況下所扔的次數比其它任意策略的最壞情況下所扔的次數要少。並求最佳策略在最壞情況下所仍的次數。

2.問題剖析

使用一個雞蛋我們別無選擇,只有一種方案就是從一樓逐層網上試探,最壞情況下需要100次試探。但是現在使用兩個雞蛋去試探安全樓層,有很多種試探方法,比如折半試探,在大樓高度一半處的樓層50層扔第一個雞蛋,碎了只能乖乖的用另一個雞蛋從一樓逐層往上試,不碎的話就從51~100層的中間層75層扔第一個雞蛋,依次類推。這種方案如果第一次在第50層樓雞蛋碎了,第49層是安全層的話,最壞情況下需要扔50次。那麼多的測試方案,我們需要找出一個最佳的測試方案,最佳體現在在最壞的情況下扔雞蛋的次數相比其它任意策略的最壞情況下所扔的次數要少。

什麼叫最壞情況,因為我們並不知道雞蛋會在哪一個樓層首碎,所以對於任意一個測試方案都會有一個最壞的情況,最壞的情況就是試探次數最多的情況。

求解這個問題有兩種辦法,一種是數學方程法,一種是動態規劃法。按照程式設計師的思路,遇到最優問題的時候,往往可以先嚐試一下動態規劃的方法。其次,在眾多的問題當中,有不少可以直接歸結為數學方程式,如果我們能夠寫出數學方程式,那麼,答案將是更加的簡潔、美妙。下面一一講解。

3.數學方程法

假設最壞情況下最少嘗試次數為x,那麼,第一個雞蛋必須要從第x層扔下,因為如果碎了,前面還有x – 1層樓需要逐層嘗試,如果沒碎,後面還有x-1次機會。

如果沒碎,第一個雞蛋第二次就必須從x (x – 1)層進行嘗試,為什麼是加上x – 1,因為現在只剩下x-1次機會了,類比第一次扔雞蛋,有多少次機會,就必須從第多少層開始仍。當此時,如果第一個雞蛋碎了,第二個雞蛋還需要從x 1 到 x (x – 1) – 1層進行逐層嘗試,有x – 2次。如果還沒碎,那第一個雞蛋,第三次從 x (x – 1) (x – 2)層嘗試。碎或者沒碎,都有x – 3次嘗試機會,依次類推。那麼x次的最少嘗試,可以確定的最高的樓層是多少呢? x (x – 1) (x – 2) … 1 = x(x 1) / 2 那反過來問,當最高樓層是100層,最少需要多少次呢?x(x 1)/2 >= 100, 得到x>=14,最少要嘗試14次。

最佳的試探方案:
這個嘗試的過程就是最佳的試探方案。具體地說,100層的樓,第一次從14層開始扔。碎了好說,從第1層開始試。不碎的話還有13次機會,再從14 13=27層開始扔,以此類推。

4.動態規劃法

使用動態規劃的方法求解,首要的我們要找到構成這個最優問題的最優子問題。

為什麼可以用動態規劃來求解這個問題呢?仔細一想,尋找100層,因為可以從1~100層之間的任意一層開始開始仍雞蛋,假設f[n]表示從n層樓找到仍雞蛋不碎安全位置的最少判斷次數。假設第一個雞蛋第一次從第i層扔下,那麼有兩種情況:
情況一:碎了,就剩一個雞蛋,為確定下面樓層中的安全位置,必須從第一層逐層試探,還需要i-1次;
情況二:沒碎,上面還有n-i層,剩下兩個雞蛋,還需要f[n-i]次。這個就是子問題了,因為實體n層樓的上n-i層需要的最少判斷次數和實體n-i層樓需要的最少判斷次數其實是一樣的。有了子問題,我們就應該要想到動態規劃。

因此,最壞情況下還需要判斷max(i-1,f[n-i])次。那麼對於每一個i從1到n層,嘗試次數最少的,就是f[n]的值。

狀態轉移方程:f[n] = min{ 1 max(i-1,f[n-i]) | i=1..n } 
初始狀態: f[0]=0(或f[1]=1)

有了初始狀態,再根據狀態轉移方程遞推到最終狀態,最終狀態就是問題的最優解。

最佳試探方案:
得到f[n]後,也就是最壞情況下最少試探次數,有了這個,就可以根據上面數學方程法中提到的試探方案得出最佳試探方案了。一旦確定了最壞情況下最少試探次數,最佳試探方案是唯一確定的,對於兩個雞蛋來說。

問題推廣:
現在推廣成n層樓,m個雞蛋。兩個雞蛋可以使用數學方程法的來解決,但是對於多個雞蛋,數學方程法就無能為力了。

還是動態規劃。假設f[n,m]表示n層樓、m個雞蛋時找到摔雞蛋不碎的最少判斷次數。則一個雞蛋從第i層扔下,如果碎了,還剩m-1個雞蛋,為確定下面樓層中的安全位置,還需要f[i-1,m-1]次(子問題);不碎的話,上面還有n-i層,還需要f[n-i,m]次(子問題,實際上n層樓的上n-i層需要的最少判斷次數和一個高度為n-i層樓需要的最少判斷次數其實是一樣的)。

狀態轉移方程:f[n,m]=min{ 1 max(f[i-1,m-1],f[n-i,m]) | i=1..n } 
初始狀態:f[i,0]=0,f[i,1]=i,i屬於[1,n]

問題解的矩陣如下:
這裡寫圖片描述

根據狀態轉移方程,逐步求出最終解f[n,m]。

具體實現:

/*********************************
@pram:high:樓層高度;eggNum:雞蛋的數量;
@ret:最少次數
@ps:min和max為C  標準函式模板,申明在<algorithm>
*********************************/
int  eggThrowCnt(int high,int eggNum){
int dp[32][1024]={0};
for(int i=1;i<=high;i  )
dp[1][i]=i;
for(int i=1;i<=eggNum;i  )
dp[i][1]=1,dp[i][0]=0;
for(int i=2;i<=eggNum;i  ){
for(int j=2;j<=high;j  ){
//從k=1層開始仍,找到k=1到j層取最小值
int k=1;                    
int minimal=1 max(dp[i-1][k-1],dp[i][j-k] 1);   
for(;k<=j;  k){
minimal=min(minimal,1 max(dp[i-1][k-1],dp[i][j-k]));
}
dp[i][j]=minimal; 
}
}
return dp[eggNum][high];
}

測試輸出:

cout<<eggThrowCnt(39,3);    //輸出6
cout<<eggThrowCnt(39,2);    //輸出9
cout<<eggThrowCnt(36,2);    //輸出8
cout<<eggThrowCnt(100,2);   //輸出14
cout<<eggThrowCnt(200,2);   //輸出20

多個雞蛋(>2)的最佳試探方案:
兩個雞蛋我們通過數學推理能夠得出最佳的試探方案。在多個雞蛋的情況下,已經求出了最少試探次數的前提下,如何找到最佳的試探方案呢?

本人在網上查了很多資料,目前還是沒有找到答案,也不知道這種情況下最佳試探方案是否唯一,請知道的網友留言告知,萬分感謝。


參考文獻

[1]樓層扔雞蛋問題
[2]谷歌面試題——動態規劃(扔雞蛋)