数学建模社区-数学中国

标题: 请教大家关于中国邮递员问题 [打印本页]

作者: 镕羽 时间: 2013-6-12 09:32
标题: 请教大家关于中国邮递员问题
我觉得下面第四步中求完备匹配有点问题。

上面的图4情况求出{v1v4，v2v3}组合没错；
但是如果是这样的情况，按照完备匹配法来求就不对了：

就是有可能 v1v3间距离很短（如只有1），v1v2间距离也很短（如只有1）

那选择“倍边”时，就选{v1v4，v1v2，v1v3}，所有奇数度点都成了偶数，再来找欧拉回路。
（这种情况不能用完备匹配法求解）

所以就觉得用完备匹配找倍边的方法不能涵盖所有情况，有点问题。

111111111.jpg (77.42 KB, 下载次数: 430)

222222222.jpg (83.02 KB, 下载次数: 546)

333333.jpg (80.97 KB, 下载次数: 430)

4444444.jpg (15.77 KB, 下载次数: 428)

作者: 镕羽 时间: 2013-6-12 09:32
请教大家哪里想错了？

作者: guoxbcqupt 时间: 2013-8-15 17:19
编程试试，看看结果怎么样·····

作者: 御剑逍遥 时间: 2013-8-16 17:43
最短路11步有关知识参考最短路问题

作者: 御剑逍遥 时间: 2013-8-16 18:32
由v3 u4 v2 u3 u2 v1 u1 v4 u6 再由u2到v5 加和11 不知对不？

欢迎光临数学建模社区-数学中国 (http://www.madio.net/)