中國郵遞員問題p課件

中國郵遞員問題(ChinesePostmanProblem)1最新版整理ppt主要內(nèi)容七橋問題與一筆畫中國郵遞員問題歐拉圖及求歐拉回路的算法求解中國郵遞員問題的算法2最新版整理ppt七橋問題SevenBridgesProblem18世紀著名古典數(shù)學問題之一。在哥尼斯堡的一個公園里，有七座橋?qū)⑵绽赘駹柡又袃蓚€島以及島與河岸連接起來(如圖)。問是否可能從這四塊陸地中任一塊出發(fā)，恰好通過每座橋一次，再回到起點？3最新版整理ppt歐拉于1736年研究并解決了此問題，

他用點表示島和陸地，兩點之間的連線表示連接它們的橋，將河流、小島和橋簡化為一個網(wǎng)絡，把七橋問題化成判斷連通網(wǎng)絡能否一筆畫的問題。之后他發(fā)表一篇論文，證明了上述走法是不可能的。并且給出了連通網(wǎng)絡可一筆畫的充要條件這一著名的結(jié)論。4最新版整理ppt一筆畫問題一筆畫問題：從某一點開始畫畫，筆不離紙，各條線路僅畫一次，最后回到原來的出發(fā)點。5最新版整理pptbca圖1v2v3v1v4圖2圖1和圖2當中哪一個圖滿足：從圖中任何一點出發(fā)，途徑每條邊，最終還能回到出發(fā)點？試想：一個圖應該滿足什么條件才能達到上面要求呢？6最新版整理ppt一筆畫問題凡是能一筆畫出的圖，奇點的個數(shù)最多有兩個。始點與終點重合的一筆畫問題，奇點的個數(shù)必是0。奇點：那個點的角度來看，數(shù)有多少條線從連接著那個點，如果連接那個點的線的數(shù)量是奇數(shù)條，那這個點就是奇點，反之，就是偶點。在一個多重邊的連通圖中，從某個頂點出發(fā)，經(jīng)過不同的線路，又回到原出發(fā)點，這樣的線路必是尤拉圖，即能一筆畫出的圖必是尤拉圖。7最新版整理ppt定理：連通的多重圖G是尤拉圖，當且僅當G中無奇點。定理：任何一個圖中的奇點個數(shù)必為偶數(shù)。推論：連通的多重圖有尤拉鏈，當且僅當圖中有兩個奇點。8最新版整理ppt歐拉圖及求歐拉回路的算法歐拉行跡—含所有邊恰好一次的行跡歐拉回路—含所有邊恰好一次的回路歐拉圖—存在歐拉回路的圖

設G是連通圖,下列命題等價:(1)G是歐拉圖.(2)每個頂點的度數(shù)都是偶數(shù).(3)G是兩兩無公共邊的圈的并.9最新版整理ppt歐拉圖及求歐拉回路的算法求歐拉回路的算法(Fleury算法，1921年)算法思想:“過河拆橋,盡量不走獨木橋”.

即若已選定跡,從中選取下一條邊使得與相關(guān)聯(lián),且不是的橋,除非無邊可選.Fleury算法的復雜度是10最新版整理ppt歐拉圖及求歐拉回路的算法求歐拉回路的算法(回路算法)算法思想:首先得到一個回路C1,再在剩下的圖G-C1中求一條與C1有公共頂點的回路C2,則C1與

C2構(gòu)成一個更長的回路,繼續(xù)下去可得到含所有邊恰好一次的回路.回路算法的復雜度是上述兩算法都是在連通歐拉圖中求歐拉回路的算法.11最新版整理ppt中國郵遞員問題一個郵遞員送信，要走完他負責投遞的全部街道，投完后回到郵局，應該怎樣走，使所走的路程最短？這個問題是我國管梅谷同志1960年首先求出來的，因此在國際上通稱為中國郵遞員問題。在物流活動中，經(jīng)常會遇到這樣的問題，如：每天在大街小巷行駛的垃圾車、灑水車、各售貨點的送貨車等都需要解決一個行走的最短路程問題。這個問題就是一筆畫問題。12最新版整理ppt管梅谷管梅谷教授。上海市人。1957年畢業(yè)于華東師范大學數(shù)學系。歷任山東師范大學講師、副教授、教授、校長，中國運籌學會第一、二屆常務理事，山東省數(shù)學學會第四屆副理事長，山東省運籌學會第一屆副理事長，山東省世界語協(xié)會理事長。是第六屆全國政協(xié)委員。從事運籌學及其應用的研究，對最短投遞路線問題的研究取得成果。所提模型在國外稱為中國投遞問題。13最新版整理ppt中國郵遞員問題在一個連通的賦權(quán)圖G（V，E）中，求一條回路，使該回路包含G中的每條邊至少一次，且該回路的權(quán)最?。ǚQ此回路為最優(yōu)回路或者中國郵路）14最新版整理ppt求解中國郵遞員問題的算法

如果中國郵遞員問題中的圖是歐拉圖，那么歐拉回路就是最優(yōu)回路。一般情形下（不是歐拉圖），最優(yōu)回路包含某些邊至少兩次。這時求最優(yōu)回路的思想是：在圖G中添加一些重復邊使新圖G*成為歐拉圖，且使得所有添加的重復邊的權(quán)和最小。再由G*的歐拉回路得到G的最優(yōu)回路。15最新版整理ppt求解中國郵遞員問題的算法管梅谷教授首先提出的方法是奇偶點圖上作業(yè)法（1962年）Edmonds，Johnson（1973年）給出有效算法。復雜度為16最新版整理ppt求解中國郵遞員問題的算法（例）17最新版整理ppt求解中國郵遞員問題的算法（例）18最新版整理ppt解決這樣的問題，可以采用奇偶點圖上作業(yè)法：如果在配送范圍內(nèi)，街道中沒有奇點，那么他就可以從配送中心出發(fā)，走過每條街道一次，且僅一次，最后回到配送中心，這樣他所走的路程也就是最短的路程。19最新版整理ppt問題對于有奇點的街道圖，該怎么辦呢？這時就必須在每條街道上重復走一次或多次。20最新版整理ppt舉例說明如圖所示。v1v2v3v4v5v632445264821最新版整理ppt如果在某條路線中，邊[vi,vj]上重復走幾次，我們就在圖中vi,vj之間增加幾條邊，令每條邊的權(quán)和原來的權(quán)相等，并把所增加的邊，稱為重復邊，于是這條路線就是相應的新圖中的尤拉圖。原來的問題可以敘述為在一個有奇點的圖中，要求增加一些重復邊，使新圖不含奇點，并且重復邊的總權(quán)為最小。我們把使新圖不含奇點而增加的重復邊簡稱為可行（重復邊）方案，使總權(quán)最小的可行方案為最優(yōu)方案。22最新版整理ppt現(xiàn)在的問題是第一個可行方案如何確定？在確定一個可行方案后，怎么判斷這個方案是否為最優(yōu)方案？若不是最優(yōu)方案，如何調(diào)整這個方案？23最新版整理ppt車輛從某配送中心（v1）出發(fā)，給街道邊上的超市（v2,v3,v4,v5,v6,v7,v8,v9）送貨，如圖1所示。舉個例子v1v3v2v4v8v7v6v5v9254339546444圖124最新版整理ppt顯然街區(qū)圖上有奇點（4個），不滿足“一筆畫”的條件，則必然有一些街道要被重復走過（添加重復邊）才能回到原出發(fā)點。此時得到的圖就無奇點。那么該怎樣添加重復邊，使得圖中全為偶點呢？其實可以通過連接匹配的奇點得到！25最新版整理ppt第一步：確定初始可行方案v1v3v2v4v8v7v6v5v9254339546444圖226最新版整理ppt這樣就得到初始方案.在這個圖中，沒有奇點，故稱它為歐拉圖。對應于這個可行方案，重復邊總權(quán)為51。27最新版整理ppt思考這樣的可行方案是不是只有一種呢？在確定一個可行方案后，怎么判斷這個方案是否為最優(yōu)方案？若不是最優(yōu)方案，如何調(diào)整這個方案？28最新版整理ppt第二步：調(diào)整可行方案最優(yōu)方案必須滿足以下（1）（2）兩個條件：（1）在最優(yōu)方案中,圖的每一邊最多有一條重復邊（2）在最優(yōu)方案中,圖中每個圈上的重復邊的總權(quán)不大于該圈總權(quán)的一半。29最新版整理ppt第二步：調(diào)整可行方案首先，去掉多余的重復邊，使圖中每一邊最多有一條重復邊。見圖3v1v2v3v4v5v6v7v8v9444342346955圖330最新版整理ppt第二步：調(diào)整可行方案其次，如果把圖中某個圈上的重復邊去掉，而給原來沒有重復邊的邊上加上重復邊，圖中仍然沒有奇點。因而如果在某個圈上重復邊的總權(quán)數(shù)大于這個圈的總權(quán)數(shù)的一半，像上面所說的那樣做一次調(diào)整，將會得到一個總權(quán)下降的可行方案。31最新版整理ppt第二步：調(diào)整可行方案在圖4中，圈（v2,v3,v4,v9,v2）的總長度為24，但圈上重復邊總權(quán)為14，大于該圈總長度的一半，因此可以做一次調(diào)整，以[v2,v9]，[v9,v4]上的重復邊代[v2,v3]，[v3,v4]上的重復邊，使重復邊總長度下降為17。見圖432最新版整理pptv1v2v3v4v5v6v7v8v9444342346955圖433最新版整理ppt檢查圖4中圈（v1,v2,v9,v6,v7,v8,v1）的總長度為24，但圈上重復邊總權(quán)為13，大于該圈總長度的一半，因此可以做一次調(diào)整，使重復邊總長度下降為15。見圖5。34最新版整理ppt

圖535最新版整理ppt檢查圖5，均滿足條件（1）和（2），于是得到最優(yōu)方案。圖5中的任一歐拉圈都是汽車的最優(yōu)配送路線。如：v1-v2-v9-v8-v1-v8-v7-v6-v5-v4-v9