25 马问题

目录 算法

这是以前在 TopLanguage 讨论组讨论过的一道题目 ,题目描述为:

有 25 匹马和 1 个赛场,但赛场只有 5 条赛道,即一次只能给最多 5 匹马提供比赛机会,并且不能计时。请问如何设计比赛策略得到最快的 3/5 匹马,使得使用赛道的次数最少。

我想了一下,下面尝试给出我的分析,如果不对的话,还请指正。

一、决出前三名的策略

决出前 3 名网上有很多讨论,答案是 7 次,没有见过更少的,策略如下:

1. 将 25 匹马分成 5 组,分别赛一轮,得出一个先后顺序,共 5 轮。
2. 将每组的头马组成一组,再赛一轮,得出一个先后顺序。这第 6 轮能确定第一名。
3. 将最快一组的二三名,第二那组的一二名,以及第三那组的第一名五匹马放在一起,再赛一轮。这第 7 轮的前两名就是最终的二三名。总共赛 7 轮。

下面是分析。不失一般性,在赛 6 次之后,我们假设这 25 匹马的序号为:

A1 A2 A3 A4 A5  // 1 <-------
B1 B2 B3 B4 B5  // 2  |     |
C1 C2 C3 C4 C5  // 3 Main   |
D1 D2 D3 D4 D5  // 4  |  Extended
E1 E2 E3 E4 E5  // 5 <--    |
--------------  //          |
A1 B1 C1 D1 E1  // 6  {A1} <-

其中主矩阵列出了 25 匹马的序号,扩展矩阵的每行是每轮比赛的结果。我们可以看到主矩阵的行有序,第一列有序,那么现在我们知道第一名是 A1。

由于已知 A1 是第一名,第二名肯定是在每轮中紧挨在 A1 后面的,因此第二名的候选集为 {A2, B1}。

它们两个占不满 5 个赛道,我们再来看第三名的候选集。第三名在每轮中只可能是挨在第一或第二名的后面,也就是说在 {A1} U {A2, B1} 的后面,那么第三名的候选集就是 {A2, A3, B1, B2, C1},正好 5 匹马(第二名的候选集肯定包含在第三名候选集中)。那么第二三名只可能在这 5 匹马中,因此我们只需要让 {A2, A3, B1, B2, C1} 这 5 匹马再比一次,得到前两名,与 {A1} 合起来就是总的前三名。这样总共的比赛次数是 7 次。

2. 决出前五名的策略

决出前 5 名,就比较复杂了,我们按照同样策略再往下思考:

{A2, A3, B1, B2, C1} 决出前两名,有几种可能呢?如果它们没有比过,可能性就是从 5 个中取 2 个后的排列数,20 种可能。但是我们前面的比赛已经得到了一些快慢信息,我们就可以发现,第 7 轮 {A2, A3, B1, B2, C1} 决出前两名只有 5 种可能情况:

A2 A3 B1       B2/C1 * // 7  {A1, A2, A3}
B1 B2 A3/C1    *     * // 7  {A1, B1, B2}
B1 C1 A2/B2    *     * // 7  {A1, B1, C1}
A2 B1 A3/B2/C1 *     * // 7  {A1, A2, B1}
B1 A2 A3/B2/C1 *     *

去掉可交换的 A2 B1,其实只有 4 种情况。我们分别来考虑这 4 种情况:

1. {A1, A2, A3}

第四名肯定是 {A1, A2, A3} 之后的马,候选集为 {A4, B1};元素不足 5,再推一下第五名,即{A1, A2, A3} U {A4, B1} 之后的马,候选集为 {A4, B1, A5, B2, C1},只有 5 匹马。就是说第四、五名可以从这五匹马中产生,那么我们只需要再比一轮,取前两名,与 {A1, A2, A3} 并起来就能得到整个的前 5 匹马。那么最少的比赛次数是 8 次。

2. {A1, B1, B2}

这种情况下,同理,第四名候选集为 {A2, B3, C1} ,第五名候选集为 {A2, A3, B3, B4, C1, C2, D1},元素多于 5 个。因此我们必须先让 {A2, B3, C1} 比赛得到第 4 名,才能将第五名候选集的元素个数减少到 5 个以内。穷举:第 8 轮 A2 第一,可以消去 {C2, D1, B4, A2};B3 第一,可以消去 {B3, A3, C2, D1};C1 第一,可以消去 {C1, A3, B4},均能保证第五名的取值集合减少到 5 以内,因此只需要再一轮,就可以得到第五名。总的比赛次数是 9 次。

3. {A1, B1, C1}

同理,第四名候选集为 {A2, B2, C2, D1},第五名候选集为{A2, A3, B2, B3, C2, C3, D1, E1}。第四名无论取哪个,都会消去四个第五名候选集中的元素,总的比赛次数仍然是 9 次。

4. {A1, A2, B1}

同理,第四名候选集为{A3, B2, C1},第五名候选集为{A3, A4, B2, B3, C1, C2, D1}。第四名无论取哪个,至少消去第五名候选集中的 3 个元素,总的比赛次数也是 9 次。

穷举结束了,现在我们可以得出结论:最坏情况下该策略决出前 5 匹马的最少比赛次数是 9 次。

三、扩展问题

我有一个问题是:这种策略下取3, 5名比赛次数一定是最少的吗?有没有数学证明?

再扩展一点儿,如果需要求前 n 名,最少需要比赛几次?

在我们的这种策略下,因为主矩阵只有 5 行,每行还是有序的,那么求下一名的候选集最多有 5 个元素。也就是说多求一名,至多需要增加一轮比赛。什么情况下可以少于一轮呢?当已经确定第 n 名的情况时,第 n+2 名的候选集元素少于 5 个,我们就可以一轮比赛确定两个名次了。

我还比较好奇的是,如果需要决出所有 25 匹马的快慢顺序,最坏情况下至少需要比赛几次?

在我们这种策略下,假设 f(n) 是第 n 名最坏情况下的最少比赛次数,我们已知 f(1) = 6, f(2) = f (3) = 7, f(4) = 8, f(5) = 9,f(n) <= (n-5)+9 = n+4。那么 f(25) = f(20)+1 <= (20-5)+9 + 1 = 25 次,其上界应该是 25。但其准确值怎么确定?穷举就太困难了。 但是如果题目要求是确定 25 个的全部顺序,我们这种策略未必是最好的。这时候这题可以看成 n 路归并排序,并且可同时比较 n 个数的优化问题。过程中有很多可优化的可能。比如我们预处理时可以对每行和每列都排一下序,能否可以得到一些额外的信息?当主矩阵(去掉已确定顺序的元素)显得不那么平衡时,用扩展矩阵中的比较信息是否可以将主矩阵平衡一下,或者消去某些行列,这样做是否有帮助?

长按识别二维码关注《边际效应》
长按识别二维码关注《边际效应》

12 条评论

  • 半瓶墨水
    2009-10-18

    路过,进来看看

    后面的思考很有益,也修改了题酷发芽网上的原题
    http://fayaa.com/tiku/view/91/

  • Iron_Feet
    2009-10-20

    这道MS是去年某个公司的笔试题,具体哪个公司忘了。当时还在实验室里讨论了一下。

  • joshua3x@gmail.com
    2009-10-22

    归并排序大致也是这个原理吧

  • Solrex Yang
    2009-10-22

    @joshua3x@gmail.com
    不太一样。归并排序只能比较两个元素,这个可以一次比较五个元素,所以关键在于如何利用这些多余比较的信息。

  • phpxer
    2009-11-04

    我觉得你这里的讨论有一些问题,以决出5名中的第二种情况为例,你的意思是第七局的结果为 B1,B2 ... 则我去一种方式: B1>B2>A2>A3>C1
    那么小于A3的都可以去掉了(包括 A4,A5, 以及 C1,C2,D1,D2,E1) 这时候只剩下下面的关系:
    A1 B1
    A2 B2
    A3 B3
    这时候只需要跑一轮决定A2 A3 B3 就可以了。也就是八场就结束。你忽视了他们之间的一部分关系。同理你下面的推理可能都有问题。
    第二个,“ 在我们的这种策略下,因为主矩阵只有 5 行,每行还是有序的,那么求下一名的候选集最多有 5 个元素。” 这句话你的意思是 新增的 5匹马跑一次? 那显然是不对的,因为不清楚去掉的五匹马与之前的那些马的关系。可能我还不太理解你这句话。

  • phpxer
    2009-11-04

    你好,等你看了我的评论后,有什么意见希望给我回复封邮件提醒一下... 多谢了。

  • Solrex Yang
    2009-11-04

    @phpxer
    我初步感觉您说的是对的,我的确忽视了第7轮中产生的顺序,等我想清楚了我会更新这篇文章,谢谢!

  • fluxay
    2010-03-11

    肯定是多路归并啦,有的实现用到败方树,说的就是这个问题。
    之所以称作败方树,就是因为记录冠军打败了谁,亚军只会从冠军的对手里产生。
    可以推广到5个的情况。

  • fluxay
    2010-03-11

    刚才想了一下,确实称作多路归并不太合适。
    但是是败方树。
    还是画出比较树会比较直观。

  • metalmax3
    2010-07-10

    恩恩……
    我觉得用第一组那剩下的四匹去比组冠军比赛中的第二名,比较合理

  • metalmax3
    2010-07-10

    前三的策略
    我的观点,前五场必须比,没有异议的
    第六场是每组的头名
    第七场是第六场冠军那一组剩下的四匹+第六场的第二名(第六场第二名可能慢于第一组的第五名)
    如果第六场的第二名在第七场比赛中获得第一名,则比第八场,否则名次排定
    第八场,第六场的第三名,和冠军那一组的剩下四匹马

  • 你知道
    2012-08-23

    拿5组的头名比出第1名,这个有问题,第1组的头名一定比第2组的第2名快?这肯定是不确定的。

发表评论

电子邮件地址不会被公开。 必填项已用*标注