网球比赛安排

网球比赛安排 前言

在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系统产生更大的影响。