算法:从一组游戏中选择成对的团队

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 场比赛。一个理想的时间表将确保在每支球队至少有一场比赛之前没有球队有他们的第二场比赛。调度程序一次选择一个游戏并为它们分配一个日期。因此，我们的想法是让调度程序跟踪在此“wave”中安排的比赛，并且永远不要选择会阻止每个团队在当前 wave 中恰好进行一次的比赛。调度程序还使用了一系列其他启发式方法，因此我无法明确地对游戏进行排序并让它按顺序进行。

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

Answer 1

是Maximum matching problem在图论中。有一些已知的算法可以解决它。

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

我建议你使用Hungarian Algorithm对于二部图和 Edmond's algorithm对于其他人。