數(shù)學建模在計算機專業(yè)的應(yīng)用

..應(yīng)用一圖論算法圖論在計算機處理問題中占有重要地位,現(xiàn)實中的很多問題最終都可以轉(zhuǎn)化成圖論問題,或者要借助圖結(jié)構(gòu)來存儲和處理。但是怎么把一張圖存入計算機就要涉及到數(shù)學建模的知識。比如下面一張圖：如果要求出從節(jié)點v1到節(jié)點v5的所有路徑,就可以借助計算機來很輕松的解決。但前提條件是,必須要把圖以一種計算機可以理解的形式存進去,即要把它抽象為數(shù)學問題。在此,我們需要定義一些關(guān)于圖的概念,以便更好的描述問題。邊與頂點的關(guān)系有如下幾種典型情況：簡單圖：無自回環(huán),無重邊的圖。無向圖：邊沒有指向,此時稱邊與頂點關(guān)聯(lián),稱頂點與頂點鄰接。有向圖:邊有指向,下面是具體涉及到圖如何存儲的問題：圖G<V,E>的關(guān)聯(lián)矩陣,若G<V,E>為無向圖,若G<V,E>為有向圖,因此該圖可以用關(guān)聯(lián)矩陣表示出來,如下所示這樣,我們就可以以矩陣的形式將圖存入計算機鄰接矩陣圖G<V,E>的鄰接矩陣,若G<V,E>為無向圖,=從到的邊數(shù),若不鄰接,取0；若G<V,E>為有向圖,=從到的有向邊數(shù),若無,取0.應(yīng)用二動態(tài)規(guī)劃問題動態(tài)規(guī)劃是運籌學的一個分支,是求解決策過程最優(yōu)化的數(shù)學方法。20世紀50年代初美國數(shù)學家R.E.Bellman等人在研究多階段決策過程的優(yōu)化問題時,提出了著名的最優(yōu)化原理,把多階段過程轉(zhuǎn)化為一系列單階段問題,利用各階段之間的關(guān)系,逐個求解,創(chuàng)立了解決這類過程優(yōu)化問題的新方法——動態(tài)規(guī)劃。也是信息學競賽中選手必須熟練掌握的一種算法。多階段決策過程的最優(yōu)化問題。含有遞推的思想以及各種數(shù)學原理〔加法原理,乘法原理等等。動態(tài)規(guī)劃一般可分為線性動規(guī),區(qū)域動規(guī),樹形動規(guī),背包動規(guī)四類。舉例線性動規(guī)：攔截導彈,合唱隊形,挖地雷,建學校,劍客決斗等；區(qū)域動規(guī)：石子合并,加分二叉樹,統(tǒng)計單詞個數(shù),炮兵布陣等；樹形動規(guī)：貪吃的九頭龍,二分查找樹,聚會的歡樂,數(shù)字三角形等；背包問題：01背包問題,完全背包問題,分組背包問題,二維背包,裝箱問題,擠牛奶。多階段決策的實際問題很多,下面通過具體例子,說明什么是動態(tài)規(guī)劃模型中數(shù)學建模知識的運用。最短路線問題：某工廠需要把一批貨物從城市A運到城市E,中間可經(jīng)過B1、B2、B3、C1、C2、C3、D1、D2等城市,各城市之間的交通線和距離如下圖所示,問應(yīng)該選擇一條什么路線,使得從A到E的距離最短？C1BC1B13D18D1AB2564AB2EC298EC272D36D3671C3BC3B37下面引進幾個動態(tài)規(guī)劃的基本概念和相關(guān)符號。<1>階段<Stage>把所給問題的過程,按時間和空間特征劃分成若干個相互聯(lián)系的階段,以便按次序去求每個階段的解,階段總數(shù)一般用字母n表示,用字母k表示階段變量。如例中<最短路線問題>可看作是n=4階段的動態(tài)規(guī)劃問題,k=2表示處于第二階段。<2>狀態(tài)<State>狀態(tài)表示每個階段開始時系統(tǒng)所處的自然狀況或客觀條件,它描述了研究問題過程狀況。描述各階段狀態(tài)的變量稱為狀態(tài)變量,常用字母sk表示第k階段的狀態(tài)變量,狀態(tài)變量的取值范圍稱為狀態(tài)集,用Sk表示。如例l中,第一階段的狀態(tài)為A〔即出發(fā)位置。第二階段有三個狀態(tài)：B1、B2、B3,狀態(tài)變量s2=B2表示第2階段系統(tǒng)所處的位置是B2。第2階段的狀態(tài)集S2={B1、B2、B3}。動態(tài)規(guī)劃中的狀態(tài)變量應(yīng)具有如下性質(zhì)：當某階段狀態(tài)給定以后,在這個階段以后過程的發(fā)展不受這個階段以前各個階段狀態(tài)的影響。也就是說,未來系統(tǒng)所處的狀態(tài)只與系統(tǒng)當前所處的狀態(tài)有關(guān),而與系統(tǒng)過去所處的狀態(tài)無關(guān),即過去歷史只能通過當前的狀態(tài)去影響它未來的發(fā)展,這種特點稱為無后效性〔又稱馬爾可夫性。如果所選定的狀態(tài)變量不具備無后效性,就不能作為狀態(tài)變量來構(gòu)造動態(tài)規(guī)劃模型。如例1中,當某階段的初始狀態(tài)即所在的城市選定以后,從這個狀態(tài)以后的運貨路線只與這個城市有關(guān),不受以前的運貨路線影響,所以是滿足狀態(tài)的無后效性的?！?決策<Decision>當系統(tǒng)在某階段處于某種狀態(tài),可以采取的行動〔或決定、選擇,從而確定下一階段系統(tǒng)將到達的狀態(tài),稱這種行動為決策。描述決策的變量,稱為決策變量。常用字母uk<sk>表示第k階段系統(tǒng)處于狀態(tài)sk時的決策變量。決策變量的取值范圍稱為決策集,用Dk<sk>表示。在例l的第二階段中,若從狀態(tài)B2出發(fā),可以做出三種不同的決策,其允許的決策集為D2<B2>={C1、C2、C3},決策u2<B2>=C2表示第二階段處于狀態(tài)B2,選擇的確行動下一階段是走到C2?！?策略<Policy>系統(tǒng)從第k階段的狀態(tài)sk開始由每階段的決策按順序組成的決策序列{uk<sk>,uk+1<sk+1>,…,un<sn>}稱為一個策略〔k=1,2,…,n,記作。在例l中,p2,4<B2>={u2<B2>=C2,u3<C2>=D1,u4<D1>=E}是一個策略,表示第二階段從狀態(tài)B2出發(fā),沿著B2→C2→D1→E的方向走到終點。注意策略必須是一串實際可行的序列行動?！?狀態(tài)轉(zhuǎn)移方程系統(tǒng)由這一階段的—個狀態(tài)進行決策后轉(zhuǎn)變到下—階段的另—個狀態(tài)稱為狀態(tài)轉(zhuǎn)移,狀態(tài)轉(zhuǎn)移既與狀態(tài)有關(guān),又與決策有關(guān),描述狀態(tài)轉(zhuǎn)移關(guān)系的方程稱為狀態(tài)轉(zhuǎn)移方程,記為：sk+1=Tk<sk,uk>它的實際意義是當系統(tǒng)第k階段處于狀態(tài)sk做決策uk時,第k+1階段系統(tǒng)轉(zhuǎn)移到狀態(tài)sk+1。狀態(tài)轉(zhuǎn)移方程在不同的問題中有不同的具體表現(xiàn)形式,在例l中,狀態(tài)轉(zhuǎn)移方程表示為：sk+1=uk<sk>。〔6階段指標階段效益是衡量系統(tǒng)階段決策結(jié)果的一種數(shù)量指標,記為：表示系統(tǒng)在第k階段處于狀態(tài)sk做出決策uk時所獲得的階段效益。這里的階段效益在不同的實際問題中有不同的意義。在例l中它表示兩個中轉(zhuǎn)站的距離,如表示從中轉(zhuǎn)站B2走到中轉(zhuǎn)站C2之間的距離為7。更一般地有?！?指標函數(shù)指標函數(shù)是用來街量所實現(xiàn)過程的優(yōu)劣的一種數(shù)量指標,它是一個定義在全過程和所有后部子過程上的確定的數(shù)量函數(shù),記為：它應(yīng)具有可分離性,并滿足遞推關(guān)系式：常見的指標函數(shù)的形式是：1過程和任一子過程的指標是它所包含的各階段指標的和。既2過程和任一子過程的指標是它所包含的各階段指標的積。既〔8最優(yōu)值函數(shù)指標函數(shù)的最優(yōu)值,稱為最優(yōu)值函數(shù),記為。它表示系統(tǒng)在第k階段處于狀態(tài)sk時按最優(yōu)策略行動所獲得總的效益。既其中opt是最優(yōu)化〔optimization的縮寫,根據(jù)實際問題可取max<最大值>和min<最小值>,表示對所有允許策略使后面算式取最優(yōu)。下面利用動態(tài)規(guī)劃的逆推歸納法,將例1從最后一個城市E逐步推算到第一個城市A,在此表示第k階段從城市sk到城市E最短路。1>當k=4時：要求,由于第4階段只有兩個城市D1、D2〔即s4的取值為D1、D2,從D1到E只有一條路,故,同理。2>當k=3時：s3的取值為C1、C2、C3,從C1出發(fā)到E有兩條路,一條是經(jīng)過D1到E,另一條是經(jīng)過D2到E,顯然：即從C1出發(fā)到E的最短路為7,相應(yīng)決策為,最短路線是C1→D1→E。同理2>當k=2時：s2的取值為