掃雪問題數(shù)學(xué)方法研究

摘 要：掃雪問題最優(yōu)路徑的選擇是現(xiàn)實(shí)工作中經(jīng)常遇到的問題，最優(yōu)的路徑可以節(jié)省資源和減少重復(fù)路線，對(duì)此提出以下模型尋找最優(yōu)路徑。通過分析，因?yàn)閳D中所有公路都是雙向道路，所以根據(jù)圖中存在歐拉回路的充要條件，本問題的解答可以轉(zhuǎn)化為在有向圖中尋找歐拉回路使得走過的路程不含有重復(fù)邊。我們根據(jù)Fleury算法并在matlab上編程實(shí)現(xiàn)，運(yùn)行結(jié)果顯示本圖中不存在歐拉回路。

關(guān)鍵詞：歐拉回路 Fleury算法 matlab

中圖分類號(hào)：O1 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1673-9795（2013）09（a）-0069-01

1 問題重述

地圖（見圖1）中實(shí)線表示馬里蘭州（Maryland）威克米克市（Wicomico）清除積雪區(qū)域雙行的道路，虛線是州高速公路；雪后，兩輛掃雪車從地圖*號(hào)標(biāo)出的兩點(diǎn)的每一地點(diǎn)以西約6.44（4 mile）處出發(fā)清掃道路上的積雪。試為兩車找出有效的路徑。掃雪車可以通過高速公路進(jìn)出市內(nèi)道路。假定掃雪過程中車子不會(huì)損壞或停止，并且道路交叉處不需要附加掃雪過程。

2 問題分析

要解決的問題是：為兩臺(tái)掃雪車設(shè)計(jì)出有效的路徑進(jìn)行威克米克市積雪道路的清掃工作。兩輛掃雪車從地圖*號(hào)標(biāo)出的兩點(diǎn)的每一地點(diǎn)以西約6.44km（4 mile）處出發(fā)清掃道路上的積雪，市內(nèi)的道路均為雙向的，掃雪車在道路的交叉點(diǎn)上可轉(zhuǎn)向行駛。把道路的交點(diǎn)作為頂點(diǎn)集V，道路作為邊集E，把所給地圖定義為有向圖，利用圖論的知識(shí)進(jìn)行分析，有向圖D是強(qiáng)連通的，且每個(gè)頂點(diǎn)的入度等于出度，即有向圖D是一個(gè)歐拉圖，圖中存在歐拉回路。

3 問題假設(shè)與符號(hào)說明

3.1 問題假設(shè)

（1）掃雪車在作業(yè)的過程中不會(huì)出現(xiàn)突發(fā)狀況使其停止工作。

（2）掃雪車在開始工作到結(jié)束工作的過程中，燃油供應(yīng)足夠，不需要中途加油。

（3）掃雪車在拐彎處不進(jìn)行特殊的掃雪處理。

（4）掃雪車在拐彎處的路程忽略不計(jì)。

（5）掃雪車在高速公路上行駛不計(jì)入工作量。

（6）掃雪車可在高速公路上任意行駛且在高速公路與市內(nèi)公路接口處任意出入。

（7）假設(shè)掃雪車經(jīng)過路面一次即把該單向路面清掃徹底。

（8）掃雪車作業(yè)過程中，已經(jīng)停雪，清掃完的路面不會(huì)被落雪重新覆蓋，且不涉及融雪問題。

（9）掃雪車遵守交通規(guī)則，靠右行駛。

（10）兩掃雪車功率一樣且作業(yè)過程以勻速進(jìn)行。

（11）假設(shè)高速公路上速度夠快，并且無(wú)需掃雪。

3.2 符號(hào)說明

表示第個(gè)頂點(diǎn)；

表示第條邊；

表示頂點(diǎn)集；

表示邊集；

表示由頂點(diǎn)集和邊集組成的有向圖；

表示路程；

表示速度。

4 模型建立與求解

4.1 模型引入

現(xiàn)實(shí)生活中存在很多路徑最優(yōu)化選擇的問題，例如郵遞員問題、旅行商問題等。簡(jiǎn)言之就是我們要從一幅地圖中選擇出一條線路，或者是經(jīng)過所有邊一次且僅一次，或者是經(jīng)過所有點(diǎn)一次且僅一次。本質(zhì)上就是尋找歐拉回路和哈密爾頓回路。對(duì)于“掃雪問題”，我們需要尋找出一條歐拉回路，每條街道只掃一次就可以把所有街道清掃干凈。

4.2 歐拉回路介紹[1]

歐拉圖：通過圖（有向圖或無(wú)向圖）中所有邊一次且僅一次行遍所有頂點(diǎn)的回路稱為歐拉回路。具有歐拉回路的圖稱為歐拉圖。

4.3 模型的建立與求解

通過問題分析，我們需要找到一條通過圖中所有邊一次且僅一次行遍所有交叉點(diǎn)的回路。

無(wú)向圖和有向圖中存在歐拉回路的充要條件[2]：

定理1：無(wú)向圖是歐拉圖當(dāng)且僅當(dāng)它是連通圖且沒有奇度頂點(diǎn)。

定理2：有向圖是歐拉圖當(dāng)且僅當(dāng)它是強(qiáng)連通的且每個(gè)頂點(diǎn)的入度等于出度。

4.3.1 模型建立

由于本題是對(duì)市內(nèi)的公路掃雪，且公路是雙向的，所以可以把本圖當(dāng)作是有向圖處理，根據(jù)定理2可以運(yùn)用Fleury算法[3]尋找出一條歐拉回路。

Fleury算法：

（1）任取，令。

（2）設(shè)，

如果中沒有與關(guān)聯(lián)的邊，則計(jì)算停止；否則按下述條件從中任取一條邊：

（a）與相關(guān)聯(lián)；

（b）除非無(wú)別的邊可供選擇，否則不應(yīng)該為中的橋。

（3）令，返回（2）。

當(dāng)算法停止時(shí)所得簡(jiǎn)單回路為一條歐拉回路。

4.3.2 模型求解

Step 1：對(duì)交叉點(diǎn)標(biāo)序

Step 2：建立頂點(diǎn)的鄰接矩陣（略）

Step 3：根據(jù)和Fleury算法，在matlab平臺(tái)上編程求解（程序見附錄一）。運(yùn)行結(jié)果如圖2。

該運(yùn)行結(jié)果顯示：該圖不存在歐拉回路。

5 模型優(yōu)缺點(diǎn)分析

5.1 模型優(yōu)點(diǎn)

（1）對(duì)于復(fù)雜圖可以根據(jù)算法準(zhǔn)確求出歐拉回路。

（2）只需要變換圖的鄰接矩陣就可以重復(fù)利用，處理類似的問題。

5.2 模型缺點(diǎn)

（1）對(duì)于簡(jiǎn)單圖顯得相對(duì)繁瑣。

（2）只能用于求歐拉回路，實(shí)用性不廣。

參考文獻(xiàn)

[1]屈婉玲，耿素云，張立昂.離散數(shù)學(xué)[M].北京：高等教育出版社，2008：296.

[2]屈婉玲，耿素云，張立昂.離散數(shù)學(xué)[M].北京：高等教育出版社，2008：296-298.

[3]屈婉玲，耿素云，張立昂.離散數(shù)學(xué)[M].北京：高等教育出版社，2008：299.