掃雪問題數學方法研究

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

關鍵詞：歐拉回路 Fleury算法 matlab

中圖分類號：O1 文獻標識碼：A 文章編號：1673-9795（2013）09（a）-0069-01

1 問題重述

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

2 問題分析

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

3 問題假設與符號說明

3.1 問題假設

（1）掃雪車在作業的過程中不會出現突發狀況使其停止工作。

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

（3）掃雪車在拐彎處不進行特殊的掃雪處理。

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

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

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

（7）假設掃雪車經過路面一次即把該單向路面清掃徹底。

（8）掃雪車作業過程中，已經停雪，清掃完的路面不會被落雪重新覆蓋，且不涉及融雪問題。

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

（10）兩掃雪車功率一樣且作業過程以勻速進行。

（11）假設高速公路上速度夠快，并且無需掃雪。

3.2 符號說明

表示第個頂點；

表示第條邊；

表示頂點集；

表示邊集；

表示由頂點集和邊集組成的有向圖；

表示路程；

表示速度。

4 模型建立與求解

4.1 模型引入

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

4.2 歐拉回路介紹[1]

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

4.3 模型的建立與求解

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

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

定理1：無向圖是歐拉圖當且僅當它是連通圖且沒有奇度頂點。

定理2：有向圖是歐拉圖當且僅當它是強連通的且每個頂點的入度等于出度。

4.3.1 模型建立

由于本題是對市內的公路掃雪，且公路是雙向的，所以可以把本圖當作是有向圖處理，根據定理2可以運用Fleury算法[3]尋找出一條歐拉回路。

Fleury算法：

（1）任取，令。

（2）設，

如果中沒有與關聯的邊，則計算停止；否則按下述條件從中任取一條邊：

（a）與相關聯；

（b）除非無別的邊可供選擇，否則不應該為中的橋。

（3）令，返回（2）。

當算法停止時所得簡單回路為一條歐拉回路。

4.3.2 模型求解

Step 1：對交叉點標序

Step 2：建立頂點的鄰接矩陣（略）

Step 3：根據和Fleury算法，在matlab平臺上編程求解（程序見附錄一）。運行結果如圖2。

該運行結果顯示：該圖不存在歐拉回路。

5 模型優缺點分析

5.1 模型優點

（1）對于復雜圖可以根據算法準確求出歐拉回路。

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

5.2 模型缺點

（1）對于簡單圖顯得相對繁瑣。

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

參考文獻

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

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

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