中國(guó)郵遞員問(wèn)題p課件

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

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

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

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

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

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