当前位置: 简表范文网 > 专题范文 > 公文范文 >

扫雪问题数学方法研究

| 来源:网友投稿

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

推荐访问:扫雪 数学 方法 研究

相关推荐

有关扫雪的小学生日记大全【10篇】 2024年度深化城乡融合“十百千万”工程工作总结(全文) 在办公室干部座谈会上讲话稿 在全县招商引资大会上致辞(完整) 经验交流:“五个坚持”创新加强党建设(全文完整) 2024年度经验交流:打造品牌集群,提升党建工作质量【精选推荐】 2024年在“乡村振兴美丽家园”创建活动上经验发言材料 202X年区法学会建设调研报告【精选推荐】 X市经信工作总结和2024年思路(范文推荐) 2024年2024年全国“两会”测试100题(全文完整) 2024年度全文学习2024年安全生产治本攻坚三年行动 扫雪趣事作文400字,菁选2篇【完整版】 单位扫雪报道稿,菁选2篇 扫雪应急预案(范例推荐) 数学教师工作内容3篇 我的数学与生活小论文【六篇】 关于新人教版九年级下数学教学计划(精选范文2篇) 2022年度高三数学老师个人总结大全(10篇)【优秀范文】 2022年度小学数学老师年度总结最新(10篇)(全文完整) 供给侧结构性改革的政治经济学方法论探析 熊彼特经济学方法论研究的新进展 从方法论视角浅析教育管理整合论 对结构化方法和面向对象方法的对比和讨论 蟹爪兰浇水方法及养殖方法,菁选3篇(完整文档) 欧美职业教育最新研究成果(通用3篇) 研究课题工作措施范文(通用5篇) 奥运会研究性报告范文(通用4篇) 研究生个人中期总结【四篇】 2022在全市政府系统办公室(研究室)主任会议上讲话

热门文章

2022年大学生档案自我鉴定300字10篇

2022年普通大学生个人社会实践实习报告精选服务社会做好思想准备和业务准备,公司内部电脑系统都是统一英文系统,就要求自己以职场……[详细]2022年党员思想汇报例文两篇【完整版】所以在以后的学习和生活中,经历过苦难的中国,工作以及生活中,特别是通过学习党章党纪……[详细]企业员工服务意识培训心得体会

追梦筑梦圆梦演讲稿

最近发表了一篇名为《追梦筑梦圆梦演讲稿》的范文,感觉很有用处,这里给大家转摘到。演讲稿特别注重结构清楚,层次简明。在日新月异的现代社会中,在很多情况下需要用到演讲稿,如何写一份恰当的演讲稿呢?下面是小编为大家整理的追梦筑梦圆梦演讲稿,希望能够帮助到大家!追梦筑梦圆梦演讲稿1尊敬的

《********大宣讲特别节目》直播观后感

最近发表了一篇名为《2022《********大宣讲特别节目》直播观后感【精选】》的范文,感觉写的不错,希望对您有帮助,希望对网友有用。,安全,在学校里,在校外,安全这个词恐怕是再熟悉不过了吧,让将安全铭记心中,时进刻刻都做到安全,让父母不再操心,让长辈不再担心,让安全从我做起,从身边

2022年度有关安全学习心得合集(2022年)

本页是最新发布的《有关安全学习心得》的详细范文参考文章,感觉很有用处,看完如果觉得有帮助请记得(CTRL+D)收藏本页。有了一些收获以后,可以记录在心得体会中,这么做能够提升的书面表达能力。相信许多人会觉得心得体会很难写吧,下面是小编为大家收集的有关学习心得,供大家参考借鉴,希望可以帮

2022员工培训学习心得体会范本合集(范文推荐)

最近发表了一篇名为《员工培训学习心得体会范文》的范文,感觉写的不错,希望对您有帮助,为了方便大家的阅读。培训能让员工不断的提高,并清楚的意识到自己的缺点。经过员工培训,你一定有许多的收获,不妨来写一篇员工培训心得。你是否在找正准备撰写“员工培训心得体会范文”,下面小编收集了相关的素材,

2022年度中考优秀作文素材别样美三篇

最近发表了一篇名为《中考优秀作文素材别样的美精选三篇》的范文,好的范文应该跟大家分享,看完如果觉得有帮助请记得(CTRL+D)收藏本页。雨过天晴,花坛边上,几只蜗牛缓缓的爬行着,留下一道彩虹般的痕迹,那柔软的外面,是坚硬的外壳,那也是一道的美丽。下面是小编为大家收集整理的关于素材别样的美精

2022不期而遇作文600字初中记叙文

《不期而遇作文600字初中记叙文》是一篇好的范文,感觉很有用处,希望对网友有用。,美词,像是袭袭的寒风慢慢轻掠大地,刺刺的,一缕****的阳光下有一小缕的橘红色静静的生长。下面是小编为大家收集整理的关于不期而遇600字初中记叙文,一起来看看吧!不期而遇作文600字篇一苏轼有语人间有味是清欢,或许正是

2022年度幼儿园清明节主题活动总结范本

《2022幼儿园清明节主题活动总结范文【精选】》是一篇好的范文,感觉很有用处,为了方便大家的阅读。,又称踏青节、行清节、三月节、祭祖节等,节期在仲春与暮春之交。清明节源自上古时代的祖先信仰与春祭礼俗,以下是小编整理的2022园清明节主题总结,希望可以提供给大家进行参考和借鉴。2022幼儿园清明节

建团百周年活动策划

《2022建团百周年活动策划【精选】》是一篇好的范文,感觉很有用处,希望大家能有所收获。党的领导是共青团顺利发展的关键所在,无论是中国早期青年团的建立,还是中国共青团的正式成立,都离不开党的领导。下面小编为大家整理了2022建团百周年策划【精选】的相关内容,以供参考,希望给大家带来帮助!20

以小见大作文500字范本(范文推荐)

最近发表了一篇名为《以小见大作文500字范文【精选】》的范文,感觉写的不错,希望对您有帮助,重新编辑了一下发到。一件事情的发生,离不开时间、地点、人物、事情的起因、经过和结果这六方面,即常说的六要素,只有交待清楚这几方面,才能使读者对所叙述的事,有个清楚、全面的了解。这里小编

大一暑假社会实践报告(精选文档)

本页是最新发布的《2022大一暑假社会实践报告》的详细范文参考文章,感觉写的不错,希望对您有帮助,希望大家能有所收获。这个暑假过得是否充实呢,有些小伙伴在假期中参加了实践,那么如何做一份报告呢?下面是小编整理的2022大一暑假社会实践报告,仅供参考,希望能够帮助到大家。2022大一暑假社会

小学品德教师期末工作总结范本合集

最近发表了一篇名为《小学品德教师期末工作总结范文》的范文,感觉很有用处,重新整理了一下发到这里[http: www fwwang cn]。时光飞逝,如梭之日,回顾这段时间的工作,一定有许多的艰难困苦,是时候在工作总结中好好总结过去的成绩了。下面小编在这里为大家精心整理了几篇小学教师期