算法：从一组游戏

Question

我试图创建一个体育联盟调度，我想安排团队组，以每队每获得一个小组赛选择对球队的。我认为我试图做的事情是计算机科学中存在的问题，但我不知道它叫什么，我无法找到有关它的信息。无论哪种方式，这里的情况：

比方说，我有一组球队A = {1,2,3,...,n}和一组对B = {(1,2), (1,3), (2,4), (6,9),...}。 B没有来自A的所有可能的组合。假设A有偶数个团队。我的程序正在尝试创建B的子集（让我们调用子集S），这样A中的每个团队都只出现一次。它通过将对从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

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

在您的问题图G（V - 组顶点，E - 组边的），其中V = A，E = B.另外添加相对边缘曲线图。每条边的重量为1.

我建议您使用Hungarian Algorithm作为二分图，Edmond's algorithm作其他作用。

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 

-