数学建模社区-数学中国

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

作者: 镕羽    时间: 2013-6-12 09:32
标题: 请教大家关于 中国邮递员 问题
我觉得下面第四步中 求完备匹配 有点问题。4 e# Z/ ~. I" S1 b; x; D0 p% D0 n

' N4 ~# W0 n- o0 U$ Q8 l" i
- R" M3 b9 @3 I
! P  o. F+ v" M/ c: W5 N$ J+ \0 I7 p4 d* Q/ ?+ e1 }1 m
上面的图4情况 求出{v1v4,v2v3}组合没错;  J5 c/ i- @2 T: M; x
但是如果是这样的情况,按照完备匹配法来求就不对了:( D" g( N- r1 k; `& [

' h( _2 M3 R# L7 ?- x5 f就是有可能  v1v3间距离很短(如只有1),v1v2间距离也很短(如只有1)
9 f6 W/ ]$ j; k( Z; C3 U0 G: L+ S- R2 X$ ?% T
那选择“倍边”时,就选{v1v4,v1v2,v1v3},所有奇数度点 都成了偶数,再来找欧拉回路。* [. X0 Y5 k6 R5 k6 B
(这种情况不能用完备匹配法求解)
2 H" }7 P: N% Q2 l. n4 i+ s+ w6 ]* _; i' h1 {1 N
所以就觉得 用完备匹配 找 倍边的 方法不能涵盖所有情况,有点问题。

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

111111111.jpg

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

222222222.jpg

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

333333.jpg

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

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   不知对不?, r; J& N, W* P! ]% H. g- o





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