http://xiaochonganty.blog.163.com/blog/static/485279320071017112652753/

今天看到一篇信息論的課件，里面講到用信息論中熵的概念解決稱球問題，正好前段時間范博提到過那個問題，決定研究研究上升到理論高度，哈哈。
??? 又搜了些資料，先說結論吧。分兩種情況，一種是知道特殊的球是比其他球輕還是重，這時稱K是最多能找出3^k個球中不同的那個，換句話說要找出k個球中不同的那個需要(log n)/(log 3)也就是以3為底求對數；

另外就是不知道特殊的球是清還是重，這時稱K是最多能找出（3^k-1）/2個球中不同的那個。比如稱3次知道輕重可以從3^3=27個球中找出不同的球出來，如果不知道輕重就只能從（3^3-1)/2=13個球中找出不同的球出來。

http://www.mwjx.com/bbs/html/4000/2202.html

http://www.infzm.com/content/79852

12個小球，其中有一個是壞球。有一架天平。需要你用最少的稱次數來確定哪個小球是壞的并且它到底是輕還是重。

這個問題是一道流傳已久的智力題。網絡上也有很多講解，還有泛化到N個球的情況下的嚴格證明。也有零星的一些地方提到從信息論的角度來看待最優解法。本來我一直認為這道題目除了試錯之外沒有其它高妙的思路了，只能一個個方法試，并盡量從結果中尋找信息，然后看看哪種方案最少。

然而，實際上它的確有其它的思路，一個更本質的思路，而且根本用不著信息論這么拗口的知識。

我們先回顧一下猜數字游戲。為了保證任何情況下以最少次數猜中，我們的策略是每次都排除恰好一半的可能性。類比到稱球問題上：壞球可能是12個球中的任意一個，這就是12種可能性；而其中每種可能性下壞球可能輕也可能重。于是“壞球是哪個球，是輕是重”這個問題的答案就有12×2=24種可能性?，F在我們用天平來稱球，就等同于對這24種可能性發問，由于天平的輸出結果有三種“平衡、左傾、右傾”，這就相當于我們的問題有三個答案，即可以將所有的可能性切成三份，根據猜數字游戲的啟發，我們應當盡量讓這三個分支概率均等，即平均切分所有的可能性為三等份。如此一來的話一次稱量就可以將答案的可能性縮減為原來的1/3，三次就能縮減為1/27。而總共才有24種可能性，所以理論上是完全可以3次稱出來的。

如何稱的指導原則有了，構造一個稱的策略就不是什么太困難的事情了。首先不妨解釋一下為什么最直觀的稱法不是最優的——6、6稱：在6、6稱的時候，天平平衡的可能性是0。剛才說了，最優策略應該使得天平三種狀態的概率均等，這樣才能三等分答案的所有可能性。

為了更清楚的看待這個問題，我們不妨假設有6個球，來考慮一下3、3稱和2、2稱的區別：

在未稱之前，一共有12種可能性：1輕、1重、2輕、2重、…、6輕、6重?，F在將1、2、3號放在左邊，4、5、6放在右邊3、3稱了之后，不失一般性假設天平左傾，那么小球的可能性就變成了原來的一半（6種）：1重、2重、3重、4輕、5輕、6輕。即這種稱法能排除一半可能性。

現在再來看2、2稱法，即1、2放左邊，3、4放右邊，剩下的5、6不稱，放一邊。假設結果是天平平衡，那么可能性剩下——4種：5重、5輕、6重、6輕。假設天平左傾，可能性也剩下4種：1重、2重、3輕、4輕。右傾和左傾的情況類似?？傊?#xff0c;這種稱法，不管天平結果如何，情況都被我們縮小到了原來的三分之一！我們充分利用了“天平的結果狀態可能有三種”這個條件來三等分所有可能性，而不是二等分。

說到這里，剩下的事情就實在很簡單了：第二步稱法，只要記著這樣一個指導思想——你選擇的稱法必須使得當天平平衡的時候答案剩下的可能性和天平左傾（右傾）的時候答案剩下的可能性一樣多。實際上，這等同于你得選擇一種稱法，使得天平輸出三種結果的概率是均等的，因為天平輸出某個結果的概率就等同于所有支持這個結果（左傾、右傾、平衡）的答案可能性的和，并且答案的每個可能性都是等概率的。

MacKay在他的書《Information Theory: Inference and Learning Algorithms》里面4.1節專門講了這個稱球問題，還畫了一張不錯的圖，我就照抄了：

圖中“1+”是指“1號小球為重”這一可能性。一開始一共有24種可能性。4、4稱了之后不管哪種情況（分支），剩下來的可能性總是4種。這是一個完美的三分。然后對每個分支構造第二次稱法，這里你只要稍加演算就可以發現，分支1上的第二次稱法，即“1、2、6對3、4、5”這種稱法，天平輸出三種結果的可能性是均等的（嚴格來說是幾乎均等）。這就是為什么這個稱法能夠在最壞的情況下也能表現最好的原因，沒有哪個分支是它的弱點，它必然能將情況縮小到原來的1/3。

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的称球问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。