最佳推销员回路精品.ppt

灾情巡视问题 093695陆获 092376韩向前 093633吕慧洁 问题复述 某县遭受水灾。为考察灾情和自救,县领导决定帶领负 责人到全县各乡(镇)、村巡视。巡视路线指从县政府所在 地出发,走遍各乡(镇)、村,又回到县政府所在地的路线 1.若分三组(路)巡视,试设计总路程最短且各组尽可能均 衡的路线。 2.若巡视人员在各乡(镇)停留肘间T≡2小肘,在各村停留 时间t=1小时,汽车行驶速度V=35公里/小时。要在24小时 内完成巡视,至少应分几组;给出这种分组下最佳的巡视路 线 3.在上述关于T,t和V的假定下,若巡视人员足够多,完成巡 视最短时间是多少;给出在这种最短肘间完成巡视的要求下, 你认为的最佳巡视路线。 4.若巡视组数已定(比如3组),要求尽快完成巡视,讨论T,t和 ν改变对最佳巡视路线的影响。 乡(镇)和村的公路网示意图 ⊙乡《镇)AB,R 模型假设 汽车在路上的速度总是一定,不会出现抛 锚等现象; 巡视当中,在每个乡镇、村的停留肘间 定,不会出现特殊情况而延误肘间; 每个小组的流车行驶速度完全一样; 分组后,各小组只能走自己区内的路,不 能走其他小组的路,除公共路外; 不考虑其他非正常情况。 理论准备(一) 哈蜜尔顿圈:经过图G的每个顶点恰好一次 的图。其中权最小的哈密尔顿圈称为最佳 哈密尔顿圈。 最佳推销员回路:经过每个顶点至少一次 的权最小的回路。 定理:完全图一定存在最佳哈密尔顿圈。 定理:加权图G的最佳推销员回路的权与G 的最佳哈蜜尔顿圈的权相同。 理论准备(二) 方法解析 最佳哈密尔顿图不一定是最佳推销员回路,而 最佳推销员贿赂也不一定是哈密尔顿图。但是最 佳推销员回路问題可以转化为最佳哈密尔顿图问 题。方法是由给定的图(V,E构造一个以V为顶点 集的完备图G(V,E),E的每条边(x,y)的权等于顶 点X与y在图中最短路的权。 算法处理 ①求带权图的任意两点问的最短距离的可用算法为 Floyd算法。 ②求最优哈密尔顿图到目前为止是没有精确算法的。 但是可以采用一些近似算法,如两边逐次修正法。 问题转化 节点一每个乡(镇)或村 边一各乡(镇)、村之间的公路 ·权一各条公路的长度(或行驶射间) 公路网 权网络图 原问題■佳推销员回路问题 即在给定的加权网络图中寻找: 从给定点O出发,行遍所有顶点至少 次再回到O点,使得总权(路程或 肘间)最小的道路。 符号说明 0表示县政府,1≤≤35表示村:36≤3≤52表示乡镇,其中36表 示A,37表示B,以此类推。 顶点集,代表从1到5所构成的集合 对矿的一个分组 G)|从0(县家)出先经过中所有点最后回到囗点的最佳惟销员回路的 权偵(即总路程) 巡视员在各乡镇停留的时间 测视入员在各村停留的时间 巡视人员的行驶速度 从0(县改府)出发,经过矿中所有点最后回到点的最佳推销员回路中 用于停留在各村,乡颖的时间总和 模型求解之问题 问题复述: 分三组(路)巡视,试设计恿路程最短且 各组尽可能均衡的路线。 问题转化 求解一个V的分组(V1,V2,V3),使得 ①∑f(V)充分小(总路程最短) ②max(f(∽)充mV洛组路程均衙) 求解步骤(一) 运用 Floyd算法,将所给图转化为满足任意两点之闻的权值 为原图中任意两点之间的最短路长度的完全图 2.将GⅣV,E),转化为G,E)。 3.将G(,E)中的顶点集∨分为三组,方法如下 ①选出三个点为基点,使得这三点两两之间的最短长度是 所有可能组合中最大的,而且三点离O点的距离比较均衙 ②对于其他任何点,离哪个基点最近,将之与该基点划为 组 由此得到初始分组。将点分到每组中,运用两边逐次修 正算法算得每组中的最优哈密尔顿圈。 各组的圈的权是: 第一组第二组第三组总路线长度 208 257.5 192.7 658.2