首页 > 搜索 > ACM图论算法邮递员投递问题6,ACM图论算法—邮递员投递问题_Touch

ACM图论算法邮递员投递问题6,ACM图论算法—邮递员投递问题_Touch

互联网 2020-10-21 14:56:52
在线算命,八字测算命理
题目描述

著名图论问题之一。邮递员从邮局出发送信,要求对辖区内每条街,都至少通过一次,再回邮局。在此条件下,怎样选择一条最短路线?此问题由中国数学家管梅谷于1960年首先研究并给出算法,故名。中国邮递员问题——可以叙述为在一个有奇点的图中,通过增加一些重复边,使新图不含奇点,并且重复边的总权为最小问题!

快递员从V1出发给V2、V3、V4、V5、V6、V7、V8、V9派发快递,求派完所有回到原出发点的最短路径?如下图所示

这里写图片描述

题目分析

在分析这道题目之前,我们在想这样的一个问题图1和图2当中哪一个图满足从图中任何一点出发,途径每条边最终还能回到原点?图1无奇点不需要走重复边;图2有奇点需要走重复边。这里写图片描述从上面的结果可以让我们得到一些灵感。

那么一个图应该满足什么条件才能达到上面要求呢?

满足各个结点的度为偶数!在一个多重边的连通图中,从某个顶点出发,经过不同的线路,又回到原出发点,这样的线路必是欧拉图。

定理1:连通的多重图G是欧拉图,当且仅当G中无奇点。欧拉圈:若存在一个简单圈,过每边一次,且仅一次,则称为欧拉圈。

1、化奇图为偶图,结果如下:这里写图片描述

注意:不是将跨越的奇点连接起来!2、但是上面这样的连接结果是最优方案?如果不是最优方案,那么什么样的指标才算是最优的方案?应该如果去找到这样的最优方案?最后对化奇图为偶图进行下面两个约束条件调优:A、在最优方案中,图的每一边最多有一条重复边B、最优方案中,图中的每一个圈(环)重复边的总权值不大于该圈总权值的一半

下面图是经过A约束条件的调优结果:这里写图片描述

B约束条件调优算法执行的步骤:1、找出图中的一个圈,既一条不存在重复路径的回路2、计算圈中的重复边的总和D,计算圈的所有边的总和S3、如果D>S/2,则把这个圈的重复边全部变成单边,单边全部变成重复边4、重复以上的1,2,3直到不存在D > S/2的情况

最优在A的调优结果基础上面,B调优结果如下:这里写图片描述圈(v2,v3,v4,v9,v2)的总长度为24,但圈上重复边总权为14,大于该圈总长度的一半,因此可以做一次调整,以[v2,v9],[v9,v4]上的重复边代[v2,v3],[v3,v4]上的重复边,使重复边总长度下降为17。

但是上面的图还存在可以调优的情况:圈(v1,v2, v9, v6,v7, v8,v1)的总长度为24,但圈上重复边总权为13,大于该圈总长度的一半,因此可以做一次调整,使重复边总长度下降为15。结果如下图这里写图片描述

最终结果

最优方案:v1-v2-v9-v8-v1-v8-v7-v6-v5-v4-v9-v6-v9-v4-v3-v2-v1(任意一个欧拉圈即可)这里写图片描述

免责声明:非本网注明原创的信息,皆为程序自动获取互联网,目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责;如此页面有侵犯到您的权益,请给站长发送邮件,并提供相关证明(版权证明、身份证正反面、侵权链接),站长将在收到邮件12小时内删除。

相关阅读

一周热门

查看更多