球员和网球场都是有限的。每一轮比赛中，最多只能有与场地数量相等的比赛进行。 没有人可以连续参加两轮比赛。每个人都要与其他人进行比赛。 生成尽可能少的轮次下的比赛安排。（由于每个人必须在两轮比赛之间休息，因此可能出现没有比赛的轮次。） 5名球员和2个场地的输出结果如下：
| 1 2 3 4 5
-|-------------------
2| 1 -
3| 5 3 -
4| 7 9 1 -
5| 3 7 9 5 -
在Prolog中，CLP(FD)约束是解决此类调度任务的正确选择。
更多信息请参见clpfd。
在这种情况下，建议使用强大的global_cardinality/2约束来限制每轮比赛的出现次数，具体取决于可用场地的数量。我们可以使用迭代加深来找到最小可接受轮数。
免费的Prolog系统足以满意地解决此任务。商业级系统将运行几十倍快。
:- use_module(library(clpfd)).
tennis(N, Courts, Rows) :-
length(Rows, N),
maplist(same_length(Rows), Rows),
transpose(Rows, Rows),
Rows = [[_|First]|_],
chain(First, #<),
length(_, MaxRounds),
numlist(1, MaxRounds, Rounds),
pairs_keys_values(Pairs, Rounds, Counts),
Counts ins 0..Courts,
foldl(triangle, Rows, Vss, Dss, 0, _),
append(Vss, Vs),
global_cardinality(Vs, Pairs),
maplist(breaks, Dss),
labeling([ff], Vs).
triangle(Row, Vs, Ds, N0, N) :-
length(Prefix, N0),
append(Prefix, [-|Vs], Row),
append(Prefix, Vs, Ds),
N #= N0 + 1.
breaks([]).
breaks([P|Ps]) :- maplist(breaks_(P), Ps), breaks(Ps).
breaks_(P0, P) :- abs(P0-P) #> 1.
示例查询：2个场地上的5名球员：
?- time(tennis(5, 2, Rows)), maplist(writeln, Rows).
% 827,838 inferences, 0.257 CPU in 0.270 seconds (95% CPU, 3223518 Lips)
[-,1,3,5,7]
[1,-,5,7,9]
[3,5,-,9,1]
[5,7,9,-,3]
[7,9,1,3,-]
SWI-Prolog版本5.8.0 for i386上返回了“false”。你知道为什么吗？也许这会是一个提示：第一个查询在5544个推理之后返回了“false”，第二个和第三个查询在42个推理之后返回了“false”。 - Bolotranspose/2，它可以正常工作。谢谢！ - BoloPython解决方案：
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)]
1. Create master-list of all matches ([12][13][14][15][16][23][24]...[45][56].)
2. While (master-list > 0) {
3. Create sub-list containing only eligible players (eliminate all players who played the previous round.)
4. While (available-courts > 0) {
5. Select match from sub-list where player1.games_remaining plus player2.games_remaining is maximized.
6. Place selected match in next available court, and
7. decrement available-courts.
8. Remove selected match from master-list.
9. Remove all matches that contain either player1 or player2 from sub-list.
10. } Next available-court
11. Print schedule for ++Round.
12. } Next master-list
我不能证明这个算法会得出最少轮次的赛程，但它应该会接近。可能会带来问题的是第5步（选择使选手剩余比赛最多的比赛）。我可以想象有一种情况，即在下一轮留下更多选择时，最好选择一个几乎最大化了“games_remaining”的比赛。
这个算法的输出大致如下：
Round Court1 Court2
1 [12] [34]
2 [56] --
3 [13] [24]
4 -- --
5 [15] [26]
6 -- --
7 [35] [46]
. . .
我不知道这是否重要，但“5名球员和2个场地”示例数据缺少另外三场比赛：[1,3]、[2,4]和[3,5]。根据指示：“每个人都要与其他所有人进行比赛。”