循环匹配定位算法
Round robin match location algorithm
我正在尝试找出一种算法来设置循环赛的比赛地点。
- 每支球队与另一支球队交手两次，一次主场，一次客场。
- 每个团队都有一个主场位置。
- 锦标赛中有很多球队共享同一个主场。
我已经有了所有匹配项的数组。一场比赛看起来像：
{
date: "Thu Jan 08 2015 12:00:00",
home: "Bob",
away: "Frank",
location: null
}
我想遍历所有匹配项并分配 location。我尝试了各种解决方案，但还没有一个完美的解决方案。
- 当然，如果 Bob 的家庭位置在
date 可用，我们就可以使用它。
- 我们必须考虑 Bob 和 Frank 参加的另一场比赛。可以更换 home/away 个团队，但我们必须确保它是平衡的。 （即鲍勃和弗兰克各在家玩一次）
- 如果即使在尝试切换后也无法分配位置 home/away，我们必须尝试 位置拆分。
位置拆分
可以拆分比赛地点，以便在同一个地点同时进行多场比赛。我们如何确定一个位置是否可以拆分超出了这个问题的范围，但我们只是说我们有一个名为 canLocationBeSplit(location) 的函数，其中 returns a bool true 或 false.
两支球队之间的任何一场比赛的主场或客场位置都可以分开。但是，除非绝对必要，否则我们只想开始拆分位置。同样，每支球队必须在主场和客场比赛一次。
如果仍然没有可用的匹配位置，我们将其保留为 null。
问题
所以我的问题是，有人对解决这个问题的合适的递归算法有什么建议吗？感谢您的宝贵时间。
这不是一个小问题。由于根本不确定是否存在任何解决方案，因此如果不使用蛮力方法并将其与每个结果进行比较，就很难证明您可能找到的任何解决方案都符合您的要求。
一个没有解决方案的星座示例是 4 个团队，它们都共享一个不能拆分的家庭位置。理想的解决方案是将 NULL 值分配给某些匹配项，并且 "optimal" 解决方案将具有尽可能少的 NULL 值（因此找到最佳解决方案是一个优化问题，甚至可能是 NP-hard？！）。
因此，根据您拥有的团队数量，我有两个建议：
使用暴力计算所有可能的位置组合。话虽这么说，让我们估计一下这意味着什么。假设您有 20 个团队。在最坏的情况下，10 场比赛都在同一天进行（例如每个星期六）。因此，对于每周（38 个不同的日期），您需要从 20 个位置中选择 10 个位置，并计算这些位置的每个排列。这为您提供 38*binom(20,10)*10! = 25.476.817.766.400 需要验证的不同组合（检查是否满足上述要求），然后进行比较以找到最佳分布。如果您只有 10 个团队，这个数字将下降到只有 241.920 个可能的组合，这实际上是相当小的！
为第一个日期创建合理的位置分布并迭代日期，在不更改先前设置的位置的情况下尽可能分配最佳位置。这很可能不会为您提供最佳结果，并且可能会留下一些没有位置的匹配项，但您至少会在短时间内获得建议的位置分布。
要获得我在第二种方法中提到的 "reasonable" 分布，我建议确定每个位置和每个日期在该位置可能进行多少场不同的比赛。然后首先分配具有最少匹配项的位置并重复直到没有匹配项。
示例：
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。
正如我所说，这不是最佳解决方案，可能会产生一些没有指定位置的匹配项，但我希望这会产生足够好的结果。
我正在尝试找出一种算法来设置循环赛的比赛地点。
- 每支球队与另一支球队交手两次，一次主场，一次客场。
- 每个团队都有一个主场位置。
- 锦标赛中有很多球队共享同一个主场。
我已经有了所有匹配项的数组。一场比赛看起来像：
{
date: "Thu Jan 08 2015 12:00:00",
home: "Bob",
away: "Frank",
location: null
}
我想遍历所有匹配项并分配 location。我尝试了各种解决方案，但还没有一个完美的解决方案。
- 当然，如果 Bob 的家庭位置在
date可用，我们就可以使用它。 - 我们必须考虑 Bob 和 Frank 参加的另一场比赛。可以更换 home/away 个团队，但我们必须确保它是平衡的。 （即鲍勃和弗兰克各在家玩一次）
- 如果即使在尝试切换后也无法分配位置 home/away，我们必须尝试 位置拆分。
位置拆分
可以拆分比赛地点，以便在同一个地点同时进行多场比赛。我们如何确定一个位置是否可以拆分超出了这个问题的范围，但我们只是说我们有一个名为 canLocationBeSplit(location) 的函数，其中 returns a bool true 或 false.
两支球队之间的任何一场比赛的主场或客场位置都可以分开。但是，除非绝对必要，否则我们只想开始拆分位置。同样，每支球队必须在主场和客场比赛一次。
如果仍然没有可用的匹配位置，我们将其保留为 null。
问题
所以我的问题是，有人对解决这个问题的合适的递归算法有什么建议吗？感谢您的宝贵时间。
这不是一个小问题。由于根本不确定是否存在任何解决方案，因此如果不使用蛮力方法并将其与每个结果进行比较，就很难证明您可能找到的任何解决方案都符合您的要求。
一个没有解决方案的星座示例是 4 个团队，它们都共享一个不能拆分的家庭位置。理想的解决方案是将 NULL 值分配给某些匹配项，并且 "optimal" 解决方案将具有尽可能少的 NULL 值（因此找到最佳解决方案是一个优化问题，甚至可能是 NP-hard？！）。
因此，根据您拥有的团队数量，我有两个建议：
使用暴力计算所有可能的位置组合。话虽这么说，让我们估计一下这意味着什么。假设您有 20 个团队。在最坏的情况下，10 场比赛都在同一天进行（例如每个星期六）。因此，对于每周（38 个不同的日期），您需要从 20 个位置中选择 10 个位置，并计算这些位置的每个排列。这为您提供
38*binom(20,10)*10! = 25.476.817.766.400需要验证的不同组合（检查是否满足上述要求），然后进行比较以找到最佳分布。如果您只有 10 个团队，这个数字将下降到只有241.920个可能的组合，这实际上是相当小的！为第一个日期创建合理的位置分布并迭代日期，在不更改先前设置的位置的情况下尽可能分配最佳位置。这很可能不会为您提供最佳结果，并且可能会留下一些没有位置的匹配项，但您至少会在短时间内获得建议的位置分布。
要获得我在第二种方法中提到的 "reasonable" 分布，我建议确定每个位置和每个日期在该位置可能进行多少场不同的比赛。然后首先分配具有最少匹配项的位置并重复直到没有匹配项。
示例：
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。
正如我所说，这不是最佳解决方案，可能会产生一些没有指定位置的匹配项，但我希望这会产生足够好的结果。