國家集訓(xùn)隊(duì)2003論文集 侯啟明

1、在信息學(xué)競賽中的簡單應(yīng)用,侯啟明,信 息 論,信息論簡介,信息論是關(guān)于信息的本質(zhì)和傳輸規(guī)律的科學(xué)的理論。通過它可以很方便地得到某些交互式問題的一個(gè)較好的步數(shù)下界(“信息論下界”),讓我們先來看一些信息論的基本理論,理論基礎(chǔ),定義：如果一個(gè)隨機(jī)變量x共有n種取值，概率分別為p0,p2,......,pn，則其熵為H(x)=f(p0,p2,......,pn)=-∑Cpilogpi 定理1：在得到關(guān)于隨機(jī)變量x的一個(gè)熵為h的信息后，

2、x的熵將會(huì)減少h。定理2：當(dāng)一個(gè)隨機(jī)變量的各種取值概率相等時(shí)，它的熵最大。,這些理論看上去和某些題目關(guān)系密切，不是嗎？ 那么，具體應(yīng)該如何運(yùn)用呢？讓我們來看一些例子：,我們宿舍二樓到三樓之間樓梯的窗戶外面是相鄰的一個(gè)平房的房頂。在那一帶棲息著三只渾身雪白，有著一只藍(lán)眼睛和一只綠眼睛的——,例1：驗(yàn)證一下定理1,貓！,A,B,C,例1：驗(yàn)證一下定理1,在天冷的時(shí)候，它們喜歡趴在樓內(nèi)的暖氣上。于是，每只貓就有了兩種狀態(tài)：在

3、屋內(nèi)和在屋外。因此，三只貓的狀態(tài)共有8種可能情況，假設(shè)它們是等概率的。 現(xiàn)在，我在一樓的小賣部。由于種種原因，我希望知道貓當(dāng)時(shí)的狀況，因此，我往上看了一眼，結(jié)果發(fā)現(xiàn)在這個(gè)位置只能知道屋內(nèi)貓的只數(shù)……,例1：驗(yàn)證一下定理1,問題1：把所有貓的情況作為一個(gè)隨機(jī)變量x，則當(dāng)我在小賣部的時(shí)候，x的熵是多少？,解答1：由于8種情況的概率相等，所以：H(x)=f(1/8,1/8,1/8,1/8,1/8,1/8,1/8,1/8)=log8,

4、問題2：我看一眼所得到的信息y的熵是多少？,解答2：由于貓的只數(shù)共有0,1,2,3四種情況，概率分別為(1/8,3/8,3/8,1/8)，所以：H(y)=f(1/8,3/8,3/8,1/8)=log8-6log3/8,例1：驗(yàn)證一下定理1,問題3：我看完之后，x的熵H'(x)是多少？,解答3：此時(shí)貓的只數(shù)為0,1,2,3的四種情況的概率依次是(1/8,3/8,3/8,1/8)，而每種情況的熵分別為(0,log3,log3,0)

5、，所以此時(shí)H'(x)的數(shù)學(xué)期望為：H'(x)=1/8*0+3/8*log3+3/8*log3+1/8*0=6log3/8,可以發(fā)現(xiàn)H(x)=H(y)+H'(x)。定理1得到了驗(yàn)證。,例2：Rods(IOI2002),一個(gè)Rod是一個(gè)由至少2個(gè)單位正方形連成的水平或豎直的長條。在一個(gè)N*N的方陣中，放了水平和豎直兩個(gè)Rod。如圖1，其中Rod用X表示。,圖1,例2：Rods(IOI2002),兩個(gè)Rod可能有公

6、共方格，比如在圖1中，方格（4，4）無法確定是僅屬于1個(gè)Rod還是同時(shí)屬于兩個(gè)Rod。因此，在這種情況下我們假定它同時(shí)屬于兩個(gè)Rod。這樣，圖中豎直Rod的上端點(diǎn)是（4，4）而不是（5，4）。,圖1,最初我們并不知道兩個(gè)Rod的位置，你的任務(wù)是編程序找出它們的位置。你只能通過庫函數(shù)rect(a,b,c,d)來定位兩個(gè)Rod。如果至少一個(gè)屬于某個(gè)Rod的方格落在矩形[a,b]x[c,d] (如圖1中陰影區(qū)域)內(nèi)的話，rect返回1，否則返

7、回0。,例2：Rods(IOI2002),圖1,對(duì)每個(gè)測試點(diǎn)，如果你的程序沒有正確確定兩個(gè)Rod的位置或調(diào)用rect超過400次，你將得到0分。否則，如果調(diào)用rect的次數(shù)至多為100，你將得到5分；在101到200間，你將得到3分；在201到400間，你將得到1分。,例2：Rods(IOI2002),圖1,比賽時(shí)我很快想到了一個(gè)最多調(diào)用rect函數(shù)6log2n+C（某個(gè)常數(shù)）次的方法，但是因?yàn)檫@個(gè)數(shù)差不多剛好達(dá)到100，所以我在這時(shí)就

8、開始試圖優(yōu)化上式中l(wèi)og2n的系數(shù)，結(jié)果徒勞無功，反而耽誤了時(shí)間。因此，看過答案以后，我試著從信息論的角度分析了一下這個(gè)問題：,例2：Rods(IOI2002),6log2n+C?,由于題目中沒有涉及到概率，因此假設(shè)所有情況都是等概率的。所以，設(shè)Rod的擺放方法為隨機(jī)變量x，x所有可能的取值數(shù)為f(n)，那么x的熵H(x)就等于log(f(n))。而由于庫函數(shù)只有兩種返回值，其熵最大為Hmax(y)=log2。因此，rect調(diào)用次數(shù)的信

9、息論下界就是L=H(x)/Hmax(y)=log(f(n))/log2=log2f(n),例2：Rods(IOI2002),在n*n的方陣中放1個(gè)Rod（無論橫豎）共有n*C(n+1,2)種方案，放兩個(gè)相交的Rod共有C2(n+2,3)種方案，所以： f(n)=(n2(n+1)/2)2-((n+2)(n+1)n/6)2 =(2n6+3n5-n4-3n3-n2)/9當(dāng)n充分大時(shí)：

10、 L=log(f(n))/log2>log2(2n6/9)≈6log2n-2.2,例2：Rods(IOI2002),下面討論f(n)的值：,由于各種原因，不一定總是使兩種返回值概率相等，所以最壞情況下的調(diào)用次數(shù)往往達(dá)不到信息論下界，兩者大約相差一個(gè)常數(shù)，因此，可以認(rèn)為6log2n+C是rect函數(shù)最大調(diào)用次數(shù)的下界。這樣，在得到一個(gè)這樣的算法之后，就沒有什么必要再去徒勞地優(yōu)化步數(shù)了。,例2：Rods(IOI2002),6

11、log2n+C!,例3：Coins(選手推薦題0024，推薦者饒向榮),有一堆n個(gè)硬幣，其中有n-1個(gè)好的，一個(gè)壞的。所有好的硬幣的質(zhì)量是相同的，但壞的硬幣的質(zhì)量卻不一樣，現(xiàn)在告訴你某一枚是好的，能否用一架天平在k次以內(nèi)稱出哪個(gè)是壞的硬幣。 輸入n和k，如果能在k此比較中找到n枚硬幣中的哪枚為壞的，就輸出'POSSIBLE'，否則輸出'IMPOSSIBLE'。,例3：Coins(選手推薦題

12、0024，推薦者饒向榮),兩年前我的一位遠(yuǎn)房親戚曾給我出過一個(gè)類似的題目（n=14，k=3），當(dāng)時(shí)我苦苦思索了一晚上，終于想出來一個(gè)可行解法。于是，那位親戚加大了數(shù)據(jù)規(guī)模(n=1101，k=7，IMPOSSIBLE)，我想了大概一周，覺得應(yīng)該無解，但苦于無法證明我的解法的最優(yōu)性，始終不能理直氣壯地回答"IMPOSSIBLE"。,例3：Coins(選手推薦題0024，推薦者饒向榮),后來她給了我一個(gè)"說明&q

13、uot;，但我始終覺得不太嚴(yán)密；拿來問我們班的IMO金牌，回答是"顯然"，我覺得也不嚴(yán)密:(。于是，這件事就成了我這兩年來的一個(gè)遺憾。,現(xiàn)在，有了信息論的武器，這個(gè)遺憾終于得到了解決!,初步分析,首先，對(duì)硬幣用1到n進(jìn)行編號(hào)，設(shè)壞硬幣的編號(hào)為x?？梢哉J(rèn)為x的所有取值情況概率相等：∴H(x)=logn?！哂锰炱椒Q一次的結(jié)果y只有3種可能情況（左邊較重，右邊較重，平衡）∴Hmax(y)=log3?！鄰膎個(gè)硬幣中通

14、過天平找出一個(gè)壞硬幣至少需要H(x)/Hmax(y)=log3n步,初步分析,下面通過構(gòu)造證明當(dāng)知道壞硬幣比好硬幣輕還是重的時(shí)候，這個(gè)下界是可以達(dá)到的： 每次把所有硬幣分成三等份，比較其中兩份，如果平衡，說明壞硬幣在第三份中，否則壞硬幣就在重的一份中，這樣每次比較得到三種結(jié)果的概率相等，H(y)≡Hmax(y)。所以此時(shí)，從n個(gè)硬幣中找出一個(gè)壞硬幣只需log3n步。,初步分析,雖然這樣，但是在原題的條件下，這個(gè)信息論下界

15、是達(dá)不到的，不過如果沒有這個(gè)結(jié)論，真正最優(yōu)的解法的最優(yōu)性就無從證明。得出這個(gè)結(jié)論后，后面的困難就迎刃而解了。,請看進(jìn)一步的分析：,進(jìn)一步的分析,通過轉(zhuǎn)化，發(fā)現(xiàn)只要計(jì)算出給出一枚好硬幣，k次比較最多在多少枚硬幣（不包括給出的好硬幣）中找出一枚壞硬幣，就可以解決原問題。 不過，轉(zhuǎn)化之后的問題仍然難以解決，一枚好硬幣實(shí)在太少，因此，不妨先將原問題“放大”一下，考慮一下有無窮枚好硬幣的情形。,進(jìn)一步的分析,設(shè)在有無窮枚好硬幣時(shí)，

16、k次比較最多從g(k)個(gè)硬幣中找出一個(gè)壞硬幣。當(dāng)k=1時(shí)，通過枚舉可以發(fā)現(xiàn)，g(1)=2。,信息論不行的時(shí)候，枚舉也是必要的。,當(dāng)k>1時(shí)：考慮第一次比較，設(shè)t為這次沒上天平的尚未確定好壞的硬幣的個(gè)數(shù)，下面分情況討論：,進(jìn)一步的分析,如果比較結(jié)果是“平衡”。 由于可以通過剩下的k-1次比較把壞硬幣從這t個(gè)硬幣中找出來，所以t<=g(k-1)。 如果比較結(jié)果不是“平衡”。 此時(shí)可以確定壞硬幣

17、在上了天平的g(k)-t個(gè)硬幣中，同樣，根據(jù)結(jié)論1，得到g(k)-t<=3k-1，故g(k)<=g(k-1)+3k-1:,進(jìn)一步的分析,現(xiàn)在通過構(gòu)造來證明g(k)=g(k-1)+ 3k-1： 第一次比較第1到3k-1號(hào)硬幣和3k-1個(gè)好硬幣，分以下情況討論：平衡：說明壞硬幣在剩下的g(k-1)個(gè)硬幣中，由g的定義，可以在k-1步內(nèi)找出。好球較輕：說明壞硬幣就在這些硬幣中，且較重，由上文結(jié)論，可以在k-1步

18、內(nèi)找出。好球較重：與上一種情況類似，不再贅述。,進(jìn)一步的分析,這樣，根據(jù)g(k)=g(k-1)+3k-1，計(jì)算得出：g(k)=(3k+1)/2。 “放大”后的問題解決了，那么原問題呢？我們可以猜想，一個(gè)好硬幣和無窮多個(gè)好硬幣是等效的，也就是說，如果設(shè)在有一個(gè)已知的好硬幣的情況下，k次比較最多從f(k)個(gè)硬幣中找出一個(gè)壞硬幣，那么f(k)≡g(k)。,下面進(jìn)行構(gòu)造證明,最后的構(gòu)造,根據(jù)計(jì)算g(k)時(shí)的推理，第一次比較應(yīng)該

19、有3k-1枚“有嫌疑”的硬幣上天平。由于這個(gè)數(shù)是奇數(shù)，所以只好把唯一一枚沒有嫌疑的硬幣也放上天平，這樣就確定了第一次比較的方案。　　如果比較結(jié)果是“平衡”，那么我們就把嫌疑縮小到了g(k-1)個(gè)硬幣中，而且有了足夠的好硬幣，很容易通過k-1次比較把壞硬幣找出來。,最后的構(gòu)造,但假如比較結(jié)果是“不平衡”呢？此時(shí)，壞硬幣編號(hào)的熵為log3k-1，如果要在k-1次比較內(nèi)找出壞硬幣，那么此后每一次比較結(jié)果的熵都得是log3。所以，這次比較得到

20、三種結(jié)果的概率必須相等。　　既然這樣，我們不妨來看看這次比較可能得到的三種結(jié)果都意味著什么。,最后的構(gòu)造,和第一次比較相同　　說明兩次比較中壞硬幣在天平同側(cè)。和第一次比較不同　　說明兩次比較中壞硬幣在天平異側(cè)。平衡　　說明第二次比較中壞硬幣沒上天平。,最后的構(gòu)造,因?yàn)檫@三種情況出現(xiàn)的概率相同且必居其一。所以第二次比較時(shí)，相對(duì)于第一次比較，有3k-2枚嫌疑硬幣保持原位，3k-2枚嫌疑硬幣換到了另一側(cè)，3k-2枚嫌疑硬幣換成了好

21、硬幣。而原來那枚好硬幣，為了保持天平兩邊硬幣數(shù)相等，也只好換到另一側(cè)。這樣，第二次比較的方案也被唯一確定了。,稍加分析不難得出后面的步驟。但由于整個(gè)過程的形式化描述過于繁瑣，故這里不再贅述。,最后的構(gòu)造,構(gòu)造完畢！,問題的解決,就這樣，在信息論的幫助下，這個(gè)困擾了我兩年的問題終于解決了。雖然這道題的重點(diǎn)在構(gòu)造而不是信息論，但信息論在證明解法的最優(yōu)性時(shí)是十分必要的，而且，信息論的分析也在本題如理亂麻的構(gòu)造過程中起著關(guān)鍵性的指導(dǎo)作用。,總結(jié)