1

I am trying to design an algorithm to optimally arrange students around a classroom in defined seats.

For each possible pair of students, I have calculated a compatibility score. Desks are not necessarily arranged uniformly, so the geometric distance between them can vary.

I think the optimum outcome is one with the highest sum for the ratio of compatibility to distance for each possible pair.

Any ideas where I should start? I was thinking about selecting the student with the highest average compatibility, putting them in the middle of the room, then assigning students around them. I could possibly produce a number of possible arrangements and solve to find the 'best'.

Thank you

P. S. I am mathematically-literate (a degree in engineering and numerate careers ever since), but it's a while since I did any pure maths, so please have patience if I don't understand you right away.

Rob
  • 11
  • Some machine learning (e.g. evolutionary algorithm) is always an option. – freakish Oct 06 '19 at 16:38
  • You might consider introducing a distance cutoff, it doesn't really matter whether two students are 10 or 20 seats apart. Also you might want to start by putting the least compatible students in the corners and around the edges. – WW1 Oct 06 '19 at 17:04
  • Thank you both. @WW1 that sounds like a more sensible idea than starting from the middle (and actually close to what I'd been doing with an earlier, much more basic, version of this).

    This may also be a good excuse for me to dip my toes into machine learning...

     – Rob Oct 06 '19 at 17:14

1 Answers1

0

Sounds like the quadratic assignment problem.

RobPratt
  • 45,619