B题第二问结果，已算出

sunshsh · 发表于 2005-11-28 12:43:33

你是怎么证的,能发过来吗?tao5a504@163.com

eyeworld · 发表于 2005-11-28 12:53:14

<a href="mailteyeworld@126.com" target="_blank" >eyeworld@126.com</A> 3x

pomop · 发表于 2005-11-28 13:55:27

pomop@263.com

xaut1015 · 发表于 2005-11-28 17:39:53

<

><a href="mailtyaya_005@yahoo.com.cn" target="_blank" >yaya_005@yahoo.com.cn</A>
<

>急！

winter_war · 发表于 2005-11-28 18:22:22

<

>能把最终答案发给我吗？
<

><a href="mailtzhouwenting@sjtu.edu.cn" target="_blank" >zhouwenting@sjtu.edu.cn</A>

方法 · 发表于 2005-11-29 01:49:43

<

><a href="mailtfeixingjianduicauc@hotmail.com" target="_blank" >feixingjianduicauc@hotmail.com</A>
<

>我的答案是5 你的答案是多少??

志同道合 · 发表于 2005-11-29 07:11:58

<

><a href="mailtguodong10518@163.com" target="_blank" >guodong10518@163.com</A>
<

>谢谢！！

志同道合 · 发表于 2005-11-29 07:15:23

<

>等的好着急 
<

>我们的也是8

chen1974 · 发表于 2005-11-29 18:43:56

<

><a href="mailtchenzhong74@126.com" target="_blank" >chenzhong74@126.com</A>
<

>我是教师，我不太相信小于10的结果，因为我可以证明这个问题的最小解是10，但不一定存在。反正比赛结束了，我希望得到8或5的学生能公布他们的结果验算。

<

>把问题转换为不同代价条件下，求图G的最长的hamiltonia路径 
代价为0时，得到最长的hamiltonia路径为50 A=[14 23 34 48 38 29 24 17 1 19 26 15 20 6 35 9 18 52 50 36 5 55 47 40 60 8 59 28 21 49 56 11 54 43 57 32 13 39 53 25 4 44 2 61 58 30 37 22 42 7] 剩下11个节点： 1 2 3 4 5 6 7 8 9 10 11 A1=[3 10 12 16 27 31 33 41 45 46 51]; 用A1形成新图G1 寻找代价为1的hamiltonia路径，注意A1中所以的单一节点都要找 A2_1=[51 16 45 41 27 46] A2_2=[10 3] A2_3=[12 31] 共3个可以的 ,共产生代价5＋1＋1＝7 剩下A1的第7个 33
把A A2_1 A2_2 A2_3的首尾两个，进行穷举匹配 可以得到： A2_1 ->fliplr(A) －> A2_3 ( -> fliplr(A2_1) ) [10 3]->[7...14] -> [12 31] ( -> [46 ....51] ) 代价 1 1 2 共4
由于> [46 ....51]加入的代价为2，暂不考虑 只加入前面的
因此新的代价为7＋2 的链路为 A=[10 3 7 42 22 37 30 58 61 2 44 4 25 53 39 13 32 57 43 54 11 56 49 21 28 59 8 60 40 47 55 5 36 50 52 18 9 35 6 20 15 26 19 1 17 24 29 38 48 34 23 14 12 31 ]
把 [51 ....46] 历遍上述A
发现插入在A的倒数9个和倒数第8个 [... 24 29 ...]之间代价为1 ，因此 A= [10 3 7 42 22 37 30 58 61 2 44 4 25 53 39 13 32 57 43 54 11 56 49 21 28 59 8 60 40 47 55 5 36 50 52 18 9 35 6 20 15 26 19 1 17 24 51 16 45 41 27 46 29 38 48 34 23 14 12 31 ]
 再把33历遍上述A 可以知道插入在第29个，也就是40和47之间代价为1
因此新的项目排列为： A=[10 3 7 42 22 37 30 58 61 2 44 4 25 53 39 13 32 57 43 54 11 56 49 21 28 59 8 60 40 33 47 55 5 36 50 52 18 9 35 6 20 15 26 19 1 17 24 51 16 45 41 27 46 29 38 48 34 23 14 12 31 ]
因此总代价为11
需要连续比赛的运动员为 290 291 317 323 360 592 603 606 773 777 872
听说有人给出代价为8的答案，我认为不可能。如果是的话，就是我的学生把参赛报名表转为0－1矩阵时搞错了（但是用Excel的替代功能完成的，应该也不会）。因此这个问题可能的最优解是10，因为代价为0的图G0,有11个节点只和其它的一个节点连接，而这样的节点只能做为头或尾，意味着还有九个节点必须位于路径中间，因此其可能产生的代价最小就是10，但也不一定存在。

chen1974 · 发表于 2005-11-29 18:49:00

<

>呵呵，但是后来想一下，最小可能应该是9，除了头和尾以外，其它9个节点分别与另外一个节点以代价1连接。

		自动登录	找回密码
密码			注-册-帐-号