我会先说,我明白这个主题很复杂,可能没有一个简单的答案。如果它很容易,那么每个人都会这样做。也就是说...
我被要求构建一个管理体育联盟的应用程序,其中大部分概念都很容易理解,除了这个:如何生成一个没有重叠的赛程表(一个队同时与两个队比赛),其中一个分区的一个队与自己的队比赛两次,但与其他分区的队比赛一次,并确保赛程表中没有漏洞(每个队每周比赛)
目前,这个过程是使用我为此目的构建的罗塞塔石碑类型的电子表格手动完成的,但它只适用于它所设计的团队数量。我为30个团队、24个团队和28个团队做了不同的修改。与其不断尝试重新调整我的翻译表,我希望能够将逻辑编码并调整这个过程。
有什么想法?
4条答案
按热度按时间ubbxdtey1#
有一个非常简单的系统用于例如国际象棋锦标赛称为循环赛。
这个想法是把玩家分到一张table的两边。其中一个玩家被指定为“枢纽”(我想找个更好的词)。锦标赛开始时,选手们面对面地互相比赛。第一轮过后,除了中锋以外,每个人都向前移动一把椅子,白色/黑(体育运动中的主客场)顺序互换。当运动员坐在原来的位置上时,整个循环赛就结束了。如果你想让每个人都玩两次,就再做一次。
Wikipedia article及其实施细节。
在你的特殊情况下,我会尝试做一次循环赛,包括所有的球队。然后你做同样的每一个分区一次,并确保球队在分区内发挥对方一次在家里和一个客场,从第一轮循环赛检查球队在这一轮的方式。
当然,这样做的缺点是,你将在锦标赛结束前打完所有的分区间比赛(因为最后n-1场比赛是对分区内球队[n=分区内球队的数量])。如果这是一个问题,你可以简单地交换比赛。
我实际上写了一个简单的Python脚本来实现这个功能。它不需要很多代码行,但产生了相当好的结果。这将创建一个时间表,每个团队在他们的分区中与每个团队进行两次比赛,并与其他分区中的团队进行一次比赛。没有检查来确保团队以同一个团队在家的方式彼此相遇两次。但是这段代码应该给予了如何创建自己的调度代码的好主意。
b4qexyjb2#
有两种算法,一种是奇数队的,一种是偶数队的,以确保循环赛的发生。
如果可以的话,我会给你生成一个图形。
奇数组
算法是顺时针旋转所有的队伍。如果我们有5支队伍:
在这一点上,我们已经完成了一轮循环赛,每个人都玩对方一次...下一轮将再次...。
偶数组
当我们有偶数个队时,你做同样的旋转,除了你把#1队固定在一个位置上,然后把其他队都绕着#1队顺时针旋转。
这将是一个完整的循环赛...下一场比赛将是...
从程序上来说,有几种方法可以实现这个。
yftpprvb3#
我会将这些约束编码为布尔公式,然后使用一些SAT求解器来获得解(例如C++的MiniSAT,Java的SAT4J,你甚至可以编写自己的简单求解器)。
对于类似问题的SAT编码,也可参见“用于社交高尔夫球手问题的SAT编码”和“用于比赛日程的基于SAT的调度器”。
a0zr77ik4#
下面是一个实现尝试
我只在纸上测试过,但是对于我的设置来说,它是有效的。通过在球队列表的开头和结尾之间交替开始,我避免了同一支球队不得不一遍又一遍地与同一支球队比赛的情况(或在同一天重复玩)在我的纸上测试中,我把每一次可能的遭遇都表示为不同的对手,但这基本上是CanPlay方法应该做的。希望这能有所帮助,尽管它不是一个完整的解决方案