文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 算法合集之《浅谈图论模型的建立与应用》
侵权投诉

算法合集之《浅谈图论模型的建立与应用》

【关键字】 图论模型、建立、转化 【摘要】 在近几年的信息学竞赛中,图论题目层出不穷。图论作为 一个新生的数学分支,相比其他数学分支来说,具有许多自有 的特性。利用图论解题,通常具有高效、简洁的便利。有了这 门工具,并不意味就能很好地解决问题,还在于我们能否熟练 地识别与建立一系列的图论模型。本文通过一些实例,简单地 介绍一下图论建模的方法。

把横向块作为X部的顶点,竖向块作为Y部的顶点,如果两个块之间有公共的空地,就在它们之间连边。这样,我们得到了下面的二部图:

算法合集之《浅谈图论模型的建立与应用》

1234

由于每条边表示一个空地,有冲突的空地之间必有公共顶点,所以问题转化为二部图的最大匹配问题。这是图论中的经典问题,可以用匈牙利算法解决。

[小结]

比较上面的两个模型,第一个过于简单,没有认清问题的本质;第二个则充分抓住了问题的内在联系,巧妙地建立了二部图模型。为什么会产生这样截然不同的结果呢?其一是由于对问题分析的角度不同,第一种模型以空地为点,第二种模型以空地为边;其二是由于第一种模型对原型中信息的选取不足,所建立的模型没有保留原型中重要的性质,而第二种模型则保留了原型中“棋盘”这个重要的性质。由此可见,对信息的选取,是图论建模中至关重要的一步。〖例题2〗出纳员的雇佣(ACM Tehran 2000)

[问题描述]

Tehran的一家每天24小时营业的超市,需要一批出纳员来满足它的需要。超市经理雇佣你来帮他解决他的问题——超市在每天的不同时段需要不同数目的出纳员(例如:午夜时只需一小批,而下午则需要很多)来为顾客提供优质服务。他希望雇佣最少数目的出纳员。

经理已经提供你一天的每一小时需要出纳员的最少数量——R0, R1, ..., R23。R0表示从午夜到上午1:00需要出纳员的最少数目,R1表示上午1:00到2:00之间需要的,等等。每一天,这些数据都是相同的。有N人申请这项工作,每个申请者I在没24小时中,从一个特定的时刻开始连续工作恰好8小时,定义tI(0≤tI≤23)为上面提到的开始时刻。也就是说,如果第I个申请者被录取,他(她)将从tI 时刻开始连续工作8小时。

你将编写一个程序,输入RI(I = 0..23)和tI (I = 1..N),它们都是非负整数,计算为满足上述限制需要雇佣的最少出纳员数目。在每一时刻可以有比对应的RI更多的出纳员在工作。

输入

上一页第3页

你可能喜欢

  • 图论算法
  • 算法竞赛
  • 图论及其应用
  • 遗传算法应用
  • 历年数学建模优秀论文
  • 图论论文

热门文档

相关文档

  • 算法合集之《图论模型的建立与转化》

    算法合集之《浅谈图论模型... 27页 免费 图论模型的建立及转化方法 2页 5...第三部分主要讨论了在图论模型的转化中,应用得较为广泛的两种方 法:拆分转化和...

  • 算法合集之《图论模型的建立与转化》

    算法合集之《图论模型的建立与转化》_天文/地理_自然科学_专业资料。算法合集...第三部分主要讨论了在图论模型的转化中,应用得较为广泛的两种方 法:拆分转化和...

  • 图论模型的建立

    图论模型的建立与应用 37页 免费 算法合集之《图论模型的建... 12页 免费 算法合集之《浅谈图论模型... 9页 免费 图论模型的构建 41页 免费 算法合集之《...

  • 图论模型的建立与转化

    图论模型的建立与应用 37页 免费 算法合集之《浅谈图论模型... 9页 免费 ...建立图论模型的目的和建立其它的数学模型一样,都是为了简化问题,突出要点,以 便...

  • 算法合集之《图论的基本思想及方法》

    算法合集之《浅谈图论模型... 27页 免费 图论的基本算法及应用 60页 2财富...图论模型为 平台挖掘问题 的性质 结语图论基本思想的精华 “模型 ” 建立模型 ...

  • 算法合集之《数学模型的建立和选择》

    算法合集之《数学模型的建立和选择》_IT/计算机_...我们就要想方设法将信 息原型对应到图论中的模型...信息原型的独特属性,并且 有效地在算法中加以应用. ...

  • 算法合集之《浅谈网络流算法的应用》

    算法合集之《浅谈网络流算法的应用》_IT/计算机_专业资料。算法合集之《浅谈...浅谈网络流算法的应用缺点:相对于其它图论算法来说,它的模型更加复杂,编程复杂度...

  • 算法合集之《图论的基本思想及方法》

    建立模型仿佛 图论的基本思想及方法 任恺 是为算法设计搭建一个平台, 接下来的... 算法合集之《浅谈图论模... 9页 免费 算法合集之《浅谈图论模... 27页 ...

  • 图论在给水调度模型中的应用

    图论模型的建立与应用 37页 免费 算法合集之《浅谈图论模型... 9页 免费喜欢此文档的还喜欢 图论模型在实际中的应用 66页 免费 图论的应用 13页 免费 图论 ...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email