我正在尝试为一个体育联盟创建一个调度程序,我想将团队按组调度,这样每个团队每个组可以得到一个游戏我想我想做的是计算机科学中存在的问题,但我不知道它叫什么,我很难找到有关它的信息。不管怎样,情况是这样的:
假设我有一组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中只玩一次的游戏调度器还使用了很多其他的启发式方法,所以我不能显式地对游戏进行排序。
如果不清楚或不太严谨,我很抱歉。请随时要求澄清,我会尽力进一步解释。
最佳答案
它在图论中是Maximum matching problem有一些已知的算法可以解决这个问题。
在问题图G(顶点的V集,边的E集)中,其中V=A,E=B。还可以将相反的边添加到图中每边的重量是1。
我建议对二部图使用Hungarian Algorithm,对其他图使用Edmond's algorithm。