网球比赛安排
数量有限的球员和数量有限的网球场。 每场比赛最多可以有多less场比赛。 没有人rest2轮。 每个人都和其他人玩。 产生尽可能less的轮次的时间表。 （因为每个人之间必须有轮休的规则，所以可以有一轮没有比赛。）5个球员和2个球场的输出可以是：
| 1 2 3 4 5 -|------------------- 2| 1 - 3| 5 3 - 4| 7 9 1 - 5| 3 7 9 5 - 在这个输出中，列和行是玩家号码，matrix内的数字是这两个玩家竞争的轮数。
问题是find一个algorithm，可以在一个可行的时间更大的情况下做到这一点。 我们被要求在Prolog中这样做，但任何语言的（伪）代码都是有用的。
我的第一个尝试是一个贪婪的algorithm，但是结果太多了。 然后我提出了一个迭代深化的深度优先search，这是我的一个朋友实现的，但是对于7个玩家来说，这个search仍然花费了太多的时间。
（这是从一个旧的考试题目，我没有任何解决scheme。）
前言
在Prolog中， CLP（FD）约束是解决这种调度任务的正确select。
有关更多信息，请参阅clpfd 。
在这种情况下，我build议使用强大的global_cardinality/2约束来限制每轮的发生次数 ，具体取决于可用法院的数量。 我们可以使用迭代加深来find最小允许轮次数。
自由可用的Prolog系统足以令人满意地解决任务。 商业级系统的运行速度要快几十倍。
变体1：使用SWI-Prolog的解决scheme
:- 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，行）），
MAPLIST（格式（ “〜T〜W〜3 +〜T〜W〜3 +〜T〜W〜3 +〜T〜W〜3 +〜T〜W〜3 +〜T〜W〜3 + \ n” 个），行）。
％6,675,665推论，在0.977秒0.970 CPU（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，行）），
MAPLIST（格式（“〜T〜W〜3 +〜T〜W〜3 +〜T〜W〜3 +〜T〜W〜3 +〜T〜W〜3 +〜T〜W〜3 +〜吨〜 w〜3 + \ n“），行）。
％125,581,090推断，18.208秒17.476 CPU（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 -
变体2：使用SICStus Prolog的解决scheme
有了以下附加的兼容性定义， 相同的程序也可以在SICStus Prolog中运行：
： - use_module（库（列表））。
： - use_module（库（之间））。
： - op（700，xfx，ins）。
Vs ins D： - maplist（in_（D），Vs）。
in_（D，V）： - V in D
链（[]，_）。
链（[L | Ls]，Pred）： -
chain_（Ls，L，Pred）。
链_（[]，_，_）。
链_（[L | Ls]，Prev，Pred）： -
调用（Pred，Prev，L），
chain_（Ls，L，Pred）。
pairs_keys_values（Ps，Ks，Vs）： - keys_and_values（Ps，Ks，Vs）。
（Pred，Ls1，Ls2，Ls3，S0，S）： -
（Ls1，Ls2，Ls3，Pred，S0，S）。
foldl _（[]，[]，[]，_，S，S）。
（[L1 | Ls1]，[L2 | Ls2]，[L3 | Ls3]，Pred，S0，S）： -
调用（Pred，L1，L2，L3，S0，S1），
（Ls1，Ls2，Ls3，Pred，S1，S）。
时间（目标）： -
统计信息（运行时，[T0 | _]），
调用（目标），
统计信息（运行时，[T1 | _]），
T＃= T1-T0，
格式（“％运行时间：〜Dms \ n”，[T]）。
主要区别：SICStus是一个商业级的Prolog，带有一个严重的CLP（FD）系统，比SWI-Prolog在这个用例和其他类似的软件中要快得多 。
指定的任务，2个法院的6名球员：
（网球（6，2，行）），
MAPLIST（格式（ “〜T〜W〜3 +〜T〜W〜3 +〜T〜W〜3 +〜T〜W〜3 +〜T〜W〜3 +〜T〜W〜3 + \ n” 个），行）。
％ 运行时间：34ms（！）
- 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，行）），
MAPLIST（格式（“〜T〜W〜3 +〜T〜W〜3 +〜T〜W〜3 +〜T〜W〜3 +〜T〜W〜3 +〜T〜W〜3 +〜吨〜 w〜3 + \ n“），行）。
％ 运行时间：884ms
- 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允许您指定改变全局基数约束的传播强度的选项，从而实现更弱和更有效的过滤。 为特定示例select正确的选项可能比selectProlog系统的影响更大。
这与旅行锦标赛问题非常相似，这是关于安排足球队的问题 。 在TTP中，他们可以find最多只有8支队伍的最佳解决scheme。 任何人打破10个或更多队伍的持续logging，在研究期刊上发表要容易得多。
NP是困难的，诀窍是使用元启发式，如禁忌search，模拟退火，…而不是暴力或分支和界限。
看看我的 Drools Planner （开源，Java）的实现。 这里是约束条件 ，应该很直接地用诸如没有人没有rest地玩两轮的限制来取代。
每个玩家必须至less玩n – 1场比赛，其中n是玩家人数。 所以最小回合数是2（n – 1） – 1，因为每个玩家都需要rest一下。 最小值也受（n（n-1））/ 2个总比赛数除以法院数的限制。 使用这两个中最小的一个可以给出最佳解决scheme的长度。 那么这是一个很好的较低的估算公式（（比赛数+剩下的）/法院）和运行A *search的问题 。
正如杰弗里所说，我认为这个问题是NP难题，但是元启发式algorithm如A *是非常适用的。
Python解决scheme：
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轮。 该列表以相反顺序显示要在回合中玩的游戏。 （虽然我认为同样的时间表是前向和后向的）我会回来解释我为什么有这个机会。
得到一个法庭，五名球员不正确的答案。
有些想法，也许是解决scheme…
把这个问题扩大到X球员和Y球场，我想我们可以放心地说，在给出select的时候，我们必须select最less完成比赛的球员，否则我们会面临只剩下一名球员的风险另外一个星期，我们结束了许多空的周。 图片与20名球员和3个法院的情况。 我们可以看到，在第一回合中，第一回合select了1-6，然后在第二回合中select了7-12回合，而在第三回合中，我们可以重复使用1-6回到第三回合。 因此，我认为我们的解决scheme不能贪婪，必须平衡球员。
有了这个假设，这是一个解决scheme的第一次尝试：
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
我不能certificate这会产生一个最less的轮次，但它应该是接近的。 可能会导致问题的步骤是＃5（select匹配，最大化玩家的游戏剩余。）我可以想象，可能会有一个情况下，select一个匹配几乎最大化'games_remaining'为了留下更多选项回合。
这个algorithm的输出看起来像这样：
Round Court1 Court2 1 [12] [34] 2 [56] -- 3 [13] [24] 4 -- -- 5 [15] [26] 6 -- -- 7 [35] [46] . . .
仔细检查会发现，在第五轮中，如果第二轮的比赛是[23]，那么在第六轮期间可以打出匹配[46]。然而，这并不保证在第6轮中不会有类似的问题稍后一轮。
我正在研究另一个解决scheme，但是这将不得不等待以后。
我不知道这个问题是否重要，“五位球员和两位球场”的例子中的数据缺less三个其他的比赛：[1,3]，[2,4]和[3,5]。 根据指示：“每个人都和其他人玩。”
