瑞士锦标赛 - 配对算法

Question

我正在使用Python的瑞士锦标赛系统,我正试图找出一个最佳的配对算法.
我最大的问题是我所带来的每个算法都会在几个序列中产生错误,其中最后一对被拾取的对象已经相互发挥作用,判断配对无效.

我正在研究的瑞士系统很简单:即使是玩家,每个人都会在每一轮比赛中进行比赛,并且基于胜利的接近度来完成配对(因此强大的球员与强大的球员对抗,弱对弱者).
没有再见,只有输赢(没有平局),对手不能互相打两次.

我目前的算法如下工作:

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

---

问题:是否有任何算法可以保证最佳配对模块,同时确保我不会在两个玩家互相玩耍时"陷入困境"？

Answer 1

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

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

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

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

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

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

例如：如果没有交易所能够进行足够好的配对，则回溯到之前的分数范围并打破配对以制作漂浮物。

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

Answer 2

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

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

对于少数玩家来说，这甚至可能会产生可行的运行时间。对于更大的数量，您需要研究优化和快捷方式。