9

我首先要说，我知道这个话题很复杂，而且可能没有一个简单的答案。如果这很容易，那么每个人都会这样做。话虽如此...

我被要求构建一个应用程序来管理一个体育联盟。除了这个之外，大多数概念都相当容易理解：如何生成没有重叠的比赛时间表（球队一次比赛 2 支球队），其中一个分区中的球队与其球队比赛两次，但比赛的球队来自其他部门一次，并确保赛程中没有漏洞（每支球队每周比赛）

现在，该过程是使用我为实现此目的而构建的 Rosetta Stone 类型的电子表格手动完成的，但它仅适用于为其设计的团队数量。我为 30 个团队、24 个团队和 28 个团队做了变化。与其不断尝试重新调整我的翻译表，我希望能够编纂该逻辑并调整该过程。

想法？

4

4 回答 4

14

在国际象棋锦标赛中使用了一个非常简单的系统，称为循环赛。

这个想法是将玩家分成桌子的两侧。其中一名玩家被指定为“中心”（为了更好的词）。比赛开始时让球员面对面比赛。在第一轮之后，除了轮毂之外的每个人都向前移动一把椅子，然后切换白色/黑色（运动中的主场/客场）顺序。当球员坐在原来的地方时，整个循环比赛都结束了。如果你想让每个人都玩两次，那就再做一次。

带有实现细节的维基百科文章。

在您的特殊情况下，我会尝试一次包括所有团队的循环赛。然后你为每个分区做一次相同的事情，并确保分区内的球队在主场和一次客场比赛中互相比赛，从第一轮循环赛中检查球队在该轮比赛中的表现。

当然，这样做的不利方面是，您将在锦标赛结束之前参加所有分区间的比赛（因为最后的 n-1 场比赛是针对分区内的球队 [n=分区内的球队数]）。如果这是一个问题，您可以简单地交换一下匹配项。

我实际上编写了一个简单的 Python 脚本来执行此操作。它不需要很多代码行，并产生了相当不错的结果。这将创建一个时间表，其中每支球队在他们的分区中与每个球队比赛两次，一次与其他分区的球队比赛。但是，没有检查以确保团队以同一团队在家的方式相遇两次。但是这段代码应该很好地了解如何创建自己的调度代码。

#!/usr/bin/python

div1 = ["Lions", "Tigers", "Jaguars", "Cougars"]
div2 = ["Whales", "Sharks", "Piranhas", "Alligators"]
div3 = ["Cubs", "Kittens", "Puppies", "Calfs"]

def create_schedule(list):
    """ Create a schedule for the teams in the list and return it"""
    s = []

    if len(list) % 2 == 1: list = list + ["BYE"]

    for i in range(len(list)-1):

        mid = int(len(list) / 2)
        l1 = list[:mid]
        l2 = list[mid:]
        l2.reverse()    

        # Switch sides after each round
        if(i % 2 == 1):
            s = s + [ zip(l1, l2) ]
        else:
            s = s + [ zip(l2, l1) ]

        list.insert(1, list.pop())

    return s


def main():
    for round in create_schedule(div1):
        for match in round:
            print match[0] + " - " + match[1]
    print
    for round in create_schedule(div2):
        for match in round:
            print match[0] + " - " + match[1]
    print
    for round in create_schedule(div3): 
        for match in round:
            print match[0] + " - " + match[1]
    print
    for round in create_schedule(div1+div2+div3): 
        for match in round:
            print match[0] + " - " + match[1]
        print

if __name__ == "__main__":
    main()
于 2009-06-24T08:47:47.350 回答
9

有两种算法，一种用于奇数队，一种用于偶数队，以确保循环赛发生。

如果可以的话，我将为您生成一个图形。

奇数#团队

该算法是顺时针旋转所有团队。如果我们有 5 个团队：

1 2 --> 3 1 --> 5 3 --> 4 5 --> 2 4
3 4     5 2     4 1     2 3     1 5
5       4       2       1       3

至此，我们已经完成了一轮循环赛，每个人都互相比赛一次......下一轮将再次......

1 2
3 4
5

偶数个团队

当我们的队伍数量为偶数时，您进行相同的轮换，除了您将＃1队伍固定在固定位置，并以顺时针方式围绕＃1轮换所有其他队伍。所以，如果我们有 4 个团队..

1 2 --> 1 3 --> 1 4 
3 4     4 2     2 3

这将是一个完整的循环赛......下一场比赛将是......

1 2 
3 4

以编程方式，有几种方法可以解决这个问题。也许上面发布的代码做同样的事情大声笑..

于 2009-06-24T16:37:29.227 回答
3

我只是将这些约束编码为布尔公式并使用一些 SAT 求解器来获得解决方案（例如 C++ 的 MiniSAT，Java 的 SAT4J，您甚至可以编写自己的简单求解器）。这些求解器的输入由 DIMACS 标准化。

有关类似问题的 SAT 编码，另请参阅“社交高尔夫球手问题的 SAT 编码”和“基于 SAT 的锦标赛日程安排程序”。

于 2009-06-24T09:02:14.823 回答
2

这是一个实现的镜头

public interface ITeam
{
   bool PlaysOn(DateTime date);
   bool canPlay(ITeam); //returns true if a game between the teams is legal (played once/twice   
                        //already, same different divisions and other applicable rules
}

IEnumerable<ITeam> teams = null; //replace with initialization
IEnumerable<ITeams> reversed = team.Reverse();
IEnumerable<DateTIme> gameDays = null;//replace with initialization
var count = teams.Count();

foreach(var date in gameDays)
{
   for(int i = 0;i<count;i++)
   {
      var innerTeams = i % 2 == 0 ? teams : reversed;
      var team = (from t in innerTeams
                  where !t.PlaysOn(date)
                  select t).First();  
      var opp = (from t in teams
                 where !t.PlaysOn(date) && t.CanPlay(team)
                 select t).First();
      SetupGame(team,opp);
   }
} //lot of optimazation possible :)

我只在纸上测试过它，但对于我的设置它是有效的。通过从队伍列表的开头和列表的末尾交替开始，我避免了在我的笔试中同一支队伍必须一遍又一遍（或在同一天重复比赛）的情况，我将每一次可能的遭遇都表示为不同的对手，但这基本上是 CanPlay 方法应该做的。希望这会有所帮助，尽管它不是一个完整的解决方案

于 2009-06-24T10:52:42.560 回答