电机协会杯数模竞赛B题第二问最优解

sunshsh

<>第二问太简单了,利用对称矩阵的特性,建立最优最简模型搞定</P>

志同道合

<>kao </P>

志同道合

<>你真的想知道最优解吗？</P>

cai_chong

.............

yirujiwang

<>搂住啊！比赛结束了，直接说第二问怎么排序的吧！谢谢了!</P>[em01]

chen1974

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

yjvv0101

<>不是8   我算出了6。开始也认为不可能  不过验证过了  可以证明下确界为5   但是找不出来</P>

scguest

<>我们用两种算法得出的结果是6啊.请问楼上是怎么证明下界为5的?</P>
<>能不能将证明过程发的我的邮箱里?</P>
<><a href="mailtscguest@126.com" target="_blank" >scguest@126.com</A></P>
<P>谢谢了!!!</P>

xueniao

<>听说有人给出代价为8的答案，我认为不可能。如果是的话，就是我的学生把参赛报名表转为0－1矩阵时搞错了（但是用Excel的替代功能完成的，应该也不会）。因此这个问题可能的最优解是10，因为代价为0的图G0,有11个节点只和其它的一个节点连接，而这样的节点只能做为头或尾，意味着还有九个节点必须位于路径中间，因此其可能产生的代价最小就是10，但也不一定存在。</P>
<>只要能让其中的九个两两相连 就是4.5个取整就是5所以大于等于5</P>

aphrodite

<>我用的方法也是求图G的最长的hamiltonia路径，方法跟上面说的几乎一样，得到最优解是10</P>
<>我也证明了要大于5</P>
<>但是我验算了别人算出的8次的结果，的确是对的，至于他们的解法感觉基本上像是在抽奖，拼人品了，把程序挂在好多台机器上，一起算随机数，呵呵。</P>
<P>我觉得这个题第三、四问才是评判的重点，前两问基本没什么可发挥的余地<BR></P>