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

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。

我建议您对二分图使用匈牙利算法，对其他图使用爱德蒙算法。

Answer 2

必须作出一些假设，以澄清下文所述内容。

First，假设我们谈论的是一个乒乓球联赛中的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

-