中国邮递员问题——欧拉巡回.ppt

MathematicaModeling 中国邮递员问题 欧拉巡回 基本概念与基本结论 主要内容 求欧拉图欧拉巡回的算法 原始模型 求解中国邮递员问题的算法 案例 铲雪车的行驶路线问题 原始模型 问题 一位邮递员从邮局选好邮件去投递 他必须经过他所管辖的每条街至少一次 然后回到邮局 如何选择一条总行程最短的路线 基本概念与基本结论 设G V E 是连通无向图 1 巡回 经过G的每边至少一次的封闭路线 2 欧拉巡回 经过G的每边正好一次的巡回 3 欧拉图 存在欧拉巡回的图 4 欧拉道路 经过G的每边正好一次的道路 5 最佳巡回 加权连通图的边权总和最小的巡回 无向图的情形 基本概念与基本结论 结论一 连通图G是欧拉图的充要条件是G无奇次顶点 结论二 连通图G有欧拉道路的充要条件是G最多有两个奇次顶点 结论三 任何无向图的奇次顶点数目必为偶数 无向图的情形 基本概念与基本结论 设G V E 是弱连通有向图 1 有向巡回 经过G的每条弧至少一次的有向封闭路线 2 有向欧拉巡回 经过G的每条弧正好一次的有向巡回 3 有向欧拉图 存在有向欧拉巡回的有向图 4 有向欧拉道路 经过G的每条弧正好一次的有向道路 5 最佳有向巡回 加权连通有向图的边权总和最小的有向巡回 有向图的情形 基本概念与基本结论 结论一 弱连通有向图D是有向欧拉图的充要条件是D的任何奇次顶点的出次等于入次 结论二 弱连通有向图D有以u为起点 v为终点的有向欧拉道路的充要条件是 u的出次比入次多1 v的出次比入次少1 其余顶点的出次等于入次 有向图的情形 Fleury算法设G是欧拉图 V G v0 v1 vn E G e1 e2 em 1 任选顶点为v0 置途径W v0 2 设途径W v0e1v1 eivi已经选定 则按下述条件从E e1 e2 ei 中选取ei 1 a ei 1与vi相关联 b 除非没有别的选择 否则一定要使ei 1不是G e1 e2 ei 的割边 3 当第2步不能执行时 算法停止 停止后 W即是所求欧拉回路 求欧拉图欧拉巡回的算法 Hierholzer算法设G是欧拉图 1 任选顶点为v0 以v0为起点 生成一个闭道路T0 i 0 2 在Ti上选择一个顶点vi 要求vi有不在Ti上的关联边 在图G E Ti 中构造以vi为起点的闭道路T 将T 插入到Ti的顶点vi处 形成一个更长的闭道路Ti 1 Ti T 3 若E Ti 1 E G 则停止 否则i i 1 返回2 停止后 Ti 1即是所求欧拉回路 求欧拉图欧拉巡回的算法 Hierholzer算法也适合于有向欧拉图 只要将其中的闭道路改为有向闭道路即可 求欧拉图欧拉巡回的算法 一般解法设G是连通加权图 1 对G添加重复边 使G成为欧拉图G 且要求添加的重复边权和近可能小 2 在G 中求一条欧拉巡回 走两条重复边相当于原图的边走两遍 结论 若连通图G正好有两个奇次顶点u v 沿u到v的一条最短路径添加重复边得到欧拉图G 则G 的欧拉巡回便是G的最佳巡回 求解中国邮递员问题的算法 最小权对集法 Edmonds 设G是连通加权图 1 求G的所有奇次顶点之间的最短路径及其长度 2 以G的所有奇次顶点为顶点集作一完全图 各条边上的权赋为两端点在原图中的最短路径长度 得到一个加权完全图 记为G1 求G1的最小权理想匹配M 得到奇次顶点的最佳配对 3 在G中 沿最佳配对奇次顶点间的最短路径添加重复边得欧拉图G G 的欧拉巡回即为所求 求解中国邮递员问题的算法 问题某地区的双车道公路如图1的图G 单位是千米 路上积满了雪 一辆扫雪车从v1点出发 扫除公路上的所有积雪 最后回到v1 要求1 请你为扫雪车选择一条路径 使它经过的总路程最短 要求2 现在先进的喷气扫雪车只需沿公路一侧行驶 就能清除两个车道的积雪 如果改用喷气扫雪车来扫雪 再请你为它选择一条路径 使它经过的总路程最短 案例1 双车道公路扫雪模型 案例1 双车道公路扫雪模型 要求1 的解法1由于是双车道 因此可将每条边看成来回两条异向弧 此时 图是有向欧拉图 可用hierholzer算法在有向图上求出有向欧拉巡回 案例1 双车道公路扫雪模型hierholzer算法求解 要求1 的解法2还可用深度优先搜索法 迷宫法则 遍历所有边 且每边正好来回各走一次 迷宫任务 从迷宫入口处出发 每个走廊都要搜索 最后再从入口出来 案例1 双车道公路扫雪模型深度优先搜索法遍历求解 要求1 的解法2 续 迷宫法则 1 沿着未走过的通道尽可能远地走下去 走到死胡同或那里已无末走过的走廊可选时 沿原路返回 2 到达路口 若有未走过的走廊时 沿这一走廊尽可能远地走下去 最后即可按索退全部走廊和厅室 再由入口处出迷宫 案例1 双车道公路扫雪模型深度优先搜索法遍历求解 威廉王迷宫 案例1 双车道公路扫雪模型深度优先搜索法遍历求解 要求1 的解法2 续 扫雪车行驶规则 从起点出发 优先选择未作业过的路段 到达交差路口时 若身后路面的两个车道都已铲且前面还有未作业过的路段 或前方路段都未作业过 则驶入最靠右边的路段继续作业 否则 身后路面只铲了一个车道 应掉头铲另一个车道 3 行驶到一头不通的道路尽头应掉头 在反向车道上作业 案例1 双车道公路扫雪模型深度优先搜索法遍历求解 案例1 双车道公路扫雪模型深度优先搜索法遍历求解 铲雪车的行驶路线问题 MCM90B题 下页地图中实线表示马里兰州 Maryland 咸克米克市 w5comico 清除积雪区域的双车道道路 虚线是州高速公路 雪后