网球比赛日程安排 [英] Tennis match scheduling

问题描述

有有限数量的玩家和网球场的数量有限。在每一轮中，可以有至多尽可能多的比赛，因为有法院。 没人玩2轮不绝。每个人都扮演了反对其他人的比赛。 产生需要的几个回合尽可能的时间表。 （因为规则有一定回合每个人的休息，也可以是圆不匹配。） 对于5名球员和2场输出可能是：

There are a limited number of players and a limited number of tennis courts. At each round, there can be at most as many matches as there are courts. Nobody plays 2 rounds without a break. Everyone plays a match against everyone else. Produce the schedule that takes as few rounds as possible. (Because of the rule that there must a break between rounds for everyone, there can be a round without matches.) The output for 5 players and 2 courts could be:

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

在此输出的列和行是游戏者的数字，和基质​​内的数字是圆形号码这两个玩家竞争。

In this output the columns and rows are the player-numbers, and the numbers inside the matrix are the round numbers these two players compete.

的问题是要找到一种算法可以在一个可行的时间执行此放大的实例。我们被要求这样做的序言，但（伪）code。在任何一种语言将是有益的。

The problem is to find an algorithm which can do this for larger instances in a feasible time. We were asked to do this in Prolog, but (pseudo-) code in any language would be useful.

我的第一次尝试是一个贪心算法，但给人太多回合的结果。 然后，我建议一个反复的深入深度优先搜索，其中我的一个朋友来实现，但仍然花了太多时间在实例小到7名球员。

My first try was a greedy algorithm, but that gives results with too many rounds. Then I suggested an iterative deepening depth-first search, which a friend of mine implemented, but that still took too much time on instances as small as 7 players.

（这是一个古老的试题。人无我说话有任何解决方案。）

(This is from an old exam question. No one I spoke to had any solution.)

推荐答案

样品Prolog的解决方案，使用SWI-Prolog的：

Sample Prolog solution, using 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.

示例查询：5名球员在2场：

Sample query: 5 players on 2 courts:

?- 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,-]

指定的任务， 6名球员在2场 1分钟的时间内很好的解决：

The specified task, 6 players on 2 courts, solved well within the time limit of 1 minute:

?- time(tennis(6, 2, Rows)), maplist(writeln, Rows).
% 5,605,107 inferences, 1.775 CPU in 2.137 seconds (83% CPU, 3156941 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,-]

另一个例子：7名球员在5场：

Further example: 7 players on 5 courts:

?- time(tennis(7, 5, Rows)), maplist(writeln, Rows).
% 105,563,012 inferences, 35.757 CPU in 46.680 seconds (77% CPU, 2952225 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,-]

这篇关于网球比赛日程安排的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！