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