《旅行商问题》PPT课件.ppt

1 图论 2 2 5旅行商问题1 旅行商问题 对正权完全图G 求G总长最短的H回路 区别Euler回路与H回路 2 求解算法 分支定界法分支定界法是一种用较好方式搜索的准枚举法 实质上就是按字典序枚举所有可能情形并结合剪枝 过滤 的办法 例由A B C D E中的三个不同字母构成的全部字符串 按字典序的排列 ABC ABD ABE ACD ACE ADE BCD BDE CDE 3 3 分支定界法初始阶段 1 将全部边按权由小到大排列 2 取前n边作为S 置d0 d0为已考察的H回路中最短的路长 迭代阶段 3 若S构成H回路且其路长d S d0 则d0 d S 跳过比当前d0差的后续情形后 用剩下未考察的第一组边作为S 返回3 全部情形考察完毕时的d0即为最短H回路长度 取其值的那个S就是问题的解 将一条边看作一个字符 步骤1已得各字符间的先后关系 对于长为n且各字符互异的所有字符串 本算法要按字典序的顺序逐一考察每一字符串 4 1 边按权排序 由小到大 d0 边 a35a24a15a14a12a13a34a23a45a25权 3449101011131620 例 5 边 a35a24a15a14a12a13a34a23a45a25权 3449101011131620分支定界 S1 a35a24a15a14a12 非H回路 d S1 30 S2 a35a24a15a14a13 非H回路 d S2 30 S3 a35a24a15a14a34 非H回路 d S3 31 S4 a35a24a15a14a23 H回路 d0 33 S5 a35a24a15a12a13 非H回路 d S5 31 S6 a35a24a15a12a34 H回路 d S6 32 d0 32 S7 a35a24a15a13a34 非H回路 d S6 32 S8 a35a24a14a12a13 非H回路 d S6 36 继续下去所得组长度会比S8差 故可终止计算 6 故最优解为S6 其长度为32 计算要掌握两个要点 1 按字典序逐一考察各边集 2 每次考察完一个边集后 应考虑是否可以用过滤条件 当前d0值 跳过一些不必要情形的考察 因为比当前d0值差的情形不需考虑 7 4 近似算法 便宜 算法分支定界法虽可求得旅行售货员问题的准确最优解 但计算复杂度为O n 故对大型问题需寻找近似算法求解 需采用近似算法往往需要增加一些限制 以便能够提高计算速度和近似程度 1 G是无向正权图 2 对图中任意的三点构成的三角形 其中任何两边之和大于第三边 8 求解思路 给v1一个自环 得到第一个回路 以后反复执行以下过程 寻找与已得回路距离最近的点 将之插入到回路中 回路以外无结点时终止 插入办法 设待插入点为j 有两种选择 1 加入 j t1 和 j t 删除 t t1 2 加入 j t2 和 j t 删除 t t2 选使回路长度增加量小的那种办法作插入 9 例 10 11 2 6最短路径1 最短路问题在一个赋权图中 将权视为边长 求指定两结点之间的最短路长及路线 正权图中V1到各点的最短路径对于正权图G 若L是点vs到点vt的最短路 且L经过点vj 记L中从vj到vt的那部分路线为L 则L 就是vj到vt的一条最短路 否则路线 vs vj L 比L更短 矛盾 12 2 正权图最短路问题的求解 Dijkstra算法问题 求起点v1到其它各点的最短路 记号 用S表示已求得最短路的结点的集合 用E表示到S中各点的最短路的边的集合 算法中的d i 称为点vi的标号 表示起点v1到vi的一条路的长度 当vi在S中时d i 是v1到vi的最短路的长度 13 Dijkstra算法 1 让d 1 0 S 1 k 1 E d i w1i i 2 3 n 若图中边 vi vj 不存在 则记wij 2 在S以外的所有点中找标号最小的点 d k0 min d j vj不在S中 3 S S k0 k k0 E E ek0 为取到值d k0 的边 并修改与vk0相邻的点的标号 d j min d j d k wkj j S 若 S n 则终止迭代 否则回到第2步 注意理解j S时标号d j 的含义 14 对本算法的理解及算法正确性的证明 实线表示图中一条边 虚线表示若干条边组成的一条路 15 例求v1到其它各点的最短路 令d v1 0 则 红点集合表示S 16 3 权均为1时最短路问题的求解因为是正权图 故可直接采用Dijkstra方法 但此时情况特殊 Dijkstra算法可以简化 每轮迭代有一批结点标号相同 让它们都进入S 修改它们的全部直接后继结点的标号 均相等 故下一次让这一批结点全部进入S 总之 每轮让一批结点进入S后 其全部直接后继结点将成为下一轮进入S的全部结点 反复这一操作 直到 S n为止 17 例求v1到其它各点的最短路 令d v1 0 则 红点集合表示S 18 2 权有负数时最短路问题的求解 Ford算法权有负数时Dijkstra算法失效 为什么 若图中不含负回路时最短路问题可解 Ford算法采用迭代的办法 逐步逼近并最终得到最优解 算法中第k次迭代后 d i 表示从起点v1到点vi的一条路的长度 且d i 小于或等于边数不超过k的最短路的长度 因此 算法的迭代次数不超过n 19 Ford算法1 令d 1 0 d i i 2 3 n p 1 2 对i 2 3 n 修改vi的标号 d i min d i min d k wki p p 1 3 若全部d i 没有变化则结束 否则 当p n时转向2 当p n时存在负回路问题无解 20 例求v1到其它各点的最短路 令d v1 0 则 21 改进Ford算法工作量由迭代次数确定 为减小迭代次数 先删除权为负数的边 使用Dijkstra算法 所得解为近似最优解 按计算所得路长对各结点从低到高排队 重新编号 再添上负数边 将Dijkstra算法得到的路长作为路长的初值 可有效提高算法的效率 22 2 7关键路径1 PT图一个结点表示一道工序 工序i完工后才能开始工序j表示为一条有向边 i j 边长表示完成此工序所需时间 于是 一个工程可用一个有向图表示 这就是PT图 求最早完工时间 就是求PT图的最长路长度 而最长路即为完成工程的关键工序 关键路径 23 PT图中不可能存在有向回路 故可对全部结点重新编号 使得每条有向边总是由编号小的结点指向编号大的 最长路的计算完全类似于Dijkstra算法的过程 求min改为求max 24 2 PERT图一条有向边表示一道工序 工序 i j 表示到结点i的所有工序都完工后 此工序才能开工 边长表示完成此工序所需时间 于是 一个工程可用一个有向图表示 这就是PERT图 求最早完工时间 就是求PERT图的最长路长度 而最长路即为完成工程的关键工序 关键路径 25 PERT图中不可能存在有向回路 故可对全部结点重新编号 使得每条有向边总是由编号小的结点指向编号大的 最长路的计算完全类似于Dijkstra算法的过程 求min改为求max 26 2 8中国邮路问题定义例某邮递员负责在若干街道投递邮件 现从邮局出发 经过每一条街道最后返邮局 问如何行走 使得投递线路最短 这就是 中国邮路 问题 中国邮路问题 设G是一个连通的正权简单图 问如何在G中添加重复边 使G有欧拉回路 且重复边的总长最小 27 2 算法定理设G是无向连通图 适当加边使G存在最佳邮路的充要条件是 1 G中每条边最多加重复边一条 2 在G的任意一个回路上 重复边的长度之和不超过该回路长度的一半 证 必要性 若某边的重复边至少有两条 则去掉其中两条后各结点仍然为偶点 故仍然存在Euler回路 28 若G的某回路C上所加重复边的长度之和超过了该回路长度的一半 则重新删增重复边 将C中原有重复边全部删除 而对C中原来没有重复边的边 每边增加一条重复边 这样 各点度数为偶的性质不变 故仍含Euler回路 且总路长下降 矛盾 充分性 略 29 算法 1 适当加边 使所有结点成为偶点 度数为偶数的点 并且每边的重复边不超过一条 2 检查每个回路 若回路中重复边长之和大于整个回路长的一半 则在该回路上作边的删增 使重复边不重复 使不重复边重复 若所有回路都满足要求 重复边长之和不大于整个回路长的一半 则终止迭代 例 p 33 30 3 有向图的中国邮路问题对于有向图来说 中国邮路问题可能无解 其原因是G中可能含有出度 正度 或入度 负度 为0的结点 可能进得去出不来或出得去回不来 如果各结点的正 负度相等 则G中存在有向Eul