運(yùn)籌學(xué)最短路徑范文

導(dǎo)語：如何才能寫好一篇運(yùn)籌學(xué)最短路徑，這就需要搜集整理更多的資料和文獻(xiàn)，歡迎閱讀由公務(wù)員之家整理的十篇范文，供你借鑒。

篇1

［關(guān)鍵詞］動(dòng)態(tài)規(guī)劃；最優(yōu)性原理；無記憶性；記憶性

在運(yùn)籌學(xué)的分支體系中，動(dòng)態(tài)規(guī)劃因其應(yīng)用的廣泛性而占有十分重要的地位。但動(dòng)態(tài)規(guī)劃僅僅是解決某類特殊的多階段決策問題的一種方法，不具有統(tǒng)一的數(shù)學(xué)模型和算法步驟[1]，而且概念多，因此學(xué)生普遍反應(yīng)“動(dòng)態(tài)規(guī)劃真的有用但確實(shí)難學(xué)”。本文以最短路問題為案例，對(duì)動(dòng)態(tài)規(guī)劃相關(guān)概念、最優(yōu)性原理、無記憶性等進(jìn)行了闡釋。

一、案例的選擇

可用動(dòng)態(tài)規(guī)劃求解的問題很多，如最短路、資源分配、生產(chǎn)與存儲(chǔ)等，而最短路問題因其空間特征明顯，易于劃分階段、易于描述每階段開始和結(jié)束時(shí)的狀態(tài)，以及在每個(gè)狀態(tài)之下做出的決策、每次決策產(chǎn)生的決策指標(biāo)值等，因此，對(duì)初學(xué)者而言，最易接受和理解的例子還是最短路問題。本文以最短路問題作為引例，幫助學(xué)生們理解和掌握動(dòng)態(tài)規(guī)劃的相關(guān)概念及基本方程、最優(yōu)性原理等。

二、相關(guān)概念的解釋

動(dòng)態(tài)規(guī)劃相關(guān)概念繁多，從階段、狀態(tài)開始，到過程指標(biāo)函數(shù)，剛接觸時(shí)，不少學(xué)生感到一頭霧水，十分茫然。而借助于最短路問題，將動(dòng)態(tài)規(guī)劃的相關(guān)概念與最短路問題中大家耳熟能詳?shù)拿Q相對(duì)應(yīng)，則十分有助于學(xué)生對(duì)動(dòng)態(tài)規(guī)劃基本概念的把握。

三、最優(yōu)性原理的解釋教材[1]

對(duì)最優(yōu)性原理作了如下表述：無論過去的決策和狀態(tài)如何，對(duì)前面的決策所形成的當(dāng)前狀態(tài)而言，余下的決策序列必須構(gòu)成最優(yōu)策略，即最優(yōu)策略的子策略總是最優(yōu)的。

四、無記憶性與記憶性

在動(dòng)態(tài)規(guī)劃一章中，教師經(jīng)常會(huì)提到“無記憶性”與“記憶性”兩個(gè)看似完全矛盾的概念，不少學(xué)生也感到十分茫然。其實(shí)，這兩個(gè)概念在動(dòng)態(tài)規(guī)劃中得到了完美的統(tǒng)一。“無記憶性”指的是可用動(dòng)態(tài)規(guī)劃方法求解的多階段決策問題，在劃分階段時(shí)，狀態(tài)必須滿足的一個(gè)特性，也稱為無后效性或馬爾科夫性。其實(shí)質(zhì)是：某階段的狀態(tài)一旦確定，則此后過程的演變不再受此前各狀態(tài)及決策的影響。即“未來與過去無關(guān)”，當(dāng)前的狀態(tài)是此前歷史的一個(gè)完整總結(jié)，此前的歷史只能通過當(dāng)前的狀態(tài)去影響過程未來的演變。[1]“記性性”指的是用動(dòng)態(tài)規(guī)劃方法求解多階段決策問題時(shí)（以逆序?yàn)槔瑸榍蟮玫贙步最優(yōu)子策略fk（Sk），必須先計(jì)算出從第K＋1階段的各狀態(tài)出發(fā)所對(duì)應(yīng)的最優(yōu)子策略fk＋1（Sk＋1），并由第K＋1步的最優(yōu)子策略fk＋1（Sk＋1）去求取第K步最優(yōu)子策略fk（Sk）。這些后續(xù)狀態(tài)對(duì)應(yīng)的最優(yōu)子策略實(shí)際上構(gòu)成了一張查找表（LookupTable）。[3]為更好地理解無記憶性與記憶性，仍以最短路問題為例進(jìn)行說明。假設(shè)有一個(gè)可分為10個(gè)階段的最短路問題，每階段有10個(gè)狀態(tài)可供選擇。“無記憶性”指的是當(dāng)游客在第k階段處于狀態(tài)Sk時(shí)，則該游客從Sk出發(fā)到終點(diǎn)的最短路徑（K步最優(yōu)子策略）只與Sk相關(guān)，而與Sk之前的狀態(tài)、決策無任何關(guān)系。“記憶性”指的是當(dāng)用動(dòng)態(tài)規(guī)劃方法求解最短路問題時(shí)，第K步最優(yōu)子策略是由第K步的決策和第K＋1步的最優(yōu)子策略共同決定的，而第K＋1步的最優(yōu)子策略已在之前求出并存放于內(nèi)存之中，這就是記憶性。動(dòng)態(tài)規(guī)劃的記憶性可節(jié)省大量的計(jì)算時(shí)間，但會(huì)占用較多的計(jì)算機(jī)內(nèi)存，即常用的“空間換時(shí)間”策略。以上題為例，10個(gè)階段每階段10個(gè)狀態(tài)的最短路問題，如果采用窮舉法，則需要計(jì)算的路徑條數(shù)（相當(dāng)于動(dòng)態(tài)規(guī)劃中的全策略）為109條，每條路徑需要進(jìn)行10次加法運(yùn)算；在109條路徑中找出最短路徑需要進(jìn)行109－1次比較運(yùn)算，則總的基本運(yùn)算是11＊109－1次。而采用動(dòng)態(tài)規(guī)劃方法時(shí)，每階段的每個(gè)狀態(tài)需要進(jìn)行10次加法運(yùn)算和9次比較運(yùn)算，則總的基本運(yùn)算次數(shù)為1539次（其中加法運(yùn)算810次，比較運(yùn)算729次），和窮舉法比較可節(jié)省大量的計(jì)算時(shí)間。從該例題的分析可知，一個(gè)多階段決策問題之所以可采用有“記憶性”的動(dòng)態(tài)規(guī)劃方法求解，恰恰是因?yàn)樵搯栴}在劃分階段時(shí)，各階段的自然特征（即狀態(tài)）滿足“無記憶性”。因此，我們說，“記憶性”與“無記憶性”在動(dòng)態(tài)規(guī)劃中得到了完美的統(tǒng)一。

五、結(jié)束語

經(jīng)教學(xué)實(shí)踐證明，在動(dòng)態(tài)規(guī)劃教學(xué)中以最短路為引例，有利于學(xué)生對(duì)動(dòng)態(tài)規(guī)劃相關(guān)概念的理解，尤其有利于學(xué)生掌握最優(yōu)性原理和無記憶性、記憶性這些晦澀難懂的原理與性質(zhì)，為學(xué)生學(xué)好、用好動(dòng)態(tài)規(guī)劃打下了良好基礎(chǔ)。

［參考文獻(xiàn)］

［1］胡運(yùn)權(quán).運(yùn)籌學(xué)教程（第四版）［M］．北京：清華大學(xué)出版社，2012：191-232．

［2］［M］．普林斯頓大學(xué)出版社，1957：58-92．

［3］北京：人民郵電出版社，2008：744-754．

［4］《運(yùn)籌學(xué)》教材編寫組.運(yùn)籌學(xué)（第三版）［M］．北京：清華大學(xué)出版社，2005：194-215．

篇2

關(guān)鍵詞：最短路徑，Dijkstra算法，優(yōu)化

 

最短路徑問題是指在一個(gè)非負(fù)權(quán)值圖中找出兩個(gè)指定節(jié)點(diǎn)間的一條權(quán)值和最小的路徑，是一類受到普遍重視和研究的網(wǎng)絡(luò)優(yōu)化問題，廣泛應(yīng)用于計(jì)算機(jī)科學(xué)、交通工程、通信工程、運(yùn)籌學(xué)等眾多領(lǐng)域。實(shí)際生活中的許多問題都可歸結(jié)為最短路徑問題。郵政自動(dòng)分揀機(jī)、計(jì)算機(jī)網(wǎng)絡(luò)結(jié)點(diǎn)上的路由選擇、人工智能游戲設(shè)計(jì)、交通咨詢系統(tǒng)等都是最短路徑問題的現(xiàn)實(shí)應(yīng)用。由于帶權(quán)圖中權(quán)值所代表的意義不同，最短路徑也不僅僅局限于地理意義上的距離最短，還可以引申為最少費(fèi)用、最短時(shí)間、延時(shí)最短、吞吐量最大等[4]。

Dijkstra算法是典型的最短路徑算法，用于計(jì)算一個(gè)結(jié)點(diǎn)到其他所有結(jié)點(diǎn)的最短路徑。。主要特點(diǎn)是以起始點(diǎn)為中心向外層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。Dijkstra算法的基本思想是以源點(diǎn)為圓心，按最短路徑長度遞增的順序通過對(duì)路徑長度迭代得到從源點(diǎn)到其他各目標(biāo)結(jié)點(diǎn)的最短路徑。

1 Dijkstra算法原理

Dijkstra(迪杰斯特拉)算法是典型的單源最短路徑算法，用于計(jì)算非負(fù)權(quán)值圖中一個(gè)結(jié)點(diǎn)到其他所有結(jié)點(diǎn)的最短路徑，是一個(gè)非常經(jīng)典的貪心算法例子。。基本思想是：把帶權(quán)圖中所有結(jié)點(diǎn)分成兩組，第1組包括已確定最短路徑的結(jié)點(diǎn)，第2組為未確定最短路徑的結(jié)點(diǎn)。按最短路徑長度遞增的順序逐個(gè)把第2組的結(jié)點(diǎn)加入第1組中，直到從源點(diǎn)出發(fā)可到達(dá)的所有結(jié)點(diǎn)都包含在第1組中[2]。

2 Dijkstra算法描述

根據(jù)Dijkstra算法的基本思想，引入如下狀態(tài)變量：

1）輔助向量D，可用數(shù)組實(shí)現(xiàn)，其每一個(gè)分量D[i]用來存放源點(diǎn)到其他結(jié)點(diǎn)的最短路徑長度；

2）集合V和S，其中V集合用來存放未確定最短路徑的結(jié)點(diǎn)，S集合用來存放已確定最短路徑的結(jié)點(diǎn)。S的初始狀態(tài)為空集，V則包含帶權(quán)圖中的所有結(jié)點(diǎn)。

3）輔助變量path_matrix，可用二維數(shù)組實(shí)現(xiàn)，用來記錄源點(diǎn)到其他各個(gè)結(jié)點(diǎn)的最短路徑所經(jīng)過的頂點(diǎn)。

由于Dijkstra算法是按照最短路徑長度遞增的順序逐個(gè)確定源點(diǎn)到各個(gè)結(jié)點(diǎn)的最短路徑的，所以源點(diǎn)到各結(jié)點(diǎn)的最短路徑或者是源點(diǎn)到此結(jié)點(diǎn)的弧，或者是中間只經(jīng)過已確定了最短路徑的頂點(diǎn)（即S集合中的結(jié)點(diǎn)）而最終到達(dá)此結(jié)點(diǎn)的路徑。

根據(jù)以上分析，得到如下的算法描述[1]：

1）初始化集合V、S，同時(shí)利用帶權(quán)圖的鄰接矩陣arcs初始化數(shù)組D，即若源點(diǎn)到相應(yīng)結(jié)點(diǎn)有弧，對(duì)應(yīng)的分量取值為弧上的權(quán)值，否則對(duì)應(yīng)的分量取值為∞；

2）選擇D中最小的數(shù)組分量，假設(shè)為D[i]，則i就是已求得源點(diǎn)到其最短路徑的終點(diǎn)，故將S=S∪{i},即將已確定最短路徑的結(jié)點(diǎn)i加入S集合；

3）根據(jù)結(jié)點(diǎn)i修改更新數(shù)組D中源點(diǎn)到集合V-S中的結(jié)點(diǎn)k所對(duì)應(yīng)的分量，即若D[i]+arcs[i][k]<D[k]，則D[k]=D[i]+arcs[i][k]；

4）重復(fù)2）、3）操作，直至所有的結(jié)點(diǎn)確定最短路徑，即集合V為空。

對(duì)下圖G施行Dijkstra算法，假設(shè)源點(diǎn)V1，求解V1到其他各個(gè)結(jié)點(diǎn)的最短路徑。

圖G

假設(shè)源點(diǎn)為v1，則第一個(gè)選擇的頂點(diǎn)是v1，路徑長是0，D[]={0，50，10，∞，16}；

Step1 S={v1}，V={v2，v3，v4，v5}，S點(diǎn)集擴(kuò)充，v3為下一個(gè)最短路徑頂點(diǎn)，路徑長為10，D[]={0，50，10，25，16}；

Step2 S={v1，v3}，V={v2，v4，v5}，S點(diǎn)集擴(kuò)充，v5為下一個(gè)最短路徑頂點(diǎn)，路徑長為16，D[]={0，50，10，21，16}；

Step3 S={v1，v3，v5}，V={v2，v4}，S點(diǎn)集擴(kuò)充，v4為下一個(gè)最短路徑頂點(diǎn)，路徑長為21，D[]={0，41，10，21，16}；

Step4 S={v1，v3，v4，v5}，V={v2}，S點(diǎn)集擴(kuò)充，v2為下一個(gè)最短路徑頂點(diǎn)，路徑長為41，D[]={0，41，10，21，16}；

Step5 S={v1，v2，v3，v4，v5}，V={}，V點(diǎn)集為空，結(jié)束算法。至此，得到從源點(diǎn)到其他各個(gè)結(jié)點(diǎn)的最短路徑。

3 Dijkstra算法優(yōu)化策略分析

Dijkstra算法是計(jì)算最短路徑的經(jīng)典算法,但在實(shí)際使用過程中，該算法耗費(fèi)大量的計(jì)算時(shí)間和存儲(chǔ)空間，在某些實(shí)際應(yīng)用中產(chǎn)生冗余。所以需要進(jìn)行優(yōu)化。在評(píng)判一個(gè)算法優(yōu)劣時(shí)，通常研究該算法的時(shí)間復(fù)雜度和空間復(fù)雜度。可見，可以從影響Dijkstra算法效率的關(guān)鍵“存儲(chǔ)空間和時(shí)間效率”進(jìn)行優(yōu)化。

3.1 權(quán)值排序優(yōu)化策略

問題：S集合中未確定最短路徑的頂點(diǎn)無序存放在數(shù)組中，每一次選擇權(quán)值最小的弧段必須將所有未選擇頂點(diǎn)對(duì)應(yīng)的數(shù)組元素完全掃描才能找到，在數(shù)據(jù)量較大的情況下，計(jì)算速度受到嚴(yán)重制約。

優(yōu)化策略：將要掃描的結(jié)點(diǎn)按其對(duì)應(yīng)弧的權(quán)值進(jìn)行順序排列，每循環(huán)一次即可得到符合條件的結(jié)點(diǎn)，大大提高了算法的執(zhí)行效率[5]。

3.2 A*算法優(yōu)化策略

問題：Dijkstra算法基于廣度優(yōu)先搜索策略，即從源點(diǎn)出發(fā)，通過權(quán)值迭代遍歷所有其他結(jié)點(diǎn)后，最后得到從源點(diǎn)到其他各結(jié)點(diǎn)的最短路徑。整個(gè)搜索好似一個(gè)圓形向外展開，直到到達(dá)目的地，這樣的搜索方式是盲目的。很明顯這樣求解一定能找到最優(yōu)解，但節(jié)點(diǎn)展開的數(shù)量和距離成級(jí)數(shù)增加，會(huì)導(dǎo)致大量無效點(diǎn)的搜索，大大的降低搜索的效率。

優(yōu)化策略：采用改進(jìn)的Dijkstra算法——A*算法。A*算法是人工智能運(yùn)用在游戲中的一個(gè)重要實(shí)踐,它主要是解決路徑搜索問題。A*算法實(shí)際是一種啟發(fā)式搜索。。所謂啟發(fā)式搜索，就是利用一個(gè)估價(jià)函數(shù)judge（）評(píng)估每次決策的價(jià)值，決定先嘗試哪一種方案。這樣可以極大地優(yōu)化普通的廣度優(yōu)先搜索。從Dijkstra算法到A*算法是判斷準(zhǔn)則的引入，如果這個(gè)判斷條件不成立，同樣地，只能采用Dijkstra算法。所以A*算法中的估價(jià)函數(shù)是至關(guān)重要[3]。

3.3 扇形優(yōu)化策略

問題：Dijkstra算法的搜索過程好似以源點(diǎn)為圓心的一系列同心圓向外展開，搜索過程中沒有考慮到終點(diǎn)所在方向或位置，搜索是盲目的。這樣導(dǎo)致大量的無用臨時(shí)結(jié)點(diǎn)被反復(fù)搜索，成為實(shí)際應(yīng)用中的瓶頸。

優(yōu)化策略：從盡量減少最短路徑分析過程中搜索的臨時(shí)結(jié)點(diǎn)數(shù)量，限制范圍搜索和限定方向搜索考慮進(jìn)行優(yōu)化。那么這種有損算法是否可行呢？我們知道，現(xiàn)實(shí)生活中行進(jìn)，不會(huì)向著目的地的相反方向行進(jìn)，否則就是南轅北轍。所以，當(dāng)所研究的網(wǎng)絡(luò)可以抽象化為平面網(wǎng)絡(luò)的條件下，也不必搜索全部結(jié)點(diǎn)，可以在以源點(diǎn)到終點(diǎn)所在直線為軸線的扇形區(qū)域內(nèi)搜索最短路徑。這樣，搜索方向明顯地趨向終點(diǎn)，提高了搜索速度，雖然拋棄了部分結(jié)點(diǎn)，但基本上不影響搜索的成功率[5]。

3.4 鄰接點(diǎn)優(yōu)化策略

問題：Dijkstra算法在提取最短路徑結(jié)點(diǎn)時(shí)需要訪問所有的未確定最短路徑的結(jié)點(diǎn)，算法的時(shí)間復(fù)雜度為O（n2），如果只希望找到從源點(diǎn)到某一特定的終點(diǎn)的最短路徑也不例外。結(jié)點(diǎn)數(shù)n越大，算法的計(jì)算效率和存儲(chǔ)效率越低。

優(yōu)化策略：只對(duì)最短路徑上結(jié)點(diǎn)的鄰接點(diǎn)作處理，不涉及其他結(jié)點(diǎn)。即（1）只從源點(diǎn)的鄰接點(diǎn)集合中選擇權(quán)值最小的結(jié)點(diǎn)作為轉(zhuǎn)接點(diǎn)，將此轉(zhuǎn)接點(diǎn)加入已確定最短路徑的結(jié)點(diǎn)集合S中；（2）對(duì)此轉(zhuǎn)接點(diǎn)的鄰接點(diǎn)集合與S的差集中的結(jié)點(diǎn)的權(quán)值進(jìn)行更新；（3）從S中所有結(jié)點(diǎn)的鄰接點(diǎn)集合的并集與S的差集中選擇權(quán)值最小的結(jié)點(diǎn)作為下一個(gè)轉(zhuǎn)接點(diǎn)，并將此轉(zhuǎn)接點(diǎn)加入S中。重復(fù)（2），（3）操作，直至所有的結(jié)點(diǎn)確定最短路徑。優(yōu)化算法在更新最短路徑值與選擇最短路徑值最小的結(jié)點(diǎn)時(shí)，僅僅涉及相關(guān)結(jié)點(diǎn)的鄰接點(diǎn)集合及S集合中所有結(jié)點(diǎn)的鄰接點(diǎn)集合與S集合的差集，時(shí)間復(fù)雜度取決于轉(zhuǎn)接點(diǎn)的鄰接點(diǎn)的數(shù)量多少，減少了計(jì)算次數(shù)與比較次數(shù)[4]。

4 總結(jié)

在詳細(xì)分析求解最短路徑問題的經(jīng)典算法Dijkstra算法的基礎(chǔ)上，針對(duì)Dijkstra算法存在的問題介紹了幾種優(yōu)化策略。Dijkstra算法在不同的現(xiàn)實(shí)應(yīng)用中，可以具體情況具體分析，從而得到算法的高效率實(shí)現(xiàn)。

參考文獻(xiàn)：

[1] 嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)（C語言版）[M]. 北京：清華大學(xué)出版社，1997，186～190.

[2] 謝柏青，佘曉歌. 算法與數(shù)據(jù)結(jié)構(gòu)[M]. 北京：高等教育出版社，2001，230～232.

[3] 陳益富，盧 瀟，丁豪杰. 對(duì)Dijkstra算法的優(yōu)化策略研究[J]. 計(jì)算機(jī)技術(shù)與發(fā)展，2006，16（9）：73～75.

[4] 章永龍. Dijkstra最短路徑算法優(yōu)化[J]. 南昌工程學(xué)院學(xué)報(bào)，2006，25（3）：30～33.

[5] 胡樹瑋，張修如，趙 洋.扇形優(yōu)化Dijkstra算法[J]. 計(jì)算機(jī)技術(shù)與發(fā)展，2006，16（12）：49～51.

篇3

關(guān)鍵詞： 智慧旅游； 導(dǎo)覽； 線路規(guī)劃； 個(gè)性化游覽線路

中圖分類號(hào)： TN911?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2016）20?0092?05

Abstract： Personalized tour route planning is one of cores of intelligent guiding to visitors， and the formalizing denotation of the information of scenic regions and view spots is the fundament of personalized automatic planning of touring routes. A method of generating the route automatically is given in this paper for automatic planning of touring route based on directed graph， H?RVT and users′ preference. On the basis of analyzing the related factors， a method of how to express the information of scenic regions and view spots is given in this paper. A expressive method of view spot information is proposed according to the table of maximum relative price. An automatic planning method of personalized tour route is offered， which considers the selection of start point， end point， view spots and visiting time control. The method of formal representation for scenic regions， view spots and routing generation provide a theory support for realization of route planning.

Keywords： wisdom tourism； guiding to visitor； rout planning； personalized tour route

0 引 言

智能導(dǎo)覽是智慧旅游研究與建設(shè)的關(guān)鍵內(nèi)容之一，也是物聯(lián)網(wǎng)技術(shù)的重要應(yīng)用[1?2]。參觀游覽路線是否科學(xué)合理在很大程度上影響到整個(gè)游覽過程的用戶體驗(yàn)。對(duì)游客而言，科學(xué)合理的游覽路線能夠使其在較短的時(shí)間、較小的路程代價(jià)下獲得較好的游覽體驗(yàn)，同時(shí)，對(duì)旅游服務(wù)提供者來說，高效的游覽路線也能使得相同服務(wù)資源代價(jià)的情況下獲得游客更高的服務(wù)評(píng)價(jià)，從而促進(jìn)旅游及其服務(wù)業(yè)的健康持續(xù)發(fā)展和進(jìn)步[3?4]。

實(shí)際情況下，游客的游覽時(shí)間有限，不足以完整地游覽當(dāng)前景區(qū)中所有的景點(diǎn)。游客的真實(shí)需求是在有限的時(shí)間內(nèi)個(gè)性化地對(duì)當(dāng)前景區(qū)內(nèi)景點(diǎn)進(jìn)行游覽。因此，如何安排游覽路線，成為智能導(dǎo)覽系統(tǒng)中急需解決的一大問題，生成的游覽路線是否可行有效且滿足游客的偏好，對(duì)用戶體驗(yàn)至關(guān)重要。

游覽路線的規(guī)劃設(shè)計(jì)工作本質(zhì)是依據(jù)游客當(dāng)前的位置信息和待參觀的景區(qū)景點(diǎn)信息，根據(jù)一定的策略篩選合適的路線和景點(diǎn)，并將之有序排列在具體游覽行程路線的過程中。完整的游覽路線應(yīng)當(dāng)包括起點(diǎn)、景點(diǎn)集合、景點(diǎn)間的路徑集合以及終點(diǎn)。因此，對(duì)景區(qū)內(nèi)最佳游覽路線問題模型的建立以及路線生成策略的設(shè)計(jì)是決定游覽路線優(yōu)劣程度的關(guān)鍵所在。

面向智能導(dǎo)覽的個(gè)性化線路自動(dòng)規(guī)劃本質(zhì)上是解決在有限約束下的最短路徑應(yīng)用問題，它是運(yùn)籌學(xué)、地理信息學(xué)以及計(jì)算機(jī)網(wǎng)絡(luò)等學(xué)科中的研究熱點(diǎn)，比如求單源且無負(fù)邊權(quán)的“一對(duì)多”的Dijkstra算法[5]、用于求多源且無負(fù)權(quán)邊的“一對(duì)一”最短路徑的Floyd算法[6]、求多個(gè)備選優(yōu)化路徑的K最短路徑算法[7]以及靜態(tài)路網(wǎng)中較為有效的“直接搜索”A*算法[8]等。同時(shí)，隨著經(jīng)典圖論和計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)的有效結(jié)合，使得各類最短路徑算法不斷涌現(xiàn)以解決不同特征的實(shí)際問題，它們?cè)跁r(shí)間復(fù)雜度、空間復(fù)雜度、應(yīng)用范圍以及易實(shí)現(xiàn)等性能上各具特色[9?10]。國內(nèi)有學(xué)者專門就最短路徑算法的分類體系以及研究進(jìn)展[11]方面進(jìn)行過較為全面的總結(jié)與研究分析。文獻(xiàn)[12]提出了一種利用線圖以及頂點(diǎn)賦權(quán)圖的最優(yōu)完全子圖的方案解決中國郵遞員問題中如何生成最優(yōu)郵遞路線的問題。該方法與通常圖的相關(guān)概念的區(qū)別在于其為圖中的節(jié)點(diǎn)（也稱頂點(diǎn)）賦加了權(quán)值，最終求出一條能訪問到圖中所有節(jié)點(diǎn)且具有最小權(quán)值的環(huán)游。文獻(xiàn)[13]提出了一種解決圖中受K頂點(diǎn)數(shù)限制的所有最短路徑BCSP算法以及其改進(jìn)的ICSP算法，運(yùn)用圖的廣度遍歷算法以及逆鄰接表、指針等數(shù)據(jù)結(jié)構(gòu)知識(shí)生成擴(kuò)展最短路徑樹。

1 問題背景

在游覽過程中，以有限的時(shí)間條件為前提，從游客需求的角度出發(fā)，有如下三點(diǎn)直觀的要求：優(yōu)先參觀景區(qū)內(nèi)游覽價(jià)值大的景點(diǎn)；要求所步行的路程最少，即花費(fèi)在步行過程中的時(shí)間短；在不超出限定時(shí)間的前提下，盡可能充分地利用限定的時(shí)間。

以現(xiàn)實(shí)中大量游客對(duì)景區(qū)的參觀游覽行為過程的總結(jié)為基礎(chǔ)，描述游客游覽某一景區(qū)的一般活動(dòng)流程為：

Step1：根據(jù)當(dāng)前的位置尋找到該景區(qū)最近的入口，從入口處進(jìn)入景區(qū)。

Step2：若游覽時(shí)間足夠長，則從當(dāng)前位置開始按距離的遠(yuǎn)近開始按序游覽景區(qū)內(nèi)景點(diǎn)，直至景區(qū)內(nèi)所有景點(diǎn)都游覽完畢，結(jié)束游覽活動(dòng)。若時(shí)間有限，不能完整游覽整個(gè)景區(qū)內(nèi)所有景點(diǎn)，則執(zhí)行Step3。

Step3：以當(dāng)前位置為參考，在限定時(shí)間內(nèi)，選擇相對(duì)游覽價(jià)值最高的未被游覽的景點(diǎn)（即該景點(diǎn)知名度高且對(duì)其進(jìn)行游覽花費(fèi)時(shí)間少）。

Step4：步行到達(dá)待參觀的景點(diǎn)并花費(fèi)一定時(shí)間完成對(duì)該景點(diǎn)的參觀。此時(shí)，檢查剩余時(shí)間是否可繼續(xù)游覽活動(dòng)。若剩余時(shí)間可繼續(xù)游覽活動(dòng)，則返回Step3，若剩余時(shí)間無法滿足繼續(xù)游覽要求，則執(zhí)行Step5。

Step5：從當(dāng)前景點(diǎn)位置行至距離最近的景區(qū)出口，離開景區(qū)結(jié)束對(duì)該景區(qū)內(nèi)景點(diǎn)的游覽，完成本次游覽活動(dòng)。

因此，解決最佳游覽路線生成問題需要完成工作為：

（1） 尋找或設(shè)計(jì)最短路徑算法，以無向圖中任意某一節(jié)點(diǎn)為起點(diǎn)，根據(jù)其余節(jié)點(diǎn)的權(quán)值、價(jià)值以及該節(jié)點(diǎn)與其余各節(jié)點(diǎn)之間的最短路徑，得到在當(dāng)前位置狀態(tài)下，滿足時(shí)間限制條件的最佳下一個(gè)待游覽節(jié)點(diǎn)。

（2） 當(dāng)需要游覽的節(jié)點(diǎn)集合選定之后，在無向圖[G]中根據(jù)邊信息以及邊的權(quán)值數(shù)據(jù)確定最佳的游覽路線，生成選定節(jié)點(diǎn)集合中節(jié)點(diǎn)的最終游覽序列。

2 景區(qū)模型抽象與景點(diǎn)屬性表示

2.1 建立無向圖處理模型

旅游景區(qū)由多個(gè)出入口、內(nèi)部景點(diǎn)集、公共服務(wù)點(diǎn)及內(nèi)部相互之間的路徑組成，游覽路線的生成工作即根據(jù)約束條件按序選擇合適的景點(diǎn)集合與路徑集合。本文以無向圖作為景區(qū)及景點(diǎn)的表示模型，將景區(qū)相關(guān)信息抽象成如圖1所示附加節(jié)點(diǎn)值的帶邊權(quán)的無向圖模型。

由圖1可知，將某景區(qū)的平面示意圖轉(zhuǎn)換為無向圖[G]，將景區(qū)中的景點(diǎn)以及出入口轉(zhuǎn)換為無向圖[G]中的頂點(diǎn)，景點(diǎn)之間的路徑轉(zhuǎn)換為無向圖中的邊。

定義1：無向圖[G]由一個(gè)二元組[V，E]組成，其中集合[V]稱為無向圖[G]的節(jié)點(diǎn)集合，記為[V={v0，v1，v2，…，vn}，（n∈N*）]，[V]中每個(gè)元素對(duì)應(yīng)代表實(shí)際景區(qū)中一個(gè)景點(diǎn)；集合[G]稱為無向圖[G]的邊集，是由集合[V]中的元素組成的無序?qū)vi，vjvi∈V，vj∈V]組成，記為[E=ei，jei，j=vi，vj或ei，j=vj，vi，vi∈V，vj∈V，][E]中每個(gè)元素表示實(shí)際情況下景區(qū)景點(diǎn)之間的一條路徑。

2.2 景點(diǎn)信息表示策略

2.2.1 節(jié)點(diǎn)相對(duì)價(jià)值

在無向圖[G]中，以[vi]為起點(diǎn)，[vj]為終點(diǎn)的一條路徑[px（vi，vj）]的定義，以及該路徑的路徑代價(jià)[Wpx（vi，vj）]的定義。一般情況下，從節(jié)點(diǎn)[vi]出發(fā)到節(jié)點(diǎn)[vj]的路徑并不惟一，并且不同的路徑代價(jià)一般各不相同。根據(jù)每條路徑的路徑代價(jià)大小，節(jié)點(diǎn)[vi]到節(jié)點(diǎn)[vj]的所有路徑的集合[Pij]中必定存在一條路徑代價(jià)最小的路徑。

對(duì)表1的幾點(diǎn)說明：

（1） 目標(biāo)節(jié)點(diǎn)表示以節(jié)點(diǎn)[vi]為起點(diǎn)出發(fā)需要達(dá)到的節(jié)點(diǎn)。節(jié)點(diǎn)vi的相對(duì)價(jià)值表中目標(biāo)節(jié)點(diǎn)中包含無向圖[G]中除vi以外的所有節(jié)點(diǎn)。

（2） 路徑時(shí)間代價(jià)表示vi與目標(biāo)節(jié)點(diǎn)之間最短路徑之中所有路徑的權(quán)值之和，即從vi出發(fā)達(dá)到目標(biāo)節(jié)點(diǎn)過程中經(jīng)過的路徑所用的路程時(shí)間。

（3） 節(jié)點(diǎn)時(shí)間代價(jià)表示目標(biāo)節(jié)點(diǎn)的時(shí)間代價(jià)，即游覽目標(biāo)節(jié)點(diǎn)對(duì)應(yīng)景點(diǎn)所需要的時(shí)間。

（4） 節(jié)點(diǎn)價(jià)值表示目標(biāo)節(jié)點(diǎn)的價(jià)值，為目標(biāo)節(jié)點(diǎn)對(duì)應(yīng)景點(diǎn)的自身固有價(jià)值。

（5） 是否已加入路線標(biāo)記目標(biāo)節(jié)點(diǎn)，是否已經(jīng)被加入到最佳路線中，1代表該目標(biāo)節(jié)點(diǎn)已加入到最佳路線中，0代表未加入。

（6） 最大相對(duì)價(jià)值表示目標(biāo)節(jié)點(diǎn)在以[vi]為起點(diǎn)的情況下的最大相對(duì)價(jià)值。在最佳路線的生成過程中，優(yōu)先選擇表[H-RVT（vi）]中相對(duì)價(jià)值高的目標(biāo)節(jié)點(diǎn)加入到最佳路線中。

在表示景點(diǎn)和路徑信息的無向圖[G]中，所有節(jié)點(diǎn)都有其最大相對(duì)價(jià)值表，每一張表中都包含了以該節(jié)點(diǎn)為起點(diǎn)，到其他所有節(jié)點(diǎn)的最大相對(duì)價(jià)值。

3 條件約束與個(gè)性化路線生成

游覽時(shí)間分為路程中花費(fèi)的時(shí)間以及對(duì)景點(diǎn)進(jìn)行參觀游覽花費(fèi)的時(shí)間，游覽價(jià)值取決于路線中所有景點(diǎn)的價(jià)值高低。從宏觀上描述最佳游覽路線的要求為“在限定的時(shí)間內(nèi)，最高效地利用有限的時(shí)間，尋找游覽價(jià)值最高游覽路線”；從路線生成過程中描述最佳游覽路線的要求為“保證每次加入到游覽路線中的景點(diǎn)都是當(dāng)前條件下最值得游覽的景點(diǎn)”。

3.1 路線起點(diǎn)選擇

3.3 路線終點(diǎn)選擇

生成最佳路線的整個(gè)流程，首先生成最佳路線的起點(diǎn)，也就是選擇進(jìn)入景區(qū)的入口；第二步是生成最佳游覽路線的主要內(nèi)容，不斷的在為圖中未加入最佳路線的節(jié)點(diǎn)集合中按照加入之后的“效益”大小的順序以及是否滿足時(shí)間限制條件來選擇下一個(gè)最值得加入路線；當(dāng)圖中未加入最佳路線的節(jié)點(diǎn)集合中沒有滿足時(shí)間限制條件的節(jié)點(diǎn)時(shí)，為最佳路線按照選擇終點(diǎn)，即選擇離開景區(qū)的出口，生成完整的最佳路線并輸出結(jié)果。

4 結(jié) 論

本文針對(duì)在有限時(shí)間生成最佳游覽路線的問題，從游客的實(shí)際需求分析著手，設(shè)計(jì)了使用無向圖數(shù)學(xué)模型，總結(jié)出在時(shí)間限定條件下影響景點(diǎn)與路徑選擇的三個(gè)主要因素，并根據(jù)分析結(jié)果為每個(gè)節(jié)點(diǎn)生成各自H?RVT表，從而成功實(shí)現(xiàn)了生成最佳的游覽路線。

參考文獻(xiàn)

[1] OWAIED H H， FARHAN H A， AL?HAWAMDEH N， et al. A model for intelligent tourism guide system [J]. Journal of applied sciences， 2011， 11（2）： 342?347.

[2] GAVALAS Damianos， KENTERIS Michael. A web?based pervasive recommendation system for mobile tourist guide [J]. Personal and ubiquitous computing， 2011， 15（7）： 759?770.

[3] 廖川榮.校園最佳游覽路線問題的數(shù)學(xué)模型分析[J].大學(xué)數(shù)學(xué)，2012，28（6）：78?82.

[4] 姜西瑞.基于GPS和GSM/GPRS的定位系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D].北京：中國科學(xué)院計(jì)算機(jī)技術(shù)研究所，2006.

[5] 章永龍.Dijkstra最短路徑算法優(yōu)化[J].南昌工程學(xué)院學(xué)報(bào)，2006，25（3）：30?33.

[6] 赫自軍，何尚錄.最短路問題的Floyd算法的若干討論[J].重慶工學(xué)院學(xué)報(bào)（自然科學(xué)版），2008，22（5）：156?159.

[7] 徐濤，丁曉璐，李建伏.K最短路徑算法綜述[J].計(jì)算機(jī)工程與設(shè)計(jì)，2013，34（11）：3900?3906.

[8] 劉浩，鮑遠(yuǎn)律.A*算法在矢量地圖最優(yōu)路徑搜索中的應(yīng)用[J].計(jì)算機(jī)仿真，2008，25（4）：253?257.

[9] ZHAN F B， NOON C E. Shortest paths algorithms： an evaluation using real road networks [J]. Transportation science， 1998， 32（1）： 65?73.

[10] CHERK ASSKY B V， GOLDBERG A V， DIZK T R A. Shortest paths algorithms： theory and experimental evaluation[J]. Mathematical programming， 1996， 73（2）： 129?174.

[11] LU Feng. Shortest path algorithms： taxonomy and advance in research [J]. ACAT geodaetica cartographica， 2001， 30（3）： 269?275.

篇4

關(guān)鍵詞：管理；運(yùn)籌學(xué)；教學(xué)改革

中圖分類號(hào)：G642.3 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1002-4107（2013）08-0050-02

運(yùn)籌學(xué)是一門集應(yīng)用數(shù)學(xué)和形式科學(xué)為一體的跨領(lǐng)域?qū)W科，它利用統(tǒng)計(jì)學(xué)、數(shù)學(xué)模型和算法等優(yōu)化方法，去尋找復(fù)雜問題中的最佳或近似最佳的結(jié)果。它也是管理類專業(yè)的一門重要專業(yè)基礎(chǔ)課，其主要教學(xué)目的是使學(xué)生掌握各種模型及其求解方法，為今后解決實(shí)際決策優(yōu)化問題打下扎實(shí)的基礎(chǔ)。因此，做好運(yùn)籌學(xué)的課堂教學(xué)對(duì)管理類專業(yè)的學(xué)生做好學(xué)習(xí)鋪墊至關(guān)重要。

一、運(yùn)籌學(xué)課堂教學(xué)現(xiàn)狀

課堂教學(xué)是教育教學(xué)中普遍使用的一種手段，它是教師給學(xué)生傳授知識(shí)和技能的全過程，也是教學(xué)的主要渠道。它主要包括教師講解，學(xué)生問答，教學(xué)活動(dòng)以及教學(xué)過程中使用的所有教具，而“教師講解”環(huán)節(jié)占整個(gè)過程的比重最大。在現(xiàn)階段運(yùn)籌學(xué)課堂教學(xué)中，主要存在以下幾個(gè)問題。

（一）學(xué)生主動(dòng)意識(shí)薄弱

長期以來，在傳統(tǒng)教育思想影響下，通常把教師當(dāng)做教學(xué)的主體，把學(xué)生當(dāng)做客體，過分強(qiáng)調(diào)教師的權(quán)威性，而在一定程度上忽視了學(xué)生作為學(xué)習(xí)主體的存在；過分強(qiáng)調(diào)了知識(shí)傳授的灌輸性，而忽視了師生之間的互動(dòng)性，這樣的形式削弱了學(xué)生主動(dòng)參與學(xué)習(xí)的積極性，容易導(dǎo)致知識(shí)掌握不牢固的結(jié)果，影響教學(xué)的有效性。

（二）差等生難以融入課堂

現(xiàn)代的高等教育已經(jīng)發(fā)展到大眾教育階段，同一個(gè)班級(jí)的學(xué)生的學(xué)習(xí)興趣、學(xué)習(xí)欲望、學(xué)習(xí)成績有很大的差別，學(xué)習(xí)不良、成績落后的學(xué)習(xí)障礙學(xué)生人數(shù)比重大為增加，這會(huì)直接影響整個(gè)班級(jí)的學(xué)習(xí)氛圍。運(yùn)籌學(xué)對(duì)數(shù)學(xué)底子薄、注意力不集中的學(xué)生來講，很容易脫離課堂教學(xué)節(jié)奏，最后放棄學(xué)習(xí)，站到“差等生”的隊(duì)列。因此，控制差等生的比重或提高差等生的學(xué)習(xí)積極性對(duì)改善整體學(xué)習(xí)狀況非常有利。

（三）學(xué)習(xí)效果評(píng)價(jià)手段單一

現(xiàn)階段運(yùn)籌學(xué)教學(xué)結(jié)果的評(píng)價(jià)一般采用傳統(tǒng)的閉卷筆試的考試方式，其中尤以期終考試卷面成績?yōu)橹鳎?0%―100%。導(dǎo)致學(xué)生將學(xué)習(xí)重點(diǎn)放在對(duì)知識(shí)的死記硬背上，難以將其“活學(xué)活用”。

二、管理類運(yùn)籌學(xué)課堂教學(xué)改革實(shí)踐

（一）教學(xué)目標(biāo)定位

聯(lián)合國教科文組織提出，21世紀(jì)的教育支柱，即是學(xué)會(huì)求知，學(xué)會(huì)做事，學(xué)會(huì)共處，學(xué)會(huì)做人。在這些人類生存所必須具備的素質(zhì)中，學(xué)會(huì)做人最重要。因此，教師在教學(xué)中不僅要讓學(xué)生掌握課程中的知識(shí)點(diǎn)，還要注重對(duì)學(xué)生學(xué)習(xí)方法及學(xué)習(xí)興趣的培養(yǎng)、創(chuàng)新能力的培養(yǎng)以及人格的教育。

（二）教學(xué)內(nèi)容優(yōu)化

運(yùn)籌學(xué)是一門具有較多分支的學(xué)科，因課時(shí)限制，教師在教授課程中不可能做到面面俱到，對(duì)教學(xué)內(nèi)容，應(yīng)堅(jiān)持適用性的原則適當(dāng)調(diào)整：難度較大、應(yīng)用性不強(qiáng)的內(nèi)容，應(yīng)少講或不講；對(duì)于純理論的數(shù)學(xué)推導(dǎo)可以少講，會(huì)運(yùn)用其推導(dǎo)結(jié)論即可；應(yīng)用性較強(qiáng)的內(nèi)容應(yīng)多講、詳講。例如，對(duì)數(shù)據(jù)包絡(luò)分析、非線性規(guī)劃、動(dòng)態(tài)規(guī)劃等較復(fù)雜的內(nèi)容可以不講；對(duì)存貯論、對(duì)策論等讓學(xué)生理解原理、能運(yùn)用結(jié)論即可；物流管理專業(yè)的授課對(duì)運(yùn)輸問題、圖與網(wǎng)絡(luò)分析可詳講，并適當(dāng)加深難度；工程管理專業(yè)的授課應(yīng)增加網(wǎng)絡(luò)計(jì)劃的內(nèi)容。

（三）教學(xué)模式改革

1.讓學(xué)生成為課堂的主人。在教學(xué)實(shí)踐中，多創(chuàng)造機(jī)會(huì)讓學(xué)生參與教學(xué)，成為課堂的主人。教師在教學(xué)中可以通過與學(xué)生互換角色來調(diào)動(dòng)其學(xué)習(xí)主動(dòng)性、積極性，達(dá)到良好的學(xué)習(xí)效果。教師將教學(xué)內(nèi)容分為簡單的、復(fù)雜的兩類，復(fù)雜的由教師自己講授，簡單的則分給愿意承擔(dān)的學(xué)生，這樣就把學(xué)生當(dāng)作了教學(xué)的主體，學(xué)生在這種壓力情況下會(huì)將課前預(yù)習(xí)的效果發(fā)揮到極致。鼓勵(lì)學(xué)生之間的合作，進(jìn)行團(tuán)隊(duì)學(xué)習(xí)，承擔(dān)不同的角色，如PPT制作，黑板板書，卡片制作、上臺(tái)講析等，各自發(fā)揮長處，并且能夠培養(yǎng)團(tuán)隊(duì)精神。如運(yùn)籌學(xué)中圖與網(wǎng)絡(luò)分析、網(wǎng)絡(luò)計(jì)劃前面的基本知識(shí)部分就可以通過這種形式進(jìn)行教學(xué)，在學(xué)生的教學(xué)活動(dòng)結(jié)束時(shí)教師再做適當(dāng)?shù)难a(bǔ)充。

課堂練習(xí)題等也可以作為學(xué)生參與教學(xué)的部分，可以讓更多的學(xué)生參與其中，通過自己的嘗試，體會(huì)講課的過程才會(huì)更加理解教師的勞動(dòng)成果，更加用心聽課，形成良性循環(huán)；學(xué)生參與課堂練習(xí)的分析也會(huì)促進(jìn)課后復(fù)習(xí)的效果。如在單純形法、指派問題等章節(jié)中鼓勵(lì)學(xué)生評(píng)講課堂練習(xí)題或者課后習(xí)題；讓學(xué)生參與期末課程總復(fù)習(xí)的指導(dǎo)。

2.全員參與式教學(xué)。成績處于中上水平的學(xué)生比較配合教師的教學(xué)，能夠緊跟課堂教學(xué)的節(jié)奏，而成績靠后的學(xué)生則很難融入進(jìn)來。在課堂教學(xué)中應(yīng)該讓差等生也能參與其中，改善班級(jí)整體學(xué)習(xí)氛圍。在這種情況下，可以通過黑板板書、畫圖等比較簡單的形式讓成績略差、缺乏學(xué)習(xí)熱情的學(xué)生也能參與到課堂教學(xué)中，并對(duì)他們進(jìn)行適當(dāng)表揚(yáng)，提高他們的學(xué)習(xí)興趣，逐漸脫離“差等生”的隊(duì)伍。

篇5

關(guān)鍵詞：蟻群算法；物流配送；路徑優(yōu)化；數(shù)學(xué)模型

DOIDOI：10.11907/rjdk.161974

中圖分類號(hào)：TP319

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)文章編號(hào)：16727800（2016）011014004

基金項(xiàng)目基金項(xiàng)目：

作者簡介作者簡介：袁文濤（1993-）男，安徽馬鞍山人，上海理工大學(xué)光電信息與計(jì)算機(jī)工程學(xué)院碩士研究生，研究方向?yàn)槟Ｊ阶R(shí)別與智能系統(tǒng)；孫紅（1964-）女，上海人，上海理工大學(xué)光電信息與計(jì)算機(jī)工程學(xué)院副教授、碩士生導(dǎo)師，研究方向?yàn)槟Ｊ阶R(shí)別與智能系統(tǒng)、 控制理論與控制工程、企業(yè)信息化系統(tǒng)與工程。

0 引言

解決組合優(yōu)化問題的最優(yōu)化求解算法有多種現(xiàn)代人工智能算法方案，優(yōu)化算法用來處理問題最優(yōu)解的求解，該問題通常由多個(gè)變量共同決定。當(dāng)前，求解最短路徑問題是圖論研究中的一個(gè)典型求解組合優(yōu)化算法問題，旨在尋找圖表（由節(jié)點(diǎn)和路徑構(gòu)成）中兩節(jié)點(diǎn)或多節(jié)點(diǎn)之間的最短路徑。常用的最優(yōu)化路徑求解方法有Bellman-Ford算法、Dijkstra算法、A*算法和蟻群算法。這些算法都有自身的優(yōu)點(diǎn)和不足。在對(duì)不同算法作出比較后，可以得出蟻群算法在解決網(wǎng)絡(luò)路由和城市交通系統(tǒng)的問題中是相對(duì)有利的。

就目前研究來看，隨著實(shí)際組合問題的變化，基本的智能算法已經(jīng)不能滿足解決這類組合優(yōu)化問題，同時(shí)其優(yōu)勢(shì)也在減弱[1]。本文采取改進(jìn)后的組合優(yōu)化蟻群算法以彌補(bǔ)傳統(tǒng)蟻群算法易陷入局部最優(yōu)解的不足，加快了求全局最優(yōu)解的構(gòu)造速率。

蟻群算法（Ant Colony Optimization， ACO），是一種模擬螞蟻群體智能行為的進(jìn)化仿生類優(yōu)化算法，在求解性能上具有強(qiáng)魯棒性、優(yōu)良的分布式計(jì)算能力、便于與其它算法相結(jié)合等優(yōu)點(diǎn)[2-3]。通常作為一種用來在多變量組合優(yōu)化問題的多候選解中尋找最優(yōu)化路徑的機(jī)率型算法。它由Marco Dorigo于1992年在其博士論文《Ant system： optimization by a colony of cooperating agents》中首先提出，其靈感來源于通過對(duì)蟻群社會(huì)的長期跟蹤觀察后發(fā)現(xiàn)，雖然單個(gè)螞蟻沒有視力、智慧程度低、工作方式簡單，但它們卻有強(qiáng)大的執(zhí)行能力和協(xié)同工作能力，依靠復(fù)雜群體的自組織協(xié)同能力發(fā)揮出超出單個(gè)個(gè)體累加的智能，是一種超個(gè)體（superorganism，又稱超有機(jī)體）存在現(xiàn)象。蟻群是在這樣的超個(gè)體案例中最有名的例子。雖然蟻群算法的嚴(yán)格理論基礎(chǔ)和實(shí)際應(yīng)用尚未成熟，國內(nèi)外相關(guān)研究暫處于實(shí)驗(yàn)階段，但這并不妨礙人們對(duì)蟻群算法的研究已經(jīng)由當(dāng)初單一的解決商旅問題（TSP）發(fā)展到解決調(diào)度問題、網(wǎng)絡(luò)通信等多個(gè)方向的最優(yōu)化求解應(yīng)用。

目前，蟻群優(yōu)化算法已廣泛應(yīng)用于多種求組合最優(yōu)化問題，在面臨路例如作業(yè)安排調(diào)度問題和路由車輛的二次分派問題上表現(xiàn)出了良好的性能，也經(jīng)常被用來求旅行推銷員問題的擬最優(yōu)解。它在圖表動(dòng)態(tài)變化情況問題的求解上相比螢火蟲算法和遺傳算法具有絕對(duì)優(yōu)勢(shì)：蟻群算法的最大優(yōu)點(diǎn)在于可以連續(xù)運(yùn)行并適應(yīng)實(shí)時(shí)變化；缺陷是在處理較大規(guī)模和復(fù)雜數(shù)據(jù)問題時(shí)，容易存在運(yùn)算耗時(shí)長、收斂速度慢、得不到全局最優(yōu)解等問題。

在求最優(yōu)解的歷次迭代中，單個(gè)螞蟻會(huì)根據(jù)給定的規(guī)則和限定條件選擇從一個(gè)城市（節(jié)點(diǎn)）轉(zhuǎn)移到另一個(gè)城市（節(jié)點(diǎn)）：它必須對(duì)所有城市訪問一次，而相對(duì)距離越遠(yuǎn)的城市被選中為下一個(gè)訪問點(diǎn)的機(jī)會(huì)越少（能見度低）；相反，在兩個(gè)城市（節(jié)點(diǎn)）邊際的一邊形成的信息素越濃烈，則該邊際作為路徑被選擇的概率越大；在較短路程情況下，短時(shí)間內(nèi)更多螞蟻會(huì)在所有走過的路徑上留下更多信息素，在每次迭代更新后，信息素軌跡濃度會(huì)按百分比揮發(fā)從而反饋給下一只途經(jīng)的螞蟻并影響它作出路徑選擇。

1 車輛路徑問題

傳統(tǒng)的車輛路徑問題也叫VRP（Vehicle Routing Problem）問題，是關(guān)系到現(xiàn)代物聯(lián)網(wǎng)發(fā)展過程中物流配送系統(tǒng)的一個(gè)關(guān)鍵問題，屬于NP難題。一直以來，該問題也是管理科學(xué)和物流運(yùn)輸方面的重要課題[4]，受到國內(nèi)外學(xué)者的廣泛關(guān)注。

VRP問題描述如下：在一些由于經(jīng)濟(jì)或者地理限定的條件約束下，組織一個(gè)車隊(duì)，從一個(gè)或者多個(gè)初始點(diǎn)出發(fā)，規(guī)定達(dá)到多個(gè)不同的地點(diǎn)，設(shè)計(jì)一個(gè)成本最小、路程最短的路線集，使得：① 每個(gè)城市只能被一輛車訪問，只訪問一次；②所有送貨車輛必須從起始點(diǎn)出發(fā)再回到起始點(diǎn)；③某些特定的約束條件需要被滿足。

VRP的數(shù)學(xué)模型表示如下：一共有k個(gè)客戶，第i個(gè)客戶的貨物需求為gi，配送中心派出車輛承擔(dān)運(yùn)輸任務(wù)，其載重為q。設(shè)gi

如果前提有約束條件用于車輛本身，即容量限制和總長限制，則稱為有能力約束的車輛路徑問題（Capacitated Vehicle Routing Problem）。此模型是車輛路徑問題的基本模型，這類VRP問題叫作CVRP問題[5]。

設(shè)每個(gè)客戶點(diǎn)只允許被訪問一次，車輛所訪問的客戶點(diǎn)的需求總和不能超過車輛的負(fù)載能力，且總行駛的路程也不得超過其最大的行駛距離，達(dá)到用最少的車輛最短的路徑完成既定任務(wù)。

。

2 可約束蟻群算法實(shí)現(xiàn)

2.1 算法實(shí)現(xiàn)方式

當(dāng)前蟻群算法領(lǐng)域存在MPDACO局部更新和MPDACO全局更新兩種方式。前者指當(dāng)單個(gè)螞蟻從一個(gè)節(jié)點(diǎn)到達(dá)下一個(gè)節(jié)點(diǎn)完成轉(zhuǎn)移后就立刻更新螞蟻通過路徑時(shí)所留下的的信息素，后者是當(dāng)螞蟻遍歷完所有給定節(jié)點(diǎn)后再更新整條路徑上的信息素，不再是對(duì)所有的螞蟻，而是僅對(duì)全局最優(yōu)的螞蟻得到的路徑使用。從兩種更新方式得到的結(jié)果作對(duì)比可以得出，全局信息素更新方法雖然可以加快收斂速率，但是存在著一定的缺陷和不足，易使路徑更快地集中于單一解，易陷入局部最優(yōu)，這些缺點(diǎn)限制了它的廣泛傳播及應(yīng)用。

本文綜合上述兩種更新方法的優(yōu)點(diǎn)和不足，列出了一種新的組合疊加更新方法：在路徑搜索的前十次循環(huán)中，采用局部最優(yōu)解更新，十次固定循環(huán)結(jié)束后，再采用全局最優(yōu)解進(jìn)行更新，這種更新方式可以有效避免蟻群搜索得到的路徑沉入局部最優(yōu)解中，有利于發(fā)現(xiàn)更多較優(yōu)解。

2.2 算法實(shí)現(xiàn)步驟

根據(jù)改進(jìn)的蟻群算法，將優(yōu)化后的蟻群算法應(yīng)用于CVRP問題的實(shí)現(xiàn)步驟如下：

（1）參數(shù)初始化。設(shè)迭代次數(shù) Nc=0；每條路徑上的信息素濃度Δτij（0）=c（c為常數(shù)），并且Δτij=0；隨機(jī)將m個(gè)螞蟻放置到初始點(diǎn)上。

（2）更新迭代（循環(huán)）次數(shù)，即Nc=Nc+1。

（3）初始化禁忌表，螞蟻禁忌表的索引號(hào)k=1。

（4）更新螞蟻數(shù)目k=k+1。

（5）判斷路徑是否在搜索熱區(qū)內(nèi)。按照式（a）～（f）計(jì)算出每只螞蟻應(yīng)當(dāng)轉(zhuǎn)移至下一個(gè)城市（節(jié)點(diǎn)）的概率并完成移動(dòng)。

（6）當(dāng)螞蟻從i城市（節(jié)點(diǎn)）出發(fā)到達(dá)j城市（節(jié)點(diǎn)）時(shí)，對(duì)其所經(jīng)過的路徑上的信息素進(jìn)行更新，并修改禁忌表，將禁忌表指針按照當(dāng)前狀況進(jìn)行修改，即將新城市（節(jié)點(diǎn)）j置于禁忌表tabuk中。

（7）執(zhí)行步驟（b）～（f），直到所有螞蟻都找到了一條包含所有城市（節(jié)點(diǎn)）的可行路徑解。

（8）在新生成的所有可行解中找到一條最短路徑作為本次迭代中的最優(yōu)路徑解。

（9）判斷循環(huán)次數(shù)是否小于十次，若小于十次，則對(duì)螞蟻找到的最優(yōu)路徑按照本次迭代最優(yōu)值進(jìn)行信息素更新；若循環(huán)次數(shù)超過十次，則按照全局信息素進(jìn)行更新。

（10）對(duì)所有螞蟻經(jīng)過的路徑，按式（1）進(jìn)行一次全局更新。

（11）循環(huán)執(zhí)行（b）～（j），直到連續(xù)多次的迭代中得到的解已收斂或循環(huán)次數(shù)Nc的值已經(jīng)達(dá)到給定的最大迭代次數(shù)的情況下選取當(dāng)前輸出值作為本次最優(yōu)解。

3 實(shí)驗(yàn)仿真

設(shè)存在一個(gè)物流中心有4輛運(yùn)輸車， 單輛車最大載重為1 000kg， 現(xiàn)需要同時(shí)向7個(gè)隨機(jī)分布的客戶點(diǎn)派送貨物， 蟻群算法的初始化參數(shù)為： 螞蟻總數(shù)為20只， 算法的最大迭代數(shù)為100次， α和β分別為1，2， 信息素的揮發(fā)速度為0.75， 實(shí)驗(yàn)重復(fù)運(yùn)行100次， 求得的平均結(jié)果為最終結(jié)果。同時(shí)初始時(shí)刻各邊上的信息痕跡為1，殘留信息的相對(duì)重要度為1，設(shè)置預(yù)見度為5。原始數(shù)據(jù)進(jìn)行處理結(jié)果分析如圖3所示。按本文提出的優(yōu)化蟻群算法求解CVRP后的處理仿真結(jié)果如圖4所示。

觀測(cè)圖3、圖4的收斂曲線，可以知道蟻群算法優(yōu)化后的結(jié)果相比之前的行車路徑有大幅度優(yōu)化[810]，如圖5所示。針對(duì)每個(gè)收斂的點(diǎn)結(jié)合數(shù)據(jù)可以看出，傳統(tǒng)蟻群算法的平均路徑在迭代次數(shù)為45時(shí)可以得到最優(yōu)解，而改進(jìn)后的蟻群算法可以在第5次左右得到最優(yōu)解，相當(dāng)于收斂速度提高了近80%。

4 結(jié)語

在當(dāng)今應(yīng)用數(shù)學(xué)和理論計(jì)算機(jī)科學(xué)的領(lǐng)域中，組合優(yōu)化（Combinatorial Optimization）是在一個(gè)有限的對(duì)象集中找出最優(yōu)對(duì)象的一類重要課題，屬于運(yùn)籌學(xué)的一個(gè)重要分支。在很多組合優(yōu)化問題中，窮舉搜索/枚舉法是不可行的。組合優(yōu)化問題的特征為可行解的集是離散或者可以簡化到離散的，并且目標(biāo)是找到最優(yōu)解。解決組合優(yōu)化問題一般采用智能算法，而這些算法都有自身的優(yōu)點(diǎn)和缺點(diǎn)。組合優(yōu)化的難處，主要是加進(jìn)來拓?fù)浞治觯诓煌耐負(fù)湫螒B(tài)下，算法也需隨著不同部分的約束關(guān)系作出相應(yīng)調(diào)整。從目前研究來看，隨著實(shí)際組合問題的變化，基本的智能算法已不能解決這類組合優(yōu)化問題。

蟻群算法作為一種仿生類進(jìn)化算法在求路徑最優(yōu)化解方面具有很好的效果。本文首先引出蟻群算法可以用于解決這一類問題，然后介紹了約束車輛路徑問題，也即CVRP問題，說明了其約束模型；接著研究了基本的蟻群算法步驟，并對(duì)其中信息素更新和改進(jìn)了啟發(fā)因子，解析并改良了蟻群算法應(yīng)用于CVRP問題的實(shí)現(xiàn)步驟和處理方法。

本文提出的組合疊加更新方法可有效克服傳統(tǒng)蟻群算法收斂質(zhì)量低、耗時(shí)長、易陷入局部最優(yōu)解等缺陷，使蟻群算法的全局優(yōu)化能力得到大幅度提高。對(duì)比實(shí)驗(yàn)前數(shù)據(jù)可以看出，蟻群算法找到最短路徑的收斂速度比傳統(tǒng)方法快了80%左右，確實(shí)是一種求解最短物流配送路徑的有效算法。

參考文獻(xiàn)：

[1] 陳昌敏.基于蟻群算法的物流配送路徑優(yōu)化研究與應(yīng)用[D].成都：西華大學(xué)，2012（4）：1154.

[2] 宋留勇，王銳，周永旺，等.動(dòng)態(tài)城市交通網(wǎng)絡(luò)優(yōu)化模型研究及算法設(shè)計(jì)[J].測(cè)繪科學(xué)，2011，36（1）：134136.

[3] 鐘石泉，賀國光.有時(shí)間窗約束車輛調(diào)度優(yōu)化的一種禁忌算法[J].系統(tǒng)工程理論方法應(yīng)用，2005，14（6）：523527.

[4] CHAO YIMING.A tabu search method for the truck and trailer routing problem[J].Computer and Operations Research，2002，29（1）：3351.

[5] 楊中秋，張延華.改進(jìn)蟻群算法在交通系統(tǒng)最短路徑問題的研究[J].科學(xué)計(jì)算與信息處理，2009，32（8）：7678.

[6] 李松，劉興，李瑞彩.基于混合禁忌搜索算法的物流配送路徑優(yōu)化問題研究[J].鐵道運(yùn)輸與經(jīng)濟(jì)， 2007， 29（3）：66 69.

[7] 陶波， 朱玉琴.改進(jìn)的7動(dòng)態(tài)規(guī)劃法在車輛最短路徑問題中的應(yīng)用[J].重慶工學(xué)院學(xué)報(bào)， 2009，23（1）：2427.

[8] 李軍，郭耀煌.物流配送車輛優(yōu)化調(diào)度理論與方法[M].北京：中國物資出版社， 2001：101113.

[9] 張萬旭，林健良，楊曉偉.改進(jìn)的最大最小螞蟻算法在有時(shí)間窗車輛路徑問題中的應(yīng)用[J].計(jì)算機(jī)集成制造系統(tǒng)，2005，11（4）：572576.

[10] 余h，胡宏智.基于改進(jìn)遺傳算法的物流配送路徑求解[J].計(jì)算機(jī)技術(shù)與發(fā)展，2009，19（3）：5255.

[11] 朱慶保，蟻群優(yōu)化算法的收斂性分析[J]. 控制與決策，2006，21（7）：3016.

[12] 鄭松，侯迪波，周澤魁，動(dòng)態(tài)調(diào)整選擇策略的改進(jìn)蟻群算法[J].控制與決策，2008，23（2）：13.

[13] 夏亞梅，程渤，陳俊亮，等.基于改進(jìn)蟻群算法的服務(wù)組合優(yōu)化[J].計(jì)算機(jī)學(xué)報(bào)，2012，35（2）：311.

篇6

Abstract: Through the analysis of path optimization of emergency logistics distribution, the article establishes its model, proposes the solving method on this basis. Finally, through an example application of path optimization of emergency logistics distribution, the solving process are described, and the results are further discussed.

關(guān)鍵詞：物流；應(yīng)急配送；路徑優(yōu)化

Key words: logistics；emergency distribution；path optimization

中圖分類號(hào)：F253 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1006-4311（2011）28-0025-02

0 引言

隨著市場經(jīng)濟(jì)的發(fā)展和競爭的加劇，市場呈現(xiàn)多品種、小批量產(chǎn)品多樣化、消費(fèi)多樣化的趨勢(shì)，物流配送就是為適應(yīng)這種趨勢(shì)而產(chǎn)生的一個(gè)重要環(huán)節(jié)，它是指對(duì)局域范圍內(nèi)的客戶進(jìn)行的多客戶、多品種的按時(shí)聯(lián)合送貨活動(dòng)。配送的“送”就是送貨運(yùn)輸。從這個(gè)角度來看，物流配送中送貨路線的選擇，是影響物流成本的一項(xiàng)重要因素。從降低物流成本的途徑來看，提高物流速度，可以減少資金占用和，縮短在物物流周期，降低儲(chǔ)存費(fèi)用，從而節(jié)省物流成本。所以，在應(yīng)急物流配送過程中，要使得各物資需求點(diǎn)能在最短時(shí)間內(nèi)得到物資補(bǔ)充，物流中心就需要選擇最優(yōu)的保障方式，將物資送達(dá)各個(gè)需求點(diǎn)。

1 影響物流中心選址的因素及物資需求問題描述

在整個(gè)物流系統(tǒng)中，配送中心地點(diǎn)的選擇更是物流系統(tǒng)優(yōu)化的一個(gè)具有戰(zhàn)略意義的問題。傳統(tǒng)意義上的物流配送中心（或分銷中心）是商品從供應(yīng)商（制造商）至零售商之間的中間儲(chǔ)存點(diǎn)，具有集中和分散物資，促進(jìn)商品迅速流轉(zhuǎn)的功能。物流中心的位置的選擇，根本目的應(yīng)以費(fèi)用低、服務(wù)好、社會(huì)效益高為目標(biāo)，以物資運(yùn)輸合理、方便用戶、投資少、有利于適應(yīng)經(jīng)濟(jì)發(fā)展的需要為基本原則。物流中心的選址需要對(duì)多種因素綜合考慮包括：自然資源的特點(diǎn)、客戶的分布、運(yùn)輸服務(wù)條件、建設(shè)費(fèi)用、城市建設(shè)的整體規(guī)劃、外部環(huán)境因素等，此外對(duì)物流中心未來的發(fā)展應(yīng)仔細(xì)研究，使決策具有前瞻性。它包括物流中心在此處有沒有發(fā)展前途和大的作為，以及一定時(shí)期內(nèi)城市經(jīng)濟(jì)發(fā)展的變化，以便使物流中心能適應(yīng)未來發(fā)展的需要。

在滿足物流中心開設(shè)地點(diǎn)要求和綜合各物資需求點(diǎn)之間距離的前提下，物流中心與各物資需求點(diǎn)之間就不可避免地存在一定的距離。由于各物資需求點(diǎn)的周圍客戶量不同，物資的銷售情況也必然不同，必然會(huì)導(dǎo)致物資需求產(chǎn)生的偶然性，而物資需求點(diǎn)相對(duì)分散。物流中心收到來自這些分散的位置的物資配送申請(qǐng)后，對(duì)這些物資需求點(diǎn)進(jìn)行物資配送，模型就是要解決在物流中心現(xiàn)有運(yùn)輸力量前提下，以最優(yōu)的方式將物資送達(dá)每一個(gè)需求點(diǎn)，由此產(chǎn)生了物資需求問題。

2 應(yīng)急物流配送路徑優(yōu)化問題建模

2.1 物流中心與物資需求點(diǎn)的實(shí)際關(guān)系 由于物資需求點(diǎn)產(chǎn)生的偶然性，使得物流中心和物資需求點(diǎn)關(guān)系如圖1所示。以五個(gè)物資需求點(diǎn)的情況為例，各點(diǎn)編號(hào)分別為1、2、3、4、5，物流中心編號(hào)為0。現(xiàn)實(shí)情況是這樣的，各需求點(diǎn)之間以及需求點(diǎn)與物流中心之間，可能是可以不經(jīng)過第三點(diǎn)直達(dá)的（如需求點(diǎn)1、需求點(diǎn)2及物流中心之間都是可直達(dá)），也可能是必須經(jīng)過第三點(diǎn)才可以到達(dá)（如需求點(diǎn)5與物流中心之間）。若可以直達(dá)，則以連線表示兩點(diǎn)之間的支路。無論怎樣，需求點(diǎn)與物流中心之間總可以找到一條路，即是可達(dá)的。若某個(gè)需求點(diǎn)與物流中心之間沒有路，則表明該點(diǎn)與物流中心不可達(dá)，則該點(diǎn)也就沒有存在的必要。

2.2 現(xiàn)實(shí)情況的完全加權(quán)圖表示 將圖1所示的現(xiàn)實(shí)情況轉(zhuǎn)化為完全加權(quán)圖形式后得到如圖2所示的關(guān)系形式。圖2中0點(diǎn)為物流中心，其他為物資需求點(diǎn)，實(shí)線為實(shí)際支路，虛線表示虛擬支路。則物流中心應(yīng)急物流配送問題可以描述為：找到從0點(diǎn)出發(fā)不重復(fù)的遍歷所有節(jié)點(diǎn)的最短閉合回路。由此，可以看出物流中心物資輸送問題實(shí)質(zhì)上為一個(gè)TSP問題。

2.3 所求最優(yōu)回路中的組成支路的權(quán)值的確定 解決該問題的目標(biāo)是找到從0點(diǎn)出發(fā)不重復(fù)的經(jīng)過所有節(jié)點(diǎn)的最短閉合回路。也就是使得這條閉合回路的組成支路的權(quán)值之和最小。所以，求得最優(yōu)路徑的問題依賴于各條組成支路的權(quán)值的確定。在現(xiàn)實(shí)情況下，各路徑的權(quán)值是綜合考慮物流中心到各需求點(diǎn)間的距離、道路狀況以及各道路安全性等因素得出的結(jié)果，因此在對(duì)實(shí)際支路賦權(quán)的過程中，會(huì)出現(xiàn)違背三角不等式的情況，在此對(duì)具體的賦權(quán)規(guī)則不做研究，而假設(shè)各實(shí)際支路的權(quán)值已得出。在對(duì)實(shí)際支路賦權(quán)完畢后，進(jìn)行虛擬支路的賦權(quán)，各虛擬支路的權(quán)值均為實(shí)際支路權(quán)值之和的m倍，m為無窮大的自然數(shù)，即虛擬支路不可通行。

2.4 設(shè)計(jì)求解最優(yōu)路徑問題的流程 物流中心應(yīng)急物流配送問題抽象后實(shí)質(zhì)為一個(gè)N個(gè)節(jié)點(diǎn)的TSP問題。因此，總能找到一條最優(yōu)路徑。現(xiàn)在假設(shè)找到了此問題的一條最優(yōu)路徑L。L若不包含虛擬支路，則表示從物流中心出發(fā)，確實(shí)存在一條最優(yōu)的配送路徑，從距離、路況及安全性角度綜合分析是最優(yōu)的配送路徑；若L中包括至少一條虛擬路徑，則表示在現(xiàn)有路徑下不存在符合條件的最優(yōu)路徑。即現(xiàn)有條件下的最短路徑中某些節(jié)點(diǎn)至少需要經(jīng)過兩次。因此，為求得較優(yōu)路徑對(duì)圖作如下處理。

假設(shè)L中某一虛擬路徑為（a，b），則總可以從點(diǎn)a到點(diǎn)b找到（a，K1，K2，…，Kn，b）這樣一條最短路，其中ki為最初的N個(gè)節(jié)點(diǎn)之一，且路（a，K1，K2，…，Kn，b）必不含虛擬路徑路，稱路（a，K1，K2，…， Kn，b）為虛擬路徑（a，b）的最短代替路徑。在已有節(jié)點(diǎn)之外新增加k個(gè)節(jié)點(diǎn)（A1，A2，…，Ak），新增節(jié)點(diǎn)的規(guī)則是節(jié)點(diǎn)Ak與Ki具有完全相同的屬性，即Ak到任何節(jié)點(diǎn)的權(quán)值與Ki到任何節(jié)點(diǎn)權(quán)值相同，特別的Ak到與Ki具有相同屬性的節(jié)點(diǎn)的權(quán)值為0。對(duì)L中每條虛擬路徑都按照（a, b）的方式處理。

完畢后則全部節(jié)點(diǎn)數(shù)目增加到N+A，其中N個(gè)是最初的實(shí)際節(jié)點(diǎn)，A個(gè)為新增節(jié)點(diǎn)。此時(shí)，對(duì)于N+A個(gè)節(jié)點(diǎn)來說已經(jīng)找到了一條回路L*，L*只包括這N+A個(gè)節(jié)點(diǎn)，且這N+A個(gè)節(jié)點(diǎn)在L*上出現(xiàn)且僅出現(xiàn)一次，同時(shí)L*上不含虛擬路徑。說明這N+A個(gè)節(jié)點(diǎn)的TSP問題存在最優(yōu)解。

根據(jù)以上分析，對(duì)物流中心應(yīng)急物流配送問題設(shè)計(jì)的求解流程如圖3。

3 模型的實(shí)例應(yīng)用

3.1 實(shí)例分析 以四個(gè)需求點(diǎn)為例進(jìn)行實(shí)例說明。假設(shè)需求點(diǎn)與物流中心的完全加權(quán)圖表示如圖4所示，各支路權(quán)值已給出。

①求這四個(gè)點(diǎn)的TSP問題，最優(yōu)解為（0，2，1，4，3，0），路的長L=12+M，其中包含虛擬路徑（2，3）。

②尋找（1，4）的最短代替路徑為（1，2，0，3，4）。

③增加點(diǎn)A，B，C，則原圖變?yōu)閳D5。

④求這八個(gè)點(diǎn)的TSP問題，最優(yōu)解為（0，2，1，C，B，3，4，A，0）。

3.2 關(guān)于求得的解的討論和實(shí)際意義解釋 以上通過增加虛擬點(diǎn)的方法建立的求解模型，最終求得的最優(yōu)路徑L可以分為兩種情況。情況一：最優(yōu)路徑L中除起點(diǎn)和終點(diǎn)外，不包含其它與起點(diǎn)具有相同屬性的點(diǎn)，說明在實(shí)施應(yīng)急物流配送過程中，運(yùn)輸車隊(duì)從物流中心出發(fā)后經(jīng)過路徑L所示的各個(gè)需求點(diǎn)，物資送達(dá)完畢返回物流中心，各個(gè)需求點(diǎn)都得到供應(yīng)。選擇該運(yùn)輸路徑，可以減少運(yùn)輸車隊(duì)的使用，只組織一支物資運(yùn)輸車隊(duì)，就可以達(dá)到完成運(yùn)輸任務(wù)的目的，有效地節(jié)約了運(yùn)輸資源。情況二：最優(yōu)路徑L中除起點(diǎn)和終點(diǎn)外還包含其它與起點(diǎn)具有相同屬性的點(diǎn)。這說明在實(shí)施應(yīng)急物流配送過程中，運(yùn)輸車隊(duì)從物流中心出發(fā)后，中途要返回物流中心，再到其他未配送的需求點(diǎn)，最后遍歷所有需求點(diǎn)后回到物流中心。解決此種情況的辦法的，根據(jù)中途回到物流中心的次數(shù)n，在可行的情況下，將整體運(yùn)輸力量分成n+1支配送小分隊(duì)，各小分隊(duì)對(duì)相應(yīng)的若干需求點(diǎn)進(jìn)行物流配送，完畢后返回物流中心。這樣，在總路徑不增加的前提下，對(duì)所有物資需求點(diǎn)展開了并行的物流配送，使得對(duì)所有需求點(diǎn)的最長物流配送時(shí)間減少，配送的效率更高。

4 結(jié)束語

物流中心是物資供應(yīng)體系中的一個(gè)重要的環(huán)節(jié)。研究應(yīng)急物流配送路徑優(yōu)化問題，對(duì)提高物流中心配送效率具有重要意義。文章對(duì)物流中心應(yīng)急物流配送路徑問題進(jìn)行了分析研究，建立了應(yīng)急物流配送路徑優(yōu)化問題的模型，設(shè)計(jì)了模型的求解流程，最后通過實(shí)例對(duì)應(yīng)急物流配送路徑優(yōu)化問題求解過程進(jìn)行了詳細(xì)說明。并結(jié)合現(xiàn)實(shí)情況，對(duì)求得的解進(jìn)行了進(jìn)一步分析討論，提出了物流中心應(yīng)急物流配送策略可能的改進(jìn)意見，供物流中心決策參考。

參考文獻(xiàn)：

[1]殷劍宏，吳開亞．圖論及其算法[M]．北京：中國科技大學(xué)出版社，2003．

篇7

關(guān)鍵詞：TSP模型；循環(huán)取貨；德邦物流

中圖分類號(hào)：F224 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-2374（2014）02-0021-03

第三方物流的迅速發(fā)展，為零擔(dān)運(yùn)輸企業(yè)提供了更多的市場機(jī)會(huì)，但同時(shí)也使市場競爭更加激烈。由于行業(yè)進(jìn)入的壁壘較低，許多小企業(yè)或個(gè)人進(jìn)入零擔(dān)運(yùn)輸市場，使得價(jià)格競爭非常激烈，對(duì)規(guī)范的市場競爭不利。第三方物流企業(yè)大打“價(jià)格戰(zhàn)”，各企業(yè)利潤空間狹小、生存壓力大，如何降低企業(yè)成本是企業(yè)經(jīng)營者長期思考的問題。

1 TSP模型及求解

1.1 TSP簡介

旅行商問題（TSP），也稱為貨郎擔(dān)問題、巡回銷售問題。該問題是一個(gè)典型的組合優(yōu)化問題，可以簡單地描述為：設(shè)有N個(gè)城市以及設(shè)定城市之間的旅行費(fèi)用，找一條走遍所有城市且費(fèi)用最低的旅行路線。旅行商問題是單回路運(yùn)輸問題中最為典型的一個(gè)問題。

配送路徑優(yōu)化問題可以說是對(duì)旅行商問題加以一定限制而形成的，這些限制包括：客戶有一定的貨物需求（貨供應(yīng)）數(shù)量且要求貨物在一定的時(shí)間范圍內(nèi)送達(dá)（或取走）、配送車輛的裝載量限制及一次配送的最大行駛距離限制等，即車輛路徑優(yōu)化問題是一個(gè)多約束的旅行商問題。

單回路運(yùn)輸問題是指在運(yùn)輸路線優(yōu)化時(shí)，在一個(gè)節(jié)點(diǎn)集合中，選擇一條合適的路徑遍歷所有的節(jié)點(diǎn)，并且要求閉合。單回路運(yùn)輸模型在運(yùn)輸模型中，主要用于單一車輛的路徑安排，目標(biāo)是在該車輛遍歷所有用戶的同時(shí)，達(dá)到所行駛距離最短，這類問題的兩個(gè)顯著特點(diǎn)：（1）單一性，只有一個(gè)回路；（2）遍歷性，經(jīng)過全部用戶，不可遺漏。

1.2 TSP數(shù)學(xué)模型

TSP問題的模型可以描述為：在給出的一個(gè)有n個(gè)定點(diǎn)網(wǎng)絡(luò)（有向或者無向）要求找出一個(gè)包含n個(gè)定點(diǎn)的具有最小消耗的環(huán)路。任何一個(gè)包含網(wǎng)絡(luò)中所有n個(gè)定點(diǎn)的環(huán)路被稱為回路。在旅行商問題中，要設(shè)法找到一條最小耗費(fèi)的回路。既然回路是包含所有定點(diǎn)的一個(gè)循環(huán)，故可以把任意一個(gè)點(diǎn)作為起點(diǎn)（也是重點(diǎn)），這也是TSP模型的一個(gè)特點(diǎn)。

TSP模型的數(shù)學(xué)描述為：

假設(shè)連通圖H，起定點(diǎn)集A。

定點(diǎn)間的距離為：

滿足：

決策變量：

求解TSP模型時(shí)，如果要得到精確的最優(yōu)解，最簡單的方法是枚舉法。對(duì)于小型問題，這也是一種十分有效的方法。但是對(duì)于大型問題，由于枚舉法的列舉次數(shù)為（n-1）次，若用枚舉法將是無法想象的。

另外，運(yùn)籌學(xué)領(lǐng)域的證書規(guī)劃的方法也可以用于結(jié)局部分TSP模型，其中分支定界法是一種比較實(shí)用的算法，但是該算法也是只能對(duì)一部分中小規(guī)模問題的TSP模型進(jìn)行求解，對(duì)于大多數(shù)問題的求解都存在一定的難度。由于此次研究是針對(duì)德邦某門店的循環(huán)取貨實(shí)證研究，主要采用Lingo軟件求解。該門店的特點(diǎn)如下：（1）需要規(guī)劃的取貨點(diǎn)少，規(guī)模不大；（2）取貨方式滿足旅行商問題的條件；（3）Lingo軟件能夠?qū)π∫?guī)模旅行商問題求解。

2 Lingo軟件程序及建模

2.1 Lingo程序簡介

Lingo全稱是Linear Interactive and General Optimizer的縮寫―交互式的線性和通用優(yōu)化求

解器。

Lingo是使建立和求解線性、非線性和整數(shù)最佳化模型更快、更簡單、更有效率的綜合工具。而且Lingo能夠提供強(qiáng)大的語言和快速的求解引擎來闡述和求解最佳化模型。

2.2 Lingo建模

簡單的模型表示：

model：

sets：

cities/1..7/：level；！level（！）=the level of city；

link（cities，cities）：

distan

ce，

x；！x（i，j）=1 if we use link i，j；

endsets

data：

distance=

enddata

n=@size（cities）；！the model size；

min=@sum（link（i，j）|i #ne# j：distance（i，j）* x（i，j））；

@FOR（cities（i）：

@sum（cities（j）|j #ne# i：x（j，i））=1；

@sum（cities（j）|j #ne# i：x（i，j））=1；

@for（cities（j）|j #gt# 1#and# j #ne# i：

level（j）>=level（i）+x（i，j）-（n-2）*（1-x（i，j））+（n-3）*x（j，i）；

）；

）；

@for（link：@bin（x））

@for（cities（i）|i#gt#1：

level（i）

3 實(shí)證研究

3.1 德邦物流簡介

德邦是國家“AAAAA”級(jí)物流企業(yè)，主營國內(nèi)公路運(yùn)輸業(yè)務(wù)。截至2013年10月末，公司已開設(shè)直營網(wǎng)點(diǎn)4200多家，服務(wù)網(wǎng)絡(luò)遍及全國，自有營運(yùn)車輛7200余臺(tái)，全國轉(zhuǎn)運(yùn)中心總面積超過88萬平方米。

德邦物流始終以客戶為中心隨時(shí)候命、持續(xù)創(chuàng)新，始終堅(jiān)持自建營業(yè)網(wǎng)點(diǎn)、自購進(jìn)口車輛、搭建最優(yōu)線路，優(yōu)化運(yùn)力成本，為客戶提供快速高效、便捷及時(shí)、安全可靠的服務(wù)體驗(yàn)，助力客戶創(chuàng)造最大的價(jià)值。

3.2 德邦物流某網(wǎng)點(diǎn)現(xiàn)狀

本文將以德邦物流某網(wǎng)點(diǎn)的上門取貨路徑做實(shí)證

研究。

該網(wǎng)點(diǎn)目前有一名門店經(jīng)理、三名營業(yè)員以及一名駕駛員。門店訂單來源主要來源于客戶上門訂單、電話訂單和網(wǎng)絡(luò)訂單。對(duì)于需要上門取貨的客戶，門店經(jīng)理根據(jù)排班表由一名營業(yè)員陪同司機(jī)駕車外出取貨。而為了達(dá)到較高的客戶滿意度，門店都是在客戶有需求的時(shí)候上門，一次出門提取的商家只有2～3家，并且出門時(shí)間不確定，完全根據(jù)客戶的需求。這樣的做法導(dǎo)致的結(jié)果是多次上門取貨汽車行駛距離長，燃油成本高，并且駕駛員需要全天處于待崗狀態(tài)，休息時(shí)間不確定，行車安全存在隱患。

3.3 路徑優(yōu)化實(shí)證

通過與服務(wù)商家協(xié)商制定配送時(shí)間表，保證取貨及時(shí)以及減少燃油成本，同時(shí)駕駛員也能有足夠的休息時(shí)間，確保行車安全。

本文選取了門店的幾個(gè)長期服務(wù)商家進(jìn)行實(shí)證研究，其中①點(diǎn)為門店所在位置，③點(diǎn)為工業(yè)園區(qū)，其中包含十余家企業(yè)，因距離近合并為一點(diǎn)。

各個(gè)節(jié)點(diǎn)之間的距離如表1所示。

各個(gè)節(jié)點(diǎn)之間的行車時(shí)間如表2所示。

將表1和表2中的數(shù)據(jù)輸入模型，應(yīng)用Lingo軟件建模運(yùn)行求解得到該問題的最短路徑為①②③⑤⑥⑧⑦④①，最短距離為56.6公里。

通過與相關(guān)商家協(xié)商，安排了如表3所示的行車時(shí)間表：

表3

節(jié)點(diǎn) 停留時(shí)間

① 14∶00（出發(fā)時(shí)間）

② 14∶04～14∶09

③ 14∶13～14∶53

⑤ 14∶09～15∶14

⑥ 15∶35～15∶40

⑧ 15∶46～15∶51

⑦ 15∶54～15∶59

④ 16∶26～16∶31

① 16∶45（回程時(shí)間）

注：根據(jù)對(duì)每次取貨流程耗費(fèi)時(shí)間的記錄，一般耗時(shí)4分鐘，我們選取五分鐘作為一個(gè)節(jié)點(diǎn)的標(biāo)準(zhǔn)時(shí)間；由于節(jié)點(diǎn)③處于工業(yè)區(qū)，周邊有十余家服務(wù)商家，停留時(shí)間為40

分鐘。

通過實(shí)證研究，循環(huán)取貨路徑得以優(yōu)化，行車距離減少，企業(yè)燃油成本能夠大幅減少，并且通過與商家協(xié)商，加強(qiáng)了伙伴關(guān)系，也提高了服務(wù)質(zhì)量。

參考文獻(xiàn)

[1] 趙春英，張鈴.求解貨郎擔(dān)問題（TSP）的佳點(diǎn)

集遺傳算法[J].計(jì)算機(jī)工程與應(yīng)用，2001，37

（3）：83-84.

[2] 蔣長兵，吳承建，彭揚(yáng).運(yùn)輸與配送管理建模與仿

真[M].北京：中國物資出版社，2011.

[3] 謝金星，薛毅.優(yōu)化建模與LINDO/LINGO軟件

篇8

[關(guān)鍵詞] 礦井 高壓供電網(wǎng)絡(luò) 區(qū)域選擇性聯(lián)鎖 短路保護(hù) 保護(hù)配置策略

中圖分類號(hào)：TD611 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：

1 煤礦井下高壓供電網(wǎng)絡(luò)中存在的問題

在我國煤礦企業(yè)安全生產(chǎn)事故中，由礦井供電直接或者間接引發(fā)的安全事故不斷呈現(xiàn)上升趨勢(shì)[1]。據(jù)相關(guān)資料顯示，煤塵爆炸與瓦斯等嚴(yán)重危害煤礦的安全事故中，有2/3以上與礦井供電系統(tǒng)問題有關(guān)[2]。

煤礦企業(yè)安全生產(chǎn)對(duì)煤礦井下供電工作提出了較高要求，要求100%安全生產(chǎn)和安全生產(chǎn)零事故[3，4]。當(dāng)前，多數(shù)煤礦企業(yè)建礦較早，且多次更新井下采煤設(shè)備，由于采礦工作面過度延伸，造成了高壓供電網(wǎng)絡(luò)過多分級(jí)，導(dǎo)致了礦井下高壓供電系統(tǒng)多發(fā)短路現(xiàn)象，繼電保護(hù)出現(xiàn)越過多級(jí)、拒動(dòng)或者誤動(dòng)跳閘，致使停電事故頻繁發(fā)生，嚴(yán)重時(shí)會(huì)威脅到礦井安全生產(chǎn)。通過考察研究我礦井生產(chǎn)的實(shí)際情況，發(fā)現(xiàn)我礦供電系統(tǒng)的實(shí)際結(jié)構(gòu)與煤礦井下巷道的走向和分布有一定關(guān)系，在很大程度上影響了煤礦供電系統(tǒng)構(gòu)建[5]。本文結(jié)合圖論，統(tǒng)一規(guī)劃了礦井下的高壓供電網(wǎng)絡(luò)，通過使用網(wǎng)絡(luò)通訊技術(shù)實(shí)現(xiàn)煤礦礦井高壓供電網(wǎng)絡(luò)繼電保護(hù)信息的一致共享，通過開關(guān)智能控制器的統(tǒng)一控制及綜合判斷，實(shí)現(xiàn)了煤礦井下供電線路繼電之間的保護(hù)閉鎖，從本質(zhì)上解決煤礦井下高壓供電系統(tǒng)中存在的越級(jí)跳閘問題。

2 圖論在礦井供電網(wǎng)絡(luò)中的應(yīng)用

圖論是一種運(yùn)籌學(xué)分支，近年來得到了廣泛應(yīng)用，可以使用圖論方法解決電力系統(tǒng)的狀態(tài)估計(jì)、可靠性分析及規(guī)劃等問題。通常情況下，圖論研究抽象圖形可以用施工流程、運(yùn)輸系統(tǒng)或者電氣圖形等形式表示。當(dāng)前，電力系統(tǒng)設(shè)計(jì)規(guī)劃中較多應(yīng)用的是最小費(fèi)用流問題、最大流問題、最短路徑問題等[6]。

本文結(jié)合圖論，針對(duì)煤礦井井下高壓供電網(wǎng)絡(luò)系統(tǒng)提出了安全可行的網(wǎng)絡(luò)化供電系統(tǒng)保護(hù)策略。主要介紹如下：

⑴在煤礦井下供電系統(tǒng)中使用網(wǎng)絡(luò)優(yōu)化技術(shù)，實(shí)現(xiàn)了多級(jí)繼電保護(hù)裝置間的聯(lián)鎖保護(hù)；⑵采用礦井供電網(wǎng)絡(luò)優(yōu)化與保護(hù)配置相互結(jié)合的供電線路級(jí)數(shù)設(shè)計(jì)策略，盡量將煤礦井下供電線路級(jí)數(shù)減少到最低；⑶減小供電系統(tǒng)回路中出現(xiàn)的低壓誤動(dòng)：通過改變欠電壓釋保護(hù)放回路的低壓動(dòng)作值來實(shí)現(xiàn)；⑷以保障選擇性為前提，盡可能縮短各保護(hù)間的時(shí)間級(jí)差，即改變過負(fù)荷保護(hù)、無時(shí)限電流速斷和限時(shí)電流速斷間的時(shí)間級(jí)差，將0. 5s改成100～300ms[7]。

3 智能控制模塊的工作原理及構(gòu)成

本文中所述智能控制模塊由光纖耦合器、光纖通信元件及單片機(jī)等主要元件構(gòu)成。其中，單片機(jī)成功輸入、輸出各種信號(hào)，通過分析各種信號(hào)，發(fā)出跳閘或者自鎖信號(hào)。信號(hào)轉(zhuǎn)換工作由光纖耦合器和光纖通信元件共同完成，且網(wǎng)絡(luò)通信在上、下級(jí)之間進(jìn)行。跳閘信號(hào)或系統(tǒng)故障信號(hào)的開合都可以由單片機(jī)系統(tǒng)的控制開關(guān)（I/O）裝置的分勵(lì)線圈回路控制，借此實(shí)現(xiàn)跳閘操作。

4 煤礦井下高壓供電網(wǎng)絡(luò)區(qū)域的選擇性聯(lián)鎖保護(hù)

煤礦井下高壓供電網(wǎng)絡(luò)的三級(jí)區(qū)域選擇性保護(hù)聯(lián)鎖的基本結(jié)構(gòu)如圖2所示，即將一個(gè)智能控制模塊安裝在原有開關(guān)裝置上，使之配合原有繼電保護(hù)裝置當(dāng)中的電流速斷保護(hù)工作，以順利實(shí)現(xiàn)區(qū)域選擇性的聯(lián)鎖保護(hù)。原有電流速斷保護(hù)的信號(hào)回路中串聯(lián)有該智能控制模塊，所以不會(huì)改變?cè)械睦^電保護(hù)裝置功能。

圖2中所示的各級(jí)繼電保護(hù)裝置中動(dòng)作閉鎖功能的原理如下：在各級(jí)繼電保護(hù)裝置中的電流速斷保護(hù)中使用智能控制模塊，并對(duì)其進(jìn)行延時(shí)閉鎖，在各級(jí)保護(hù)間進(jìn)行可行的信息傳遞和通信聯(lián)絡(luò)，也就是在發(fā)生故障后，智能控制模塊能及時(shí)接到速斷保護(hù)信號(hào)，在有效延時(shí)時(shí)間內(nèi)行聯(lián)絡(luò)閉鎖通信，將各級(jí)保護(hù)間的操作時(shí)間安排好。如果故障線路上安裝的保護(hù)裝置未能在在規(guī)定的延時(shí)時(shí)間內(nèi)接到由下級(jí)繼電保護(hù)裝置中智能控制模塊發(fā)過來的閉鎖信號(hào)，則需要將本保護(hù)裝置發(fā)來的閉鎖信號(hào)解除，接著由本級(jí)保護(hù)裝置發(fā)出的速斷保護(hù)動(dòng)作來執(zhí)行。而系統(tǒng)末端開關(guān)裝置中所安裝的智能控制模塊無需延時(shí)閉鎖。

區(qū)域選擇性聯(lián)鎖保護(hù)優(yōu)化方案發(fā)揮作用的關(guān)鍵是要完成煤礦井下各種智能控制模塊的成功通信，對(duì)各種智能控制模塊控制程序的綜合性判斷要依據(jù)控制模塊自身及各級(jí)模塊傳來的信號(hào)進(jìn)行，并發(fā)出跳閘或者自鎖的控制信號(hào)，然后結(jié)合硬件和軟件，以順利實(shí)現(xiàn)煤礦井下高壓供電網(wǎng)絡(luò)區(qū)域的選擇性保護(hù)聯(lián)鎖功能，依此來解決供電系統(tǒng)中存在的越級(jí)跳閘問題[8]。

由以上內(nèi)容可以看出，當(dāng)出現(xiàn)線路故障時(shí)，可以借助上下級(jí)通信信號(hào)，安排各級(jí)保護(hù)裝置所具有的速斷保護(hù)動(dòng)作，實(shí)現(xiàn)保護(hù)裝置的保護(hù)聯(lián)鎖，避免越級(jí)跳閘現(xiàn)象的出現(xiàn)以及事故擴(kuò)大；三級(jí)線路可以承受的最大短路能量沖擊時(shí)間是0.2s，既降低了三級(jí)線路所承受的內(nèi)部應(yīng)力及較重電動(dòng)力，又減少了故障電流帶來的沖擊，因此達(dá)到了較好的保護(hù)效果[2，5]。

5 結(jié)語

綜上所述，區(qū)域選擇性聯(lián)鎖保護(hù)方案指將一個(gè)智能控制模塊安裝到原有的礦用開關(guān)上，從而與原有速斷保護(hù)裝置配合工作，借此實(shí)現(xiàn)

煤礦井下高壓供電線路的閉鎖保護(hù)。該智能控制模塊在僅串聯(lián)在速斷保護(hù)脫扣信號(hào)回路中，不改變保護(hù)裝置的傳統(tǒng)功能。該方案既能降低短路電流對(duì)供電網(wǎng)絡(luò)系統(tǒng)的影響，又能實(shí)現(xiàn)工作配合的完全選擇性，值得將其應(yīng)用于煤礦井下高壓供電網(wǎng)絡(luò)中。

參考文獻(xiàn)

[1]劉士光. 煤礦井下高壓供電系統(tǒng)過電壓的分析與預(yù)防[J]. 科技創(chuàng)新導(dǎo)報(bào)，2013，19：23.

[2]余存泰. 一種區(qū)域選擇性聯(lián)鎖保護(hù)裝置的設(shè)計(jì)[J]. 低壓電器，2011，03：18-21.

[3]王光超，史世杰，張根現(xiàn)，鄒有明. 煤礦井下高壓供電網(wǎng)絡(luò)優(yōu)化[J]. 中州煤炭，2011，06：80-81.

[4]高鋒. 煤礦井下3.3 kV供電網(wǎng)絡(luò)漏電故障保護(hù)研究[J]. 科學(xué)技術(shù)與工程，2012，29：7525-7531.

[5]衛(wèi)小兵. 煤礦井下高壓供電系統(tǒng)繼電保護(hù)配置分析[J]. 科技與企業(yè)，2013，13：150.

[6]任憲友. 煤礦井上、下高壓供電方式的改造[J]. 電子世界，2013，11：57.

篇9

關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò)；關(guān)聯(lián)性風(fēng)險(xiǎn)；無標(biāo)度網(wǎng)絡(luò)；小世界網(wǎng)絡(luò)

中圖分類號(hào)：F83

文獻(xiàn)標(biāo)識(shí)碼：A

doi：10.19311/ki.16723198.2016.30.051

1引言

伴隨金融自由化、復(fù)雜化趨勢(shì)的發(fā)展，金融機(jī)構(gòu)之間更緊密地相互聯(lián)系在一起，這種相互聯(lián)系增加了金融危機(jī)迅速蔓延的可能性，由次貸危機(jī)所引發(fā)的全球金融危機(jī)顯示了金融傳染的危害性。研究表明，金融系統(tǒng)的微觀特征以及展現(xiàn)的宏觀結(jié)構(gòu)對(duì)于系統(tǒng)內(nèi)部風(fēng)險(xiǎn)傳染的程度具有重要影響。近年來，統(tǒng)計(jì)物理學(xué)領(lǐng)域在復(fù)雜網(wǎng)絡(luò)的形成及特征等方面獲得顯著進(jìn)展，在諸多領(lǐng)域中，基于復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)理論分析個(gè)體間結(jié)構(gòu)及關(guān)聯(lián)性卓有成效，這為本文的研究提供了堅(jiān)實(shí)的理論基礎(chǔ)和有益的借鑒。

作為貨幣市場的核心以及銀行間業(yè)務(wù)的重要組成部分，同業(yè)拆借市場平穩(wěn)運(yùn)行具有重要意義。同業(yè)拆借市場的平穩(wěn)運(yùn)行對(duì)于調(diào)節(jié)機(jī)構(gòu)之間的流動(dòng)性以及貨幣政策的實(shí)施至關(guān)重要。同業(yè)拆借市場因其市場化的運(yùn)作以及高效率的機(jī)制使得同業(yè)拆借利率及時(shí)、靈敏地反映了市場資金的供求。因此在貨幣政策執(zhí)行中，中央銀行將同業(yè)拆借利率作為反映金融系統(tǒng)中資金供求狀況重要指標(biāo)，同業(yè)拆借利率成為貨幣市場上的基準(zhǔn)利率之一。同時(shí)，銀行同業(yè)拆借市場也是商業(yè)銀行之間進(jìn)行短期資金借貸的場所，是一國金融體系的重要組成部分。銀行主要依靠同業(yè)拆借市場進(jìn)行流動(dòng)性管理，銀行間市場的發(fā)展為銀行間資金調(diào)劑提供了順暢渠道.作為貨幣市場的核心部分，中國同業(yè)拆借市場進(jìn)入了穩(wěn)定發(fā)展階段，市場規(guī)模逐步擴(kuò)大，2013年同業(yè)拆借市場總規(guī)模超過45萬億元，其中銀行與銀行之間拆借交易成交量占整個(gè)市場成交量的80%以上。然而，同業(yè)間風(fēng)險(xiǎn)暴露也使得銀行間的關(guān)聯(lián)性風(fēng)險(xiǎn)增大。因此，基于同業(yè)拆借產(chǎn)生的銀行間的關(guān)聯(lián)性風(fēng)險(xiǎn)是危機(jī)傳染的重要渠道之一。

為了提高分析結(jié)果的穩(wěn)健性，在基于同業(yè)拆借市場分析的基礎(chǔ)之上，利用上市銀行股票收益的格蘭杰因果檢驗(yàn)進(jìn)一步分析銀行體系網(wǎng)絡(luò)結(jié)構(gòu)特征。

2文獻(xiàn)綜述及理論分析

由于銀行之間存在復(fù)雜的債權(quán)債務(wù)關(guān)系，導(dǎo)致銀行之間形成緊密的內(nèi)在關(guān)聯(lián)性，一旦某個(gè)銀行倒閉，銀行間的信貸關(guān)系使得破產(chǎn)危機(jī)在銀行之間傳染。要實(shí)現(xiàn)對(duì)系統(tǒng)性風(fēng)險(xiǎn)有效監(jiān)管，對(duì)關(guān)聯(lián)性風(fēng)險(xiǎn)進(jìn)行有效評(píng)估至關(guān)重要。國際貨幣基金組織在《全球金融穩(wěn)定報(bào)告》（2009）介紹了評(píng)估系統(tǒng)性關(guān)聯(lián)風(fēng)險(xiǎn)的四種方法：網(wǎng)絡(luò)傳導(dǎo)分析法、共同風(fēng)險(xiǎn)模型法、困境依賴矩陣法以及違約強(qiáng)度模型法。金融系統(tǒng)是由多子系統(tǒng)、多種性質(zhì)參與主體以及復(fù)雜交互作用關(guān)系構(gòu)成的復(fù)雜網(wǎng)絡(luò)系統(tǒng)，這使得基于單個(gè)機(jī)構(gòu)的分析無法有效評(píng)估整個(gè)金融系統(tǒng)所面臨的風(fēng)險(xiǎn)。復(fù)雜網(wǎng)絡(luò)金融理論認(rèn)為，金融體系的內(nèi)部結(jié)構(gòu)必然與其功能以及運(yùn)行狀態(tài)有緊密的關(guān)聯(lián)性。復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)通常可以描述金融系統(tǒng)的共同特征，復(fù)雜網(wǎng)絡(luò)理論通過研究金融系統(tǒng)結(jié)構(gòu)的拓?fù)涮卣鳎瑥亩鴮?duì)金融系統(tǒng)運(yùn)行規(guī)律進(jìn)行有效的揭示并達(dá)到控制風(fēng)險(xiǎn)的目的。該理論將金融網(wǎng)絡(luò)用抽象圖來替代，就是用抽象的節(jié)點(diǎn)來表示金融網(wǎng)絡(luò)中的個(gè)體，并用兩個(gè)節(jié)點(diǎn)間的連線表示個(gè)體之間的某種關(guān)聯(lián)性，金融系統(tǒng)中個(gè)體之間的關(guān)聯(lián)性通常是基于債權(quán)債務(wù)關(guān)系而產(chǎn)生。通過分析反映金融網(wǎng)絡(luò)結(jié)構(gòu)特征一些參數(shù)指標(biāo)，可以揭示金融系統(tǒng)的結(jié)構(gòu)與特征。伴隨復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)理論的發(fā)展，將復(fù)雜網(wǎng)絡(luò)的研究方法運(yùn)用到金融領(lǐng)域問題的研究得到了極大的發(fā)展，尤其是針對(duì)系統(tǒng)性風(fēng)險(xiǎn)問題，復(fù)雜網(wǎng)絡(luò)金融理論基于系統(tǒng)論視角分析金融體系內(nèi)部關(guān)聯(lián)性風(fēng)險(xiǎn)，二者之間在邏輯關(guān)系上存在一致性。

利用網(wǎng)絡(luò)結(jié)構(gòu)理論研究關(guān)聯(lián)性風(fēng)險(xiǎn)主要包括微觀路徑和宏觀路徑兩種方法。在微觀路徑研究中，主要是運(yùn)用風(fēng)險(xiǎn)管理、復(fù)雜網(wǎng)絡(luò)等領(lǐng)域的知識(shí)，并結(jié)合金融風(fēng)險(xiǎn)的發(fā)生機(jī)制研究穩(wěn)定性較高的金融網(wǎng)絡(luò)所需具備的微觀特征。該領(lǐng)域的早期研究關(guān)注銀行間的連接方式及連接的緊密程度，Allen和Gale（2000）假設(shè)流動(dòng)性沖擊來自于存款者取款時(shí)間的不確定性，當(dāng)網(wǎng)絡(luò)處于完全連接狀態(tài)，網(wǎng)絡(luò)系統(tǒng)具有較高的穩(wěn)定性，而當(dāng)網(wǎng)絡(luò)處于不完全連接狀態(tài)時(shí)，系統(tǒng)會(huì)變得較為脆弱。Gai（2010）借鑒其他學(xué)者研究復(fù)雜網(wǎng)絡(luò)的數(shù)學(xué)方法，通過模擬金融網(wǎng)絡(luò)的形成過程分析穩(wěn)健性的金融網(wǎng)絡(luò)應(yīng)具備的特征，得出的結(jié)論是最短路徑長度應(yīng)適當(dāng)偏長。部分學(xué)者嘗試?yán)眠\(yùn)籌法判斷最優(yōu)微觀結(jié)構(gòu)，Leitner（2005）運(yùn)用運(yùn)籌學(xué)理論，得出最優(yōu)金融網(wǎng)絡(luò)的規(guī)模特征即每個(gè)小群體內(nèi)最優(yōu)節(jié)點(diǎn)數(shù)量為5。在宏觀路徑研究中，主要基于節(jié)點(diǎn)度、聚類系數(shù)、最短路徑長度等微觀指標(biāo)研究金融網(wǎng)絡(luò)所呈現(xiàn)的宏觀結(jié)構(gòu)。Hajime Inaoka等（2004）利用銀行交易結(jié)算數(shù)據(jù)分析了銀行網(wǎng)絡(luò)結(jié)構(gòu)特征，研究表明銀行網(wǎng)絡(luò)具有自相似以及無標(biāo)度特征。此外，并從理論上分析了不同網(wǎng)絡(luò)結(jié)構(gòu)特征下的穩(wěn)定性。該文將沖擊分為隨機(jī)性沖擊與選擇性沖擊兩種類別。對(duì)于隨機(jī)網(wǎng)絡(luò)，隨機(jī)性沖擊與選擇性沖擊的效應(yīng)趨于一致，而對(duì)于無標(biāo)度網(wǎng)絡(luò)，選擇性沖擊的效應(yīng)遠(yuǎn)遠(yuǎn)大于隨機(jī)性沖擊。Michael Boss、Helmut Elsinger等（2004）基于同業(yè)拆借數(shù)據(jù)，并利用最小交互熵方法對(duì)奧地利銀行間市場網(wǎng)絡(luò)結(jié)構(gòu)特征進(jìn)行了分析，研究表明少數(shù)銀行具有大量關(guān)聯(lián)性，而多數(shù)銀行具有較少的連接。此外，奧地利銀行網(wǎng)絡(luò)呈現(xiàn)出群體結(jié)構(gòu)特征，群體內(nèi)部關(guān)聯(lián)性緊密，而群體之間的連接較為稀疏。Giulia Iori等（2008）利用隔夜拆借數(shù)據(jù)分析了意大利銀行間網(wǎng)絡(luò)結(jié)構(gòu)特征及其演化特征。研究表明銀行間網(wǎng)絡(luò)具有隨機(jī)網(wǎng)絡(luò)的特征，并且呈現(xiàn)出度增加而強(qiáng)度減弱的狀態(tài)，研究還發(fā)現(xiàn)不同規(guī)模主體行為具備差異性。Nier（2007）研究表明銀行網(wǎng)絡(luò)集中度對(duì)關(guān)聯(lián)性風(fēng)險(xiǎn)產(chǎn)生的影響并不是單調(diào)的，在一定的閾值范圍內(nèi)，集中度增加⒌賈鹿亓性風(fēng)險(xiǎn)增大，但當(dāng)集中度超過一定的閾值范圍后，集中度增加反而會(huì)降低關(guān)聯(lián)性風(fēng)險(xiǎn)。Simone Lenzu（2012）基于市場主體的行為探討了銀行網(wǎng)絡(luò)形成的內(nèi)生機(jī)制，并基于模擬分析風(fēng)險(xiǎn)傳染的特征。該文基于關(guān)聯(lián)形成的內(nèi)生機(jī)制形成了隨機(jī)網(wǎng)絡(luò)與無標(biāo)度網(wǎng)絡(luò)，為了研究不同網(wǎng)絡(luò)的穩(wěn)健性，對(duì)網(wǎng)絡(luò)進(jìn)行隨機(jī)性沖擊模擬，結(jié)果發(fā)現(xiàn)無標(biāo)度網(wǎng)絡(luò)比隨機(jī)網(wǎng)絡(luò)具有更高的脆弱性。李守偉等（2010）通過構(gòu)建有向網(wǎng)絡(luò)模型，通過分析隨機(jī)性攻擊與選擇性攻擊對(duì)網(wǎng)絡(luò)成分的影響研究銀行間網(wǎng)絡(luò)的穩(wěn)定性。研究結(jié)果表明，銀行間網(wǎng)絡(luò)對(duì)于選擇性攻擊具有較低的穩(wěn)定性，而對(duì)于隨機(jī)性攻擊具有較高的穩(wěn)定性。

上述研究表明，金融網(wǎng)絡(luò)的微觀特征以及展現(xiàn)的宏觀結(jié)構(gòu)對(duì)于分析金融系統(tǒng)的關(guān)聯(lián)性風(fēng)險(xiǎn)具有重要意義。本文以復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)理論為基礎(chǔ)，基于銀行間市場同業(yè)拆借關(guān)系以及上市銀行股票收益的格蘭杰因果檢驗(yàn)分析了銀行體系網(wǎng)絡(luò)結(jié)構(gòu)特征及關(guān)聯(lián)性風(fēng)險(xiǎn)。具體結(jié)構(gòu)安排如下：第三部分主要介紹矩陣法網(wǎng)絡(luò)模型及因果網(wǎng)絡(luò)模型；第四部分對(duì)銀行網(wǎng)絡(luò)結(jié)構(gòu)特征進(jìn)行實(shí)證分析；最后一部分內(nèi)容對(duì)于本文的主要觀點(diǎn)與結(jié)論進(jìn)行總結(jié)，并闡述了相關(guān)的政策啟示。

3研究設(shè)計(jì)

3.1基于矩陣法構(gòu)建銀行網(wǎng)絡(luò)模型

首先基于最大熵的方法估計(jì)銀行間同業(yè)拆借矩陣，并利用RAS算法進(jìn)行優(yōu)化，該方法意味著各銀行盡量可能均勻分布資產(chǎn)；然后利用閾值法構(gòu)建銀行網(wǎng)絡(luò)模型，由于在實(shí)際拆借行為中不可能任意兩個(gè)銀行間都存在雙向信用拆借關(guān)系，因此假設(shè)只有兩個(gè)銀行之間拆借規(guī)模超過一定閾值水平才認(rèn)為兩個(gè)銀行之間存在拆借關(guān)系；最后計(jì)算度、聚類系數(shù)以及平均路徑長度等相關(guān)指標(biāo)進(jìn)而揭示銀行間同業(yè)市場網(wǎng)絡(luò)結(jié)構(gòu)特征及關(guān)聯(lián)性風(fēng)險(xiǎn)。

由于只能獲取各個(gè)銀行同業(yè)拆借的總資產(chǎn)和總負(fù)債數(shù)據(jù)，無法獲得各個(gè)銀行相互之間交易的具體數(shù)據(jù)，因此需要基于總資產(chǎn)和總負(fù)債數(shù)據(jù)利用熵最優(yōu)化法測(cè)算銀行同業(yè)拆借矩陣。銀行間市場同業(yè)拆借關(guān)系可以用矩陣X=（xi，j）N×N表示。其中，xi，j表示銀行i對(duì)銀行j的同業(yè)資產(chǎn)頭寸，N表示銀行數(shù)量。設(shè)ai表示銀行i對(duì)其他銀行的資產(chǎn)總額，ai=∑Nj=1xi，j，lj表示銀行對(duì)其他銀行的負(fù)債總額，lj=∑Nj=1xi，j。在一個(gè)具有N家銀行的系統(tǒng)中，X包含N2個(gè)元素，xi，j的具體值是未知的，但是ai和lj是已知的，在缺少其他約束l件下可以選擇最大化雙邊交易不確定性分布（信息熵最大化）。通過標(biāo)準(zhǔn)化，X視為聯(lián)合分布函數(shù)f（a，l）的實(shí)現(xiàn)值，而a和l可視為邊際分布函數(shù)f（a）和f（b）的實(shí)現(xiàn)值。如果f（a）和f（b）相互獨(dú)立，通過最大熵的方法可以得出xi，j=ai×lj。這種方法意味著i銀行對(duì)j銀行的資產(chǎn)額度取決于i銀行對(duì)其他銀行的資產(chǎn)總額以及j銀行對(duì)其他銀行的負(fù)債總額。通過上述方法可以計(jì)算出矩陣X，但是銀行不能與自身發(fā)生借貸關(guān)系，也就意味著xi，i=0，因此需要對(duì)矩陣X進(jìn)行修正，修正后的矩陣為X*。求解X*等同于如下問題求解：

min∑Ni=1∑Nj=1x*i，jln（x*i，j/xi，j）

s.t.ai=∑Nj=1x*i，j，lj=∑Nj=1x*i，jx*i，j≥0

上述最優(yōu)化的解可以利用RAS法計(jì)算獲得，從而得到銀行間同業(yè)拆借矩陣。在銀行間同業(yè)拆借矩陣的基礎(chǔ)上，本文采用閾值法構(gòu)建銀行網(wǎng)絡(luò)特征。由于大部分銀行的銀行間資產(chǎn)、負(fù)債占所有銀行間資產(chǎn)、負(fù)債的比例在區(qū)間（0，0.01）之間，因此，我們將閾值c界定在（0.00001，0.0001）之間。如果當(dāng)兩銀行之間同業(yè)拆借比例大于閾值c，則認(rèn)為兩銀行之間存在拆借關(guān)系，在復(fù)雜網(wǎng)絡(luò)理論中意味著兩節(jié)點(diǎn)之間存在邊進(jìn)行連接。本方法利用各個(gè)銀行的合并報(bào)表的拆借數(shù)據(jù)進(jìn)行實(shí)證分析。我們使用兩組數(shù)據(jù)進(jìn)行分析，一組是73家銀行2015年的同業(yè)拆借數(shù)據(jù)，另外一組是16家上市銀行2008-2015年間的同業(yè)拆借數(shù)據(jù)。

3.2因果網(wǎng)絡(luò)模型

在一個(gè)由n個(gè)金融機(jī)構(gòu)構(gòu)成的金融體系中，Ri表示金融機(jī)構(gòu)i的股票收益率，Rm表示市場回報(bào)率，Rf表示無風(fēng)險(xiǎn)利率，則資本資產(chǎn)定價(jià)模型可以表示如下：

Ri―Rf=βi（Rm―Rf）+εii=1，2，……，n

則余項(xiàng)εi反映公司i特定風(fēng)險(xiǎn)溢價(jià)，本文定義Li=εi反映金融機(jī)構(gòu)i所承擔(dān)的公司風(fēng)險(xiǎn)。由于金融時(shí)間序列數(shù)據(jù)通常具有波動(dòng)集聚現(xiàn)象，本文利用GARCH（1，1）模型來描述公司風(fēng)險(xiǎn)的動(dòng)態(tài)相關(guān)性。

Li，t=μi+σi，tZi，t

σ2i，t=wi+αiu2i，t-1+βiσ2i，t―1

其中，μi表示條件均值，σi，t表示條件標(biāo)準(zhǔn)誤，Zi，t表示白噪聲過程，ui，t=σi，tZi，t。

如果時(shí)間序列Zi，t包含時(shí)間序列Zj，t的有效信息，有助于提高Zj，t預(yù)測(cè)精度，則認(rèn)為Zi，t是Zj，t的格蘭杰原因。

Zj，t+1=ajZj，t+bjiZi，t+ej，t+1

Zi，t+1=aiZi，t+bijZj，t+ei，t+1

如果bji顯著不為0，則Zi，t是Zj，t的格蘭杰原因。類似，如果bij顯著不為0，則Zj，t是Zi，t的格蘭杰原因。基于因果關(guān)系檢驗(yàn)結(jié)果界定金融機(jī)構(gòu)之間的網(wǎng)絡(luò)關(guān)系，如果存在因果關(guān)系，則表明代表金融機(jī)構(gòu)的節(jié)點(diǎn)之間存在有向邊所連接。本方法利用16家上市銀行2015年股票收益數(shù)據(jù)分析銀行體系的因果網(wǎng)絡(luò)結(jié)構(gòu)。

4實(shí)證分析

4.1銀行網(wǎng)絡(luò)節(jié)點(diǎn)度分布

為了分析銀行間市場網(wǎng)絡(luò)節(jié)點(diǎn)度分布情況，將閾值設(shè)定為0.00001、0.00003、0.00005、0.00007四種狀態(tài)，分別計(jì)算每一對(duì)應(yīng)閾值狀態(tài)下各個(gè)節(jié)點(diǎn)的度，為了能夠更清晰地反映度的分布特征，我們將各節(jié)點(diǎn)度劃分到若干等距區(qū)間，即[0，9][10-19][20-29][30-39][40-49]，然后分別計(jì)算每一區(qū)間的概率，利用各個(gè)區(qū)間的概率分布來描述節(jié)點(diǎn)度分布狀況。圖1揭示了不同閾值水平下節(jié)點(diǎn)度分布狀況，我們發(fā)現(xiàn)節(jié)點(diǎn)度分布具備冪律分布的基本形態(tài)。

上述結(jié)論是建立在一定假設(shè)前提的基礎(chǔ)之上得出的，為了驗(yàn)證該方法的有效性，我們可以從另外一個(gè)角度分析銀行市場的無標(biāo)度網(wǎng)絡(luò)特征。我們分析了16家上市銀行2008年―2015年的同業(yè)拆借的總量，實(shí)際數(shù)據(jù)表明16家銀行借入資金總量與借出資金總量呈現(xiàn)出穩(wěn)步上升趨勢(shì)，如圖2所示。而且根據(jù)2015年的完整數(shù)據(jù)，16家銀行同業(yè)拆借的總量占樣本73家銀行同業(yè)拆借的總量的比例達(dá)到38%。通過以上分析，進(jìn)一步說明銀行間市場網(wǎng)絡(luò)存在一些中心銀行，銀行間同業(yè)拆借業(yè)務(wù)主要發(fā)生在這些銀行之間以及這些銀行與其他銀行之間。這些處于中心的銀行一旦出現(xiàn)危機(jī)，很容易通過他們的高連接狀態(tài)而影響整個(gè)銀行體系。H.A.Degryse（2004）將銀行間市場的這種結(jié)構(gòu)稱作貨幣中心結(jié)構(gòu)，從風(fēng)險(xiǎn)傳染的角度來看，決定整個(gè)銀行體系穩(wěn)定性的是處于核心地位的銀行，而其他規(guī)模較小的銀行影響有限。根據(jù)H.A.Degryse（2004）研究表明，當(dāng)處于貨幣中心地位的銀行倒閉時(shí)，貨幣中心型的市場結(jié)構(gòu)比完備型的市場結(jié)構(gòu)具備更強(qiáng)的傳染性，而當(dāng)處于中心地位的銀行平穩(wěn)運(yùn)營時(shí)，貨幣中心型的市場結(jié)構(gòu)更具穩(wěn)健性。

因此，我們可以得出結(jié)論，銀行間市場網(wǎng)絡(luò)具有無標(biāo)度網(wǎng)絡(luò)特征，即少數(shù)銀行具有較大的度，絕大多數(shù)銀行具有較小的度。無標(biāo)度網(wǎng)絡(luò)特征意味著銀行間市場對(duì)于隨機(jī)性沖擊具有較強(qiáng)的穩(wěn)健性，而對(duì)于選擇性沖擊具有脆弱性。因?yàn)榻^大多數(shù)銀行具有較小的度，因此無標(biāo)度網(wǎng)絡(luò)在遭受隨機(jī)沖擊時(shí)，這些具有較小度的銀行最容易遭到破壞，但這些銀行又只有較少的連接，所以這些銀行的危機(jī)對(duì)整個(gè)銀行體系的影響有限。但當(dāng)銀行系統(tǒng)中具有較大度的銀行面臨危機(jī)時(shí)，局部危機(jī)會(huì)迅速擴(kuò)散到整個(gè)銀行體系進(jìn)而產(chǎn)生系統(tǒng)性危機(jī)。

4.2銀行網(wǎng)絡(luò)聚類系數(shù)及平均路徑長度分析

理論分析表明，如果一個(gè)網(wǎng)絡(luò)同時(shí)具有較大的集聚系數(shù)和較小的平均路徑長度，那么這樣的網(wǎng)絡(luò)稱為小世界網(wǎng)絡(luò)。在上文分析的基礎(chǔ)上，利用同業(yè)拆借矩陣計(jì)算不同閾值水平下的平均路徑長度與聚類系數(shù)。為了獲得因果網(wǎng)絡(luò)結(jié)構(gòu)，需要對(duì)16家上市銀行股票收益數(shù)據(jù)兩兩之間進(jìn)行格蘭杰因果關(guān)系檢驗(yàn)。首先，基于資本資產(chǎn)定價(jià)模型計(jì)算β系數(shù)；其次，利用殘差數(shù)據(jù)，基于GARCH（1，1）模型進(jìn)行參數(shù)估計(jì)；最后，在顯著水平為10%的條件下進(jìn)行格蘭杰因果關(guān)系檢驗(yàn)。表1為兩種不同方法所計(jì)算出來的平均路徑長度和聚類系數(shù)。

從上述數(shù)據(jù)可以看出，銀行間市場網(wǎng)絡(luò)具有較大的聚類系數(shù)和較小的平均路徑長度，這說明銀行間市場具有典型的小世界網(wǎng)絡(luò)特征。小世界網(wǎng)絡(luò)特征意味著一旦一個(gè)銀行出現(xiàn)嚴(yán)重危機(jī)，就會(huì)迅速傳導(dǎo)給并無直接關(guān)聯(lián)的其他銀行，從而導(dǎo)致整個(gè)銀行體系陷入危機(jī)狀態(tài)。因此，銀行間市場小世界網(wǎng)絡(luò)特征是導(dǎo)致關(guān)聯(lián)性系統(tǒng)性風(fēng)險(xiǎn)的重要原因。需要說明的是，在兩種不同的分析方法下，平均路徑長度趨于一致，但是聚類系數(shù)相差較大，這是由于相關(guān)指標(biāo)值受閾值水平的影響較大。但根據(jù)網(wǎng)絡(luò)結(jié)構(gòu)理論表明，即使是0.21的聚類系數(shù)水平仍然可以顯示網(wǎng)絡(luò)結(jié)構(gòu)的無標(biāo)度特征。

5結(jié)論及政策啟示

5.1銀行同業(yè)市場網(wǎng)絡(luò)結(jié)構(gòu)特征及系統(tǒng)性風(fēng)險(xiǎn)分析

本文由復(fù)雜網(wǎng)絡(luò)金融理論與系統(tǒng)性風(fēng)險(xiǎn)管理之間的內(nèi)在聯(lián)系出發(fā)，探討網(wǎng)絡(luò)結(jié)構(gòu)對(duì)銀行間關(guān)聯(lián)性風(fēng)險(xiǎn)產(chǎn)生的重要影響，基與銀行間資產(chǎn)負(fù)債數(shù)據(jù)，通過理論與實(shí)證相結(jié)合的分析方法得出以下幾點(diǎn)結(jié)論：

（1）基于系統(tǒng)論的視角，進(jìn)一步明確了系統(tǒng)性風(fēng)險(xiǎn)的內(nèi)涵。系統(tǒng)性風(fēng)險(xiǎn)主要表現(xiàn)在兩個(gè)方面：一是金融系統(tǒng)作為整體與實(shí)體經(jīng)濟(jì)相互作用過程中，導(dǎo)致系統(tǒng)性風(fēng)險(xiǎn)積聚；二是金融體系內(nèi)部的關(guān)聯(lián)性風(fēng)險(xiǎn)，尤其表現(xiàn)為金融機(jī)構(gòu)之間的風(fēng)險(xiǎn)溢出效應(yīng)。

（2）各個(gè)銀行的同業(yè)拆借規(guī)模存在很大差異性，以中、農(nóng)、工、建為代表的16家上市銀行形成了同業(yè)拆借網(wǎng)絡(luò)的中心，其他銀行之間雖然也存在業(yè)務(wù)往來，但規(guī)模較小，對(duì)銀行間市場的影響有限。

（3）實(shí)證上，通過閾值法對(duì)度、平均路徑長度以及聚類系數(shù)等相關(guān)指標(biāo)進(jìn)行分析，研究結(jié)果表明銀行間網(wǎng)絡(luò)具備小網(wǎng)絡(luò)特征以及無標(biāo)度特征。這意味著銀行間市場對(duì)于隨機(jī)性沖擊具有較強(qiáng)的穩(wěn)健性，而對(duì)選擇性沖擊具有較大的脆弱性。

5.2本文結(jié)論對(duì)金融監(jiān)管的有效啟示

銀行間同業(yè)市場處于核心地位的銀行數(shù)量雖然較少，但與大多數(shù)銀行之間存在信貸關(guān)聯(lián)，一旦這些銀行出現(xiàn)危機(jī)，會(huì)迅速傳播到整個(gè)網(wǎng)絡(luò)，威脅銀行同業(yè)拆借市場的穩(wěn)定。因此，加強(qiáng)對(duì)銀行間市場具有系統(tǒng)重要性銀行的監(jiān)管有助于維護(hù)銀行間市場的穩(wěn)定，確保銀行系統(tǒng)平穩(wěn)運(yùn)行。系統(tǒng)重要性銀行監(jiān)管的首要問題是系統(tǒng)重要性機(jī)構(gòu)的界定，需要根據(jù)我們國家的實(shí)際情況確定有效的指標(biāo)體系，并選擇合理的方法進(jìn)行量化以及相關(guān)指標(biāo)的合成，減少執(zhí)行操作的難度。

相關(guān)研究表明（馬君潞，2007），單一系統(tǒng)重要銀行產(chǎn)生的影響較為有限，如果處于網(wǎng)絡(luò)中心的眾多銀行同時(shí)出現(xiàn)危機(jī)，則會(huì)對(duì)金融體系產(chǎn)生重大沖擊。由于經(jīng)濟(jì)波動(dòng)的周期性以及其他共同風(fēng)險(xiǎn)暴露因素可能會(huì)導(dǎo)致多家銀行同時(shí)倒閉，從而引發(fā)更為嚴(yán)重的傳染。現(xiàn)階段我國經(jīng)濟(jì)形勢(shì)較為復(fù)雜，在全球經(jīng)濟(jì)復(fù)蘇進(jìn)程緩慢的背景下，我們正處在產(chǎn)業(yè)結(jié)構(gòu)調(diào)整的關(guān)鍵時(shí)期，經(jīng)濟(jì)增長下行壓力較大。從金融體系改革與監(jiān)管的層面來看，需要處理好以下幾方面的問題：

（1）實(shí)現(xiàn)金融和實(shí)體經(jīng)濟(jì)的有效結(jié)合。次貸危機(jī)表明，只有正確處理金融發(fā)展與實(shí)體經(jīng)濟(jì)的關(guān)系，才能有效預(yù)防危機(jī)發(fā)生。中國在金融體系快速發(fā)展過程中，出現(xiàn)了金融脫離實(shí)體經(jīng)濟(jì)的狀態(tài)，尤其是表現(xiàn)為房地產(chǎn)價(jià)格泡沫。針對(duì)金融發(fā)展過程中脫離實(shí)體經(jīng)濟(jì)的苗頭，需要有效的預(yù)警機(jī)制，并通過相應(yīng)的措施化解潛在的金融失衡風(fēng)險(xiǎn)。

（2）構(gòu)建危機(jī)預(yù)警指標(biāo)。陳雨露（2011）提出“金融失衡指數(shù)”這一指標(biāo)對(duì)金融體系的失衡進(jìn)行描述，用以構(gòu)建“金融失衡指數(shù)”的基本指標(biāo)包括：社會(huì)融資總量、投資、企業(yè)杠桿、利差水平、房地產(chǎn)價(jià)格和股票價(jià)格。該方法為構(gòu)建危機(jī)預(yù)警指標(biāo)提供有益引導(dǎo)，但關(guān)于預(yù)警指標(biāo)的選擇與測(cè)度方法需要進(jìn)一步深入研究。

（3）穩(wěn)步推進(jìn)金融混業(yè)經(jīng)營。面對(duì)全球范圍內(nèi)金融業(yè)混業(yè)經(jīng)營大趨勢(shì)，為了提高中國金融體系的穩(wěn)定性與效率，推進(jìn)金融混業(yè)經(jīng)營勢(shì)在必行。但在現(xiàn)階段金融監(jiān)管滯后、內(nèi)外約束機(jī)制尚不健全的狀況下，混業(yè)經(jīng)營的推進(jìn)要保持效率與穩(wěn)定之間的動(dòng)態(tài)平衡。

參考文獻(xiàn)

[1]IMF.Global Financial Stability Report：Responding to the Financial Crisis and Measuring Systemic Risk[R].working paper，April，2009.

[2]Allen F，Gale D.Financial contagion[J].The Journal of Political Economy，2000，（108）：133.

[3]Gai，P.，Kapadia， S. Contagion in Financial Networks[J].Proceedings of the Royal Society A，2010，466（2120）：24012433.

[4]Leitner，Y.Financial Networks： Contagion，Commitment，and Social Coordination[J].The Journal of Finance，2005，60（6）：29252953.

[5]Hajime Inaoka， Hideki Takayasu.Self-similarity of banking network[J].Physica A，2004，（339）：621634.

[6]Boss，M.，Elsinger，H.，Summer，M. Network Topology of the interbank Market[J].Quantitative Finance，2004，4（6）：677684.

[7]Giulia Iori，Giulia De Masi.A network analysis of the Italian overnight money market[J].Journal of Economic Dynamics & Control，2008，（32）：259278.

[8]Nier，E.，Yang，work Models and Financial Stability[J].Journal of Economic Dynamics & Control，2007，31（6）：20332060.

篇10

關(guān)鍵詞：離散數(shù)學(xué)；輻射作用；輻射體系；編譯原理；數(shù)據(jù)庫

中圖分類號(hào)：TP3-4

離散數(shù)學(xué)是現(xiàn)代數(shù)學(xué)的一個(gè)重要分支，也是計(jì)算機(jī)科學(xué)與技術(shù)的理論基礎(chǔ)，所以又稱為計(jì)算機(jī)數(shù)學(xué)[1]。離散數(shù)學(xué)研究離散量的結(jié)構(gòu)及其相互關(guān)系，通過離散數(shù)學(xué)的學(xué)習(xí)，不但可以掌握離散結(jié)構(gòu)的描述工具和方法，為后續(xù)課程的學(xué)習(xí)創(chuàng)造條件，而且可以提高抽象思維和邏輯推理能力，為將來參與創(chuàng)新性的研究與開發(fā)工作打下堅(jiān)實(shí)的基礎(chǔ)。

離散數(shù)學(xué)課程所傳授的思想、方法與工具，廣泛地體現(xiàn)在計(jì)算機(jī)相關(guān)專業(yè)的諸領(lǐng)域，從科學(xué)計(jì)算到數(shù)據(jù)處理，從計(jì)算機(jī)科學(xué)理論基礎(chǔ)到計(jì)算機(jī)應(yīng)用技術(shù)，從計(jì)算機(jī)軟件與理論到計(jì)算機(jī)硬件及體系結(jié)構(gòu)，從人工智能到知識(shí)系統(tǒng)與工程，無不與離散數(shù)學(xué)密切相關(guān)。由于計(jì)算機(jī)本身是一個(gè)離散結(jié)構(gòu)，它只能處理離散的或離散化了的對(duì)象及對(duì)象關(guān)系，因此，無論計(jì)算機(jī)科學(xué)理論本身，還是與計(jì)算機(jī)應(yīng)用密切相關(guān)的現(xiàn)代科學(xué)的其它研究領(lǐng)域，都面臨著如何對(duì)離散結(jié)構(gòu)進(jìn)行數(shù)學(xué)建模的問題；當(dāng)然，也需要考慮如何將已建立的離散數(shù)學(xué)模型進(jìn)行計(jì)算機(jī)應(yīng)用的問題。

隨著計(jì)算機(jī)專業(yè)研究生入學(xué)考試中專業(yè)課程統(tǒng)考的實(shí)行，很多高校的計(jì)算機(jī)專業(yè)對(duì)離散數(shù)學(xué)的教學(xué)投入開始縮減，減少課時(shí)，降低難度，避重就輕；學(xué)生也無法認(rèn)識(shí)與理解離散數(shù)學(xué)在整個(gè)計(jì)算機(jī)專業(yè)課程體系中的重要性，致使離散數(shù)學(xué)的教學(xué)與學(xué)習(xí)在計(jì)算機(jī)專業(yè)越來越邊緣化。實(shí)際上，離散數(shù)學(xué)在各學(xué)科領(lǐng)域，特別在計(jì)算機(jī)相關(guān)專業(yè)領(lǐng)域有著廣泛的應(yīng)用；離散數(shù)學(xué)是計(jì)算機(jī)專業(yè)許多專業(yè)基礎(chǔ)課程，如數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、編譯原理、人工智能、數(shù)據(jù)庫系統(tǒng)原理、算法設(shè)計(jì)與分析、理論計(jì)算機(jī)科學(xué)基礎(chǔ)、軟件工程等必不可少的先行課程[2]。

作為計(jì)算機(jī)相關(guān)專業(yè)數(shù)學(xué)基礎(chǔ)的離散數(shù)學(xué)，對(duì)其它計(jì)算機(jī)專業(yè)基礎(chǔ)課程有很強(qiáng)的知識(shí)輻射作用。本文致力于從一些計(jì)算機(jī)專業(yè)基礎(chǔ)課內(nèi)容中還原離散數(shù)學(xué)知識(shí)，從而體現(xiàn)離散數(shù)學(xué)核心內(nèi)容在計(jì)算機(jī)專業(yè)系統(tǒng)知識(shí)中的輻射作用。通過對(duì)離散數(shù)學(xué)輻射作用的介紹，讓計(jì)算機(jī)相關(guān)專業(yè)的本科生重新認(rèn)識(shí)到離散數(shù)學(xué)對(duì)計(jì)算機(jī)專業(yè)系統(tǒng)知識(shí)學(xué)習(xí)的重要性，從而提高本科生學(xué)習(xí)離散數(shù)學(xué)的興趣，重視自己數(shù)學(xué)理論基礎(chǔ)的鞏固和形式思維能力的培養(yǎng)。

1 離散數(shù)學(xué)輻射體系

離散數(shù)學(xué)是計(jì)算機(jī)及相關(guān)專業(yè)的一門核心課程，它不是一門純數(shù)學(xué)課程，而是計(jì)算機(jī)學(xué)科的專業(yè)基礎(chǔ)課程。離散數(shù)學(xué)是應(yīng)計(jì)算機(jī)科學(xué)的發(fā)展而形成的一門交叉課程，主要內(nèi)容涵蓋了計(jì)算機(jī)相關(guān)專業(yè)對(duì)數(shù)學(xué)的一些基本要求。廣義的離散數(shù)學(xué)主題包括集合論、數(shù)理邏輯、關(guān)系理論、圖論、代數(shù)結(jié)構(gòu)、數(shù)論、信息論、組合數(shù)學(xué)等，甚至包含拓?fù)鋵W(xué)、運(yùn)籌學(xué)的內(nèi)容。有些高校將除拓?fù)鋵W(xué)、運(yùn)籌學(xué)等內(nèi)容外的主題分為三門課程，即集合論與圖論、代數(shù)結(jié)構(gòu)與組合數(shù)學(xué)、數(shù)理邏輯。本文談到的離散數(shù)學(xué)內(nèi)容只涉及到數(shù)理邏輯、關(guān)系理論、集合論、圖論以及代數(shù)結(jié)構(gòu)。

離散數(shù)學(xué)課程與后續(xù)的計(jì)算機(jī)相關(guān)專業(yè)基礎(chǔ)課程有著千絲萬縷的聯(lián)系，對(duì)其它專業(yè)基礎(chǔ)課程的影響極其深遠(yuǎn)，在很多計(jì)算機(jī)專業(yè)課程內(nèi)容中都會(huì)涉及到離散數(shù)學(xué)知識(shí)。無論計(jì)算機(jī)軟件系列專業(yè)基礎(chǔ)課程，還是計(jì)算機(jī)硬件相關(guān)基礎(chǔ)課程，例如編譯原理、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫、操作系統(tǒng)、軟件工程和計(jì)算機(jī)組成原理。本文選擇這六門計(jì)算機(jī)相關(guān)專業(yè)基礎(chǔ)課程來闡述離散數(shù)學(xué)在專業(yè)系統(tǒng)知識(shí)中的輻射作用，如圖1所示的離散數(shù)學(xué)輻射體系。

在圖1中，編譯原理的課程內(nèi)容中就可以還原出全部的離散數(shù)學(xué)知識(shí)結(jié)構(gòu)；數(shù)據(jù)庫的課程內(nèi)容則可還原出離散數(shù)學(xué)內(nèi)容中的關(guān)系理論、代數(shù)結(jié)構(gòu)、集合論與圖論等內(nèi)容；操作系統(tǒng)、軟件工程、數(shù)據(jù)結(jié)構(gòu)和計(jì)算機(jī)組成原路中都有離散數(shù)學(xué)知識(shí)輻射的印跡。

2 離散數(shù)學(xué)輻射作用

2.1 編譯原理中的離散數(shù)學(xué)

編譯原理是計(jì)算機(jī)相關(guān)專業(yè)的一門重要專業(yè)基礎(chǔ)課[3]，旨在介紹編譯器構(gòu)造的一般原理和基本方法，課程內(nèi)容除了形式文法、有窮自動(dòng)機(jī)等編譯原理所涉及的基礎(chǔ)知識(shí)外，其它內(nèi)容基本上圍繞處理程序設(shè)計(jì)語言的編譯器應(yīng)該具有的各功能模塊展開，包括詞法分析、語法分析、語法制導(dǎo)翻譯、中間代碼生成、存儲(chǔ)管理、代碼優(yōu)化和目標(biāo)代碼生成。

離散數(shù)學(xué)的數(shù)理邏輯中最重要的內(nèi)容就是邏輯推理，由前提事實(shí)出發(fā)，采用相應(yīng)的邏輯恒等式、永真蘊(yùn)涵式、推理規(guī)則、推理方法等進(jìn)行不停的推導(dǎo)演繹，最終得到想要的結(jié)論，這是一個(gè)嚴(yán)格的演繹分析過程。在編譯原理中，與這一演繹分析過程相對(duì)應(yīng)的則是語法自上而下分析方法，即從形式文法的開始符號(hào)（前提）出發(fā)，利用文法規(guī)則產(chǎn)生式（永真蘊(yùn)涵式），采用相應(yīng)的推理方法（最左或最右推導(dǎo)），最終得到想要的句型或句子（結(jié)論）。在推理證明中還有一種常用的證明方法，那就是從要求證的最終結(jié)論出發(fā)，依次為其找到相應(yīng)的邏輯恒等式、永真蘊(yùn)涵式、推理規(guī)則等作為最終結(jié)論或中間結(jié)論的依據(jù)，即從結(jié)論出發(fā)追本溯源到前提事實(shí)，這是一種典型的歸納邏輯。在編譯原理的語法分析中，自底向上的語法分析方法則是歸納過程的代表，即從要得到的句型或句子出發(fā)，利用文法產(chǎn)生式規(guī)則和推理方法，進(jìn)行不停的歸約，一直到開始符號(hào)或失敗至，這是一直明顯的歸納邏輯推理過程，對(duì)應(yīng)最右推導(dǎo)。

在離散數(shù)學(xué)的關(guān)系理論中，等價(jià)關(guān)系尤為重要。而在編譯原理中，處處有等價(jià)原理輻射的痕跡，例如形式文法等價(jià)、有窮自動(dòng)機(jī)等價(jià)、中間代碼表示形式等價(jià)等。在編譯原理的內(nèi)容中，有關(guān)等價(jià)的部分還包括正規(guī)文法與正則表達(dá)式的等價(jià)性、正則表達(dá)式與有窮自動(dòng)機(jī)的等價(jià)性、正規(guī)文法與有窮自動(dòng)機(jī)的等價(jià)性。實(shí)際上，有窮自動(dòng)機(jī)等價(jià)是進(jìn)行非確定有窮自動(dòng)機(jī)確定化、確定有窮自動(dòng)機(jī)化簡的理論基礎(chǔ)。

編譯原理的很多內(nèi)容中都使用了形式化技術(shù)，最典型的就是狀態(tài)圖刻畫有窮自動(dòng)機(jī)、語法樹表示語法分析過程，當(dāng)然在LL（1）文法FIRST集與FOLLOW集計(jì)算、算符優(yōu)先文法的優(yōu)先函數(shù)關(guān)系圖以及基本塊有向圖中都體現(xiàn)了離散數(shù)學(xué)的集合論與圖論。在編譯原理全部內(nèi)容中都貫穿了符號(hào)串運(yùn)算，符號(hào)串與其上的運(yùn)算則構(gòu)成了一個(gè)完整的代數(shù)系統(tǒng)。

2.2 數(shù)據(jù)庫中的離散數(shù)學(xué)

數(shù)據(jù)庫技術(shù)和系統(tǒng)已經(jīng)成為信息基礎(chǔ)設(shè)施的核心技術(shù)和重要基礎(chǔ)，數(shù)據(jù)庫技術(shù)作為數(shù)據(jù)管理的最有效的手段，極大的促進(jìn)了計(jì)算機(jī)應(yīng)用的發(fā)展[4]。數(shù)據(jù)庫的數(shù)據(jù)模型中的關(guān)系模型就經(jīng)典地體現(xiàn)了離散數(shù)學(xué)中的關(guān)系理論，尤其是關(guān)系模型中的參照完整性。數(shù)據(jù)庫概念模型描述中使用的實(shí)體-聯(lián)系模型（圖）更是生動(dòng)地呈現(xiàn)了實(shí)體型之間的關(guān)系。在離散數(shù)學(xué)中，函數(shù)是一類特殊關(guān)系，而關(guān)系數(shù)據(jù)理論中的函數(shù)依賴則描述了關(guān)系模式屬性（集）之間的語義關(guān)聯(lián)。數(shù)據(jù)庫中的查詢處理與優(yōu)化的理論基礎(chǔ)則是離散數(shù)學(xué)中等價(jià)原理，查詢被處理或優(yōu)化前后在功能和語義上必須滿足等價(jià)關(guān)系。

與關(guān)系模型緊密相連的則是關(guān)系代數(shù)，這是一類典型的代數(shù)系統(tǒng)。關(guān)系數(shù)據(jù)結(jié)構(gòu)是其運(yùn)算對(duì)象，關(guān)系操作則是定義在關(guān)系上的具體運(yùn)算，如選擇、投影、連接、除等，這些運(yùn)算都滿足封閉性，關(guān)系操作的輸入與輸出則都是表示關(guān)系數(shù)據(jù)的集合，因此集合運(yùn)算中的并、交、差、笛卡爾積等也是關(guān)系操作的一部分。關(guān)系數(shù)據(jù)模型中常用的SQL語言則是關(guān)系代數(shù)的一種具體實(shí)現(xiàn)，即一種具體的代數(shù)系統(tǒng)。

數(shù)據(jù)庫理論中被集合論與圖論輻射到的內(nèi)容包括：（1）一個(gè)關(guān)系數(shù)據(jù)庫是關(guān)系模式（二維表）的集合；（2）一個(gè)關(guān)系模式（二維表）就是一個(gè)實(shí)體集，表中每一個(gè)就是一個(gè)具體的實(shí)體元素；（3）在概念世界中描述實(shí)體型以及實(shí)體型間關(guān)系的實(shí)體-聯(lián)系圖；（4）關(guān)系查詢處理與優(yōu)化中的查詢樹。

2.3 其它課程中的離散數(shù)學(xué)

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)程序設(shè)計(jì)的重要理論技術(shù)基礎(chǔ)[5]，也是計(jì)算機(jī)存儲(chǔ)與組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，因而，數(shù)據(jù)結(jié)構(gòu)課程中很多具體的數(shù)據(jù)結(jié)構(gòu)都是集合，如隊(duì)列、棧、線性表等。數(shù)據(jù)結(jié)構(gòu)除描述集合中數(shù)據(jù)元素的特性外，還要刻畫集合中數(shù)據(jù)元素之間的關(guān)系，因此，一般認(rèn)為，一個(gè)數(shù)據(jù)結(jié)構(gòu)是由數(shù)據(jù)元素依據(jù)某種邏輯聯(lián)系組織起來的，對(duì)數(shù)據(jù)元素間邏輯關(guān)系的描述稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)課程內(nèi)容中的樹、二叉樹以及圖等結(jié)構(gòu)則是離散數(shù)學(xué)圖論內(nèi)容的延續(xù)，基于圖結(jié)構(gòu)的各種算法，如最短路徑、最小生成樹、關(guān)鍵路徑等，在離散數(shù)學(xué)和數(shù)據(jù)結(jié)構(gòu)中都有不同深度的描述。

操作系統(tǒng)課程中的進(jìn)程狀態(tài)圖為典型的圖論內(nèi)容；操作系統(tǒng)在對(duì)進(jìn)程等對(duì)象進(jìn)行管理時(shí)，很多內(nèi)容涉及到對(duì)象間關(guān)系，如死鎖中進(jìn)程間時(shí)序上的先后關(guān)系；操作系統(tǒng)中很多算法都使用到了集合概念，如死鎖的解鎖算法等。離散數(shù)學(xué)的核心內(nèi)容輻射到了操作系統(tǒng)的管理與控制中。

軟件工程最終的產(chǎn)物是軟件系統(tǒng)，既然是軟件系統(tǒng)，在進(jìn)行軟件系統(tǒng)分析與設(shè)計(jì)時(shí)，不可避免要研究系統(tǒng)各部分之間的關(guān)系。在結(jié)構(gòu)化分析方法中，有自頂而下和自底而上兩類分析方法，自頂而下對(duì)應(yīng)數(shù)理邏輯中的演繹邏輯，而自底而上則表示數(shù)理邏輯中的歸納邏輯。軟件工程內(nèi)容中同圖論有關(guān)的包括軟件開發(fā)模型、軟件模塊間關(guān)系表示、軟件測(cè)試等。

計(jì)算機(jī)組成原理作為計(jì)算機(jī)專業(yè)硬件方面的基礎(chǔ)課，在學(xué)生對(duì)計(jì)算機(jī)的認(rèn)知方面有著舉足輕重的作用。計(jì)算機(jī)硬件的基礎(chǔ)組成單元“邏輯門”等以離散數(shù)學(xué)中的命題邏輯為基礎(chǔ)；計(jì)算機(jī)處理器的結(jié)構(gòu)形式化等都離不開集合論與圖論的參與。實(shí)際上，在讓學(xué)生認(rèn)知軟件與硬件的功能等價(jià)性時(shí)，則充分體現(xiàn)了軟硬件的邏輯等價(jià)原理。

3 結(jié)論

針對(duì)離散數(shù)學(xué)課程在計(jì)算機(jī)專業(yè)課程體系中越來越邊緣化的問題，本文以編譯原理、數(shù)據(jù)庫、數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、軟件工程和計(jì)算機(jī)組成原理計(jì)算機(jī)專業(yè)基礎(chǔ)課為例，論述了離散數(shù)學(xué)在計(jì)算機(jī)專業(yè)綜合知識(shí)體系中的輻射作用，從而體現(xiàn)離散數(shù)學(xué)在計(jì)算機(jī)專業(yè)教育中的重要性和必要性。

參考文獻(xiàn)：

[1]傅彥，顧小豐，王慶先等.離散數(shù)學(xué)及其應(yīng)用[M].北京：高等教育出版社，2007.

[2]耿素云，屈婉玲，王捍貧.離散數(shù)學(xué)教程[M].北京：北京大學(xué)出版社，2002.

[3]張素琴，呂映芝，蔣維杜等.編譯原理（第二版）[M].北京：清華大學(xué)出版社，2005.

[4]王珊，薩師煊.數(shù)據(jù)庫系統(tǒng)概論（第4版）[M].北京：高等教育出版社，2006.

[5]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].北京：清華大學(xué)出版社，2011.

作者簡介：胡慧君（1976-），女，講師，研究方向：智能信息處理；劉茂福（1977-），男，教授，研究方向：自然語言處理。