數(shù)學(xué)模型及其在信息學(xué)競賽中的應(yīng)用論文

1、數(shù)學(xué)模型及其在信息學(xué)競賽中的應(yīng)用數(shù)學(xué)模型及其在信息學(xué)競賽中的應(yīng)用【關(guān)鍵字】【關(guān)鍵字】數(shù)學(xué)模型，可靠性，可解性【引言】【引言】數(shù)學(xué)模型是人們解決現(xiàn)實問題的有力武器。人們把現(xiàn)實問題經(jīng)過科學(xué)地抽象、提煉得到數(shù)學(xué)模型，再用數(shù)學(xué)方法去解決。數(shù)學(xué)模型可分為離散和連續(xù)兩種。連續(xù)數(shù)學(xué)模型需要大量的高等數(shù)學(xué)知識，中學(xué)生很少接觸。在信息學(xué)競賽經(jīng)常出現(xiàn)的則是離散數(shù)學(xué)模型。本文主要介紹的就是離散數(shù)學(xué)模型的一般概念及建立方法?！菊摹俊菊摹克^數(shù)學(xué)模型，就是現(xiàn)

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

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

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

5、數(shù)學(xué)模型中，因此由此模型得出的解是可行的。我們求從1到n’的最大費用最大流。若得到的最大流量不是2，則無解（即不可能從西飛到東再飛回來），否則我們設(shè)得到的最大費用為C。因為有兩條路線，所以每個未被訪問的城市在費用中的貢獻為2，被訪問的城市的貢獻為3?？紤]到最西最東兩個城市的貢獻是2而不是3，旅行路線中訪問城市數(shù)=C22N。因為C最大，所以訪問城市數(shù)也一定最多，即方案最佳，模型具有可靠性。因為這是一個最大費用最大流的問題，我們可以使用Fd

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

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

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