數學模型及其在信息學競賽中的應用

1、數學模型及其在信息學競賽中的應用數學模型及其在信息學競賽中的應用上海市復旦附中高三（8）班郭一【關鍵字】【關鍵字】數學模型，可靠性，可解性【引言】【引言】數學模型是人們解決現實問題的有力武器。人們把現實問題經過科學地抽象、提煉得到數學模型，再用數學方法去解決。數學模型可分為離散和連續(xù)兩種。連續(xù)數學模型需要大量的高等數學知識，中學生很少接觸。在信息學競賽經常出現的則是離散數學模型。本文主要介紹的就是離散數學模型的一般概念及建立方法。【正文

2、】【正文】所謂數學模型，就是現實世界中某一類特殊的運動變化過程、關系或結構的一種模擬性的數學結構，其實也就是對現實模型進行科學抽象后得到的模型。在信息學競賽中，試題給出的問題通常是一個現實問題，這也就需要選手在審清題意后首先把問題的關鍵因素總結、提煉出來，形成一個抽象的數學模型，這樣有利于問題的分析與解決。一般來說，我們在解一道有關現實問題的試題時，需要分以下幾個步驟：１審清題意審清題意，了解題目的來龍去脈，弄清哪些量是已知的（輸入），

3、需要求什么（輸出），數據規(guī)模如何等等。這是解決問題的前提。２建立模型建立模型，使之能夠簡潔高效地表達出題目給出的現實模型。３解決模型解決模型，得出算法。建模之后就是要解決模型。這步順利與否很大部分上取決于所建模型的可解性如何。４編程實現編程實現。其中，２、３兩步是關鍵。模型建立與解決得好與壞對能否成功解決該題起著決定性的作用。（一）對于同一個現實問題，可能可以建立不同的數學模型這種現象十分普遍，也就是平時所說的一題多解。既然如此，這里有

4、必要討論一下數學模型的選擇問題，其實也就是評判一個模型好壞標準的問題。一個好的數學模型不僅要能夠準確地反映出現實模型（可靠性），所建立的模型還必須能夠被有效地解決（可解性）。這里“有效”指的是解決它的算法所需的空間與時間都在可以承受的范圍之內。通常在解一些要求最優(yōu)解或要求準確計數的一類具有唯一正確解的試題時，我們一般在保證可靠性的前提下，盡量提高模型的可解性。若幾個模型都具有可靠性，則當然可解性越強的模型越好。至此，本題的數學模型已經建

5、立，試題給出的限制條件已體現在數學模型中，因此由此模型得出的解是可行的。我們求從1到n’的最大費用最大流。若得到的最大流量不是2，則無解（即不可能從西飛到東再飛回來），否則我們設得到的最大費用為C。因為有兩條路線，所以每個未被訪問的城市在費用中的貢獻為2，被訪問的城市的貢獻為3。考慮到最西最東兩個城市的貢獻是2而不是3，旅行路線中訪問城市數=C22N。因為C最大，所以訪問城市數也一定最多，即方案最佳，模型具有可靠性。因為這是一個最大費用

6、最大流的問題，我們可以使用FdFulkerson算法去解。這個模型與搜索相比，可解性大大提高，時間復雜度從指數級降低到了多項式級（大約為O（N^3））。但我們還是覺得這個模型不夠簡潔，抽象程度還是不夠。【動態(tài)規(guī)則模型】設f[ij]為從頂點1出發(fā)的兩條不相交的路線分別到達頂點i與頂點j時，兩路線的所需乘航線之和的最大值。有兩種情況，若ij，或i=j=n時，我們考慮i的前趨頂點，不妨設為k。此時，到達頂點k與j的兩條路線的所需乘航線之和也一

7、定最大，否則與f[ij]最大矛盾。若ij時，結論同理可得。由此，我們有如下的動態(tài)規(guī)則方程：?????????????????????????)(1)(1][0]11[)()(jikifMinnjijijkfMinjiffEjkjkEikik且且或f[ii]無意義(1in）實際最多可能的訪問城市數為f[nn]2。時間復雜度降為O（N^2）。對于最佳旅行路線這一個問題，我們建立了三種不同的數學模型。這三種模型都具有可靠性（可以得出最優(yōu)解），

8、但可解性不同。一般來說，建立的模型越簡潔，抽象程度越高，算法實現時不必要的操作也越少，運行效率也就越高。值得注意的是，最近的一些競賽中有時會出現根據解的近似程度給分的題目。對于這類題目，我們更多考慮的則是所建模型的可解性。當然，可靠性的降低也是有限度的，這個限度就是方案的可行性及誤差允許范圍。此外，許多數學模型有近似解法，這些都是通過適當犧牲模型自身可靠性來提高模型的可解性。（二）一個模型可能同時適用于多個現實問題。這也就是我們要研究數