文档介绍：洒水车问题
指导老师: 窦霁虹
报告人: 林小围20021090086
黄志华20021090075
张宁辉20021090062
日期: 2005年6月3日
摘要
本文提出西北大学洒水车的路线问题,结合西北大学路面的实际情况将其进行抽象,建立了图论模型。并引进了“中国邮路问题”的理论与算法对问题进行求解,然后将算法中逐步寻找具有奇度数节点最优匹配的过程进行改进,即建立等价的0-1规划模型,用Lingo软件求解,这样减少了算法中寻找包含奇度数节点回路的大量且易出错的工作。在文中,我们还解决了一个益智题,即如何走一个网格的每一边。
[关键词]:中国邮路问题佛罗莱算法奇偶点作业法图论模型 0-1规划
一、问题提出
西北大学的洒水车要给主要路面洒水,该如何确定行车路线?
二、问题分析
我们首先根据西北大学的实际情况确定需要洒水的路段。从网址[1]处得到校园的平面图,并进行的细化,绘制出在尺度上大致准确的示意图(图 1)。洒水车要给主要路面洒水,也就意味着行车路线必需经过图示所有的路面至少一次。这类似于图论中一个典型的问题:中国邮路问题。中国邮路问题说的是:一个邮递员从邮局出发,到所辖街道投递邮件,最后返回邮局,如果他必须走遍所辖的每条街道至少一次,那么该如何选择投递路线,使所走的路程最短。
图 1
三、假设与符号约定
假设:
洒水车行驶过一次即能满足路面的洒水要求;
洒水车一次加水,即有足够水量给图示所有路面洒水,或者用完水后能在可以忽略路程内加水;
符号约定:
:图的第个节点;
:图中连接第个顶点与第个节点的边;
:边上的权;
:以为节点集,以为边集的图;
:以为起点为终点的路;
:图的第个节点的度数;
:图的一个附加边子集;
:边集的总权;
:经过边的次数;
:最短路矩阵
四、一些基本概念、算法和定理
下面是本文将要用到的一些基本概念、算法和定理:
欧拉回路:设G(V,E)为一个图,若存在一条回路,使它经过图中的每条边且只经过一次又回到起始节点,就称这种回路为欧拉回路,并称图G为欧拉图。
节点的度数:连接节点的边数为此节点的度数。当为奇数时,称为奇节点;否则,称为偶节点。
附加边子集:将图的奇节点配对,每对节点之间在图中有相应的最短路,连接这些最短路即构成一个附加边子集。
佛罗莱算法(Fleury Algorithm):
Step 1:任取起始节点,取连接这起始节点的任一边为初始路,即;
Step 2:设路已经选出,则从中选出边,使与相连,除非没有其他选择。不应为的断边,即仍为连通图;
Step 3:重复Step 2直到不能进行下去为止。
确定邮路问题最优路线的定理(证明从略):
设为一个连通的赋权图,则使附加边子集的权数为最小的充要条件是(1)中任意边至多重复一次;(2)中的任意回路中重复边的权数之和不大于该回路总和的一半。
上面定理的证明给我们提供了一般情况下寻求最优投递路线的方法,即奇偶点作业法:
Step 1:任给初始方案,使图的各节点的度数为偶数,图成为边权的欧拉图;
Step 2:检查每一回路中重复边的长度和是否超过回路长度的一半,如是,则现行方案即为最优解,否则进行下一步;
Step 3:调整重复边,即将回路中重复的边改为不重复,不重复的边改为重复