运动员的数量有限,网球场的数量也有限。在每一轮,最多有多少场比赛就有多少场比赛。没有人在两轮比赛中不休息。每个人都在和其他人比赛。制作出尽可能少轮次的时间表。(因为规则是每个人都必须在两轮之间休息,所以可以有一轮没有比赛的回合。)5名球员和2个球场的输出可能是:
| 1 2 3 4 5
-|-------------------
2| 1 -
3| 5 3 -
4| 7 9 1 -
5| 3 7 9 5 -
在此输出中,列和行是玩家编号,矩阵中的数字是这两个玩家竞争的整数。
问题是找到一种算法,可以在可行的时间内对更大的实例做到这一点。我们被要求用Prolog来做这件事,但是任何语言的(伪)代码都是有用的。
我的第一次尝试是一个贪婪的算法,但它给出的结果太多了。然后我建议了一个迭代加深深度优先搜索,我的一个朋友实现了,但在小到7个玩家的实例上仍然花费了太多的时间。
(这是一道旧的考题。我采访过的人中没有人有任何解决方案。)
发布于 2011-01-20 21:48:43
这非常类似于Traveling Tournament Problem,它是关于安排足球队的。在TTP中,他们最多只能找到8个团队的最优解决方案。任何打破10个或更多团队的持续记录的人,都更容易在研究期刊上发表文章。
这是NP困难的,诀窍是使用元启发式,如禁忌搜索,模拟退火,...而不是蛮力或分枝捆绑。
看一下使用Drools Planner的my implementation (开源的java)。Here are the constraints,它应该是直接的,用限制来代替它,比如没有人打2轮没有休息。
发布于 2011-01-26 22:10:38
每个玩家必须至少玩n-1场比赛,其中n是玩家的数量。所以最小轮次是2(n - 1) - 1,因为每个玩家都需要休息一场比赛。最小值还由(n(n-1))个/2总匹配除以法庭数量确定。使用这两种方法中最小的一种可以得到最优解的长度。然后是一个很好的较低的估计公式((剩余的matches+rests数)/courts)并运行A* search。
正如Geoffrey所说,我认为这个问题是NP困难的,但是像A*这样的元启发式非常适用。
发布于 2011-01-21 09:45:39
Python解决方案:
import itertools
def subsets(items, count = None):
if count is None:
count = len(items)
for idx in range(count + 1):
for group in itertools.combinations(items, idx):
yield frozenset(group)
def to_players(games):
return [game[0] for game in games] + [game[1] for game in games]
def rounds(games, court_count):
for round in subsets(games, court_count):
players = to_players(round)
if len(set(players)) == len(players):
yield round
def is_canonical(player_count, games_played):
played = [0] * player_count
for players in games_played:
for player in players:
played[player] += 1
return sorted(played) == played
def solve(court_count, player_count):
courts = range(court_count)
players = range(player_count)
games = list( itertools.combinations(players, 2) )
possible_rounds = list( rounds(games, court_count) )
rounds_last = {}
rounds_all = {}
choices_last = {}
choices_all = {}
def update(target, choices, name, value, choice):
try:
current = target[name]
except KeyError:
target[name] = value
choices[name] = choice
else:
if current > value:
target[name] = value
choices[name] = choice
def solution(games_played, players, score, choice, last_players):
games_played = frozenset(games_played)
players = frozenset(players)
choice = (choice, last_players)
update(rounds_last.setdefault(games_played, {}),
choices_last.setdefault(games_played, {}),
players, score, choice)
update(rounds_all, choices_all, games_played, score, choice)
solution( [], [], 0, None, None)
for games_played in subsets(games):
if is_canonical(player_count, games_played):
try:
best = rounds_all[games_played]
except KeyError:
pass
else:
for next_round in possible_rounds:
next_games_played = games_played.union(next_round)
solution(
next_games_played, to_players(next_round), best + 2,
next_round, [])
for last_players, score in rounds_last[games_played].items():
for next_round in possible_rounds:
if not last_players.intersection( to_players(next_round) ):
next_games_played = games_played.union(next_round)
solution( next_games_played, to_players(next_round), score + 1,
next_round, last_players)
all_games = frozenset(games)
print rounds_all[ all_games ]
round, prev = choices_all[ frozenset(games) ]
while all_games:
print "X ", list(round)
all_games = all_games - round
if not all_games:
break
round, prev = choices_last[all_games][ frozenset(prev) ]
solve(2, 6)
输出:
11
X [(1, 2), (0, 3)]
X [(4, 5)]
X [(1, 3), (0, 2)]
X []
X [(0, 5), (1, 4)]
X [(2, 3)]
X [(1, 5), (0, 4)]
X []
X [(2, 5), (3, 4)]
X [(0, 1)]
X [(2, 4), (3, 5)]
这意味着它将需要11轮。该列表以相反的顺序显示了要在轮次中进行的游戏。(尽管我认为相同的时间表可以向前和向后工作。)我会回来解释为什么我有这个机会。
对于一个球场,五名球员,得到了错误的答案。
https://stackoverflow.com/questions/4747498
复制相似问题