行遍性问题2014

1、欢迎同学们参加暑期数学建模培训欢迎参加全国高校规模最大的基础性学科竞赛欢迎参加全国高校规模最大的基础性学科竞赛 - 一次参赛，终生受益！一次参赛，终生受益！全国大学生数学建模竞赛创办于1992年，每年一届，目前已成为全国高校规模最大的基础性学科竞赛，也是世界上规模最大的数学建模竞赛。 2014高教社杯全国大学生数学建模竞赛”赛题将于竞赛开始时（2014年9月12日上午8：00）发布在全国大学生数学建模竞赛、中国大学生在线网站、高等教育出版社网站、中国数模网等网站。21世纪是科学和工程数学化世纪是科学和工程数学化(Mathematization)的世纪的世纪. -美国科学基金会数学部主任美国科学

2、基金会数学部主任Eisenstein “As the statistics I have related to you today make clear, Mathematics Equals Opportunity. There could be no more crucial massage to send to the parents and students of America as we prepare for the coming century. ” Richard W. Riley, The state of mathematics education: Building a

3、 strong foundation for the 21st century, a speech presented at the invitation of the AMS Committee on Science Policy and the AMS Committee on Education, Notices of the AMS, v. 45(1998), no. 4, 487- 491. Richard W. Riley, 前美国教育部长前美国教育部长 Riley为了平息上世纪为了平息上世纪90年代发生在加州的数学战争年代发生在加州的数学战争(Math War)做做的报告中的话的

4、报告中的话 数学等于机会数学等于机会 Mathematics Equals Opportunity “我今天给你们的统计资料清楚地表明：我今天给你们的统计资料清楚地表明：“数学等于机会数学等于机会”。当我们为即将来临的。当我们为即将来临的世纪作准备时，不可能再送给美国父母和世纪作准备时，不可能再送给美国父母和学生别的更关键的信息了。学生别的更关键的信息了。行行 遍遍 性性 问问 题题一、中一、中 国国 邮邮 递递 员员 问问 题题二、推二、推 销销 员员 问问 题题三、建模案例：最佳灾情巡视路线三、建模案例：最佳灾情巡视路线（一）（一） 欧欧 拉拉 图图（二）（二） 中中 国国 邮邮 递递 员

5、员 问问 题题（一）（一） 哈哈 密密 尔尔 顿顿 图图（二）（二） 推推 销销 员员 问问 题题一一.中国邮递员问题中国邮递员问题(CPP-Chinese Postman Problem)一名邮递员负责投递某个街区的邮件一名邮递员负责投递某个街区的邮件. . 如何设计一条最短如何设计一条最短的投递路线的投递路线( (从邮局出发，经过投递区内每条街道至少一次，从邮局出发，经过投递区内每条街道至少一次，最后返回邮局最后返回邮局) )？由于这一问题是我国学者？由于这一问题是我国学者管梅谷管梅谷教授教授19601960年首先提出的，所以国际上称之为中国邮递员问题年首先提出的，所以国际上称之为中国邮递

6、员问题. . 二二. 旅行商问题旅行商问题(TSP-Traveling Salesman Problem)一名推销员准备前往若干城市推销产品一名推销员准备前往若干城市推销产品. 如何为他如何为他(她她)设设计一条最短的旅行路线计一条最短的旅行路线(从驻地出发，经过每个城市恰好从驻地出发，经过每个城市恰好一次，最后返回驻地一次，最后返回驻地)？这一问题的研究历史十分悠久，？这一问题的研究历史十分悠久，通常称之为旅行商问题通常称之为旅行商问题. BACDEFGHI 定定义义 设图 G =（V，E） ，ME，若 M 的边互不相邻，则称 M 是 G 的一个匹匹配配.若顶点 v与 M 的一条边关联，则称

7、 v是 M饱和的饱和的 设 M 是 G 的一个匹配，若 G 的每个顶点都是 M饱和的，则称 M 是 G 的理理想想匹匹配配.基本概念V7e3v1v2v3v4e1e2e4e5V5V6e6e7e8e9割边G的边e是割边的充要条件是e不含在G的圈中 割边的定义割边的定义：设G连通，e E(G),若从G中删除边e后，图G-e不连通，则称边e为图G的割边e3v1v2v3v4e1e2e4e5e6欧欧 拉拉 图图 定义定义设 G=(V,E)是连通无向图（）经过 G 的每边至少一次的闭通路称为巡回巡回（）经过 G 的每边正好一次的巡回称为欧拉巡回欧拉巡回（）存在欧拉巡回的图称为欧拉图欧拉图（）经过 G 的每边

8、正好一次的道路称为欧拉道路欧拉道路e3v1v2v3v4e1e2e4e5巡回：v1e1v2e2v3e5v1e4v4e3v3e5v1欧拉道路：v1e1v2e2v3e5v1e4v4e3v3欧拉巡回：v1e1v2e2v3e5v1e4v4e3v3e6v1定理定理对于非空连通图 G，下列命题等价：（）G 是欧拉图（）G 无奇次顶点（）G 的边集能划分为圈推推论论设 G 是非平凡连通图，则 G 有欧拉道路的充要条件是 G 最多只有两个奇次顶点e3v1v2v3v4e1e2e4e5e3v1v2v3v4e1e2e4e5e6欧拉图非欧拉图返回返回中国邮递员问题中国邮递员问题- -定义定义 邮递员发送邮件时，要从邮局

9、出发，经过他投递范围内的每条街道至少一次，然后返回邮局，但邮递员希望选择一条行程最短的路线这就是中国邮递员问题中国邮递员问题. 若将投递区的街道用边表示，街道的长度用边权表示，邮局街道交叉口用点表示，则一个投递区构成一个赋权连通无向图中国邮递员问题转化为：在一个非负加权连通图中，寻求一个权最小的巡回这样的巡回称为最最佳佳巡巡回回中国邮递员问题中国邮递员问题- -算法算法 1、G是欧拉图是欧拉图 此时 G 的任何一个欧拉巡回便是最佳巡回问题归结为在欧拉图中确定一个欧拉巡回Fleury 算算法法：求欧拉图的欧拉巡回 Fleury算法算法-基本思想基本思想：从任一点出发，每当访问一条边时，先要进行检

10、查如果可供访问的边不只一条，则应选一条不是未访问的边集的导出子图的割边割边作为访问边，直到没有边可选择为止.V7e3v1v2v3v4e1e2e4e5V5V6e6e7e8e9e10Fleury 算算法法 算算法法步步骤骤 ：（）任选 一个顶点 v0，令道路 w0=v0（）假定 道路 wi=v0e1v1e2eivi已经选好，则从 Ee1,e2, ,ei中选一条边 ei+1，使： a）ei+1与 vi相关联b）除非不能 选择，否 则一定要 使 ei+1不是 Gi=GE-e1,e2, ,ei的割边（）第（ ）步不 能进行时 就停止2、G 不是欧拉图不是欧拉图 若G不是欧拉图，则G的任何一个巡回经过某些

11、边必定多于一次 解决这类问题的一般方法是，在一些点对之间引入重复边（重复边与它平行的边具有相同的权），使原图成为欧拉图，但希望所有添加的重复边的权的总和为最小情形情形G正好有两个奇次顶点正好有两个奇次顶点（）用 Dijkstra 算法求出奇次顶点 u 与 v 之间的最短路径 P（）令 G*=GP，则 G*为欧拉图（）用 Fleury 算法求出 G*的欧拉巡回，这就是 G 的最佳巡回V7e3v1v2v3v4e1e2e4e5V5V6e6e7e8e9情形情形G有有n个奇次顶点个奇次顶点（n）Edmonds 最小对集算法：最小对集算法：基 本 思 想 ： 先将奇次顶点配对，要求最佳配对，即点对之间距离

12、总和最小再沿点对之间的最短路径添加重复边得欧拉图G*，G*的欧拉巡回便是原图的最佳巡回 算法步骤：算法步骤：（）用 Floyd 算法求出的所有奇次顶点之间的最短路径和距离（）以 G 的所有奇次顶点为顶点集（个数为偶数） ，作一完备图，边上的权为两端点在原图 G 中的最短距离，将此完备加权图记为 G1（）在 G 中沿配对顶点之间的最短路径添加重复边得欧拉图 G*（）用 Fleury 算法求出 G*的欧拉巡回，这就是 G 的最佳巡回（）求出G1的最小权理想匹配M，得到奇次顶点的最佳配对例例求右图所示投递区的一条最佳邮递路线1图中有 v4、v7、v8、v9四个奇次顶点用 Floyd 算法求出它们之间

13、的最短路径和距离：3),(,6),(,9),(,6)(,3),(,5),(,9898979787879,49848484747234989787948474vvdvvPvvdvvPvvdvvPvvdvvvPvvdvvPvvdvvvvPvvvvvvvvvvvv2以 v4、v7、v8、v9为顶点，它们之间的距离为边权构造完备图 G13求出 G1的最小权完美匹配 M=(v4,v7),(v8,v9)4在 G 中沿 v4到 v7的最短路径添加重复边，沿 v8到 v9的最短路径 v8v9添加重复边，得欧拉图 G2G2中一条欧拉巡回就是 G 的一条最佳巡回其权值为返回返回哈哈 密密 尔尔 顿顿 图图定定义义

14、设 G=(V,E)是连通无向图（） 经过 G 的每个顶点正好一次的路径，称为 G 的一条 哈哈密密尔尔顿顿路路径径（） 经过 G 的每个顶点正好一次的圈，称为 G 的哈哈密密尔尔 顿顿圈圈或 H 圈（）含 H 圈的图称为哈哈密密尔尔顿顿图图或 H 图返回返回推销员问题推销员问题- -定义定义 流动推销员需要访问某地区的所有城镇，最后回到出发点问如何安排旅行路线使总行程最小这就是推销员问题推销员问题 若用顶点表示城镇，边表示连接两城镇的路，边上的权表示距离（或时间、费用），于是推销员问题就成为在加权图中寻找一条经过每个顶点至少一次的最短闭通路问题定义定义在加权图G=(V,E)中，（）权最小的哈密

15、尔顿圈称为最佳最佳H圈圈（）经过每个顶点至少一次的权最小的闭通路称为最佳推销员回路最佳推销员回路 一般说来，最佳哈密尔顿圈不一定是最佳推销员回路，同样最佳推销员回路也不一定是最佳哈密尔顿圈H回路，长22最佳推销员回路，长4定定理理在加权图G=(V,E)中，若对任意x,y,zV，zx,zy,都有 w(x,y)w(x,z)+w(z,y)，则图 G 的最佳 H 圈也是最佳推销员回路最佳推销员回路问题可转化为最佳 H 圈问题方法是由给定的图 G=(V,E)构造一个以 V 为顶点集的完备图 G=(V,E)，E的每条边(x,y)的权等于顶点 x 与 y 在图中最短路的权即：x,yE w(x,y)=mind

16、G(x,y)定理定理加权图 G 的最佳推销员回路的权与 G的最佳 H 圈的权相同推销员问题近似算法：推销员问题近似算法：二边逐次修正法二边逐次修正法：（）任取初始 H 圈: C0=v1,v2,vi, ,vj,vn,v1（）对所有的 i ,j，1i+1jn,若w(vi, vj)+w(vi+1,vj+1)w(vi,vi+1)+w(vj,vj+1)则在 C0中删去边(vi,vi+1)和(vj,vj+1)而加入边(vi, vj)和(vi+1,vj+1)，形成新的 H 圈 C，即C= v1,v2,vi,vj , vj-1, ,vi+1,vj+1, ,vn,v1）对 C 重复步骤（） ，直到条件不满足为止

17、，最后得到的C即为所求例例对以下完备图，用二边逐次修正法求较优H圈返回返回例例1 最短路问题（最短路问题（SPPshortest path problem）一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。例例2 公路连接问题公路连接问题某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪

18、些城市间修建高速公路，使得总成本最小？例例3 指派问题（指派问题（assignment problem）一家公司经理准备安排N名员工去完成N项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的。如何分配工作方案可以使总回报最大？例例4 运输问题（运输问题（transportation problem）某种原材料有 M个产地，现在需要将原材料从产地运往 N个使用这些原材料的工厂。假定 M个产地的产量和 N家工厂的需要量已知，单位产品从任一产地到任一工厂的运费已知，那么如何安排运输方案可以使总运输成本最低？作业2013年B题 2013高教社杯全国大学生数学建模竞

19、赛题目（请先阅读“全国大学生数学建模竞赛论文格式规范”）B题题 碎纸片的拼接复原碎纸片的拼接复原破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题：1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节

20、点。复原结果以图片形式及表格形式表达（见【结果表达格式说明】）。2. 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。3. 上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。【数据文件说明【数据文件说明】每一附件为同一页纸的碎片数据。附

21、件1、附件2为纵切碎片数据，每页纸被切为19条碎片。附件3、附件4为纵横切碎片数据，每页纸被切为1119个碎片。附件5为纵横切碎片数据，每页纸被切为1119个碎片，每个碎片有正反两面。该附件中每一碎片对应两个文件，共有21119个文件，例如，第一个碎片的两面分别对应文件000a、000b。【结果表达格式说明【结果表达格式说明】复原图片放入附录中，表格表达格式如下：附件1、附件2的结果：将碎片序号按复原后顺序填入119的表格；附件3、附件4的结果：将碎片序号按复原后顺序填入1119的表格；附件5的结果：将碎片序号按复原后顺序填入两个1119的表格；不能确定复原位置的碎片，可不填入上述表格，单独列表。2011高教社杯全国大学生数学建模竞赛题目（请先阅读“全国大学生数学建模竞赛论文格式规范”）B题题 交巡警服务平台的设置与调度交巡警服务平台的设置与调度“有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和