球员数量有限，网球场数量有限。在每一轮中，最多可以有与球场一样多的比赛。没有人会不间断地进行 2 轮比赛。每个人都与其他人进行比赛。制定尽可能少的轮次的时间表。（由于每个人都必须在回合之间休息的规则，因此可能会有没有比赛的回合。）5名球员和2个球场的输出可能是：
| 1 2 3 4 5
-|-------------------
2| 1 -
3| 5 3 -
4| 7 9 1 -
5| 3 7 9 5 -
在此输出中，列和行是玩家编号，矩阵内的数字是这两个玩家竞争的轮数。
问题是找到一种算法，可以在可行的时间内为更大的实例执行此操作。我们被要求在 Prolog 中执行此操作，但任何语言的（伪）代码都是有用的。
我的第一次尝试是一个贪心算法，但它给出了太多轮次的结果。然后我建议了一个迭代加深深度优先搜索，我的一个朋友实施了，但在小到 7 个玩家的实例上仍然花费了太多时间。
（这是来自一个古老的考试问题。与我交谈过的人都没有任何解决方案。）
在 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,-]
指定任务，2场6人，1分钟内很好解决：
?- 时间(网球(6, 2, Rows)),
maplist(format("~t~w~3+~t~w~3+~t~w~3+~t~w~3+~t~w~3+~t~w~3+\n" ），行）。
% 6,675,665 推理，0.970 CPU 在 0.977 秒内（99% CPU，6884940 唇）
- 1 3 5 7 10
1 - 6 9 11 3
3 6 - 11 9 1
5 9 11 - 2 7
7 11 9 2 - 5
10 3 1 7 5 -
进一步的例子： 5 个球场上的 7 名球员：
?- 时间（网球（7, 5, Rows）），
maplist(format("~t~w~3+~t~w~3+~t~w~3+~t~w~3+~t~w~3+~t~w~3+~t~ w~3+\n"), 行)。
% 125,581,090 次推理，17.476 CPU 在 18.208 秒内（96% CPU，7185927 唇）
- 1 3 5 7 9 11
1 - 5 3 11 13 9
3 5 - 9 1 7 13
5 3 9 - 13 11 7
7 11 1 13 - 5 3
9 13 7 11 5 - 1
11 9 13 7 3 1 -
通过以下附加的兼容性定义，相同的程序也可以在 SICStus Prolog 中运行：
:- 使用模块（库（列表））。
:- 使用模块（库（之间））。
:- op(700, xfx, ins)。
Vs ins D :- maplist(in_(D), Vs)。
in_(D, V) :- D 中的 V。
链（[]， _）。
链（[L|Ls]，预测）：-
链_（Ls，L，Pred）。
链_（[]， _， _）。
chain_([L|Ls], Prev, Pred) :-
调用（上一个，上一个，L），
链_（Ls，L，Pred）。
pair_keys_values(Ps, Ks, Vs) :- keys_and_values(Ps, Ks, Vs)。
foldl(Pred, Ls1, Ls2, Ls3, S0, S) :-
foldl_(Ls1, Ls2, Ls3, Pred, S0, S)。
foldl_([], [], [], _, S, S)。
foldl_([L1|Ls1], [L2|Ls2], [L3|Ls3], Pred, S0, S) :-
呼叫（Pred，L1，L2，L3，S0，S1），
foldl_(Ls1, Ls2, Ls3, Pred, S1, S)。
时间（目标）：-
统计数据（运行时，[T0|_]），
呼叫（目标），
统计数据（运行时，[T1|_]），
T #= T1 - T0,
格式（“%运行时间：~Dms\n”，[T]）。
主要区别：SICStus 是一个商业级 Prolog，带有一个严肃的 CLP(FD) 系统，在这个用例和其他类似的用例中比 SWI-Prolog快得多。
指定任务，2场6名队员：
?- 时间(网球(6, 2, Rows)),
maplist(format("~t~w~3+~t~w~3+~t~w~3+~t~w~3+~t~w~3+~t~w~3+\n" ），行）。
%运行时间：34 毫秒（！）
- 1 3 5 7 10
1 - 6 11 9 3
3 6 - 9 11 1
5 11 9 - 2 7
7 9 11 2 - 5
10 3 1 7 5 -
更大的例子：
| ?- 时间（网球（7, 5, Rows）），
maplist(format("~t~w~3+~t~w~3+~t~w~3+~t~w~3+~t~w~3+~t~w~3+~t~ w~3+\n"), 行)。
%运行时间：884 毫秒
- 1 3 5 7 9 11
1 - 5 3 9 7 13
3 5 - 1 11 13 7
5 3 1 - 13 11 9
7 9 11 13 - 3 1
9 7 13 11 3 - 5
11 13 7 9 1 5 -
在这两个系统中，global_cardinality/3允许您指定更改全局基数约束的传播强度的选项，从而实现更弱且可能更有效的过滤。为特定示例选择正确的选项可能比选择 Prolog 系统产生更大的影响。
这与关于安排足球队的巡回锦标赛问题非常相似。在 TTP 中，他们最多只能找到 8 个团队的最佳解决方案。任何打破 10 个或更多团队的持续记录的人，都更容易在研究期刊上发表文章。
它是 NP 难的，诀窍是使用元启发式算法，例如禁忌搜索、模拟退火……而不是蛮力或分支定界。
看看我使用Drools Planner（开源，java）的实现。 这是约束，应该很简单地用约束替换它，例如没有人不间断地玩 2 轮。
每个玩家必须至少参加 n - 1 场比赛，其中 n 是玩家人数。所以最少轮数是 2(n - 1) - 1，因为每个玩家都需要休息一场比赛。最小值也受 (n(n-1))/2 总比赛除以球场数量的限制。使用这两者中最小的一个可以为您提供最佳解决方案的长度。然后是想出一个好的较低估计公式（（比赛数+剩余剩余数）/球场）并运行A* search 的问题。
正如 Geoffrey 所说，我认为问题出在 NP Hard，但像 A* 这样的元启发式算法非常适用。
蟒蛇解决方案：
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轮。该列表以相反的顺序显示要在各轮中进行的游戏。（虽然我认为相同的时间表向前和向后。）我会回来解释为什么我有机会。
得到一个球场，五名球员的错误答案。
一些想法，也许是一个解决方案......
将问题扩展到 X 球员和 Y 球场，我认为我们可以有把握地说，当有选择的时候，我们必须选择完成比赛最少的球员，否则我们会冒着最终剩下一名球员的风险，他只能参加每场比赛。另一周，我们之间会有许多空旷的星期。想象一下有 20 名球员和 3 个球场的情况。我们可以看到，在第 1 轮中，玩家 1-6 相遇，然后在第 2 轮中，玩家 7-12 相遇，在第 3 轮中，我们可以重复使用玩家 1-6，留下 13-20 玩家直到稍后。因此，我认为我们的解决方案不能贪婪，必须平衡玩家。
有了这个假设，这是解决方案的第一次尝试：
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 轮中，如果 Court2 上的比赛是 [23]，那么比赛 [46] 可能会在第 6 轮中进行。但是，这并不能保证不会出现类似的问题后一轮。
我正在研究另一种解决方案，但这将不得不等待稍后。
我不知道这是否重要，“5 Players and 2 Courts”示例数据缺少其他三个匹配项：[1,3]、[2,4] 和 [3,5]。根据指示：“每个人都与其他人进行比赛。”