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

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

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

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

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

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

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

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

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