我正在尝试找出一种为循环赛设置比赛位置的算法。
- 每支球队与对方球队交手两次，一次在主场，一次在客场。
- 每个团队都有一个主场位置。
- 锦标赛中有许多球队共享相同的主场位置。
我已经有所有匹配项的数组。匹配项如下所示：
{
date: "Thu Jan 08 2015 12:00:00",
home: "Bob",
away: "Frank",
location: null
}
我想遍历所有匹配项并分配location.我已经尝试了各种解决方案，但还没有完美的效果。
- 当然，如果鲍勃的家庭位置在
date可用，我们可以使用它。 - 我们必须考虑到鲍勃和弗兰克参加的另一场比赛。更换主客场球队是可以的，但我们必须确保它是平衡的。(即鲍勃和弗兰克各自在家玩一次(
- 如果在尝试切换主页/离开后也无法分配位置，则必须尝试位置拆分。
位置拆分
可以拆分比赛位置，以便在单个位置同时进行多场比赛。我们如何确定一个位置是否可以拆分超出了这个问题的范围，但假设我们有一个名为 canLocationBeSplit(location) 的函数，它返回一个bool true 或 false。
两支球队之间的任何一场比赛的主场或客场位置都可以分开。但是，除非绝对必要，否则我们只想开始拆分位置。同样，每支球队必须在主场进行一次比赛，在客场进行一次比赛。
如果仍然没有匹配的可用位置，我们只需将其保留为 null .
问题
所以我的问题是，有没有人对解决这个问题的合适递归算法有任何建议？谢谢你的时间。
一个微不足道的问题。由于不确定是否存在任何解决方案，因此很难证明您在不使用蛮力方法并将其与每个结果进行比较的情况下找到的任何解决方案都是针对您的要求的最佳解决方案。
没有解决方案的星座的一个例子是 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。
就像我说的，这不是一个最佳解决方案，可能会在没有指定位置的情况下产生一些匹配，但我希望这会产生足够好的结果。