1、<p>　　淺析非完美算法在信息學(xué)競(jìng)賽中的應(yīng)用</p><p>　　湖南省長(zhǎng)沙市長(zhǎng)郡中學(xué) 胡偉棟</p><p><b>　　【目錄】</b></p><p><b>　　摘要 2</b></p><p><b>　　關(guān)鍵字 2</b></p>

2、<p><b>　　正文 2</b></p><p><b>　　引言 2</b></p><p>　　非完美算法的一些基本方法 3</p><p><b>　　隨機(jī)貪心法 3</b></p><p><b>　　抽樣測(cè)試法 4</

3、b></p><p><b>　　部分忽略法 8</b></p><p>　　完美算法的依據(jù)——RP類問(wèn)題與Monte-Carlo算法 11</p><p>　　非完美算法的共性 11</p><p>　　非完美算法的優(yōu)點(diǎn)與缺點(diǎn) 12</p><p><b>　　總

4、結(jié) 13</b></p><p><b>　　感謝 13</b></p><p><b>　　參考文獻(xiàn) 13</b></p><p><b>　　附錄 13</b></p><p><b>　　【摘要】</b></p>

5、;<p>　　非完美算法就是用算法正確性的少量損失來(lái)?yè)Q取時(shí)間、空間效率以及編程復(fù)雜度的算法。本文介紹了非完美算法的幾種重要方法及非完美算法的優(yōu)缺點(diǎn)，從中，可以看出：并不是完全正確的算法就一定好過(guò)非完美算法，有可能因?yàn)榉峭昝浪惴ǖ牟煌耆?，反而使不正確的算法在很多方面比正確算法表現(xiàn)得更好。</p><p><b>　　【關(guān)鍵字】</b></p><p>　

6、　非完美算法 隨機(jī)化貪心法 抽樣測(cè)試法 部分忽略法</p><p><b>　　【正文】</b></p><p><b>　　一、引言</b></p><p>　　在平時(shí)，我們研究的算法基本都是完全正確的算法，我們所追求的，也是盡量使我們的算法正確。但在實(shí)際應(yīng)用中，有很多情況都不會(huì)對(duì)數(shù)據(jù)進(jìn)行天衣無(wú)縫的正確處理。如：圖片、音

7、頻、視頻的壓縮存儲(chǔ)，很多壓縮率比較高的方法都是有損壓縮；很多密碼驗(yàn)證的方法都是采用多對(duì)一的運(yùn)算方法，通過(guò)驗(yàn)證的不代表密碼真正正確；搜索引擎所提供的搜索，并不能將所有滿足條件的都找到……顯然，我們不會(huì)因?yàn)樗鼈兊牟煌昝蓝皇褂盟鼈?，它們的存在，有著它們的?shí)際意義：圖片、音頻、視頻的壓縮存儲(chǔ)，如果不損失一些，不可能將文件壓縮得很小；密碼驗(yàn)證雖是多對(duì)一，但找到兩個(gè)所對(duì)的是同一個(gè)何嘗容易；搜索引擎雖不能搜索到100%的結(jié)果，但其方便、快捷是無(wú)以倫

8、比的……</p><p>　　那么，在信息學(xué)競(jìng)賽中是否也可以用非完美算法解題呢？</p><p>　　本文試圖介紹一些比較有用的常見(jiàn)非完美算法，并希望讀者能從此得到一些啟發(fā)。</p><p>　　在開(kāi)始此文前，希望讀者能認(rèn)同一點(diǎn)：在信息學(xué)乃至整個(gè)計(jì)算機(jī)科學(xué)領(lǐng)域，不一定絕對(duì)正確的算法就是最好的算法，有可能一個(gè)在絕大多數(shù)情況下正確的算法(非完美算法)比一個(gè)完全正確的算法

9、更有前途?；蛘撸捎谒鼪](méi)有完全正確的算法考慮得全面，而使得它的空間或時(shí)間使用得較少；或者，由于它沒(méi)有正確的算法那么嚴(yán)謹(jǐn)，使得編程實(shí)現(xiàn)時(shí)較容易；或者，由于所用的知識(shí)沒(méi)有正確算法那么深?yuàn)W，使得它更容易被接受。</p><p>　　二、非完美算法的一些基本方法</p><p>　　1.1 隨機(jī)化貪心法</p><p>　　隨機(jī)化貪心是目前用得較廣泛的一種非完美算法。特別是

10、對(duì)求較優(yōu)解的題目，這種方法可以說(shuō)是首選。</p><p>　　隨機(jī)貪心，就是用隨機(jī)與貪心結(jié)合，在算法的每一步，都盡量使決策取得優(yōu)，但不一定是最優(yōu)決策。通過(guò)多次運(yùn)行，使得算法能取得一個(gè)較優(yōu)的解。有時(shí)，由于決策的優(yōu)劣判斷較復(fù)雜，直接用多次隨機(jī)也能得到較優(yōu)的結(jié)果。</p><p><b>　　例：傳染病控制</b></p><p><b>

11、　　題目大意</b></p><p>　　給出一棵傳染病傳播樹(shù)，其中根結(jié)點(diǎn)是被感染結(jié)點(diǎn)。每個(gè)時(shí)刻，被感染結(jié)點(diǎn)都會(huì)將傳染病傳播到它的子結(jié)點(diǎn)。但是，如果某時(shí)刻t切段A與其父結(jié)點(diǎn)B之間的邊，則時(shí)刻t以后，傳染病不會(huì)從B傳染給A(即A不會(huì)患病)。</p><p>　　每個(gè)時(shí)刻，只能切斷一條傳播途徑。問(wèn)每個(gè)時(shí)刻怎樣切段傳播途徑，使最少的人被感染。</p><p>

12、<b>　　說(shuō)明</b></p><p>　　本題的標(biāo)準(zhǔn)算法是搜索。關(guān)于如何用搜索解決此題，請(qǐng)參見(jiàn)附件《傳染病控制解題報(bào)告》，此解題報(bào)告由周戈林同學(xué)提供。</p><p><b>　　分析</b></p><p>　　顯然，如果某個(gè)結(jié)點(diǎn)已被感染，則以后沒(méi)有必要切斷它與它的父結(jié)點(diǎn)之間的傳播途徑，因?yàn)檫@樣和不切斷沒(méi)有區(qū)別(即切

13、斷已被感染的結(jié)點(diǎn)與其父結(jié)點(diǎn)之間的傳播途徑是無(wú)效的)；如果在一個(gè)時(shí)刻，切斷A與A的父結(jié)點(diǎn)之間的傳播途徑是有效的，切斷B與B的父結(jié)點(diǎn)之間的傳播途徑也是有效的，同時(shí)，B是A的子孫結(jié)點(diǎn)，則切斷A與A的父結(jié)點(diǎn)的傳播途徑優(yōu)于切斷B與B的父結(jié)點(diǎn)的傳播途徑。由于第t時(shí)刻被感染的顯然只可能是前t層的。因此可得到，第t時(shí)刻切斷的必然是第t層與第t+1層之間的傳播途徑。</p><p>　　本題可以用隨機(jī)貪心來(lái)做。</p>

14、<p>　　根據(jù)經(jīng)驗(yàn)，每次將一個(gè)結(jié)點(diǎn)數(shù)最多的子樹(shù)從原樹(shù)中切開(kāi)，結(jié)果會(huì)比較好。但這樣并不能適應(yīng)所有情況，有時(shí)，選結(jié)點(diǎn)數(shù)第二多的或第三多的反而能使以后的最終結(jié)果要好一些。所以，可以多次貪心，每次都隨機(jī)的選一個(gè)能切斷的結(jié)點(diǎn)數(shù)較多的方案切(或者說(shuō)每次使能切斷的結(jié)點(diǎn)數(shù)多的方案數(shù)被切的幾率大一些)，這樣，雖然大多數(shù)情況下其結(jié)果都比貪心要差，但只要隨機(jī)到一定的數(shù)量，這中間出現(xiàn)正確答案的概率就很大了。</p><p&g

15、t;　　上面加概率的隨機(jī)貪心有一點(diǎn)難處理的就是怎樣設(shè)置每種情況被選擇的概率。其實(shí)，對(duì)于此題，只要將每種情況被選到的概率都設(shè)成同樣大(即被選中的概率與其子結(jié)點(diǎn)數(shù)無(wú)關(guān))就可以了。這樣，這種方法就變成了純粹的隨機(jī)法，這種方法也能使此題得到滿分。</p><p><b>　　小結(jié)</b></p><p>　　隨機(jī)貪心是信息學(xué)競(jìng)賽中的一個(gè)重要工具，由于一般情況下它都是基于簡(jiǎn)單的

16、貪心，所以往往編程復(fù)雜性會(huì)比較低，同時(shí)運(yùn)行的時(shí)間復(fù)雜度也會(huì)比較低。隨機(jī)多次是隨機(jī)貪心的一個(gè)重要手段，通過(guò)多次運(yùn)行，往往能使程序得到非常優(yōu)的結(jié)果。</p><p><b>　　1.2 抽樣測(cè)試法</b></p><p>　　抽樣，即從統(tǒng)計(jì)總體中，任意抽出一部分單位作為樣本，并以其結(jié)果推算總體的相應(yīng)指標(biāo)。</p><p>　　在某些題目中，題設(shè)會(huì)給

17、出一系列需要測(cè)試的測(cè)試元(總體)S，若存在某一個(gè)測(cè)試元滿足某個(gè)條件A，則說(shuō)S滿足性質(zhì)P，若所有測(cè)試元都不滿足條件A，則說(shuō)S不滿足性質(zhì)P。</p><p>　　對(duì)于這個(gè)總體S，判斷它是否滿足性質(zhì)P，通常要將S中所有的測(cè)試元全部列舉出來(lái)才能知道。如果不列舉出全部(哪怕只有一個(gè)沒(méi)有列舉到)且當(dāng)前已測(cè)試的測(cè)試元都不滿足條件A，則不敢保證剩下的測(cè)試元不滿足條件，也就不能斷定S是否滿足性質(zhì)P。</p><

18、p>　　但是，若總體具有下面的性質(zhì)：它或者不含滿足條件的測(cè)試元，或者滿足條件的測(cè)試元的個(gè)數(shù)比較多。這時(shí)，只要選取一些具有代表性的很少一部分測(cè)試元進(jìn)行測(cè)試，就是保證結(jié)果基本正確。所謂有代表性，就是指取一些很特殊的測(cè)試元，同時(shí)取一些不特殊的測(cè)試元——就像問(wèn)卷調(diào)查一樣，從各種工作崗位、各種年齡階段的人群中取得的問(wèn)卷調(diào)查結(jié)果往往比在同一個(gè)工作崗位且年齡相仿的人群中取得的調(diào)查結(jié)果更讓人信服。</p><p>　　下面

19、，我們來(lái)看一個(gè)例子：一個(gè)總體S中含有10000個(gè)測(cè)試元，其中有100個(gè)測(cè)試元滿足條件A，現(xiàn)在，若從S中取出100個(gè)測(cè)試元進(jìn)行測(cè)試，則檢查出S滿足性質(zhì)P的概率約為：63.6%，若取200個(gè)測(cè)試元，則檢查出的概率為86.9%，若取300個(gè)，則檢查出的概率可達(dá)95.3%。</p><p>　　下圖中給出了取的個(gè)數(shù)與正確率之間的關(guān)系(注意：這里只畫(huà)了取0至800個(gè)時(shí)的圖像，當(dāng)取800個(gè)以上時(shí)，由于其正確率太接近100%，

20、其圖像近似一條水平直線而沒(méi)有再畫(huà)出的意義)：</p><p>　　從圖中還可以看出，只要抽樣大約70個(gè)，就有50%的正確率，抽樣大約230個(gè)，就有90%的正確率。</p><p>　　再看一個(gè)例子：如果總體S是{’A’,’B’,…,’Z’}的所有子集，而條件A是同時(shí)含有’A’~’G’的子集。按照上面，根據(jù)上面一例，可以想到，如果取一定量的子集測(cè)試，效果也會(huì)比較好，但好，對(duì)于總體S，它存在一

21、些特殊的子集——如空集、全集{’A’,’B’,…,’Z’}、只含一個(gè)元素的集合{’A’},{’B’}……這些都是我們認(rèn)為比較特殊的集合，如果從這些特殊的集合中先取出幾個(gè)測(cè)試，則可能在這些集合中就能找到滿足條件A的，如此例中取全集顯然就會(huì)滿足條件。</p><p>　　下面看一個(gè)具體的實(shí)例：</p><p>　　例：Intuitionistic Logic(直覺(jué)主義邏輯)</p>

22、<p><b>　　題目大意</b></p><p>　　給定一個(gè)有向無(wú)環(huán)圖G=(V,E)，在頂點(diǎn)V之間建立一些偏序關(guān)系：對(duì)于x,yV，定義x≤y當(dāng)且僅當(dāng)x到y(tǒng)之間存在路徑(可能長(zhǎng)度為0)。對(duì)于一個(gè)頂點(diǎn)集合S，定義Max(S)為S中所有最大元素的集合(即Max(S)中的任意一個(gè)頂點(diǎn)都不可能通過(guò)一條或多條E中的邊到達(dá)S中的其他頂點(diǎn))，寫(xiě)成表達(dá)式的形式為：</p>&

23、lt;p>　　Max(S)={xS|不存在yS,x≠y,x≤y}</p><p>　　令β為所有滿足Max(S)=S的集合所組成的集合，即：</p><p>　　β={S|Max(S)=S}</p><p>　　令0=Max(V)，1=，顯然0和1都屬于β</p><p>　　定義β中元素的一些操作：</p><p&

24、gt;　　P=>Q={xQ|不存在yP,x≤y},</p><p>　　PQ=Max(P∪Q),</p><p>　　PQ=Max({xV|存在yP,zQ,x≤y,x≤z}),</p><p><b>　　P=(P=>0),</b></p><p>　　P≡Q=((P=>Q)(P=>Q)) <

25、;/p><p>　　問(wèn)題：對(duì)于一個(gè)含有變量的表達(dá)式，問(wèn)是否無(wú)論變量如何在β中取值，其運(yùn)算結(jié)果都是1？</p><p>　　數(shù)據(jù)范圍：其中|V|≤100；|E|≤5000；對(duì)于同一個(gè)圖，要處理k個(gè)表示式，k≤20；每個(gè)表達(dá)式長(zhǎng)度不超過(guò)254個(gè)字符；|β|≤100； (vj是在第j個(gè)表達(dá)式中用到的變量個(gè)數(shù))</p><p><b>　　分析</b>&l

26、t;/p><p>　　本題的最后一個(gè)數(shù)據(jù)范圍其實(shí)暗示了我們，此題可以用枚舉來(lái)做，即枚舉所有變量的所有可能取值。顯然，如果要求完全正確，變量取值的總方案數(shù)是不可能減少的，即可能達(dá)到106，這時(shí)，就得設(shè)法減少計(jì)算的復(fù)雜度。顯然，上面的基本運(yùn)算都是O(|V|)或O(|E|)或更高的，而計(jì)算一個(gè)表達(dá)式可能要使用上百次基本運(yùn)算，這樣，盡管此題有5秒的時(shí)限，這樣的枚舉也是很難出解的。</p><p>　　

27、由|β|≤100，可以想到，將β中的每一個(gè)元素先用一個(gè)整數(shù)代替，并計(jì)算出對(duì)這些數(shù)進(jìn)行上面的基本運(yùn)算所得的值(當(dāng)然也用整數(shù)表示)。對(duì)這些值列一個(gè)表，以后計(jì)算時(shí)就只要從表中查找結(jié)果了。這樣，基本運(yùn)算的復(fù)雜度就可以降到O(1)，總的復(fù)雜度就可以降為。</p><p>　　此題還有一種解決方法，那就是抽樣。將變量取β中一些比較特殊的值(如0，1，……)看作特殊樣品，其它的看作一般樣品。抽取一些特殊樣品和一些一般樣品，對(duì)它

28、們進(jìn)行測(cè)試，如果對(duì)于一個(gè)式子，所有的樣品都滿足條件，則說(shuō)明式子滿足條件，否則說(shuō)式子滿足條件。實(shí)踐證明，只要抽取不到1000個(gè)樣品即可得到比較高的正確率。</p><p>　　當(dāng)然，對(duì)于這類多測(cè)試數(shù)據(jù)的題目，要基本保證一個(gè)測(cè)試點(diǎn)對(duì)，每組測(cè)試數(shù)據(jù)的正確概率必須更高一些。如：對(duì)于有20個(gè)組測(cè)試數(shù)據(jù)的測(cè)試點(diǎn)，如果保證每組數(shù)據(jù)的正確概率為95%，則整個(gè)測(cè)試點(diǎn)的正確概率只有0.9520，還不到36%；如果保證每組數(shù)據(jù)的正確概

29、率為99%，整個(gè)測(cè)試點(diǎn)的正確概率才82%；如果每組數(shù)據(jù)正確概率達(dá)到99.9%，則整個(gè)測(cè)試點(diǎn)的正確概率就會(huì)有98%。</p><p>　　這里特別要說(shuō)明的是：一般情況下，抽樣的數(shù)目應(yīng)該盡量多(在保證不超時(shí)的前提下)，這樣才能保證正確概率較大。</p><p><b>　　抽樣法的實(shí)際運(yùn)用：</b></p><p>　　在測(cè)試質(zhì)數(shù)時(shí)，抽樣法是一個(gè)非

30、常有用的工具。下面給出一種質(zhì)數(shù)判定方法：</p><p>　　對(duì)于待判定的整數(shù)n。設(shè)n-1=d*2s(d是奇數(shù))。對(duì)于給定的基底a，若</p><p><b>　　或存在0≤r<s使</b></p><p>　　則稱n為以a為底的強(qiáng)偽質(zhì)數(shù)(Strong Pseudoprime)。利用二分法，可以在O(log2n)的時(shí)間內(nèi)判定n是否為以a為

31、底的強(qiáng)偽質(zhì)數(shù)。</p><p>　　對(duì)于合數(shù)c，以小于c的數(shù)為底，c至多有1/4的機(jī)會(huì)為強(qiáng)偽質(zhì)數(shù)(Monier 1980, Rabin 1980)。</p><p>　　根據(jù)這條，判斷一個(gè)數(shù)n是否為質(zhì)數(shù)，可以隨機(jī)地抽取小于n的k個(gè)數(shù)為底。這樣，正確的概率不小于1-4-k。顯然，這已經(jīng)非常優(yōu)秀了，通常只要取幾十組就可以保證基本正確。</p><p>　　如果不是隨機(jī)抽

32、樣，而是抽樣特殊情況——最小的幾個(gè)質(zhì)數(shù)，則：</p><p>　　如果只用2一個(gè)數(shù)進(jìn)行測(cè)試，最小的強(qiáng)偽質(zhì)數(shù)(反例)是2047(所以一個(gè)數(shù)顯然不夠)；</p><p>　　如果用2和3兩個(gè)數(shù)進(jìn)行測(cè)試，最小的強(qiáng)偽質(zhì)數(shù)大于106；</p><p>　　如果用2,3,5進(jìn)行測(cè)試，最小的強(qiáng)偽質(zhì)數(shù)大于2×107；</p><p>　　如果用2,

33、3,5,7進(jìn)行測(cè)試，最小的強(qiáng)偽質(zhì)數(shù)大于3×109，已經(jīng)比32位帶符號(hào)整數(shù)的最大值(Pascal中的Maxlongint)還大了。</p><p>　　可見(jiàn)，通常只要抽取2,3,5,7這幾個(gè)固定的數(shù)進(jìn)行測(cè)試就能保證測(cè)試的正確性了。</p><p>　　我們知道，最樸素的質(zhì)數(shù)測(cè)試方法是用2至的數(shù)對(duì)n進(jìn)行試除。這樣，測(cè)試一個(gè)數(shù)的復(fù)雜度為O(n0.5)，用上面的方法，每次測(cè)試只要O(lo

34、g2n)的復(fù)雜度，由于只要測(cè)試很少的幾次，所以，其總復(fù)雜度仍是O(log2n)的?？梢?jiàn)，用抽樣的方法對(duì)質(zhì)數(shù)進(jìn)行測(cè)試的算法明顯優(yōu)于樸素的質(zhì)數(shù)測(cè)試法。</p><p><b>　　小結(jié)</b></p><p>　　從上面的例子可以看出，由于抽樣法只對(duì)總體中的一部分更行測(cè)試，所以它要測(cè)試的次數(shù)非常少，從而使得算法需要的時(shí)間比完全枚舉少很多，算法的效率也會(huì)高很多。</p

35、><p><b>　　1.3 部分忽略法</b></p><p>　　在信息學(xué)中，可能會(huì)遇到這樣情況：一個(gè)題的分類非常復(fù)雜，且某些情況的處理非常復(fù)雜，但這些情況往往不是主要情況(即出現(xiàn)的概率很小或不處理這些情況對(duì)答案不會(huì)造成很大的影響)。有時(shí)，忽略這些復(fù)雜卻影響不大的情況會(huì)使程序達(dá)到令人滿意的結(jié)果。</p><p><b>　　例：Pol

36、ygon</b></p><p><b>　　題目大意</b></p><p>　　在此題中，所有的多邊形均指凸多邊形。</p><p>　　給定兩個(gè)多邊形A和B，A和B的Minkowski和是指包含所有形如(x1+x2, y1+y2) 的點(diǎn)的多邊形，其中(x1,y1) 是A中的點(diǎn)，(x2,y2)是B中的點(diǎn)。</p>

37、<p>　　我們考慮Minkowski和的一種逆運(yùn)算。給定一個(gè)多邊形P, 我們尋找兩個(gè)多邊形A和B，滿足：</p><p>　　- P是A和B的Minkowski和；</p><p>　　- A有2到4個(gè)不同的頂點(diǎn)(線段、三角形或四邊形)；</p><p>　　- A必須包含盡可能多的頂點(diǎn)。</p><p>　　說(shuō)明：此題附官方解答

38、，其復(fù)雜度為O(N2m2)，其中N為多邊形P的頂點(diǎn)數(shù)，m為P的邊上的整點(diǎn)個(gè)數(shù)的最大值</p><p><b>　　分析</b></p><p>　　由于本題中，位置并不是很難處理，所以此題將不考慮多邊形的位置問(wèn)題，只考慮其形狀和大小。</p><p>　　根據(jù)定義可以知道，對(duì)兩個(gè)多邊形A、B求Minkowski和，就是將它們的所有的邊看作有順序

39、的向量，對(duì)所有向量按其級(jí)角排序，然后將所有的向量順次連接，最后將共線同向的向量合并的過(guò)程。</p><p>　　由上面加法的過(guò)程不難想到，原來(lái)的多邊形A、B的每條邊在P中仍存在一條邊與原邊共線同向且模不小于原邊，因此：</p><p>　　將一個(gè)多邊形P拆成邊數(shù)為K的多邊形A與不定邊數(shù)的多邊形B相加的形式，就是要從P中找出K條邊，從每邊取出一段(或整條邊)，使這K段正好能圍成一個(gè)多邊形，這

40、個(gè)多邊形就是A，剩下的按照向量首尾相連可得到B。</p><p>　　如：從上圖的多邊形P中取一個(gè)邊數(shù)為2的多邊形：</p><p>　　從P中取出一個(gè)三角形、四邊形，也是同樣的方法。</p><p>　　這個(gè)算法看起來(lái)很簡(jiǎn)單，但實(shí)現(xiàn)起來(lái)并沒(méi)有想象中那么輕松。</p><p>　　找一個(gè)二邊形，只要找到一對(duì)共線向量即可。</p>

41、<p>　　找一個(gè)三角形，可以枚舉三條邊，然后判斷，其復(fù)雜度是O(N3m3)。在提交答案類題看來(lái)，已經(jīng)很不錯(cuò)了。</p><p>　　找一個(gè)四邊形，如果枚舉四條邊，然后判斷，其復(fù)雜度是O(N4m4)，因其中的m是未知的，所以不敢輕易使用。這時(shí)可以枚舉三條邊，另一條邊通過(guò)對(duì)邊的二分查找得到。由于第四條邊可能是多邊形P中某條邊的一段，而P中一共可能有N*m段，因m未知，使得空間分配也不好處理；同時(shí)，由于存

42、儲(chǔ)時(shí)不僅要存儲(chǔ)每段所對(duì)應(yīng)的原來(lái)的邊的序號(hào)，還要存儲(chǔ)每段是占原來(lái)的幾分之幾……此時(shí)遇到的問(wèn)題可能還遠(yuǎn)不只這些，這時(shí)，就很難保證程序不出錯(cuò)。</p><p>　　這種，不妨做一個(gè)大膽的假設(shè)：假設(shè)第四條邊是P中的一條完整的邊。這樣，只要存儲(chǔ)P條邊即可，且這P條邊都是原來(lái)多邊形中的完整的邊，所以編程中要考慮的問(wèn)題就少多了，同時(shí)出錯(cuò)的可能性也小多了。</p><p>　　這樣做，對(duì)于官方的數(shù)據(jù)，有9

43、個(gè)測(cè)試點(diǎn)可以出解，所出的解全部是最優(yōu)解。另一個(gè)測(cè)試點(diǎn)可以用手做。</p><p>　　部分忽略法的實(shí)際應(yīng)用</p><p>　　下面看一下判斷一個(gè)點(diǎn)P是否在一個(gè)簡(jiǎn)單多邊形內(nèi)的算法：</p><p>　　假設(shè)已經(jīng)判斷了P在多邊形邊上這種特殊情況，剩下的只有點(diǎn)在多邊形內(nèi)和外的問(wèn)題。</p><p>　　傳統(tǒng)的判斷算法是：以P為端點(diǎn)作一條射線，然后

44、根據(jù)射線與多邊形的交點(diǎn)個(gè)數(shù)是奇數(shù)個(gè)還是偶數(shù)個(gè)來(lái)判斷其是否在多邊形內(nèi)。</p><p>　　但是，在計(jì)算交點(diǎn)個(gè)數(shù)的時(shí)候，有一種特殊情況：所作的射線經(jīng)過(guò)多邊形的某個(gè)頂點(diǎn)(有可能更特殊的與多邊形的一條邊重合)。如下圖：</p><p>　　在(a)中，處理的結(jié)果應(yīng)為射線與多邊形有奇數(shù)個(gè)交點(diǎn)，而(b)中，處理的結(jié)果應(yīng)為射線與多邊形有偶數(shù)個(gè)交點(diǎn)，如果不加特殊處理，則兩種情況所得到的結(jié)果是相同的。&l

45、t;/p><p>　　如果采用部分忽略法似乎會(huì)出現(xiàn)錯(cuò)誤。但是，如果取的射線是一條很“一般”的射線：如在平面內(nèi)隨機(jī)取一個(gè)異于P的點(diǎn)Q，且保證Q的坐標(biāo)有若干位小數(shù)，從P作一條射線，使射線經(jīng)過(guò)Q，則，可以說(shuō)，要出錯(cuò)的概率是非常小的。如果多取幾個(gè)點(diǎn)，分別對(duì)這幾個(gè)點(diǎn)進(jìn)行判斷，然后取這些結(jié)果中出現(xiàn)得最多的結(jié)果，則要出錯(cuò)就更不可能了。</p><p><b>　　小結(jié)</b></

46、p><p>　　通過(guò)上面的例題可以看出，能過(guò)忽略部分復(fù)雜情況，能使算法的思考復(fù)雜性和編程復(fù)雜性降低。僅管它可能造成算法在一定程度上的錯(cuò)誤，但這種錯(cuò)誤通常是很小的。所以，有時(shí)采用部分忽略法仍是非常好的選擇。</p><p>　　三、非完美算法的依據(jù)——RP類問(wèn)題與Monte-Carlo算法</p><p>　　前面所講的一些方法，似乎都是靠的“運(yùn)氣”成分。但是，這些算法有

47、它的依據(jù)：</p><p>　　如果一個(gè)問(wèn)題存在一個(gè)隨機(jī)算法，使得它有50%以上的概率得到期望的結(jié)果，那么這個(gè)問(wèn)題屬于RP類問(wèn)題。該算法稱為Monte-Carlo算法。</p><p>　　如果一個(gè)問(wèn)題是RP類問(wèn)題，可以通過(guò)多次運(yùn)行它的一個(gè)Monte-Carlo算法而得到“幾乎每次都是正確”的算法。</p><p>　　由于RP類問(wèn)題與Monte-Carlo算法不是

48、本文研究的重點(diǎn)，這里不再多做介紹，有興趣的讀者可以參閱相關(guān)的資料。</p><p>　　四、非完美算法的共性</p><p>　　非完美算法有很多種，但是，它們并不是完全不同的，它們之間存在一個(gè)共同的性質(zhì)，那就是不完全性。上面的非完美算法都是由于其不完全性而使得它們具有一些完全正確的算法所不能具備的優(yōu)勢(shì)，同時(shí)，其不完全性也導(dǎo)致了算法不是完全正確的。</p><p>

49、　　五、非完美算法的優(yōu)點(diǎn)與缺點(diǎn)</p><p><b>　　4.1 優(yōu)點(diǎn)</b></p><p>　　從上面的分析和舉例，相信讀者對(duì)非完美算法的優(yōu)點(diǎn)已經(jīng)有所了解了，現(xiàn)整理如下：</p><p>　?、贂r(shí)空消耗低：這是非完美算法的一個(gè)最突出的優(yōu)點(diǎn)，也是大多數(shù)情況下使用它的原因。</p><p>　?、诰幊虖?fù)雜度低：因?yàn)榉峭?/p>

50、美算法會(huì)可能繞過(guò)紛繁的處理或會(huì)忽略掉非常難處理的一些情況，其編程復(fù)雜度可以得到一定的降低。在比賽中，低的編程復(fù)雜度往往比低的算法時(shí)間復(fù)雜更容易得到令人滿意的結(jié)果。</p><p>　?、鬯季S復(fù)雜度低：同樣也是因?yàn)榉峭昝浪惴赡芎雎缘舴浅ｋy處理的一些情況。</p><p>　　④能減少編程錯(cuò)誤：通過(guò)前面幾點(diǎn)，這點(diǎn)也就顯然了。也許，一個(gè)非常優(yōu)秀的算法，因?yàn)樗囊稽c(diǎn)點(diǎn)小錯(cuò)誤，就導(dǎo)致其前功盡棄，而

51、一個(gè)非完美的算法，因?yàn)樗^容易實(shí)現(xiàn)，減少或避免了編程錯(cuò)誤，反而能得到意想不到的好結(jié)果。</p><p><b>　　4.2 缺點(diǎn)</b></p><p>　　非正確性：這是不言而喻的，非完美算法，值得利用的就是它的非正確性。但非正確性使得算法不僅依賴算法的好壞、代碼的好壞，還依賴于數(shù)據(jù)。如果數(shù)據(jù)較弱，非完美算法可能得到較高的分?jǐn)?shù)，如果數(shù)據(jù)較強(qiáng)，其結(jié)果不一定很理想。&l

52、t;/p><p><b>　　【總結(jié)】</b></p><p>　　本文主要介紹了非完美算法的幾種重要方法。從上面的算法可以看到，并不是正確的算法就一定好過(guò)不完全正確的算法，因?yàn)榉峭昝浪惴ǖ牟煌耆?，反而使非完美算法在很多方面比正確算法表現(xiàn)得更好。因此，合理的使用非完美算法能使我們得到令人滿意結(jié)果。</p><p><b>　　【感謝】&

53、lt;/b></p><p>　　衷心感謝向期中老師在我寫(xiě)這篇論文時(shí)對(duì)我的指導(dǎo)和幫助。</p><p>　　衷心感謝劉汝佳教練對(duì)我的指導(dǎo)和啟發(fā)。</p><p>　　衷心感謝王俊、任愷同學(xué)對(duì)我的支持和幫助。</p><p>　　衷心感謝肖湘寧、周戈林同學(xué)在臨近期末考試時(shí)還能為我看論文，并向我提很多寶貴的意見(jiàn)，特別感謝周戈林同學(xué)提供NOI

54、P2003《傳染病控制》的解題報(bào)告。</p><p><b>　　【參考文獻(xiàn)】</b></p><p>　　《論隨機(jī)化算法的原理與設(shè)計(jì)》——周詠基,1999</p><p>　　《The CRC Concise Encyclopedia of Mathematics》——Eric W. Weisstein,CRC Press</p>

55、<p>　　《計(jì)算幾何——算法分析與設(shè)計(jì)》——周培德,清華大學(xué)出版社,廣西科學(xué)技術(shù)出版社</p><p>　　《算法藝術(shù)與信息學(xué)競(jìng)賽》——?jiǎng)⑷昙?、黃亮，清華大學(xué)出版社</p><p>　　《IOI'04: Solution of Polygon》——Ioannis Emiris and Elias Tsigaridas,2004</p><p>

56、;<b>　　【附錄】</b></p><p><b>　　最小強(qiáng)偽質(zhì)數(shù)表</b></p><p>　　傳染病控制原題(NOIP2003)</p><p><b>　　【問(wèn)題背景】</b></p><p>　　近來(lái)，一種新的傳染病肆虐全球。蓬萊國(guó)也發(fā)現(xiàn)了零星感染者，為防止該病在

57、蓬萊國(guó)</p><p>　　大范圍流行，該國(guó)政府決定不惜一切代價(jià)控制傳染病的蔓延。不幸的是，由于人們尚未完</p><p>　　全認(rèn)識(shí)這種傳染病，難以準(zhǔn)確判別病毒攜帶者，更沒(méi)有研制出疫苗以保護(hù)易感人群。于是，</p><p>　　蓬萊國(guó)的疾病控制中心決定采取切斷傳播途徑的方法控制疾病傳播。經(jīng)過(guò) WHO（世界衛(wèi)</p><p>　　生組織）以及

58、全球各國(guó)科研部門(mén)的努力，這種新興傳染病的傳播途徑和控制方法已經(jīng)研究</p><p>　　消楚，剩下的任務(wù)就是由你協(xié)助蓬萊國(guó)疾控中心制定一個(gè)有效的控制辦法。</p><p><b>　　【問(wèn)題描述】</b></p><p>　　研究表明，這種傳染病的傳播具有兩種很特殊的性質(zhì)；</p><p>　　第一是它的傳播途徑是樹(shù)型的

59、，一個(gè)人X只可能被某個(gè)特定的人Y感染，只要Y不</p><p>　　得病，或者是XY之間的傳播途徑被切斷，則X就不會(huì)得病。</p><p>　　第二是，這種疾病的傳播有周期性，在一個(gè)疾病傳播周期之內(nèi)，傳染病將只會(huì)感染一</p><p>　　代患者，而不會(huì)再傳播給下一代。</p><p>　　這些性質(zhì)大大減輕了蓬萊國(guó)疾病防控的壓力，并且他們已經(jīng)

60、得到了國(guó)內(nèi)部分易感人群</p><p>　　的潛在傳播途徑圖（一棵樹(shù)）。但是，麻煩還沒(méi)有結(jié)束。由于蓬萊國(guó)疾控中心人手不夠，同</p><p>　　時(shí)也缺乏強(qiáng)大的技術(shù)，以致他們?cè)谝粋€(gè)疾病傳播周期內(nèi)，只能設(shè)法切斷一條傳播途徑，而</p><p>　　沒(méi)有被控制的傳播途徑就會(huì)引起更多的易感人群被感染（也就是與當(dāng)前已經(jīng)被感染的人有</p><p>　

61、　傳播途徑相連，且連接途徑?jīng)]有被切斷的人群）。當(dāng)不可能有健康人被感染時(shí)，疾病就中止</p><p>　　傳播。所以，蓬萊國(guó)疾控中心要制定出一個(gè)切斷傳播途徑的順序，以使盡量少的人被感染。</p><p>　　你的程序要針對(duì)給定的樹(shù)，找出合適的切斷順序。</p><p><b>　　【輸入格式】</b></p><p>　　

62、輸入格式的第一行是兩個(gè)整數(shù)n（1≤n≤300）和p。接下來(lái)p行，每一行有兩個(gè)整數(shù)i</p><p>　　和j，表示節(jié)點(diǎn)i和j間有邊相連（意即，第i人和第j人之間有傳播途徑相連）。其中節(jié)點(diǎn)</p><p>　　1是已經(jīng)被感染的患者。</p><p><b>　　【輸出格式】</b></p><p>　　只有一行，輸出總共被

63、感染的人數(shù)。</p><p><b>　　【輸入樣例】</b></p><p><b>　　7 6</b></p><p><b>　　1 2</b></p><p><b>　　1 3</b></p><p><b>　

64、　2 4</b></p><p><b>　　2 5</b></p><p><b>　　3 6</b></p><p><b>　　3 7</b></p><p><b>　　【輸出樣例】</b></p><p>&l

65、t;b>　　3</b></p><p>　　Polygon中文原題</p><p><b>　　【問(wèn)題描述】</b></p><p>　　凸多邊形的定義如下：多邊形內(nèi)任意兩點(diǎn)X和 Y 的連線上的所有點(diǎn)都在多邊形內(nèi)部。在本題中的所有多邊形都是擁有至少兩個(gè)頂點(diǎn)的凸多邊形并且所有頂點(diǎn)互不相同，且具有整數(shù)坐標(biāo)。多邊形的任意三個(gè)頂點(diǎn)不共

66、線。在下文中的“多邊形” 一詞都是指這樣的多邊形。</p><p>　　給定兩個(gè)多邊形A 和 B， A 和 B 的Minkowski 和 包含所有形如(x1+x2, y1+y2) 的點(diǎn)，其中 (x1, y1) 是 A 中的點(diǎn)，(x2, y2) 是 B 中的點(diǎn)。多邊形的Minkowski 和也是一個(gè)多邊形。下圖是一個(gè)例子：兩個(gè)三角形和它們的 Minkowski 和。</p><p>　　我

67、們考慮Minkowski 和 的一種逆運(yùn)算。給定一個(gè)多邊形P, 我們尋找兩個(gè)多邊形A 和 B ，滿足:</p><p>　　P 是A 和 B 的Minkowski 和, </p><p>　　A 有2 到 4 個(gè)不同的頂點(diǎn)，例如，它是一條線段（2個(gè)頂點(diǎn)）, 一個(gè)三角形（3個(gè)頂點(diǎn)），或一個(gè)四邊形（4個(gè)頂點(diǎn)），</p><p>　　A 必須包含盡可能多的頂點(diǎn)，例如：&

68、lt;/p><p>　　A 如果可能的話，必須是一個(gè)四邊形， </p><p>　　如果 A 不可能是一個(gè)四邊形而有可能是一個(gè)三角形，則它必須是一個(gè)三角形， </p><p><b>　　否則它是一條線段。</b></p><p>　　很顯然， A 和 B 都不能等于 P ，因?yàn)槿绻渲幸粋€(gè)等于P， 則另一個(gè)只能是一個(gè)點(diǎn)，而

69、點(diǎn)不是一個(gè)合法的多邊形。</p><p>　　給定多個(gè)輸入文件，每個(gè)輸入文件描述一個(gè)多邊形P。 對(duì)于每一個(gè)輸入文件，你必須找出滿足上述條件的A 和 B， 并且創(chuàng)建一個(gè)文件來(lái)描述A 和 B 。 對(duì)于所有給定的輸入文件， A 和 B 一定存在。如果存在多組解，只需要輸出其中的任意一組。不要提交源程序，只需要提交輸出文件。 </p><p><b>　　【輸入格式】</b>

70、</p><p>　　共有十組輸入文件從 polygon1.in 到 polygon10.in, 在polygon 后的數(shù)字是輸入文件序號(hào)。每個(gè)輸入文件的構(gòu)成如下：第一行包含一個(gè)整數(shù)N： 多邊形 P的頂點(diǎn)個(gè)數(shù)。 接下來(lái)的N 行以逆時(shí)針?lè)较蛎枋隽薔 個(gè)頂點(diǎn)的坐標(biāo)，每個(gè)頂點(diǎn)一行。第I+1 (I = 1, 2, ..., N) 行包含兩個(gè)整數(shù)XI 和 YI， 以一個(gè)空格隔開(kāi)，表示第I 個(gè)頂點(diǎn)。所有坐標(biāo)為非負(fù)整數(shù)。&l

71、t;/p><p><b>　　【輸出格式】</b></p><p>　　針對(duì)給定的輸入文件，你需要給出相應(yīng)的10個(gè)輸出文件用以描述相應(yīng)的A 和 B。輸出文件的第一行應(yīng)包含：</p><p>　　#FILE polygon I</p><p>　　這里整數(shù)I 表示相應(yīng)的輸入文件序號(hào)。</p><p>　

72、　輸出文件的格式與輸入文件類似。第二行包含一個(gè)整數(shù) NA：A中的頂點(diǎn)數(shù) (2≤NA≤4)。 接下來(lái)的 NA 行以逆時(shí)針?lè)较蛎枋鯝 的NA個(gè)頂點(diǎn)，每個(gè)頂點(diǎn)一行。第 I+2 ( I = 1, 2, ..., NA) 行包含兩個(gè)整數(shù) X 和 Y, 以一個(gè)空格隔開(kāi)：表示A的第I個(gè)頂點(diǎn)。</p><p>　　第 NA +3 行包含一個(gè)整數(shù) NB： 表示 B 中的頂點(diǎn)個(gè)數(shù) (2≤NB)。 接下來(lái)的 NB 行以逆時(shí)針?lè)较蛎枋鯞

73、 的NB 個(gè)頂點(diǎn)，每個(gè)頂點(diǎn)一行。第NA +J+3 ( J = 1, 2, ..., NB) 行包含兩個(gè)整數(shù)X 和 Y， 以一個(gè)空格隔開(kāi)：表示B 的第 J個(gè)頂點(diǎn)。 </p><p><b>　　【輸入輸出樣例】</b></p><p>　　polygon0.in</p><p>　　對(duì)于上面的輸入，下面兩種輸出都是正確的，因?yàn)樵诿糠N輸出中A 都是