我想知道是否有一种方法可以加快给定足球联赛表的足球（足球）保证促销的计算。似乎问题有很多结构，所以详尽的解决方案可能比必要的要慢。
在问题中，有一个schedule（一对球队的列表）将在将来互相比赛，并且每个球队在过去的比赛中获得了table（地图）的积分。我在包含了一个示例的现实生活中的积分表。每个未来的比赛都可以赢，输或并列，并且每个球队在获胜时获得 3 分，在正数 / 整数时获得 1 分。
问题是要确定哪些（如果有的话）团队目前可以保证晋升。保证晋升意味着无论决赛结果如何，球队最终都必须晋升。
def promoted(num_of_promoted_teams, table, schedule):
return guaranteed_promotions
我一直在考虑使用深度优先搜索 (对未来的比赛结果) 来淘汰那些会降低平均水平但不会降低最差表现的球队。这肯定会在赛季初有所帮助，但问题可能会在赛季中期变得很大，然后在接近尾声时再次缩小。看起来可能有更好的方法。
由于巧妙的修剪算法，约束求解器在实践中应该足够快，并且很难搞砸。这是 OR-Tools CP-SAT 求解器的一些示例代码。
from ortools.sat.python import cp_model
def promoted(num_promoted_teams, table, schedule):
for candidate in table.keys():
model = cp_model.CpModel()
final_table = table.copy()
for home, away in schedule:
home_win = model.NewBoolVar("")
draw = model.NewBoolVar("")
away_win = model.NewBoolVar("")
model.AddBoolOr([home_win, draw, away_win])
model.AddBoolOr([home_win.Not(), draw.Not()])
model.AddBoolOr([home_win.Not(), away_win.Not()])
model.AddBoolOr([draw.Not(), away_win.Not()])
final_table[home] += 3 * home_win + draw
final_table[away] += draw + 3 * away_win
candidate_points = final_table[candidate]
num_not_behind = 0
for team, team_points in final_table.items():
if team == candidate:
continue
is_behind = model.NewBoolVar("")
model.Add(team_points < candidate_points).OnlyEnforceIf(is_behind)
model.Add(candidate_points <= team_points).OnlyEnforceIf(is_behind.Not())
num_not_behind += is_behind.Not()
model.Add(num_promoted_teams <= num_not_behind)
solver = cp_model.CpSolver()
status = solver.Solve(model)
if status == cp_model.INFEASIBLE:
yield candidate
print(*promoted(2, {"A": 10, "B": 8, "C": 8}, [("B", "C")]))
这里有一个替代解决方案，它的可扩展性较低，可能较慢，以换取自包含和可。
此解决方案由一个算法组成，该算法用于测试特定团队是否可以在一组特定的其他团队之后完成（假设不利的抢七局），这些团队被包裹在由前 k 个团队和一组 k 个团队组成的成对循环中 W 可能会或可能不会提前完成（其中 k 是晋升团队的数量）。
如果没有平局，那么我们可以使用二分匹配。标记为输掉了剩余的比赛，标记为 W 赢得了与不在 W 中的球队的比赛。在二分图的一侧，有与 W 成员之间的比赛相对应的节点。在另一侧，W 中的每个团队都有零个或多个节点，对应于该团队必须赢得的比赛数才能在前场晋级之前完成。
因此,在最多 k 的所有子集上循环选择 2 对团队,并在将子集中的每对标记为已绘制一次后运行上面的算法。
（我可以提出改进，但是 k 很小，计算机便宜，程序员昂贵，体育迷无情。）
本站系公益性非盈利分享网址，本文来自用户投稿，不代表码文网立场，如若转载，请注明出处
评论列表（10条）