M
M
MayRiv2015-09-16 13:33:13
Mathematics
MayRiv, 2015-09-16 13:33:13

What is the algorithm for seating players on several tables with the conditions in the description?

There are 25 teams of 4 people each. Players on the same team should not sit at the same table.
There are 10 tables, each seating 10 players.
Each player must play 10 games, and it is desirable that the players play approximately the same number of games with each other (if possible). It is desirable that each player plays at least once with other players (except members of his own team).
There is an old seating on the screen, but it is lousy - a large number of players do not play with each other at all.a28adb01d46a4146b7d266c791c4415f.png

Answer the question

In order to leave comments, you need to log in

1 answer(s)
A
Andrew, 2015-09-16
@OLS

The minimum task is a one-time solution to the problem.
Ideal - the ability to create more and more new seating arrangements for a different number of players and tables. The method of creating seating arrangements is very interesting, I have no idea how to solve this problem correctly, if not randomly form an array, checking whether it fits the restrictions :)

Your conditions give too many restrictions on the final array, so when checking a ready-made random array, it will not suit you with a 99.999% probability. Therefore, either the array must be filled gradually with checking each new cell for all restrictions that have already arisen during its filling and possible rollback back (and very far) if all branches further along the filling turn out to be dead ends. Or, as it seems to me, the genetic filling algorithm should work well on this task - you set a random initial seating and calculate the total penalty for all violations of the conditions (at which you can set very large "protective" penalties for absolutely unacceptable conditions), and then optimize by changing line by line / by columns minimizing the penalty.

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question