信息與計(jì)算科學(xué)畢業(yè)設(shè)計(jì)（論文）中國(guó)郵遞員問題綜述

1、信息與計(jì)算科學(xué)畢業(yè)設(shè)計(jì)（論文）-中國(guó)郵遞員問題綜述 本科畢業(yè)論 設(shè)計(jì) 題國(guó)郵遞員問題綜學(xué) 統(tǒng)計(jì)與數(shù)理學(xué)院 專 業(yè) 級(jí) 20071班 學(xué) 號(hào) 名 指導(dǎo)師 國(guó)郵遞員問題綜，問題圖論郵遞員遞線關(guān)鍵詞遞 歐拉回路 最短路 Lingo一、引言圖論應(yīng)廣泛運(yùn)籌學(xué)廣泛應(yīng)學(xué)學(xué)制論論學(xué)電計(jì)個(gè)領(lǐng).在實(shí)際產(chǎn)學(xué)問題圖論理論來決.組織產(chǎn)為項(xiàng)務(wù)學(xué)間樣銜產(chǎn)務(wù).一個(gè)郵遞員送信負(fù)責(zé)遞務(wù)郵應(yīng)該樣線線國(guó)遞員問題1960年我們從產(chǎn)實(shí)際個(gè)數(shù)學(xué)問題從實(shí)際問題來個(gè)遞員應(yīng)該選擇條線負(fù)責(zé)的我們開始國(guó)遞員問題國(guó)究過謂貨員問題，個(gè)貨員要個(gè)貨問應(yīng)該選擇樣條線. 題顯歸納為貨員問題，實(shí)遞員須個(gè)點(diǎn)個(gè).但是一般來說遞員約二個(gè)點(diǎn)歸納為貨員問題來決將是個(gè)規(guī)問題

2、，無決.但是，在仔細(xì)遞員臨問題后，我們發(fā)現(xiàn)這個(gè)問題點(diǎn)點(diǎn)較實(shí)際我們稱這個(gè)問題為遞線路問題1965年后國(guó)稱為國(guó)遞員問題.二、概念與原理一名郵遞員帶著發(fā)的郵件從郵發(fā)，經(jīng)過發(fā)的個(gè)郵郵須過他轄范圍內(nèi)條選擇遞線郵遞員盡這個(gè)問題國(guó)數(shù)學(xué)山東師學(xué)數(shù)學(xué)1962年首次提出的，因此在國(guó)際稱為國(guó)郵遞員問題圖論語個(gè)連賦權(quán)圖尋條該中的每條邊該權(quán)數(shù)最說從的每條邊條權(quán)數(shù)最實(shí)際們?yōu)閷?duì)之間的關(guān)會(huì)紙點(diǎn)線畫樣圖.8世紀(jì)時(shí)歐個(gè)風(fēng)麗, 那里有七座橋.圖1島、右岸各有兩橋連結(jié)兩間陸地、各有一座橋連結(jié).問個(gè)樣橋橋過發(fā)點(diǎn)這個(gè)例是歷7橋問題.現(xiàn)國(guó)個(gè)圖1當(dāng)發(fā)島圖當(dāng)間傳遠(yuǎn)個(gè)難題.1736年，數(shù)學(xué)歐統(tǒng)決這類問題.七橋問題數(shù)學(xué)歐17071783）的關(guān).他

3、把具體七橋歸為圖2簡(jiǎn)單圖七橋問題變個(gè)筆問題樣從、中的某一點(diǎn)發(fā)，筆這個(gè)簡(jiǎn)單圖筆開紙、各條線只畫點(diǎn)圖2一筆圖點(diǎn)或數(shù)條線連點(diǎn)有兩個(gè)點(diǎn)數(shù)條線連.歐: 如果一個(gè)絡(luò)是連頂點(diǎn)個(gè)數(shù)0或2，那么它可以一筆則筆.定義 經(jīng)過條邊跡Euler跡閉Euler跡Euler回路或回路,含Euler回路的圖Euler圖.觀地講Euler圖從頂點(diǎn)發(fā)邊過發(fā)點(diǎn)種圖邊發(fā)點(diǎn).1（1）是Euler圖條連頂點(diǎn)皆偶.（2）是Euler圖條連.（3）中有Euler跡條連有兩個(gè)點(diǎn).2 對(duì)連圖GV，E），下列條 （1）G是一個(gè)歐圖 （2）G的每一個(gè)節(jié)點(diǎn)數(shù)數(shù) （3）G的邊E可以分解為個(gè)“奇點(diǎn)”，與偶數(shù)條線相連的點(diǎn)叫“偶點(diǎn)”三、運(yùn)名郵遞員帶著發(fā)的郵件

4、從郵發(fā)，經(jīng)過發(fā)的個(gè)郵郵須過他轄范圍內(nèi)條選擇遞線郵遞員盡這個(gè)問題國(guó)數(shù)學(xué)山東師學(xué)數(shù)學(xué)1962年首次提出的，因此在國(guó)際稱為國(guó)郵遞員問題圖論語個(gè)連賦權(quán)圖尋條該中的每條邊該權(quán)數(shù)最說從的每條邊條權(quán)數(shù)最是歐圖則羅萊個(gè)歐不是歐圖數(shù)節(jié)點(diǎn)則國(guó)遞員問題的決難標(biāo)給數(shù)節(jié)點(diǎn)連圖尋權(quán)數(shù)路與哥尼斯堡7橋問題相聯(lián)系的在哥尼斯堡7橋問題中，歐拉證明了不存在這樣的回路，使它經(jīng)過圖中每條邊且只經(jīng)過一次又回到起始點(diǎn)與此相反，設(shè)為一個(gè)圖，若存在一條回路，使它經(jīng)過圖中每條邊且只經(jīng)過一次又回到起始點(diǎn)，就稱這種回路為歐拉回路，并稱圖為歐拉圖在一個(gè)圖中，連接一個(gè)節(jié)點(diǎn)的邊數(shù)稱為該節(jié)點(diǎn)的度數(shù)對(duì)歐拉圖，我們有下列結(jié)果：定理3 下列條件是相互等價(jià)的：

5、（1）是一個(gè)歐拉圖； （2）的每一個(gè)節(jié)點(diǎn)的度數(shù)都是偶數(shù)； （3）的邊集合可以分解為若干個(gè)回路的并 證明 ： 已知為歐拉圖，則必存在一個(gè)歐拉回路回路中的節(jié)點(diǎn)都是偶度數(shù) 設(shè)中每一個(gè)節(jié)點(diǎn)的度數(shù)均為偶數(shù)若能找到一個(gè)回路使，則結(jié)論成立否則，令，由上每個(gè)節(jié)點(diǎn)的度數(shù)均為偶數(shù)，則中的每個(gè)節(jié)點(diǎn)的度數(shù)亦均為偶數(shù)于是在必存在另一個(gè)回路令，?由于為有限圖，上述過程經(jīng)過有限步，最后必得一個(gè)回路使 上各節(jié)點(diǎn)的度數(shù)均為零，即這樣就得到的一個(gè)分解 設(shè)，其中（I 1,2,r）均為回路由于為連通圖，對(duì)任意回路,必存在另一個(gè)回路與之相連，即與存在共同的節(jié)點(diǎn)現(xiàn)在我們從圖G的任意節(jié)點(diǎn)出發(fā)，沿著所在的回路走，每走到一個(gè)共同的節(jié)點(diǎn)處，就轉(zhuǎn)

6、向另一個(gè)回路，?，這樣一直走下去就可走遍的每條邊且只走過一次,最后回到原出發(fā)節(jié)點(diǎn)，即為一個(gè)歐拉圖利用定理1去判斷一個(gè)連通圖是否為歐拉圖比較容易，但要找出歐拉回路，當(dāng)連通圖比較復(fù)雜時(shí)就不太容易了下面介紹一種求歐拉回路的算法即：弗羅萊算法算法步驟如下：（1）任取起始點(diǎn) （2）設(shè)路已選出，則從E中選出邊，使與相連，除非沒有其它選擇，仍應(yīng)為連通的 （3）重復(fù)步驟（2），直至不能進(jìn)行下去為止定理4 有向圖存在歐拉回路的充分必要條件是對(duì)任意節(jié)點(diǎn)，進(jìn)入該節(jié)點(diǎn)邊數(shù)（進(jìn)數(shù)）與離開該點(diǎn)的邊數(shù)（出數(shù)）相等 如果是歐拉圖，則很容易由弗羅萊算法求出一個(gè)歐拉回路，但是若不是歐拉圖，即存在奇度數(shù)的節(jié)點(diǎn)，則中國(guó)由遞員問題的解

7、決要困難得多本節(jié)的主要目標(biāo)是給出在有奇度數(shù)節(jié)點(diǎn)的連通圖中尋找最小權(quán)數(shù)的回路的方法首先注意到，若圖有奇數(shù)度節(jié)點(diǎn)，則的奇數(shù)度節(jié)點(diǎn)必是偶數(shù)個(gè)把奇數(shù)度節(jié)點(diǎn)分為若干對(duì)，每對(duì)節(jié)點(diǎn)之間在中有相應(yīng)的最短路，將這些最短路畫在一起構(gòu)成一個(gè)附加的邊子集令，即把附加邊子集迭加在原圖上形成一個(gè)多重圖，這時(shí)G/中連接兩個(gè)節(jié)點(diǎn)之間的邊不止一條顯然是一個(gè)歐拉圖，因而可以求出的歐拉回路該歐拉回路不僅通過原圖中每條邊，同時(shí)還通過中的每條邊，且均僅一次郵遞員問題的難點(diǎn)在于當(dāng)?shù)钠鏀?shù)度節(jié)點(diǎn)較多時(shí)，可能有很多種配對(duì)方法，應(yīng)怎樣選擇配對(duì)，能使相應(yīng)的附加邊子集 的權(quán)數(shù)為最小？為此有下列定理 定理 5 設(shè)為一個(gè)連通的賦權(quán)圖，則使附加邊子集的權(quán)

8、數(shù)為最小的充分必要條件是中任意邊至多重復(fù)一次，且中的任意回路中重復(fù)邊的權(quán)數(shù)之和不大于該回路總權(quán)數(shù)的一半必要性用反證法設(shè)存在一種奇節(jié)點(diǎn)集的配對(duì)，使其附加邊子集權(quán)數(shù) 為最小若中有一條邊重復(fù)次，由于為歐拉圖，所以刪去相應(yīng)的二次重復(fù)邊后仍為歐拉圖這樣，相應(yīng)的附加邊子集的權(quán)數(shù)將減小，這與為最小的假設(shè)矛盾這說明中的邊均互不相同 其次，若中存在一個(gè)回路，使它的重復(fù)邊的權(quán)數(shù)之和大于該回路總權(quán)數(shù)的一半，則在中刪去這些重復(fù)邊（注意：這些邊均在中），而代之以該回路的其余部分的邊再重復(fù)一次經(jīng)過這種替代后所得到的邊子集仍為附加子集，且，又產(chǎn)生矛盾 充分性設(shè)有兩個(gè)附加邊子集和，均使/和中每條邊至多重復(fù)一次，且每個(gè)回路中的

9、重復(fù)邊的權(quán)數(shù)和不大該回路權(quán)數(shù)的一半，我們來證明首先注意到，由和不相同的部分組成的圖（記為）是由一個(gè)或若干個(gè)歐拉子圖所組成的這是因?yàn)橹忻總€(gè)節(jié)點(diǎn)的度數(shù)均為偶數(shù)，而和的公共邊數(shù)也是偶數(shù)，故中每個(gè)節(jié)點(diǎn)的度數(shù)仍為偶數(shù)，所以它若為連通圖時(shí)是一個(gè)歐拉圖；若為非連通圖時(shí)則由若干個(gè)歐拉子圖組成的任何回路都由E/和E/中的邊組成，而E/和E/在回路中的權(quán)數(shù)分別不大于該回路權(quán)數(shù)的一半，因而任何回路中屬于中的權(quán)數(shù)之和與屬于中的邊數(shù)之和必定相等，所以它就是最優(yōu)附加邊子集的權(quán)數(shù)，即和均為使附加邊子集的權(quán)數(shù)達(dá)到最小的最優(yōu)附加邊子集.四 數(shù)型分析 由定理3可得一個(gè)尋找郵遞員問題最優(yōu)解的方法現(xiàn)舉例如下： 圖3 知郵遞員要投遞的

10、街道如圖3示，試求最優(yōu)郵路先找出奇節(jié)點(diǎn)：，奇節(jié)點(diǎn)進(jìn)行配對(duì)，不妨把與，與，A3與B3，與配對(duì)，求其最短路顯然它不是最優(yōu)解下面我們根據(jù)定理3來進(jìn)行調(diào)解圖4第一次調(diào)整：刪去多于一條的重復(fù)邊，即與，與中的調(diào)整后，實(shí)際上成為與，與，與，與的配對(duì)，它們的最短路如圖4示圖5第二次調(diào)整：發(fā)現(xiàn)在回路 ， 中重復(fù)邊的權(quán)數(shù)和為11，大于該回路權(quán)數(shù)20的一半因而調(diào)整時(shí)，把該回路的重復(fù)邊刪去，代之以重復(fù)其余部分，得圖5可以看出，實(shí)際上是調(diào)整為與，與，與，與配對(duì)圖6第三次調(diào)整：在圖5中發(fā)現(xiàn)回路 ， 中重復(fù)邊的權(quán)數(shù)和為7，大于該回路權(quán)數(shù)10的一半，因而刪去原重復(fù)邊（，）和（，），而添加（，），得到圖6進(jìn)行檢查發(fā)現(xiàn)，既沒有多

11、于一條的重復(fù)邊，也沒有任何回路使其重復(fù)邊的權(quán)數(shù)之和大于該回路的一半，因此圖6就是最優(yōu)的附加邊子集，而為歐拉圖，因此，可以求得最優(yōu)的路線為.五 優(yōu)化模型 上述的郵遞員問題，郵遞員遞圍內(nèi)條沒別實(shí)際遞過單線兩邊單時(shí)遞問題.這樣問題稱為廣義國(guó)郵遞員問題.這廣義國(guó)郵遞員問題為個(gè)圖問題. 類郵遞員問題稱為傳統(tǒng)郵遞員問題廣義郵遞員問題綜為：給個(gè)連圖個(gè)上有非負(fù)權(quán)尋的一個(gè)過個(gè)總權(quán).對(duì)廣義國(guó)郵遞員問題，個(gè)數(shù)1條時(shí)已經(jīng)條對(duì)應(yīng)連圖點(diǎn)進(jìn)數(shù)數(shù)相從,存在回路（回路）.在此，如,則稱是頂點(diǎn)進(jìn)時(shí)的出向弧.可以證的頂點(diǎn)數(shù)為則每條條實(shí)現(xiàn)頂點(diǎn)進(jìn)項(xiàng)數(shù)數(shù)相.根據(jù)以上分析，對(duì)的每條定義數(shù)變，表示弧上增加了條個(gè)圖.類廣義國(guó)郵遞員顯數(shù)規(guī)）:

12、min s.t.通過這廣義國(guó)郵遞員問題的遞線.慮圖國(guó)郵遞員問題圖8根據(jù)前面的模型討論這一數(shù)郵遞員問題對(duì)應(yīng)數(shù)規(guī)lingo程序如下：minZ 2* x18+x81 +4* x87+x78 +5* x12+x21 +3* x89+x98 +6* x29+x92 +3* x67+x76 +4* x69+x96 +5* x32+x23 +4* x94+x49 +4* x56+x65 +9* x43+x34 +4* x54+x45 ;x21+x81-x12-x18 0;x12+x92+x32-x21-x29-x23 0;x23+x43-x32-x34 0;x34+x94+x54-x43-x49-x45 0

13、;x65+x45-x56-x54 0;x76+x96+x56-x67-x69-x65 0;x67+x87-x76-x78 0;x18+x78+x98-x81-x87-x89 0;x29+x49+x69+x89-x92-x94-x96-x98 0;x18+x81 1 ;x87+x78 1;x12+x21 1;x89+x98 1;x67+x76 1;x29+x92 1;x96+x69 1;x23+x32 1;X94+X49 1;X56+X65 1;X43+X34 1;X45+X54 1;表9運(yùn)行l(wèi)ingo9.0得到結(jié)果如下Feasible solution found.Total solver i

14、terations: 6 Variable Value MINZ 88.00000 X18 0.000000 X81 1.000000 X87 2.000000 X78 0.000000 X12 1.000000 X21 0.000000 X89 0.000000 X98 3.000000 X29 0.000000 X92 1.000000 X67 0.000000 X76 2.000000 X69 1.000000 X96 0.000000 X32 0.000000 X23 2.000000 X94 0.000000 X49 3.000000 X56 0.000000 X65 1.00000

15、0 X43 0.000000 X34 2.000000 X54 1.000000 X45 0.000000 Row Slack or Surplus 1 0.000000 2 0.000000 3 0.000000 4 0.000000 5 0.000000 6 0.000000 7 0.000000 8 0.000000 9 0.000000 10 0.000000 11 0.000000 12 1.000000 13 0.000000 14 2.000000 15 1.000000 16 0.000000 17 0.000000 18 1.000000 19 2.000000 20 0.0

16、00000 21 1.000000 22 0.000000 所以這一問題的最優(yōu)解是其它，最小權(quán)為8.假定郵點(diǎn)V,則遞線：注意這問題的遞線.同理可以求得郵從點(diǎn)發(fā)時(shí)遞線.當(dāng)然，在本文之外還有很多涉及此問題的相關(guān)論題，我們還要不斷努力，不斷學(xué)習(xí)，為我國(guó)的郵遞事業(yè)進(jìn)到一點(diǎn)貢獻(xiàn).參考文獻(xiàn)：1管梅谷 奇偶點(diǎn)圖上作業(yè)法M.數(shù)學(xué)學(xué)報(bào), 1960.3.2管梅谷 郵遞員問題綜述M.數(shù)學(xué)研究與評(píng)論1965.53李瑋 、王雷 中國(guó)郵遞員問題的DNA計(jì)算M 中國(guó)教育出版,2009.64許志國(guó)、桂湘云 運(yùn)籌學(xué)（第三版）M清華大學(xué)出版社2008.75韓中庚. 用運(yùn)籌學(xué)模型、方法計(jì)算M.清華大學(xué)出版,2007.96哈拉里 圖

17、論 M 上海科技出版社 1980.97李念祖 關(guān)于中國(guó)郵遞員問題的最有完全子圖算法社J 2009.19 07 8吳杰 求解中國(guó)郵遞員問題的一種思路J 科技資訊 2007,169馮俊文 中國(guó)郵遞員問題的整數(shù)規(guī)劃模型J ,2010.1210 金毅 對(duì)中國(guó)郵遞員的理性分析 J, 科技經(jīng)濟(jì)市場(chǎng) 2009.5A review of the Chinese postman problem Gao KunAbstract: This article gives a conmprehensive review of the Chinese postman problem CPP , the use of op

18、erations research principles of graph theory, Euler circuit, by the Konigsberg problem associated with the first issue of a stroke, the postman problem into a graph theory-related model, using the shortest Road principle of making the shortest postman's delivery routes, and further discussed the actua