球员人数有限，网球场数量也有限。在每个回合中，最多只能有场比赛。没有人不间断地进行两轮比赛。每个人都与其他人比赛。产生需要尽可能少的回合的时间表。（由于每个人的回合之间都必须休息的规则，因此可能会有不比赛的回合。）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约束条件来限制每个回合的 发生次数 ，具体取决于可用法院的数目。我们可以使用 迭代加深 来找到允许的回合的最小数量。
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分钟的时间内解决了好问题：
？-time（网球（6，2，行））， 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.977秒内获得0.970 CPU（99％CPU，6884940 Lips） -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名球员：
？-time（网球（7，5，行））， maplist（format（“（t〜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推论，18.208秒内17.476 CPU（96％CPU，7185927 Lips） -1 3 5 7 9 11 1-5 3 11 13 9 3 5-9 1 7 13 5 3 9-13 13 7 7 11 1 13-5 3 9 13 7 11 5-1 11 9 13 7 3 1-
使用以下用于兼容性的其他定义， 同一 程序也可以在SICStus Prolog中运行：
：-use_module（library（lists））。 ：-use_module（library（between））。 ：-op（700，xfx，ins）。 Vs ins D：-maplist（in_（D），Vs）。 in_（D，V）：-D中的V。 链（[]，_）。 链（[L | Ls]，Pred）：- chain_（Ls，L，Pred）。 chain _（[]，_，_）。 chain _（[L | Ls]，Prev，Pred）：- 呼叫（Pred，Prev，L）， chain_（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是带有严重CLP（FD）系统的商业级Prolog，在此用例及其他类似情况下，其 速度 比SWI-Prolog 快得多 。
指定的任务，在2个场上有6名球员：
？-time（网球（6，2，行））， 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-
较大的示例：
| ？-time（网球（7，5，行））， maplist（format（“（t〜t〜w〜3 +〜t〜w〜3 +〜t〜w〜3 +〜t〜w〜3 +〜t〜w〜3 +〜t〜w〜3 +〜t〜 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 13 9 7 9 11 13-3 1 9 7 13 11 3-5 11 13 7 9 1 5-
在这两个系统中，global_cardinality/3您都可以指定选项来更改全局基数约束的传播强度，从而启用较弱且可能更有效的过滤。为特定示例选择正确的选项可能会比选择Prolog系统产生更大的影响。
global_cardinality/3
