算法合集之《論當(dāng)今信息學(xué)競(jìng)賽中數(shù)學(xué)建模的靈活性》

1、隱蔽化、多維化、開放化 論當(dāng)今信息學(xué)競(jìng)賽中數(shù)學(xué)建模的靈活性杭州外國(guó)語(yǔ)學(xué)校 石潤(rùn)婷【關(guān)鍵字】 數(shù)學(xué)建模 隱蔽化 多維化 開放化【摘要】數(shù)學(xué)建模是信息學(xué)奧林匹克競(jìng)賽的有機(jī)組成部分。當(dāng)今信息學(xué)競(jìng)賽越來(lái)越追求數(shù)學(xué)建模的靈活性。其表現(xiàn)大致有模型的隱蔽化、多維化和開放化三條。本文通過(guò)對(duì)這“三化”的含義及表現(xiàn)的探討，研究相應(yīng)的解題策略一、引子 數(shù)學(xué)建模作為信息學(xué)奧林匹克競(jìng)賽的一個(gè)不可或缺的組成部分，自該競(jìng)賽誕生以來(lái)，一直在進(jìn)化，在完善，在發(fā)展。當(dāng)今信息學(xué)競(jìng)賽越來(lái)越追求數(shù)學(xué)建模的靈活性。也正是這種靈活性，使數(shù)學(xué)建模的魅力畢現(xiàn)，從而賦予信息學(xué)競(jìng)賽以無(wú)限的生命力和廣闊的發(fā)展前景。 通過(guò)對(duì)一系列新興競(jìng)賽題的考察和研

2、究，我發(fā)現(xiàn)當(dāng)今信息學(xué)競(jìng)賽中數(shù)學(xué)建模的靈活性可以概括為模型的隱蔽化、多維化和開放化這三條。下面，讓我們通過(guò)對(duì)這“三化”的含義及其表現(xiàn)的探討，以獲得相應(yīng)的解題策略。二、主體（一）隱蔽化、定義“隱蔽”的本意是“借旁的事物來(lái)遮掩”。而具體落實(shí)到信息學(xué)競(jìng)賽中，“旁的事物”和被“遮掩”的對(duì)象便有了特定的指代。顯然，從我們的論題便可一目了然：被“遮掩”的對(duì)象即數(shù)學(xué)模型；而“旁的事物”在這里指的是撲朔迷離的現(xiàn)實(shí)情景。這樣，信息學(xué)競(jìng)賽中數(shù)學(xué)模型隱蔽化的定義便顯而易見了，即借撲朔迷離的現(xiàn)實(shí)情景來(lái)遮掩數(shù)學(xué)模型。、表現(xiàn)隱蔽化在信息學(xué)競(jìng)賽中的一大表現(xiàn)就是“老模型，新面孔”也就是說(shuō)，沿用我們都熟悉的模型，而制造出全新的場(chǎng)

3、景來(lái)容納此模型，從而給原本赤裸裸的模型披上了新裝，將它“掩護(hù)”起來(lái)。因而相同的模型，在不同競(jìng)賽題中的表現(xiàn)往往變幻莫測(cè)，如最佳旅行路線（NOI97）和新型導(dǎo)彈兩題，就是典型的例子。題目請(qǐng)參閱附錄一、二。這兩題前者描述的是一個(gè)由“林蔭道”、“旅游街”組成的街道網(wǎng)格，而后者描述卻的是一個(gè)“導(dǎo)彈爆炸”問(wèn)題。因此，單從表面看，兩者應(yīng)該是風(fēng)馬牛不相及的。然而，兩種截然不同的表面現(xiàn)象背后，恰恰蘊(yùn)藏著相同的原型求一維數(shù)列中“最大”（元素和最大）連續(xù)子序列的問(wèn)題，即已知數(shù)列求這兩題有一個(gè)共同點(diǎn)，即題目本身并沒(méi)有直截了當(dāng)?shù)貙?shù)學(xué)模型展現(xiàn)出來(lái)，而是通過(guò)對(duì)復(fù)雜的實(shí)際情景的具體描繪，要求選手自己從實(shí)際情景中歸納、抽象出

4、數(shù)學(xué)模型。因而，它們充分地體現(xiàn)了信息學(xué)競(jìng)賽中數(shù)學(xué)模型的隱蔽化特點(diǎn)。、策略“撥開迷霧”法雖然撲朔迷離的現(xiàn)實(shí)情景往往給觀者以一種霧里看花的朦朧感，但是，只要我們能以敏銳的目光，透過(guò)這紛繁復(fù)雜的表面現(xiàn)象去觀察并很好地把握模型的實(shí)質(zhì)，問(wèn)題往往就能迎刃而解。下面，讓我們通過(guò)對(duì)新型導(dǎo)彈一題的分析，具體看一看我們撥開迷霧、挖掘問(wèn)題本質(zhì)的思維歷程。我們首先不能被所謂的“屏蔽半徑”和“攻擊半徑”、“居民點(diǎn)”和“碉堡”這些表象所迷惑。我們應(yīng)該注意到以下事實(shí)：可以將居民點(diǎn)的分值修改為它的相反數(shù)，則爆炸總利益所有居民點(diǎn)的分值和所有碉堡的分值和；于是我們就能將居民點(diǎn)和碉堡統(tǒng)一起來(lái)看待。一旦確定了“屏蔽半徑”和“攻擊半徑

5、”后，某一個(gè)建筑物是否被炸毀只與它與圓心（爆炸點(diǎn)）之間的距離有關(guān)，而與其在平面內(nèi)（戰(zhàn)場(chǎng)上）的具體位置無(wú)關(guān)。因此，我們?cè)谧x入數(shù)據(jù)的時(shí)候，就可以只儲(chǔ)存各點(diǎn)與圓心之間的距離，而摒棄具體的x,y坐標(biāo)。可以將這些點(diǎn)按照離圓心由近到遠(yuǎn)的順序排序，同時(shí)將與圓心等距的點(diǎn)合并成一個(gè)代表點(diǎn)，其分值為這些點(diǎn)的總分值。如圖：于是，我們的任務(wù)就變成了求上圖所示的一維表的最大子序列問(wèn)題，即模型的實(shí)質(zhì)。（附程序新型導(dǎo)彈missile.pas）總之，我們?cè)谀玫筋}目時(shí)，不能急于動(dòng)手編程，而首先應(yīng)該冷靜地去思考分析問(wèn)題，并從與之關(guān)聯(lián)的各種信息中，正確地“過(guò)濾”掉迷惑人的無(wú)用的部分，“提煉”出關(guān)鍵的部分，從而很好地把握這“新面孔”

6、背后隱藏的“老模型”。俗話說(shuō)，磨刀不誤砍柴功。只有經(jīng)過(guò)了周密深入的思考，我們才有可能透過(guò)現(xiàn)象洞察到問(wèn)題的本質(zhì)。而此時(shí)再著手編程，就能胸有成竹，事半功倍。 （二）多維化模型的多維化是信息學(xué)競(jìng)賽中數(shù)學(xué)建模靈活性的另一個(gè)體現(xiàn)。多維化大致可分為“實(shí)”的和“虛”的兩類。、“實(shí)”的多維化(1)含義 所謂“實(shí)”的多維化，顧名思義，就是指實(shí)實(shí)在在的，“看得見，摸得著”的多維化。這是它的內(nèi)涵。而它的外延就是模型由線向面擴(kuò)展，由面向空間擴(kuò)展。 我們來(lái)看如下兩個(gè)模型，從中來(lái)領(lǐng)略一下“由線向面向空間”的具體含義：模型1已知平面內(nèi)的若干個(gè)點(diǎn)，求覆蓋這些點(diǎn)的最小圓。模型2已知空間內(nèi)的若干個(gè)點(diǎn)，求覆蓋這些點(diǎn)的最小球。我們可

7、以看出，模型2是在模型1的基礎(chǔ)上進(jìn)行多維化而得到的產(chǎn)物。 事實(shí)上，這類多維化模型已屢次在競(jìng)賽題和練習(xí)題中出現(xiàn)。上述模型2只是其中小小的一例。 (2)策略“降維”法這種“實(shí)”的多維化趨勢(shì)增添了我們所要考慮的空間因素，進(jìn)而加大了模型求解的難度。 解這類題目時(shí)，我們往往需要追尋出題者的思路，也來(lái)一個(gè)循序漸進(jìn)，先從低維的問(wèn)題出發(fā)，在找到低維問(wèn)題的合適解法后，再加以引申和推廣，從而得到相應(yīng)多維問(wèn)題的解法。這實(shí)際上就是一種“降維”的思想，其優(yōu)點(diǎn)在于它先化繁為簡(jiǎn)，有利于我們找出分析思考的著手點(diǎn)。而在我們把握了低維模型的解法后，再由簡(jiǎn)返難，就如囊中探物般地獲得多維問(wèn)題的解法。 “降維”思想在不同的題目中有著不

8、同的運(yùn)用方式。i.類比法讓我們以NOI97衛(wèi)星覆蓋一題為例（請(qǐng)參閱附錄三）。此題在分析過(guò)程中的第一大障礙也許要數(shù)空間難度了。但是此時(shí)，如果擺在面前的不是一個(gè)三維情景，而是簡(jiǎn)單的二維情景，我們也許就會(huì)信心百倍了。那么，何不先嘗試著去求解此二維模型，或許還能從中獲得一點(diǎn)啟示。事實(shí)上，該題的二維模型，即求若干個(gè)可能有重疊的共面矩形所覆蓋的總面積的問(wèn)題，在第五屆IOI中求圖形面積一題（請(qǐng)參閱附錄四）已經(jīng)出現(xiàn)過(guò)，因此為我們所熟悉。其算法描述如下： 第一步，預(yù)處理。刪去所有被包含矩形。 第二步，平面離散化。 第三步，統(tǒng)計(jì)所有被覆蓋離散平面格的總面積。然后，通過(guò)類比，我們順利地推出相應(yīng)的三維模型的求解方法：

9、第一步，預(yù)處理。刪去所有被包含立方體。 第二步，空間離散化。 第三步，統(tǒng)計(jì)所有被“覆蓋”離散立方格的總體積。該三維模型求解方案與二維模型求解方案大同小異，只是考慮到效率問(wèn)題，在統(tǒng)計(jì)的時(shí)候還需要做一些優(yōu)化工作。就這樣，通過(guò)運(yùn)用“降維”的思想，我們?cè)谙鄳?yīng)二維模型求解方案的啟示下，圓滿地完成了三維模型的求解。（附程序衛(wèi)星覆蓋cover.pas） 通過(guò)上面的例子可以看到，多維模型從低維模型中誕生，因而難免“遺傳”了低維模型的某些特征，使得我們有可能通過(guò)類比法直接套用低維模型的求解模式，來(lái)為較為復(fù)雜的多維問(wèn)題“接生”。ii.落到實(shí)處的“降維”法 從上述類比法中，我們看到，“降維”思想的整個(gè)運(yùn)用過(guò)程其實(shí)是

10、在我們的腦海中完成的，而程序的實(shí)際操作對(duì)象始終都是多維模型。因此，“降維”并沒(méi)有真正在我們的程序中體現(xiàn)，即沒(méi)有落到實(shí)處。 雖然有不少“多維化”競(jìng)賽題可以運(yùn)用類比法直接套用現(xiàn)成的低維求解模式，但是我們也應(yīng)該看到，這一招并不是時(shí)時(shí)處處都能夠左右逢源的。我們來(lái)看宇宙探險(xiǎn)一題（請(qǐng)參閱附錄五）。 該題的一維模型是上面已經(jīng)提到過(guò)的求一維數(shù)列中最大（元素和最大）連續(xù)子序列的問(wèn)題。但是，該一維模型的求解模式（一重循環(huán)法）并無(wú)法直接套用到三維空間來(lái)。對(duì)于此題，比較容易想到的就是窮舉法，但是其效率奇低。因?yàn)闉榱舜_定一個(gè)子長(zhǎng)方體，共需要6個(gè)變量，即長(zhǎng)方體的左下前角坐標(biāo)（a1,b1,c1），以及長(zhǎng)方體的右上后角坐標(biāo)（

11、a2,b2,c2）。因而需要六重循環(huán)。而即使不考慮這六重循環(huán)內(nèi)為統(tǒng)計(jì)該長(zhǎng)方體分值和而帶來(lái)的新的循環(huán)，算法的時(shí)間復(fù)雜度也已經(jīng)達(dá)到了N6（N=50）規(guī)模。這顯然是個(gè)龐大的數(shù)字。因此，這樣的算法是不可取的。 這里，我們可以采用一種落到實(shí)處的“降維”方法來(lái)解該題。具體的方法是：假設(shè)我們當(dāng)前所搜索的長(zhǎng)方體是自上往下第a1-a2層的，為了找出夾在a1-a2層之間分值最高的長(zhǎng)方體，即進(jìn)一步確定b1,b2,c1,c2，我們可以先將該a1-a2層從三維壓縮到二維的，然后再加以討論。如圖：現(xiàn)在我們已經(jīng)將問(wèn)題轉(zhuǎn)化為了一個(gè)二維模型如何在一張二維表內(nèi)找出一個(gè)分值最大的矩形。我們很容易發(fā)現(xiàn)，這個(gè)“最大”矩形還原到三維，就

12、是夾在a1-a2層間的“最大”長(zhǎng)方體。為了求解上述二維模型，我們可以用同樣的方法先確定b1,b2，然后將b1-b2層從二維壓縮到一維，然后，就可以運(yùn)用已知的一維模型求解模式進(jìn)行最終求解。如圖。 這樣，我們不僅在最后求解一維模型時(shí)，利用了現(xiàn)成的優(yōu)秀算法而節(jié)省了一重循環(huán)，從而將算法的時(shí)間復(fù)雜度降低到N5，更重要的是，我們可以利用“降維”過(guò)程減少重復(fù)的求和工作。當(dāng)我們已經(jīng)完成對(duì)a1-a2層的搜索，而著手進(jìn)行對(duì)a1-a2+1層壓縮時(shí)，我們可以把累加工作建立在已有的a1-a2層壓縮表上，即只需把a(bǔ)2+1層對(duì)應(yīng)地往a1-a2層壓縮表上累加。這樣，我們就有效地利用了已經(jīng)獲得的信息而避免了大量的重復(fù)計(jì)算；二維

13、到一維的壓縮過(guò)程類似。與窮舉法相比，該算法的統(tǒng)計(jì)工作是分散地進(jìn)行的，即分布在各層循環(huán)之間進(jìn)行，而非嵌套在最后一重循環(huán)內(nèi)部。這樣，就有效地控制了算法復(fù)雜度的急劇增長(zhǎng)趨勢(shì)。（附程序宇宙探險(xiǎn)explore.pas） 在此題的求解過(guò)程中，我們將“降維”過(guò)程物理地落實(shí)到了程序中去。這就是我們所說(shuō)的“落到實(shí)處”的降維。通過(guò)與窮舉法的對(duì)比，可以看到，這種“落到實(shí)處”的降維，不僅為思考分析問(wèn)題提供了清晰的思路，而且往往還能收到一些意想不到的奇妙效果。由于多維化題自身的多樣性，“降維”思想的運(yùn)用方式還有很多。關(guān)鍵是要針對(duì)每題的獨(dú)特性靈活運(yùn)用。由于篇幅關(guān)系，在此只介紹較為常見的兩種運(yùn)用方式，希望能起到拋磚引玉的作

14、用。 、“虛”的多維化(1) 定義在上述“實(shí)”的多維化中，“維”沿用了它的本義，即構(gòu)成“構(gòu)成空間的因素”。而在“虛”的多維化中，“維”的含義可以引申為廣義的“構(gòu)成數(shù)學(xué)模型的因素”。由此，“虛”的多維化的含義就是“構(gòu)成數(shù)學(xué)模型的因素”的增加。(2) 表現(xiàn)和策略區(qū)別于“實(shí)”的多維化，“虛”的多維化的是以增加階段參數(shù)或狀態(tài)參數(shù)等形式體現(xiàn)在我們的數(shù)學(xué)模型和程序當(dāng)中的。這既是“虛”的多維化的表現(xiàn)形式，也是相應(yīng)的解題策略。其中最為典型的就是動(dòng)態(tài)規(guī)劃模型的多維化。（圖論中的標(biāo)號(hào)法可以看成是動(dòng)態(tài)規(guī)劃的優(yōu)化，因此，這里把標(biāo)號(hào)法也歸入動(dòng)態(tài)規(guī)劃。） 我們知道，經(jīng)典的動(dòng)態(tài)規(guī)劃是由階段、狀態(tài)、決策三重循環(huán)構(gòu)成的。但是，

15、如今的動(dòng)態(tài)規(guī)劃，常常不再局限于這陳舊的三重循環(huán)模式，而是借助于階段、狀態(tài)變量的增加，將模型建筑到了多重循環(huán)之上。具有代表性的試題有第七屆IOI商店購(gòu)物、NOI97積木游戲以及IOI98中國(guó)隊(duì)組隊(duì)賽羅杰游戲等題。題目請(qǐng)參閱附錄六、七、八。為了說(shuō)明問(wèn)題，我們以羅杰游戲一題為例來(lái)具體看一看“虛”的多維化的表現(xiàn)形式。在看該題之前，我們首先來(lái)看一個(gè)熟悉的模型，以區(qū)別比較： 有一個(gè)A*B的二維表格，表中每一格都被賦予一個(gè)整數(shù)值-1或0-255?，F(xiàn)在，我們要從表中(x1,y1)格出發(fā)，走到(x2,y2)，途中不能經(jīng)過(guò)-1格。把沿途經(jīng)過(guò)的所有格中的數(shù)累加起來(lái)，稱為該路線的費(fèi)用。求所有可能路線的最小費(fèi)用。眾所周

16、知，該模型是一個(gè)經(jīng)典的動(dòng)態(tài)規(guī)劃模型。其動(dòng)態(tài)規(guī)劃方程可以表示為：現(xiàn)在，我們來(lái)看一下羅杰游戲一題是怎樣在上述模型的基礎(chǔ)上進(jìn)行“多維化”的。我們看到，同樣是從(x1,y1)格出發(fā)，走到(x2,y2)，與第一個(gè)模型相比，羅一題由于“羅杰”自身六個(gè)面上的數(shù)字位置不同而引進(jìn)了成千上萬(wàn)種不同狀態(tài)。因此，為了體現(xiàn)這些狀態(tài)間的區(qū)別，新的動(dòng)態(tài)規(guī)劃方程勢(shì)必要引入新的參量，即新的“維”：（附程序羅杰游戲roger.pas）、小結(jié)無(wú)論是“實(shí)”的多維化，還是“虛”的多維化，都著重考查了選手的思維素質(zhì)，和知識(shí)的引申、遷移能力。因此我們?cè)谄綍r(shí)的練習(xí)中，特別要注意聯(lián)想與比較，學(xué)會(huì)用發(fā)展的眼光來(lái)看信息學(xué)競(jìng)賽。不要滿足于對(duì)某個(gè)具體

17、問(wèn)題的練習(xí)，而要在解決該問(wèn)題后，注意引申和拓寬，去主動(dòng)地開展多維化，而不是被動(dòng)地應(yīng)付多維化。只有這樣，才能更上一層樓。（三）開放化1、 含義“開放”的本義是“打破禁令、封鎖、束縛”，在信息學(xué)競(jìng)賽中，我們將它引申為“打破原有的、經(jīng)典的模型的束縛”。如果說(shuō)上文所述的隱蔽化、多維化過(guò)程是建立在現(xiàn)有模型的基礎(chǔ)上的，那么開放化就是一個(gè)徹底的推陳出新，因?yàn)樗耆蚱屏诵畔W(xué)競(jìng)賽中數(shù)學(xué)模型的陳舊模式。、表現(xiàn) 競(jìng)賽中不斷涌現(xiàn)出來(lái)的開放化模型，往往給人以一種煥然一新的感覺；同時(shí)，也常常使得那些“有名有姓”的算法無(wú)用武之地。由于失去了經(jīng)典模型的借鑒，解題者往往難以找到入手點(diǎn)。這就充分地考驗(yàn)了選手們的創(chuàng)造力。它不但

18、要求我們能夠靈活運(yùn)用已知的模型來(lái)解各種題目，更要求我們?cè)谟龅匠搅私?jīng)典模型的能力范圍的新題時(shí)，學(xué)會(huì)創(chuàng)造性地分析新情況，解決新問(wèn)題。因此，它是一類頗具挑戰(zhàn)性的題目。比如說(shuō)IOI98中國(guó)隊(duì)組隊(duì)賽中電阻網(wǎng)絡(luò)一題，就是典型的一例。題目請(qǐng)參閱附錄九。這是一個(gè)來(lái)源于物理電學(xué)的題目。它出現(xiàn)在信息學(xué)競(jìng)賽中，從頭到尾都是嶄新的，沒(méi)有任何的經(jīng)驗(yàn)?zāi)Ｐ涂梢越梃b。如果說(shuō)該題有什么獨(dú)特的算法的話，那就是利用簡(jiǎn)單串并聯(lián)電路的幾個(gè)基本物理公式，按部就班地兩兩合并能夠合并的電阻，直至最后只剩下唯一的電阻，即外電路總電阻這是“順推”；然后，我們?cè)傺刂绊樛啤钡哪_步逐漸回溯，直到將該總電阻再擴(kuò)展回到原來(lái)的電阻網(wǎng)絡(luò)，并在回溯過(guò)程中沿

19、途求得所有電阻上的電流和電壓這是逆推。但是，要實(shí)現(xiàn)這“兩步曲”，并不是件容易的事。最大的障礙就是沒(méi)有專門用來(lái)描述電路的現(xiàn)成的數(shù)據(jù)結(jié)構(gòu)可以依賴。因此，此題的關(guān)鍵就在于如何利用有限的程序語(yǔ)言來(lái)儲(chǔ)存、表示以及操作這張縱橫交錯(cuò)的電阻網(wǎng)絡(luò)，才能既方便快捷又保證不產(chǎn)生歧義。而如何設(shè)計(jì)出一套漂亮的數(shù)據(jù)結(jié)構(gòu)模型，也為我們提供了發(fā)揮自己的創(chuàng)造與想象能力的廣闊天地。而考查選手們運(yùn)用知識(shí)的靈活程度和創(chuàng)造性思維，恐怕也正是該題命題者的意圖所在吧。、策略對(duì)癥下藥由于開放化所引進(jìn)的模型是千變?nèi)f化的，沒(méi)有什么固定的解題模式可尋，因此，只有隨機(jī)應(yīng)變，對(duì)癥下藥，才是解決這類題唯一通用的方法。（附程序電阻網(wǎng)絡(luò)resistor.pas）、小結(jié)