第4讲 行遍性问题.ppt

第4讲行遍性问题 一 中国邮递员问题 二 推销员问题 三 建模案例 最佳灾情巡视路线 一 欧拉图 二 中国邮递员问题 一 哈密尔顿图 二 推销员问题 G的边e是割边的充要条件是e不含在G的圈中 割边的定义 设G连通 eE G 若从G中删除边e后 图G e 不连通 则称边e为图G的割边 欧拉图 巡回 v1e1v2e2v3e5v1e4v4e3v3e5v1 欧拉道路 v1e1v2e2v3e5v1e4v4e3v3 欧拉巡回 v1e1v2e2v3e5v1e4v4e3v3e6v1 欧拉图 非欧拉图 中国邮递员问题 定义 中国邮递员问题 算法 Fleury算法 基本思想 从任一点出发 每当访问一条边时 先要进行检查 如果可供访问的边不只一条 则应选一条不是未访问的边集的导出子图的割边作为访问边 直到没有边可选择为止 若G不是欧拉图 则G的任何一个巡回经过某些边必定多于一次 解决这类问题的一般方法是 在一些点对之间引入重复边 重复边与它平行的边具有相同的权 使原图成为欧拉图 但希望所有添加的重复边的权的总和为最小 求出G1的最小权理想匹配M 得到奇次顶点的最佳配对 哈密尔顿图 推销员问题 定义 流动推销员需要访问某地区的所有城镇 最后回到出发点 问如何安排旅行路线使总行程最小 这就是推销员问题 推销员问题是NP 完备问题 即没有多项式时间算法 若用顶点表示城镇 边表示连接两城镇的路 边上的权表示距离 或时间 费用 于是推销员问题就成为在加权图中寻找一条经过每个顶点至少一次的最短闭通路问题 定义在加权图G V E 中 权最小的哈密尔顿圈称为最佳H圈 经过每个顶点至少一次的权最小的闭通路称为最佳推销员回路 一般说来 最佳哈密尔顿圈不一定是最佳推销员回路 同样最佳推销员回路也不一定是最佳哈密尔顿圈 H回路 长22 最佳推销员回路 长4 推销员问题近似算法 二边逐次修正法 例对以下完备图 用二边逐次修正法求较优H圈 图a 图b 图c 图d 例 从北京 Pe 乘飞机到东京 T 纽约 N 墨西哥城 M 伦敦 L 巴黎 Pa 五城市做旅游 每城市恰去一次再回北京 应如何安排旅游线 使旅程最短 各城市之间的航线距离如下表 例 有7个人 A会讲英语 B会讲英语和汉语 C会讲英语 意大利语和俄语 D会讲日语和汉语 E会讲德语和意大利语 F会讲法语 日语和俄语 G会讲法语和德语 问能否将他们沿圆桌安排就坐成一圈 使得每个人都能与两旁的人交谈 ACEGFDBA是一条哈密顿回路 按此顺序就坐即可 解 作无向图 每人是一个顶点 2人之间有边 他们有共同语言 建模实例灾情巡视路线 图为某乡 镇 村公路网示意图 公路边的数字为该路段的公里数 有一年夏天该县遭受水灾 为考察灾情 组织自救 县领导决定 带领有关部门负责人到全县各乡 镇 村巡视 巡视路线指从县政府所在地出发 走遍各乡 镇 村 又回到县政府所在地的路线 1 若分三组 路 巡视 试设计总路程最短且各组尽可能均衡的巡视路线 2 假定各巡视人员在各乡 镇 停留时间T 2小时 在各村停留时间T 1小时 汽车行驶速度v 35千米 小时 要在24小时内完成巡视 至少应分几组 给出这种分组下你认为最佳的巡视路线 3 在上述关于T t和v的假定下 如果巡视人员足够多 完成巡视的最短时间是多少 给出在这种最短时间完成巡视的要求下 你认为最佳的巡视路线 4 若巡视组数已定 如三组 要求尽快完成巡视 讨论T t和v改变时最佳巡视路线的影响 以下我们参考当年的优秀答卷对这一问题作一分析 一 关于问题的数学模型本题给出了某县的道路交通网络图 要求的是在不同的条件下 灾情巡视的最佳分组方案和路线 这是一类图上的点的普遍性问题 也就是用若干条闭链覆盖图上的所在顶点 关使某些指标达到最优 点的遍历性问题在图论属于哈密顿问题和旅行推销员问题 本题所求得分组巡视的最佳路线与多个旅行推销员问题类似但也有不同 因为还有均衡性的要求 由于旅行推销员问题属于NP 完全类 本题的规模比较大 包括县城共有53个点 所以要想求出真正的最优解是不现实的 为此只能针对具体问题 采取一些启发式算法求得近似最优解 在求本题的解之前 对原问题所给条件作一些适当的假设的必要的 例如 公路不考虑等级差别 也不受灾情或交通情况的影响 各条公路段段上汽车汽车行驶速度可以认为是均匀的 各巡视组巡视的乡 镇 村不受行政区划的影响 即某乡 镇 与隶属于它的村不一定要分在同一组内 各巡视组统一行动 即不允许一个巡视组在分成若干小组等等 二 关于问题的具体求解本题的第一问 要求设计分三组巡视时使总路程最短 且各组尽可能均衡的巡视路线 这里有两个目标 若即三组的巡视路线长度从小到大分别为 则该两目标的数学表达式为 以及但是这两个目标又是相互矛盾的 也就是不可能同时达到最小 因此具体求解时 应两者兼顾 用多目标的方法处理 为简单起见 根据实际问题灾情巡视的背景 一种较为合理的考虑是转换成一个目标函数 即 然而具体求解是 光凭上述数学表达式是无济于事的 对于巡视组的划分 我们可以利用原图的最小生成树从县城出发的最短路生成树 或者原图的单个旅行推销员路线等做为依据 因为它们都是有某种指标下的最优解 而这类指标与原题的要求又很接近 当然 也可以直接利用地理位置 对边界进行合理划分后向内扩展或是修改边界点的归属等直观方法做近似处理 分组以后 由于规模较小 最优巡视路线的设计就变的较为简单 一般可借助现成的软件求出精确解来 即便没有这类软件采取近似算法或者直接搜索也都能较容易地找出很多的近似最优解 以下有两种参考答案 前者的总路程较短但均衡性较差 后者的均衡性相当好但总路程较长 第一组结果 第一组 O C G 34 35 32 30 Q 28 Q 29 R 31 33 A 1 O 总里程为153 1千米 第二组 O P 26 27 26 N 24 23 21 K 22 17 16 I 15 I 18 J 19 L 20 25 M O 总里程为210 5千米 第三组 O 2 3 D 4 8 E 9 F 10 F 12 H 14 13 G 11 E 7 6 5 2 O 总里程为210 5千米 第二种结果 第一组 O 1 B 34 35 32 31 33 A R 29 Q 30 Q 28 27 24 23 N 26 P O 总里程为197 6千米 第二组 O M 25 20 21 K 22 17 16 I 13 G 11 E 8 4 D 3 C O 总里程为200 4千米 第三组 O 2 5 6 L 19 J 18 I 15 14 H 12 F 10 F 9 E 7 6 5 2 O 总里程为203 5千米 三 由时间约束的最佳路线本题的第二问是添加了巡视组停留时间T 2小时 t 1小时以及汽车行驶速度V 35千米 小时的条件后 要求在24小时内完成巡视的最少分组数以及相应的最佳巡视路线 第三文则是在上述时间参数条件下 尽可能的最短时间内完成巡视所需的最少组数以及相应的巡视方案 尽管提法雷同 但却蕴含着不同的数学内涵 通过计算原图的单个旅行推销员的路线长度可以估算出分组巡视路程的下界 这在回答第二问时是有用的 因为单个旅行推销员的路线长度均在500千米以上 所以各组花在汽车行驶时间之和将超过14小时 加上各乡镇村的停留时间小时 各组所需时间之和将大于14 69 83小时 这样 若分成三组 就不可能在24小时内完成巡视 于是 所求的最小分组数为4组 若记为第j组的巡视路线长度 分别表示该组停留的乡镇和村数 j 1 2 3 4 则各组所花的时间为和第一问的情况类似 所谓最佳的要求仍然是两目标的 即要求以及假若我们仍然以后者为主要目标来考虑 那么 乡镇 村的均衡性和各组路程的均衡性就依然是分组的主要依据 参照第一闻捷达的方法和所得的结果 并对各组的交接作适当的调整 用计算机搜索的方法容易得到较好的解 一个比较好的分组方案为 第一组 O C 3 D 4 8 E 9 F 10 F 9 E 7 6 5 2 O 总路程千米 总巡视时间小时 第二组 O 2 5 6 L 19 J 13 14 H 12 G 11 J 19 20 25 M O 第三组 O P 28 27 24 23 22 17 16 I 15 I 18 K 21 23 N 26 p O 千米 第四组 O 1 B 34 35 32 30 Q 29 R 31 33 A I O P O 以上各组巡视路线中括号的点为只经不停留的点 各组的巡视时间均在22小时左右 相差仅6 3小时 以为标准而言 是已知的最好方案之一 第三问是如果有足够多的巡视人员 要示出完成巡视的最短时间 并给出在最短时间限制下的最佳巡视路线 事实上 完成巡视的最短时间受到单独巡视离县城最远的乡 镇 村所需时间的制约 采用Dijkstra算法 可以求得从县城到各点的距离 离县城最远的点是H点 距离为77 5千米 因此 单独巡视该乡所需时间为小时 所以 即使人员再多 分组再细 完成巡视至少需要6 43小时 于是 问题便成为在6 43小时内完成巡视所需的最小分组数和巡视方案 容易验证 要在6 43小时内完成巡视 有些点 如I J H 只能单独作为一组 时间不允许在别的乡村停留 而绝大部分乡村可以和其它乡村分在同一组内 并在限定时间内完成巡视 参照点在图中从县城出发的最短路上的位置 采用就近归组的搜索方法 容易得到最优解22组的分组方法及相应的巡视路线 这里不在列出 四 关于T t V的讨论本题第四问要求在巡逻组数一定情况下尽快完成巡视 讨论参数T t V的改变对最佳巡视路线的影响 前面已经提到 要尽快完成巡视 即要求各组巡视时间的最大值也要最小 用数学式子表示就是 这里k是给定的分组数 分别是第j组停留的乡镇数和村数 是第j组巡视路线的长度 在上述的表达式中 T和t的作用相仿 所以为简化讨论起见 对任意给定的T和t 不妨设即T pt 于是可简化为 它是t和的线性函数 将随着t和的增大而值经可能小 就要求的最大值及可能的小 但是当t和T的关系确定后 是定值C pm n 其中m是全县的乡镇数17 n是全县的村数35 上述要求就成为各组停留乡村数 加权以后之和 尽可能均匀 用数学式子表示为 这里 a 和 a 分别表示a的下整数 当然 在调整各组停留的乡村数使之达到均衡时 自然会给各