- 1、本文档共12页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
匹配应用的实现数学建模创新
中山一中 黄源河 例题1 Place the Robots(ZOJ1654) 问题描述 有一个N*M(N,M=50)的棋盘,棋盘的每一格是三种类型之一:空地、草地、墙。机器人只能放在空地上。在同一行或同一列的两个机器人,若它们之间没有墙,则它们可以互相攻击。问给定的棋盘,最多可以放置多少个机器人,使它们不能互相攻击。 例题1 Place the Robots(ZOJ) 模型一 例题1 Place the Robots(ZOJ) 模型一 例题1 Place the Robots(ZOJ) 模型二 例题1 Place the Robots(ZOJ) 模型二 例题1 Place the Robots(ZOJ) 模型二 例题1 Place the Robots(ZOJ) 小结 例题2 救护伤员(TOJ1148) 无情的海啸夺取了无数人的生命.很多的医疗队被派往灾区拯救伤员.就在此时,医疗队突然发现自己带的药品已经不够用了,只剩下了N种。(1 n = 20),随着病人病情的发展,每种药在每天能获得的效果是不一样的。同时,每天病人只能服用一种药。也就是说,这些药还够支持N天。现在,给出你每种药在每天使用的效果,请你判断当每种药都用完后所有药达到的效果之和最大可以是多少。 例题3 打猎 猎人要在n*n的格子里打鸟,他可以在某一行中打一枪,这样此行中的所有鸟都被打掉,也可以在某一列中打,这样此列中的所有鸟都打掉。问至少打几枪,才能打光所有的鸟? 建图:二分图的X部为每一行,Y部为每一列,如果(i,j)有一只鸟,那么连接X部的i与Y部的j。 该二分图的最大匹配数则是最少要打的枪数。 例题4 最小路径覆盖 一个不含圈的有向图G中,G的一个路径覆盖是一个其结点不相交的路径集合P,图中的每一个结点仅包含于P中的某一条路径。路径可以从任意结点开始和结束,且长度也为任意值,包括0。请你求任意一个不含圈的有向图G的最小路径覆盖数。 理清一个关系:最小路径覆盖数=G的定点数-最小路径覆盖中的边数 例题4 最小路径覆盖 试想我们应该使得最小路径覆盖中的边数尽量多,但是又不能让两条边在同一个顶点相交。 拆点:将每一个顶点i拆成两个顶点Xi和Yi。然后根据原图中边的信息,从X部往Y部引边。所有边的方向都是由X部到Y部。 例题4 最小路径覆盖 因此,所转化出的二分图的最大匹配数则是原图G中最小路径覆盖上的边数。因此由最小路径覆盖数=原图G的顶点数-二分图的最大匹配数便可以得解。 * * Wall Grass Empty 5 4 6 7 8 3 2 1 1 2 3 4 6 5 7 8 于是,问题转化为求图的最大独立集问题。 在问题的原型中,草地,墙这些信息不是我们所关心的,我们关心的只是空地和空地之间的联系。因此,我们很自然想到了下面这种简单的模型: 以空地为顶点,有冲突的空地间连边,我们可以得到右边的这个图: 5 4 6 7 8 3 2 1 1 2 3 4 6 5 7 8 在问题的原型中,草地,墙这些信息不是我们所关心的,我们关心的只是空地和空地之间的联系。因此,我们很自然想到了下面这种简单的模型: 以空地为顶点,有冲突的空地间连边,我们可以得到右边的这个图: 这是NP问题! 我们将每一行,每一列被墙隔开,且包含空地的连续区域称作“块”。显然,在一个块之中,最多只能放一个机器人。我们把这些块编上号。 同样,把竖直方向的块也编上号。 1 2 3 4 5 1 2 3 4 1 2 3 4 5 1 2 3 4 把每个横向块看作X部的点,竖向块看作Y部的点,若两个块有公共的空地,则在它们之间连边。 于是,问题转化成这样的一个二部图: 1 1 2 2 3 3 4 4 5 由于每条边表示一个空地,有冲突的空地之间必有公共顶点,所以问题转化为二部图的最大匹配问题。 1 2 3 4 1 2 3 5 4 1 1 2 2 3 3 4 4 5 比较前面的两个模型:模型一过于简单,没有给问题的求解带来任何便利;模型二则充分抓住了问题的内在联系,巧妙地建立了二部图模型。为什么会产生这种截然不同的结果呢?其一是由于对问题分析的角度不同:模型一以空地为点,模型二以空地为边;其二是由于对原型中要素的选取有差异:模型一对要素的选取不充分,模型二则保留了原型中“棋盘”这个重要的性质。由此可见,对要素的选取,是图论建模中至关重要的一步。
您可能关注的文档
- 公共部门绩效管理PPT--胡税根.ppt
- 公关部培训大纲.doc
- 真空压铸机工作总结.pptx
- 公务员、事业单位招聘考试——“三农”工作知识练习题共五章附答案.doc
- 公务员、事业单位公共管理考试复习题.doc
- 公关关系基础课件.pptx
- 北师大版高中英语模块1一8单词表.doc
- 北广集团项目建议书.ppt
- 公务员事业单位考试-2016年时事政治热点汇总.doc
- 公务员制度复习资料.doc
- 甘肃省白银市会宁县第一中学2025届高三3月份第一次模拟考试化学试卷含解析.doc
- 2025届吉林市第一中学高考考前模拟生物试题含解析.doc
- 四川省三台县芦溪中学2025届高三下第一次测试生物试题含解析.doc
- 2025届江苏省启东市吕四中学高三适应性调研考试历史试题含解析.doc
- 浙江省宁波市十校2025届高三二诊模拟考试历史试卷含解析.doc
- 甘肃省甘南2025届高考生物必刷试卷含解析.doc
- 河北省石家庄市一中、唐山一中等“五个一”名校2025届高考历史四模试卷含解析.doc
- 江西省南昌市进贤一中2025届高考生物考前最后一卷预测卷含解析.doc
- 甘肃省白银市会宁县第四中学2025届高三第二次模拟考试历史试卷含解析.doc
- 宁夏银川市宁夏大学附属中学2025届高考化学押题试卷含解析.doc
最近下载
- 2024年上海市各区中考二模语文分类汇编 现代文1之说明文.docx VIP
- 国开03129社会心理适应任务1答案.pdf VIP
- 反电信网络诈骗知识竞赛题库(含答案).docx VIP
- thelibidofortheugly全文讲义学习.pptx
- 申论规范词1000条【2024版】.doc VIP
- 中粮家佳康养殖部生产管理SOP题库(202112)附有答案.docx
- 技改革新方法与实践理论考试题库-下(多选、判断题汇总).docx
- 2024年秋新版北师大版一年级上册数学全册教案.pdf VIP
- 2024年上海市各区中考二模语文分类汇编 现代文阅读.docx VIP
- 90米天然气隧道窑使用说明书.pdf
文档评论(0)