12

我正在使用 Python 开发一个瑞士锦标赛系统，并且正在尝试找出最佳配对算法。
我最大的问题是，我提出的每个算法都会在几个序列中产生错误，其中最后一个被选中的对已经互相玩了，裁定配对无效。

我正在研究的瑞士系统很简单：即使是球员，每个人都在每一轮比赛，并且根据获胜的距离进行配对（所以强者对抗强者，弱者对抗弱者）。
No Bye，只有赢/输（没有平局），对手不能互相比赛两次。

我所做的当前算法如下：

  1. 按排名顺序生成玩家列表（最多获胜到最少获胜）
  2. 选择玩家，从获胜最多的玩家开始
  3. 将他与排名最接近的玩家匹配。如果他们已经玩过，将他与下一个匹配，直到找到匹配
  4. 将这对从列表中弹出并返回到 1

例如：
2轮后的排名： 

1. P1: [P2 win, P3 win] 2 wins
2. P5: [P6 win, P2 win] 2 wins
3. P3: [P4 win, P1 lost] 1 win, 1 loss
4. P4: [P6 win, P3 lost] 1 win, 1 loss
5. P2: [P1 lost, P5 lost] 2 losses
6. P6: [P5 lost, P4 lost] 2 losses

第一个选择是 P1，第一个匹配是 P5。将 (P1,P5) 从列表中取出。

1. P3: [P4 win, P1 lost] 1 win, 1 loss
2. P4: [P6 win, P3 lost] 1 win, 1 loss
3. P2: [P1 lost, P5 lost] 2 losses
4. P6: [P5 lost, P4 lost] 2 losses

第一个选择是 P3，已经玩过 P4，所以比赛是 P2。将 (P3,P2) 从列表中删除。
在这个序列中，我以一对相互对战并且配对无效：

1. P4: [P6 win, P3 lost] 1 win, 1 loss
2. P6: [P5 lost, P4 lost] 2 losses

问题：是否有任何算法可以保证最佳配对模块，同时确保我不会在最后被两个互相玩的玩家“卡住”？

4

4 回答 4

5

也许我可以帮你。在国际象棋中，我们有不同的瑞士配对算法，但它们都适用于强弱配对（可能会有惊喜）。

荷兰语（最常用）的基本原则是，一旦您分配了配对号码，您就可以将算法应用于每个分数范围。

该算法的工作原理大致如下：

在第一个得分组中，选择（大约）一半的球员并将他们放在一个子组中，并将其他球员放在另一个子组中。如果播放器兼容，则将它们配对。如果它们不兼容，请尝试交换第二个子组中的播放器。如果没有配对兼容，则在子组之间交换播放器。如果括号中的玩家人数为奇数，则将向下浮动。

在下一个分数括号中：如果有漂浮物，请先配对。然后，对残差组执行与之前相同的操作。

添加了更多规则以确保至少有一对可能。

例如：如果没有交易所能够做出足够好的配对，则回溯到上一个得分范围并打破配对以进行浮动。

这是对荷兰配对系统的一个非常粗略的解释，但这是我回答你的问题。

于 2015-12-15T19:11:33.723 回答
3

蛮力算法将保证找到一个最佳配对模块，如果有的话：

  1. 定义配对的惩罚函数（可能是配对玩家获胜的差异）
  2. 在此基础上，为pairing modules定义一个惩罚函数（可能是模块中pairings各自惩罚值的平方和）
  3. 枚举所有有效模块（注意可能没有）
  4. 对于每个有效模块，根据（2）计算模块惩罚值
  5. 按此值排序并选择具有最小惩罚值的（一个）模块。（最小值可能由几个人共享。）

对于少数玩家，这甚至可能导致可行的运行时。对于更大的数字，您需要研究优化和快捷方式。

于 2015-02-20T14:03:12.993 回答
2

前段时间我有同样的问题，最终在python中使用最小权重最大匹配算法构建了一个解决方案。甚至还有一个不错的图书馆！https://healthyalgorithms.com/2009/03/23/aco-in-python-minimum-weight-perfect-matchings-aka-matching-algorithms-and-reproductive-health-part-4/

我在博客文章中写下了我的思考过程，并确保链接到我在构建它时使用的资源。希望这会有所帮助：https ://www.leaguevine.com/blog/18/swiss-tournament-scheduling-leaguevines-new-algorithm/

于 2016-06-24T22:00:02.610 回答
1

我遇到了同样的问题并通过以下方式解决了它。

  1. 我把中间的排名分成了两组

  2. 对于每个组： a. 在 b 行和列中创建一个包含玩家的矩阵。为禁止配对（例如：已经玩过，如果玩家人数为奇数的情况下为虚拟玩家）分配高成本（例如：10000） c．为所有其他配对分配一个“表现”值，例如基于获得和失去的点数 d。找到所有可能的匹配，只在矩阵的一半，因为它是一面镜子。求和该解决方案的“性能值” e。成本 > 10000 f 的跳过对。对解决方案列表进行排序，取总和最低的条目

  3. 如果没有解决方案，则在不拆分玩家的情况下重新执行相同的算法。

只有在圈数得到控制的情况下，总有最优解。例如，对于 20 名玩家，最佳回合数是 5，更多可能会很危险（没有找到任何解决方案）。

我已经用 C++ 实现了这个算法，并在现场进行了真正的锦标赛测试，效果很好。你可以在 Github 的Tanca 存储库中找到它，在名为“Tournament.cpp”的文件中。

我还在我的博客上写了一篇文章（法语，抱歉）。

于 2017-07-03T15:31:06.587 回答