扫雪问题数学方法研究

摘 要：扫雪问题最优路径的选择是现实工作中经常遇到的问题，最优的路径可以节省资源和减少重复路线，对此提出以下模型寻找最优路径。通过分析，因为图中所有公路都是双向道路，所以根据图中存在欧拉回路的充要条件，本问题的解答可以转化为在有向图中寻找欧拉回路使得走过的路程不含有重复边。我们根据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.