城市道路掃雪模型課件

圖論模型

瑞士數(shù)學(xué)家歐拉(E.Euler)在研究哥尼斯堡七橋問題的同時(shí)開創(chuàng)了圖論研究的先河。經(jīng)過(guò)兩百多年的發(fā)展，尤其是在20世紀(jì)中葉以后，伴隨著計(jì)算機(jī)科學(xué)的發(fā)展，圖論也得到迅速發(fā)展和廣泛應(yīng)用，內(nèi)容及其豐富。這里僅介紹圖論中的幾個(gè)最常見問題，主要目的是通過(guò)一些例子來(lái)闡述它們的應(yīng)用價(jià)值。9/12/20231圖論模型瑞士數(shù)學(xué)家歐拉(E.E

§1城鎮(zhèn)道路掃雪模型

郵遞員從郵局中取出郵件，遞送到不同地點(diǎn)，然后再返回郵局。假設(shè)要求他至少一次走過(guò)他投遞范圍內(nèi)的每一條街道，我們希望選擇一條盡可能短的路線。這個(gè)問題稱為中國(guó)郵遞員問題，因?yàn)樗俏覈?guó)數(shù)學(xué)家管梅谷首先研究的。在一個(gè)網(wǎng)絡(luò)N=(V,E,W)中，經(jīng)過(guò)它的每條邊的鏈稱為歐拉鏈，經(jīng)過(guò)N中每一邊至少一次的閉鏈稱為N的環(huán)游，經(jīng)過(guò)N中每一邊恰好一次的環(huán)游稱為歐拉環(huán)游。一個(gè)圖能一筆畫就是該圖有歐拉環(huán)游。顯然中國(guó)郵遞員問題就是在具有非負(fù)權(quán)的網(wǎng)絡(luò)中找出一條權(quán)最小的環(huán)游，這種環(huán)游稱為最優(yōu)環(huán)游。9/12/20232

§1城鎮(zhèn)道路掃雪模型郵遞員從郵

若N有歐拉環(huán)游，則它的每一條歐拉環(huán)游具有相同的權(quán)，它也必然是最優(yōu)環(huán)游。對(duì)有歐拉環(huán)游的網(wǎng)絡(luò)，我們可以采用弗萊里（Fleury）算法求得N的最優(yōu)環(huán)游。弗萊里算法計(jì)算步驟如下：（１）任意選取N的一個(gè)頂點(diǎn)ｖ0，置Z=ｖ0。（２）假設(shè)鏈Z=v0e1v1…eivi已選定，從E\{e1,e2,…,ei}中按下述方法選取ei+1；①ei+1和vi相關(guān)聯(lián)；9/12/20233若N有歐拉環(huán)游，則它的每一條歐拉環(huán)游具

②ei+1盡量不選Gi（是G中去掉邊e1,e2,…,ei而得到的圖）的割邊（即去掉此邊后，圖Gi變?yōu)椴贿B通），除非沒有非割邊可選擇。（３）設(shè)ei+1另一關(guān)聯(lián)點(diǎn)為ｖi+1。若E\{e1,…,ei+1}?，重復(fù)步驟（2）；否則v1e1v2…ei+1vi+1即為N的一條歐拉環(huán)游。若網(wǎng)絡(luò)N沒有歐拉環(huán)游，此時(shí)最優(yōu)環(huán)游通過(guò)的某些邊將超過(guò)一次。例如圖1(a)的圖中xuywvzwyxuwvxzyx是最優(yōu)環(huán)游，此時(shí)四條邊ux,xy,yw和wv都被這環(huán)游通過(guò)二次。9/12/20234②ei+1盡量不選Gi（是G中去掉12265122423423xvwyzxvyz121236511222(b)圖1w9/12/2023512265122423423xvwyzxvyz1212365下面是一種有關(guān)引進(jìn)重復(fù)邊的算法。將邊e的兩個(gè)端點(diǎn)再用一條權(quán)為w(e)的新邊連接時(shí)，稱為邊e的重復(fù)邊。例如把上述圖(a)中邊ux,xy,yw和wv重復(fù)，得到圖1（b）。因此，中國(guó)郵遞員問題可以重新敘述如下：給定一個(gè)具有非負(fù)權(quán)的網(wǎng)絡(luò)N，①用添重復(fù)邊的方法求得N的一個(gè)歐拉賦權(quán)母圖N+，使得盡可能小；②求N+的歐拉環(huán)游。9/12/20236下面是一種有關(guān)引進(jìn)重復(fù)邊的算法。將邊e

解②可用弗萊里算法；解①已有好算法（愛德蒙斯Edmonds和約翰遜Johnson算法），由于這一算法比較復(fù)雜，這里就不再介紹了，有興趣的讀者可以參閱有關(guān)圖論算法的書。當(dāng)點(diǎn)數(shù)較少時(shí)，可用奇偶點(diǎn)圖上作業(yè)法求解，為此我們不加證明介紹下述兩個(gè)結(jié)論。結(jié)論1網(wǎng)絡(luò)N有歐拉環(huán)游當(dāng)且僅當(dāng)N中每一點(diǎn)的次為偶數(shù)。結(jié)論2最優(yōu)環(huán)游具有這樣的性質(zhì)：（1）每條邊至多重復(fù)一次；（2）每一圈上重復(fù)邊的長(zhǎng)度不超過(guò)該圈總長(zhǎng)的一半。當(dāng)某一圈上重復(fù)邊的長(zhǎng)度超過(guò)該圈總長(zhǎng)的一半時(shí)，將該9/12/20237解②可用弗萊里算法；解①已有好算法圈中的所有重復(fù)邊去掉，該圈中未重復(fù)的邊重復(fù)，從而得奇偶點(diǎn)圖上作業(yè)法如下：（1）若N每一點(diǎn)的次均為偶數(shù)，則用弗萊里算法求得其歐拉環(huán)游，此即為N的最優(yōu)環(huán)游。（2）若不然，則用添重復(fù)邊的辦法得到N的歐拉賦權(quán)母圖N*。求得N*的歐拉環(huán)游（用弗萊里算法）。（3）若某一條邊在歐拉賦權(quán)母圖N*中重復(fù)多次，只要去掉該邊的偶數(shù)次重復(fù)邊，總可以使得該邊至多重復(fù)一次，這樣的圖仍為歐拉賦權(quán)母圖。（4）然后逐一檢查N*的每一個(gè)圈，當(dāng)某一圈上重復(fù)邊的長(zhǎng)度超過(guò)該圈總長(zhǎng)的一半時(shí)，將該圈中的所有重復(fù)邊9/12/20238圈中的所有重復(fù)邊去掉，該圈中未重復(fù)的邊重復(fù)，從而得去掉，該圈中未重復(fù)的邊重復(fù)，所得到的圖也是歐拉賦權(quán)母圖。例設(shè)某郵遞員負(fù)責(zé)投遞郵件的街道如圖2（a）所示,求出該郵遞員的最短投遞路線。

解該網(wǎng)絡(luò)有8個(gè)奇點(diǎn):v2、v4、v5、v7、v8、v9、v11、v12，用添重復(fù)邊的辦法得圖2(b)。按結(jié)論2進(jìn)行調(diào)整,圈v4v10v11v5其總長(zhǎng)為12,而重復(fù)邊長(zhǎng)為11,此時(shí)去掉重復(fù)邊v4v10、v10v11、v11v5,添加重復(fù)邊v4v5。同樣在圈v2v3v9v7v6v2中其總長(zhǎng)為21，重復(fù)邊長(zhǎng)為12也超過(guò)一半。經(jīng)調(diào)整后得到新的網(wǎng)絡(luò)圖2（c）。9/12/20239去掉，該圈中未重復(fù)的邊重復(fù)，所得到的圖也是歐拉賦權(quán)母v2v3v5v6v8v7v9v12v13v2v5v6v8v7v9v11v12v13v2v3v5v6v8v7v9v11v13v1v4v10v1v4v10圖2(a)圖2(b)圖2(c)457444224511252v11v12v101v4v14v39/12/202310v2v3v5v6v8v7v9v12v13v2v5v6v8v7檢查圖2(c)的每一個(gè)圈,其重復(fù)邊的長(zhǎng)度均不大于該圈長(zhǎng)的一半,因此用弗萊里算法求得圖2(c)中網(wǎng)絡(luò)的歐拉環(huán)游即為要求的最優(yōu)環(huán)游。

下面一個(gè)問題是美國(guó)1990年數(shù)模競(jìng)賽B題:圖3(a)中的實(shí)線表示美國(guó)馬里蘭州威克米爾市需要清除積雪的雙向行車道路,虛線是州高速公路。雪后,兩輛掃雪車分別從地圖*號(hào)標(biāo)出的兩點(diǎn)以西約4英里處出發(fā)清掃道路上的積雪。掃雪車可以通過(guò)高速公路進(jìn)入市內(nèi)道路。假定掃雪過(guò)程中掃雪車不會(huì)損壞或停止,并且道路交叉處不需要另外附加的掃雪程序.試為兩車找出有效的路徑。應(yīng)用前面的方法.我們可以解決這個(gè)問題。

9/12/202311檢查圖2(c)的每一個(gè)圈,其重復(fù)邊的北圖3(a)3英里**9/12/202312北圖3(a)3英里**8/3/202312

1．問題的分析我們的目的是尋找一個(gè)有效的辦法用兩臺(tái)掃雪車清除威克米爾市內(nèi)道路（不包括州高速公路）的積雪。這個(gè)問題的有效解法應(yīng)該有以下特點(diǎn)：①掃完全部路面所花的時(shí)間盡量少；②掃雪完畢后，兩車應(yīng)盡快回到出發(fā)點(diǎn)；③兩車工作時(shí)間大致相同。如果掃雪車沒有重復(fù)走某一條路，或者掃雪車重復(fù)走的路徑和最小，我們就認(rèn)為掃雪所花的時(shí)間最少。為使交通盡快暢通，通常應(yīng)該把所花時(shí)間少放在最重要的地位來(lái)考慮。當(dāng)然，有時(shí)需要先掃除主要干線上的積雪，再考慮掃清剩下9/12/2023131．問題的分析8/3/202313

的道路，此時(shí)就要涉及確定哪一些路線是主干線的問題。2．模型的假設(shè)對(duì)模型作如下假設(shè)：①掃雪過(guò)程中沒有下雪，所有市內(nèi)道路都有積雪需要清除；②兩輛掃雪車性能相同，都能正常工作；③兩輛掃雪車司機(jī)駕駛技術(shù)相同，掃雪時(shí)，車速相同；④在所有交叉路口，包括市內(nèi)道路與高速公路的接口，掃雪車可不減速地轉(zhuǎn)彎；⑤兩輛車出發(fā)的時(shí)間相同；9/12/202314的道路，此時(shí)就要涉及確定哪一些路線是主干線的問題。8/

⑥每條路面的積雪范圍、厚度相同。3．模型的建立（1）雙行道問題假定每條道路均有兩條方向相反的行車道。此時(shí)，將地圖中每個(gè)交叉路口（包括市內(nèi)與高速公路的交叉口）看成點(diǎn)，每條市內(nèi)道路看成邊，它的長(zhǎng)度看成該邊對(duì)應(yīng)的權(quán)，這樣我們就得到了網(wǎng)絡(luò)N=(V,E,W)。由于每條公路均是雙行道，這樣的網(wǎng)絡(luò)N是一個(gè)歐拉有向圖，每點(diǎn)的入次和出次相同。利用弗萊里算法可以求得N的歐拉環(huán)游。如果只有一輛掃雪車，這就是中國(guó)郵遞員問題?，F(xiàn)在有兩輛掃雪車，為了使工作過(guò)程最優(yōu)，兩輛掃雪車應(yīng)掃過(guò)幾乎同樣長(zhǎng)9/12/202315⑥每條路面的積雪范圍、厚度相同。8/3/20度的道路。為此，我們將網(wǎng)絡(luò)N分成兩個(gè)子網(wǎng)絡(luò)Nˊ和N",使得Nˊ和N"均連通，且Nˊ和N"兩網(wǎng)絡(luò)的權(quán)盡可能相等。這可以用如下辦法實(shí)現(xiàn)：把網(wǎng)絡(luò)N分為兩個(gè)連通子網(wǎng)絡(luò)，分別算出兩個(gè)子網(wǎng)絡(luò)中所有邊的總長(zhǎng)度，由于N的總邊長(zhǎng)已知，在總長(zhǎng)較大的子網(wǎng)絡(luò)中減去一些與另一子網(wǎng)絡(luò)相連的邊，添加到總長(zhǎng)較小的子網(wǎng)絡(luò)中。最后調(diào)整的結(jié)果如圖3（b）所示。如果掃雪車在市內(nèi)道路交叉路口或市內(nèi)道路與高速公路交叉處可以掉頭，即掃雪車到達(dá)城市邊緣可以不經(jīng)高速公路而重新進(jìn)入市區(qū)，則可用上述方法求解。如果忽略掃雪車在高速公路上的行車時(shí)間，則可同上述情況一樣求解。否則，我們要將高速公路看成上述網(wǎng)絡(luò)的若干條新邊，然后再用上述方法求解。

9/12/202316度的道路。為此，我們將網(wǎng)絡(luò)N分成兩個(gè)子網(wǎng)絡(luò)Nˊ和N"-------高速公路*分劃處*******3英里******北圖3（b）*9/12/202317-------高速公路*******3英里******北圖

（2）單行道問題。近代噴氣掃雪車已問世，它靠噴射熱氣流來(lái)清除積雪。因此，這種掃雪車在雙行道一邊行駛時(shí)，就可輕易清除整條路面上的積雪，無(wú)需再沿另一邊重新行駛。求這種情況的最優(yōu)解問題稱為單行道問題。對(duì)這類問題，與雙行道問題一樣，將它對(duì)應(yīng)一個(gè)網(wǎng)絡(luò)N，并將N分成兩個(gè)子網(wǎng)絡(luò)N1和N2，要求N1和N2兩個(gè)子網(wǎng)絡(luò)的邊總長(zhǎng)度相等，這樣利用求解中國(guó)郵遞員問題的算法，可以分別求得N1和N2的歐拉環(huán)游，得到要求的近似解。9/12/202318（2）單行道問題。8/3/2023184、進(jìn)一步討論。對(duì)雙行道與單行道兩種情況，都必須對(duì)原網(wǎng)絡(luò)進(jìn)行分劃。為此，對(duì)原始途徑進(jìn)行測(cè)量，然后用手工或計(jì)算機(jī)輸入一定數(shù)量的數(shù)據(jù)，通過(guò)計(jì)算機(jī)將網(wǎng)絡(luò)進(jìn)行分劃。如果兩輛掃雪車的性能不同，或者兩輛