网球比赛安排

Question

球员人数有限，网球场数量也有限。在每个回合中，最多只能有场比赛。没有人不间断地进行两轮比赛。每个人都与其他人比赛。产生需要尽可能少的回合的时间表。（由于每个人的回合之间都必须休息的规则，因此可能会有不比赛的回合。）5个球员和2个球场的输出可能是：

 |  1   2   3   4   5
-|------------------- 
2|  1   - 
3|  5   3   - 
4|  7   9   1   - 
5|  3   7   9   5   -

在此输出中，列和行是玩家编号，矩阵内的数字是这两个玩家竞争的轮数。

问题是找到一种算法，可以在可行的时间内对较大的实例执行此操作。我们要求在Prolog中执行此操作，但是任何语言的（伪）代码都将很有用。

我的第一个尝试是贪婪算法，但结果却带来了太多回合。然后，我提出了一个迭代的加深深度优先搜索，我的一个朋友实施了该搜索，但是在小到7个玩家的实例上仍然花费了太多时间。

（这是来自一个古老的考试问题。我没有与之交谈的人有任何解决方案。）

Answer 1

在Prolog中， CLP（FD）约束 是解决此类计划任务的正确选择。

有关更多信息，请参见 clpfd 。

在这种情况下，我建议使用强大的global_cardinality/2约束条件来限制每个回合的 发生次数
，具体取决于可用法院的数目。我们可以使用 迭代加深 来找到允许的回合的最小数量。

免费提供的Prolog系统足以令人满意地解决该任务。商业级系统的运行速度将提高数十倍。

方案1：使用SWI-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-

方案2：使用SICStus Prolog解决方案

使用以下用于兼容性的其他定义， 同一 程序也可以在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系统产生更大的影响。