数学建模社区-数学中国

标题: 请教大家关于 中国邮递员 问题 [打印本页]
作者: 镕羽    时间: 2013-6-12 09:32
标题: 请教大家关于 中国邮递员 问题
我觉得下面第四步中 求完备匹配 有点问题。5 U# t3 `4 ~7 G- ?
; u  A" a7 q5 K+ {( v: d3 y, q1 b
4 ^+ ?; J5 j1 m0 ^2 h. @, o
/ P; J/ ?- a" x0 e; `
/ E' t/ d! q! `7 A" o0 U1 u+ q6 o7 }
上面的图4情况 求出{v1v4，v2v3}组合没错；; `: [4 s/ }/ f! ?5 S
但是如果是这样的情况，按照完备匹配法来求就不对了：( a8 A" R! P* N1 u, ^0 p7 ~" `
: z0 C6 a* [$ j& y& [+ K2 e
就是有可能  v1v3间距离很短（如只有1），v1v2间距离也很短（如只有1）
% }- ?# w' T( b7 I+ I% b9 R# B# |% V; M) C. h* G# h' O# N
那选择“倍边”时，就选{v1v4，v1v2，v1v3}，所有奇数度点 都成了偶数，再来找欧拉回路。
/ E0 o8 ?+ m! M; I3 f9 [; f, s（这种情况不能用完备匹配法求解）
* b2 o, \+ K5 j; G$ |7 g; v+ o  m8 ^
所以就觉得 用完备匹配 找 倍边的 方法不能涵盖所有情况，有点问题。

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

111111111.jpg

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

222222222.jpg

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

333333.jpg

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

4444444.jpg

作者: 镕羽    时间: 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   不知对不？
" B3 a* ^; K. S# }/ `



欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5