算法：从一组游戏中选择成对的球队

Question

我正在尝试为体育联盟创建一个调度程序，我想将球队分组，以便每个球队每组进行一场比赛。我认为我想做的事情是计算机科学中现有的问题，但我不知道它叫什么，而且我很难找到有关它的信息。无论哪种方式，情况如下：

假设我有一组团队 A = {1,2,3,...,n} 和一组这些团队对 B = {（1,2），（1,3），（2,4），（6,9），...}。 B 并不拥有 A 中所有可能的球队组合。假设 A 有偶数个球队。我的程序正在尝试创建 B 的子集（我们称其为 S 子集），以便 A 中的每个团队在 S 中恰好出现一次。它通过将这些对从 B 移动到 S 来实现这一点，一次一个。假设它已经将几对放入 S 中。如何确定在当前情况下是否可以成功创建 S？

示例：

A = {1,2,3,4}, B = {(1,2), (1,3), (1,4), (3,4)}

If after one move, S = {(1,2)}, then it can be completed by moving (3,4).
If after one move, S = {(1,3)}, then it cannot be completed.

更新： 该算法将是我在日程生成器中使用的启发式算法之一。目标是隐式地将赛程分成“波”，其中每支球队每波有一场比赛。假设我有 16 支球队的池子，每支球队将与池子里的其他球队进行 5 场比赛。理想的赛程表应确保在每支球队都至少打一场比赛之前，没有球队进行第二场比赛。调度程序一次选择一场比赛并为其分配一个日期。因此，我们的想法是让调度程序跟踪此“波”中安排的比赛，并且永远不要选择会阻止每个团队在当前波中只玩一次的比赛。调度程序还使用了许多其他启发式方法，因此我无法明确对游戏进行排序并使其按顺序进行。

如果这不清楚或不是很严格，我很抱歉。请随时要求澄清，我会尽力进一步解释。

Answer 1

这是图论中的最大匹配问题。有一些已知的算法可以解决这个问题。

在您的问题图中 G（V - 顶点集，E - 边集），其中 V = A，E = B。还要向图中添加相反的边。每条边的权重为1。

我建议您使用匈牙利算法< /a> 用于二分图和 Edmond 的算法供其他人使用。

Answer 2

做出一些假设来澄清下面的内容非常重要。
首先，假设我们正在讨论乒乓球联赛中的 16 支球队，并且您希望制定一个赛程表，其中所有球队都进行五场比赛，并且不重复任何对手。
第二，您希望所有 16 支球队在任何球队再次比赛之前完成每盘比赛。
第三，您希望所有球队都分布在 8 张桌子上比赛，而不是总是安排一支球队在同一张桌子上比赛。

如果我的假设正确，那么您需要的是平衡的 16 支球队循环赛赛程中的前 5 个“组”（您将每组称为一波）比赛。这将为您提供锦标赛类型的团队比赛，其中每支球队与 5 支不同的球队进行 5 场比赛。每盘（或波）有 8 场比赛，并且没有球队总是被安排在同一张桌子上比赛，并且在所有球队都打完当前盘之前，球队不会进行下一场比赛。

以下是我为您创建的 16 支球队的平衡赛程表中的前 5 个“组”。一探究竟。

16 TEAM SCHEDULE       DATE 8/3/14            

DATE   DAY  TIME    LOCATION    GM#  HOME VS VISITOR

___ __ ___ _______  Table #1     1   #1  v  #16
___ __ ___ _______  Table #2     1   #2  v  #15
___ __ ___ _______  Table #3     1   #3  v  #14
___ __ ___ _______  Table #4     1   #4  v  #13
___ __ ___ _______  Table #5     1   #5  v  #12
___ __ ___ _______  Table #6     1   #6  v  #11
___ __ ___ _______  Table #7     1   #7  v  #10
___ __ ___ _______  Table #8     1   #8  v  #9

___ __ ___ _______  Table #1     2   #13 v  #2
___ __ ___ _______  Table #2     2   #15 v  #1
___ __ ___ _______  Table #3     2   #16 v  #14
___ __ ___ _______  Table #4     2   #12 v  #3
___ __ ___ _______  Table #5     2   #11 v  #4
___ __ ___ _______  Table #6     2   #10 v  #5
___ __ ___ _______  Table #7     2   #9  v  #6
___ __ ___ _______  Table #8     2   #7  v  #8

___ __ ___ _______  Table #1     3   #6  v  #7
___ __ ___ _______  Table #2     3   #16 v  #12
___ __ ___ _______  Table #3     3   #15 v  #13
___ __ ___ _______  Table #4     3   #14 v  #1
___ __ ___ _______  Table #5     3   #2  v  #11
___ __ ___ _______  Table #6     3   #4  v  #9
___ __ ___ _______  Table #7     3   #5  v  #8
___ __ ___ _______  Table #8     3   #3  v  #10

___ __ ___ _______  Table #1     4   #8  v  #3
___ __ ___ _______  Table #2     4   #14 v  #12
___ __ ___ _______  Table #3     4   #1  v  #13
___ __ ___ _______  Table #4     4   #9  v  #2
___ __ ___ _______  Table #5     4   #10 v  #16
___ __ ___ _______  Table #6     4   #11 v  #15
___ __ ___ _______  Table #7     4   #4  v  #7
___ __ ___ _______  Table #8     4   #5  v  #6

___ __ ___ _______  Table #1     5   #3  v  #6
___ __ ___ _______  Table #2     5   #13 v  #11
___ __ ___ _______  Table #3     5   #15 v  #9
___ __ ___ _______  Table #4     5   #2  v  #7
___ __ ___ _______  Table #5     5   #10 v  #14
___ __ ___ _______  Table #6     5   #16 v  #8
___ __ ___ _______  Table #7     5   #12 v  #1
___ __ ___ _______  Table #8     5   #4  v  #5

-