Tennis Schedule

Question

There is a limited number of players and a limited number of tennis courts. On each round there can be no more such matches as there are courts. No one plays 2 rounds without a break. Everyone plays a match against everyone else. Create a schedule that will take as few rounds as possible. (Due to the rule that there should be a gap between the rounds for everyone, there may be a round without matches.) The result for 5 players and 2 vessels can 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 numbers of the players, and the numbers inside the matrix are the round numbers these two players compete with.

The problem is to find an algorithm that can do this for large instances in a reasonable amount of time. We were asked to do this in Prolog, but (pseudo) code in any language would be helpful.

My first attempt was a greedy algorithm, but it gives results with too many rounds. Then I suggested an iterative in-depth search for depth of depth, which was implemented by my friend, but it took too much time on instances of up to 7 players.

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

Answer 1

Introduction

In Prolog, CLP (FD) constraints are the right choice for such planning tasks.

See clpfd for more information.

In this case, I suggest using the powerful global_cardinality/2 restriction to limit the number of entries of each depending on the number of vessels available. We can use an iterative recess to find the minimum number of allowable rounds.

The freely available Prolog systems are sufficient to solve the problem satisfactorily. Commercial systems will work ten times faster.

Option 1: 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. 

Example request: 5 players on two ships:

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

The specified problem, 6 players on 2 ships , is well solved within 1 minute:

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

Further example: 7 players on 5 ships:

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

Option 2: Solution with SICStus Prolog

With the following additional compatibility definitions, the same program also runs in 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]).

The main difference: SICStus, which is a commercial Prolog that comes with a serious CLP (FD) system, is much faster than SWI-Prolog in this case and others like it.

The specified task, 6 players on 2 ships:

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

Example:

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

Concluding observations

In both systems, global_cardinality/3 allows you to specify parameters that change the propagation power of the global power constraint, which allows weaker and potentially more efficient filtering. Choosing the right options for a particular example can have even greater effect than choosing a Prolog system.

Answer 2

This is very similar to the Traveling Tournament Challenge , which concerns the planning of football teams. In TTP, they can find the optimal solution for up to 8 teams. Anyone who violates the current record of 10 or more teams is much easier to publish in a research journal.

This NP is difficult, and the trick is to use metaheuristics such as taboo search, simulated annealing ... instead of brute force or branch and anchor.

Check out my implementation with Drools Planner (open source, java). Here are the restrictions , it should just be replaced by restrictions such as no one playing 2 rounds without a break.

Answer 3

Each player must play a minimum of n - 1 matches, where n is the number of players. Thus, the minimum rounds is 2 (n - 1) - 1, since each player needs to play a match. The minimum is also related to (n (n-1)) / 2 totals divided by the number of vessels. Using the smallest of these two gives you the length of the optimal solution. Then we are talking about a formula with a lower scoring formula (number of matches + residues) / courts) and do A * search .

As Jeffrey said, I believe the problem is NP Hard, but metaheuristics such as A * are very applicable.

Answer 4

Python solution:

 import itertools def subsets(items, count = None): if count is None: count = len(items) for idx in range(count + 1): for group in itertools.combinations(items, idx): yield frozenset(group) def to_players(games): return [game[0] for game in games] + [game[1] for game in games] def rounds(games, court_count): for round in subsets(games, court_count): players = to_players(round) if len(set(players)) == len(players): yield round def is_canonical(player_count, games_played): played = [0] * player_count for players in games_played: for player in players: played[player] += 1 return sorted(played) == played def solve(court_count, player_count): courts = range(court_count) players = range(player_count) games = list( itertools.combinations(players, 2) ) possible_rounds = list( rounds(games, court_count) ) rounds_last = {} rounds_all = {} choices_last = {} choices_all = {} def update(target, choices, name, value, choice): try: current = target[name] except KeyError: target[name] = value choices[name] = choice else: if current > value: target[name] = value choices[name] = choice def solution(games_played, players, score, choice, last_players): games_played = frozenset(games_played) players = frozenset(players) choice = (choice, last_players) update(rounds_last.setdefault(games_played, {}), choices_last.setdefault(games_played, {}), players, score, choice) update(rounds_all, choices_all, games_played, score, choice) solution( [], [], 0, None, None) for games_played in subsets(games): if is_canonical(player_count, games_played): try: best = rounds_all[games_played] except KeyError: pass else: for next_round in possible_rounds: next_games_played = games_played.union(next_round) solution( next_games_played, to_players(next_round), best + 2, next_round, []) for last_players, score in rounds_last[games_played].items(): for next_round in possible_rounds: if not last_players.intersection( to_players(next_round) ): next_games_played = games_played.union(next_round) solution( next_games_played, to_players(next_round), score + 1, next_round, last_players) all_games = frozenset(games) print rounds_all[ all_games ] round, prev = choices_all[ frozenset(games) ] while all_games: print "X ", list(round) all_games = all_games - round if not all_games: break round, prev = choices_last[all_games][ frozenset(prev) ] solve(2, 6) 

Output:

 11 X [(1, 2), (0, 3)] X [(4, 5)] X [(1, 3), (0, 2)] X [] X [(0, 5), (1, 4)] X [(2, 3)] X [(1, 5), (0, 4)] X [] X [(2, 5), (3, 4)] X [(0, 1)] X [(2, 4), (3, 5)] 

This means that it will take 11 rounds. The list shows the games that will be played in rounds in reverse order. (Although I think the same schedule works back and forth). I will come back and explain why I have a chance.

Received incorrect answers for one trial, five players.

Answer 5

Some thoughts, maybe a solution ...

Having developed the problem for the players of the X and Y ships, I think we can say with confidence that when you give a choice, we must choose the players with the least number of completed matches, otherwise we risk being with one player on the left who can play every week, and in the end we get many empty weeks. Imagine an example with 20 players and three ships. We see that during round 1, players 1-6 meet, then in round 2 players 7-12 meet, and in the third round we can reuse players 1-6, leaving players 13 to 20 later. Therefore, I believe that our decision cannot be greedy and balance the players.

Under this assumption, here is the first attempt at a solution:

  1. Create master-list of all matches ([12][13][14][15][16][23][24]...[45][56].) 2. While (master-list > 0) { 3. Create sub-list containing only eligible players (eliminate all players who played the previous round.) 4. While (available-courts > 0) { 5. Select match from sub-list where player1.games_remaining plus player2.games_remaining is maximized. 6. Place selected match in next available court, and 7. decrement available-courts. 8. Remove selected match from master-list. 9. Remove all matches that contain either player1 or player2 from sub-list. 10. } Next available-court 11. Print schedule for ++Round. 12. } Next master-list 

I can’t prove that this will lead to the schedule with the least number of rounds, but it should be close. The step that can cause problems is # 5 (choose a match that maximizes the remaining games of the players). I can imagine that there may be times when it’s better to choose a match that almost maximizes games_remaining to leave more options in the next round.

The result of this algorithm will look something like this:

 Round Court1 Court2 1 [12] [34] 2 [56] -- 3 [13] [24] 4 -- -- 5 [15] [26] 6 -- -- 7 [35] [46] . . . 

A closed check will show that in round 5, if the match at Court2 was [23], then match [46] could be played during round 6. This, however, does not guarantee that there will not be a similar problem in the later round.

I am working on another solution, but this will have to wait later.

Answer 6

I don’t know if it matters, in the examples of the data “5 players and 2 ships” there are no three other matches: [1,3], [2,4] and [3,5]. Based on the instructions: "Everyone plays a match against everyone else."