javascript - 循环匹配定位算法

Question

我正在尝试找出一种算法来设置循环赛的比赛地点。

• 每支球队与另一支球队交手两次，一次在主场，一次在客场。
• 每个团队都有一个家。
• 锦标赛中有许多球队共享同一个主场。

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

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

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

• 当然，如果 Bob 的家庭位置在 date 可用，我们就可以使用它。
• 我们必须考虑 Bob 和 Frank 参加的另一场比赛。主客场互换没问题，但我们必须确保平衡。 (即 Bob 和 Frank 每人在家玩一次)
• 如果即使在尝试切换回家/离开后也无法分配位置，我们必须尝试位置拆分。

位置分割

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

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

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

问题

所以我的问题是，有没有人对解决这个问题的合适的递归算法有任何建议？感谢您的宝贵时间。

Answer 1

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

一个没有解决方案的星座示例是 4 个团队，它们都共享一个不能分开的家庭位置。理想的解决方案是将 NULL 值分配给某些匹配项，并且“最佳”解决方案将具有尽可能少的 NULL 值(因此找到最佳解决方案是一个优化问题，甚至可能是 NP-hard？!)。

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

• 使用暴力破解并计算所有可能的位置组合。话虽这么说，让我们估计一下这意味着什么。假设您有 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 3，这只会留下Location 1 分配给 Match 1。

正如我所说，这不是最佳解决方案，可能会产生一些没有指定位置的匹配项，但我希望这会产生足够好的结果。