1

我正在尝试找出一种算法来为循环赛设置比赛位置。

  • 每支球队与对方球队交手两次，一次在主场，一次在客场。
  • 每支球队都有一个主场。
  • 比赛中有许多球队共享相同的主场。

我已经有一个包含所有匹配项的数组。一场比赛看起来像：

{
  date: "Thu Jan 08 2015 12:00:00",
  home: "Bob",
  away: "Frank",
  location: null
}

我想遍历所有匹配项并分配location. 我尝试了各种解决方案，但还没有一个完美的解决方案。

  • 当然，如果 Bob 的家庭位置可用，date我们就可以使用它。
  • 我们必须考虑鲍勃和弗兰克参加的另一场比赛。可以切换主队/客队，但我​​们必须确保它是平衡的。（即鲍勃和弗兰克在家里各玩一次）
  • 如果即使在尝试切换回家/离开之后也无法分配位置，那么我们必须尝试位置拆分。

位置拆分

可以拆分比赛地点，以便在一个地点同时进行多场比赛。我们如何确定一个位置是否可以拆分超出了这个问题的范围，但我们只是说我们有一个调用的函数canLocationBeSplit(location)，它返回bool真或假。

两支球队之间的任何一场比赛的主场或客场位置都可以分开。但是，除非绝对必要，否则我们只想开始拆分位置。同样，每支球队必须在主场比赛一次，在客场比赛一次。

如果仍然没有匹配的可用位置，我们将其保留为null。

问题

所以我的问题是，是否有人对可以解决此问题的合适递归算法有任何建议？谢谢你的时间。

4

1 回答 1

1

这不是一个小问题。由于根本不确定是否有任何解决方案，因此如果不使用蛮力方法并将其与每个结果进行比较，就很难证明您可能找到的任何解决方案都符合您的要求。

一个没有解决方案的星座的例子是 4 个团队，它们都共享一个不能拆分的家庭位置。所需的解决方案是将 NULL 值分配给某些匹配项，并且“最佳”解决方案将具有尽可能少的 NULL 值（因此，找到最佳解决方案是一个优化问题，甚至可能是 NP 难题？！）。

因此，根据您拥有的团队数量，我有两个建议：

  • 使用蛮力并计算所有可能的位置组合。话虽如此，让我们估计一下这意味着什么。假设您有 20 个团队。在最坏的情况下，10 场比赛都在同一日期进行（例如每个星期六）。因此，对于每周（38 个不同的日期），您需要从您拥有的 20 个位置中选择 10 个位置并计算这些位置的每个排列。这为您提供了38*binom(20,10)*10! = 25.476.817.766.400需要验证的不同组合（检查您是否满足上述要求），然后进行比较以找到最佳分布。如果你只有 10 个团队，这个数字会归结为只有241.920可能的组合，这实际上是相当小的！

  • 为第一个日期创建合理的位置分布并迭代日期，在不更改先前设置的位置的情况下尽可能地分配位置。这很可能不会为您提供最佳结果，并且可能会留下一些没有位置的匹配项，但您至少会在短时间内获得建议的位置分布。

为了获得我在第二种方法中所说的“合理”分布，我建议确定每个地点和每个日期在该地点可能进行多少场不同的比赛。然后首先分配可能匹配最少的位置，然后重复直到没有匹配项。

例子：

Team A - Home Location: 1
Team B - Home Location: 1
Team C - Home Location: 1
Team D - Home Location: 2
Team E - Home Location: 3
Team F - Home Location: 4

在某个给定日期匹配：

Match 1: Team A vs Team D
Match 2: Team B vs Team E
Match 3: Team C vs Team F

如果 A 队之前在位置 2 与 D 队交手，我们得到：

Location 1 could host 3 matches (all matches)
Location 2 could host no matches
Location 3 could host 1 match (Match 2)
Location 4 could host 1 match (Match 3)

因此，我们将分配Location 3给Match 2和只剩下分配Location 4给。Match 3Location 1Match 1

就像我说的那样，这不是一个最佳解决方案，并且可能会在没有指定位置的情况下产生一些匹配，但我希望这会产生足够好的结果。

于 2015-04-10T11:48:41.867 回答