中國郵遞員問題p課件

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

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

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

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

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

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