网球比赛安排

Question

球员数量有限,网球场数量有限.在每轮比赛中,最多可以有比赛更多的比赛.没有休息,没有人打2轮.每个人都与其他人比赛.制定尽可能少轮次的计划.(由于每个人的轮次之间必须休息的规则,可以有一轮没有比赛.)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(tennis(6, 2, Rows)),
   maplist(format("~t~w~3+~t~w~3+~t~w~3+~t~w~3+~t~w~3+~t~w~3+\n"), Rows).
% 6,675,665 inferences, 0.970 CPU in 0.977 seconds (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(tennis(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"), Rows).
% 125,581,090 inferences, 17.476 CPU in 18.208 seconds (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 11  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) :- V in D.

chain([], _).
chain([L|Ls], Pred) :-
        chain_(Ls, L, Pred).

chain_([], _, _).
chain_([L|Ls], Prev, Pred) :-
        call(Pred, Prev, L),
        chain_(Ls, L, Pred).

pairs_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) :-
        call(Pred, L1, L2, L3, S0, S1),
        foldl_(Ls1, Ls2, Ls3, Pred, S1, S).

time(Goal) :-
        statistics(runtime, [T0|_]),
        call(Goal),
        statistics(runtime, [T1|_]),
        T #= T1 - T0,
        format("% Runtime: ~Dms\n", [T]).

主要区别:SICStus是一款商用级Prolog,配有严格的CLP(FD)系统,在此用例和其他类似用户中比SWI-Prolog 快得多.

指定的任务,2个球场上的6名球员:

?-   time(tennis(6, 2, Rows)),
     maplist(format("~t~w~3+~t~w~3+~t~w~3+~t~w~3+~t~w~3+~t~w~3+\n"), Rows).
% Runtime: 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  -

更大的例子:

| ?- time(tennis(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"), Rows).
% Runtime: 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允许您指定用于更改全局基数约束的传播强度的选项,从而实现更弱且可能更有效的过滤.为特定示例选择正确的选项可能比选择Prolog系统产生更大的影响.

Answer 2

这与旅行锦标赛问题非常相似,这是关于安排足球队的问题.在TTP中,他们可以找到最多只有8个团队的最佳解决方案.任何打破10个或更多团队持续记录的人,都可以更容易地在研究期刊上发表.

这是NP很难,诀窍是使用元启发式,如禁忌搜索,模拟退火,...而不是暴力或分支和绑定.

看看我的实现与Drools Planner(开源,java). 以下是约束条件,应该可以直接用限制条件替换它,例如Nobody可以不间断地玩2轮.

Answer 3

每位玩家必须至少玩n - 1场比赛,其中n是球员的数量.所以最小轮数是2(n - 1) - 1,因为每个球员都需要休息一场比赛.最低限度也受(n(n-1))/ 2总匹配除以法院数量的约束.使用这两者中最小的一个可以得到最优解的长度.然后,这是一个提出一个良好的较低估计公式((匹配数+剩余的休息数)/法院)并运行A*搜索的问题.

正如Geoffrey所说,我认为问题是NP Hard,但是像A*这样的元启发式算法非常适用.