python - 组合学 - 安排比赛的团队协会

Question

tl;dr

我想通过游戏的不同事件分配玩家。
在比赛期间，一支球队可以进行固定数量的回合。
主要限制是:每个球队必须参加每场比赛，但每个球队不必与比赛>所有团队。

我已经在网上搜索了答案，但它们都与锦标赛有关，没有像我一样的限制。

您现在可以跳过接下来的两个部分。

介绍

我是大型游戏组织的一员，我有责任通过游戏期间的不同事件来分配玩家。当我意识到这不是一个容易解决的问题时，我尝试编写一个 Python 脚本来完成这项工作。然后，我意识到我做错了，因为我的脚本以一种确定性的方式工作。人们告诉我应该使用求解器(约束编程)来完成。但是我在这个领域没有概念。它试图使用包 python-constraint解决我的问题，但我没有成功定义良好的约束。

我做过的搜索

我也在网上搜索过这个问题，但我找到的大部分答案都与锦标赛有关，它没有像我一样的限制。事实上，锦标赛的主要目标是确保每支球队都与所有其他球队比赛。在这里，主要的限制是确保每个团队都参加每项事件。
我找到了 a similar thread在 math.stackexchange 上，但约束不一样，没有正确的答案。

输入

• 有 36 个团队。
• 有22 项事件。 (有决斗)
• 有22轮。

约束

1. 球队不能与自己比赛。
2. 每个团队都必须参加每项事件。
3. 一个团队在比赛中不能进行超过22 项事件。 (因为只有 22 轮)
4. 尽量减少球队与他们已经打过比赛的球队比赛。

由于有36支球队进行22场对决，所以每轮都会有一些事件是空的。
由于有 22 项事件和 22 轮，一个团队不能多次进行一项事件。

可能的答案示例

       | Round 1        | Round 2        | Round n        
------ | -------------- | -------------- | --------------  
Game 1 | Team1 vs Team2 | Team3 vs Team5 | Team? vs Team?  
Game 2 | Team3 vs Team4 | Team1 vs Team6 | Team? vs Team?  
Game n | Team? vs Team? | Team? vs Team? | Team? vs Team?  

Python 中的问题模型

from constraint import *

problem = Problem()
problem.addVariable("Activity", [i for i in range(1, 22+1)])
problem.addVariables(["Team1", "Team2"], [i for i in range(1, 36+1)])
problem.addVariable("Round", [i for i in range(1, 22+1)])
problem.addConstraint(lambda a, b: a != b, ("Team1", "Team2"))
???

我的问题

我正在寻找能够:

• 定义我应该使用什么约束来解决我的问题。
• 或者用组合学解决这个问题。

它可以使用任何语言或使用任何工具。我以 Python 为例。

无论如何，我们将不胜感激。先感谢您!

Answer 1

你的问题一点也不简单，但我会尝试解决它。​​:) 我会尝试根据约束可满足性定义问题。我会依靠Boolean satisfiability并使用 Tseitin transformation对您的任务进行编码。

首先，让我们介绍一组 bool 变量，它们对应于一个团队在一轮比赛中进行的比赛:

game0_team0_round0, g0_t0_r1, ..., gk_tm_rn

我们将把约束编码为 bool 公式。它返回 True 当且仅当存在满足所有给定约束的这样的时间表。上面定义的一组变量值表示一个时间表:如果变量等于 True，则相应团队在相应轮次中进行了比赛。我们引入了很多约束。让我们同意，如果约束公式返回 True，则违反了此约束。

第一个约束禁止球队在一轮内打几场比赛:

for round in rounds:
    for team in teams:
        games = get_games_from_team_and_round (round, team)
        constr = greater_then_equal (games, 2)
        add_must_be_false_constr (constr)

'greater_then_equal' 构建伪 bool 值 约束，确保只有一场比赛对于团队/回合而言可以是True。你可以阅读here如何实现。 'add_must_be_false_constr' 确保不会违反约束。

接下来，让我们引入决斗约束:在一个回合内，必须有两支队伍进行比赛。同时，他们必须玩同一个游戏:

for round in rounds:
    for game in games:
        teams = get_teams_from_round (round)
        constr = greater_then_equal (teams, 3)
        add_must_be_false_constr (constr)

最后，每支球队必须参加每场比赛:

for round in rounds:
    for team in teams:
        games = get_games_from_team_and_round (round, team)
        constr = boolean_or (games)
        add_must_be_false_constr (constr)

我们确保每轮至少进行一场比赛。

您可以将结果公式放入求解器(例如 Glucose )，它会找到满足所有给定约束的随机计划。

现在是棘手的部分 - 最小化。我不确定如何正确地做到这一点，但是，例如，如果一对团队在给定的一轮比赛中进行了一场比赛，您可以引入一个变量，该变量为 True。接下来，您将引入“greater_then_equal”约束来限制这些变量的 True 值的数量。最后，你可以使用 assumptions找到重复次数最少的最佳时间表。

请注意，使用这种方法可能会花费很多时间来解决任务:以正确的方式实现所有内容并非易事，所以这就是为什么我不为您提供代码，而只是给您一个非常通用的原因描述如何去做。解决一个问题可能需要几个小时，但这取决于问题本身和限制条件。其他问题 - 它可能会消耗大量内存。我有通过做类似的事情解决非常大(10^4 个变量，10^6 个约束)问题的实践经验。祝你好运!