3

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

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

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

4

2 回答 2

4

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

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

我建议您将匈牙利算法 用于二分图，将 Edmond 算法用于其他图。

于 2011-10-24T19:03:09.740 回答
0

重要的是要做出一些假设来澄清下面介绍的内容。
首先，假设我们谈论的是乒乓球联赛中的 16 支球队，并且您想要一个所有球队都打 5 场比赛而不重复任何对手的赛程。
其次，您希望所有 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

-
于 2014-08-03T05:22:17.290 回答