2

我有一个循环赛,我为 8 支球队创建了所有必要的比赛(每位参与者 7 场比赛)。但是,我需要每个参与者进行 10 场比赛,这意味着我需要重复比赛,而且 1 和 5 不能互相比赛。您可以从下面的数据中看到我为每个参与者生成的游戏(游戏数量),按照创建的顺序,这将是一轮。

我试图找出复制比赛的最佳方法,并以这样一种方式分配比赛,即没有复制三次的比赛,每个参与者仍然保留 10 场比赛,而 1 场和 5 场比赛不互相比赛。任何建议都会对如何解决这个问题有所帮助。这也需要是其他可能性仍然有效的通用解决方案。

1 (6)
    1 vs 2
    1 vs 3
    1 vs 4
    1 vs 6
    1 vs 7
    1 vs 8
2 (7)
    1 vs 2
    2 vs 4
    2 vs 3
    2 vs 6
    2 vs 5
    2 vs 8
    2 vs 7
3 (7)
    3 vs 4
    1 vs 3
    2 vs 3
    3 vs 7
    3 vs 8
    3 vs 5
    3 vs 6
4 (7)
    3 vs 4
    2 vs 4
    1 vs 4
    4 vs 8
    4 vs 7
    4 vs 6
    4 vs 5
5 (6)
    5 vs 6
    5 vs 7
    5 vs 8
    2 vs 5
    3 vs 5
    4 vs 5
6 (7)
    5 vs 6
    6 vs 8
    6 vs 7
    2 vs 6
    1 vs 6
    4 vs 6
    3 vs 6
7 (7)
    7 vs 8
    5 vs 7
    6 vs 7
    3 vs 7
    4 vs 7
    1 vs 7
    2 vs 7
8 (7)
    7 vs 8
    6 vs 8
    5 vs 8
    4 vs 8
    3 vs 8
    2 vs 8
    1 vs 8
4

1 回答 1

1

首先,您没有严格定义什么是“均匀分布”的比赛。所以我建议这意味着每对球队都打 1 或 2 场比赛。有了这个限制,我对您的原始案例有一个解决方案,并对一般案例有一些想法。

原案

8支球队,每支球队必须打10场比赛,1队不应该和5队比赛。这是对战矩阵:

    1  2  3  4  5  6  7  8
    ----------------------
1 | 0  2  2  1  0  1  2  2
2 | 2  0  1  2  1  2  1  1
3 | 2  1  0  2  2  1  1  1
4 | 1  2  2  0  2  1  1  1
5 | 0  1  2  2  0  2  2  1
6 | 1  2  1  1  2  0  1  2
7 | 2  1  1  1  2  1  0  2
8 | 2  1  1  1  1  2  2  0

以及根据值着色的单元格的相同矩阵:

在此处输入图像描述

这个矩阵是对称的,每行(每列)总和为 10,这意味着每支球队的总比赛次数为 10。所有值都是 1 或 2,除了主对角线上的零(团队不自己玩)和 (1, 5) 和 (5, 1) 单元格(团队 1 和 5 不互相玩)。

一般情况

我将通过几个步骤解释我是如何为原始案例构建矩阵的。这些步骤可以概括为几种不同的条件。但不是所有人。我不建议针对最一般情况的解决方案。

  1. 从所有可以参加比赛的球队开始,只参加一场比赛。该矩阵的行总和为[6 7 7 7 6 7 7 7],其中 6 位于位置 1 和 5。
  2. 尝试使每一行的总和相同。为此,添加团队 1 和 8、1 和 7、5 和 4、5 和 3、2 和 6 之间的比赛。总和现在是[8 8 8 8 8 8 8 8]。好的。
  3. 尝试每队增加两场比赛,禁止前一项的配对。在这一步,只对前四支队伍进行。添加团队 1 和 2、2 和 4、4 和 3、3 和 1 之间的比赛。总和现在是[10 10 10 10 8 8 8 8]
  4. 对最后四支球队重复之前的模式。现在总和[10 10 10 10 10 10 10 10]。每对球队(允许比赛)进行 1 或 2 场比赛。我们完成了。

另一个想法,这可能会有所帮助。在均匀分布的比赛中,允许的对之间的对局数可能相差不超过 1。我们可以这样认为:所有对玩N游戏,而几对玩N+1游戏。在我的解决方案中,我从所有配对开始玩 1 场比赛。它给出了初始总和,必须通过选择这几对玩额外的游戏来纠正。所以一般问题可以重新表述如下:如何将几个1放入零对称矩阵的允许位置,以使行和等于给定向量?

于 2014-11-03T08:00:30.890 回答