6
$\begingroup$

Problem is as following:

We are 8 trumpet players in an orchestra.

There are for example 4 parts so there are always two players on the same part.

Now, there are not always the same two players playing the same part meaning the combination of players that play the same part change from piece to piece.

What is the cheapest way in terms of distance and/or the least amount of switches resulting that the players playing the same parts can sit next to each other on every piece?


Trumpet Players: a,b,c,d,e,f,g,h

Parts: 1,2,3,4

Seats are arranged like that:

1st piece
| a1 | b1 | c2 | d2 |

| e3 | f3 | g4 | h4 |

Next piece the players might play the following parts:
| a2 | b1 | c3 | d1 |

| e3 | f4 | g2 | h4 |

and the next one againt different distribution of the parts:
| a4 | b3 | c1 | d3 |

| e2 | f4 | g2 | h1 |

how do we seat the players so that the least amount has to be traveled in order to reach the desired positions for the players playing the same parts to sit next to each other in the next piece?

additional notes: i dont care where the pairs are starting and if a1 sits left of b1 or the other way around.

$\endgroup$
  • $\begingroup$ "We are 8 trumpet players in an orchestra" Do you imply you could have, say, 20 or even 100 of players? I am just checking if exhaustive search could work. $\endgroup$ – Apass.Jack Feb 1 at 6:15
  • $\begingroup$ In this case it would probably never exceed 12 or so. But if the algorithm was scaleable like that it would be great. $\endgroup$ – jteichert Feb 1 at 8:04
  • $\begingroup$ how would I solve this with exhaustive search? Build a decision tree? $\endgroup$ – jteichert Feb 3 at 11:21
  • 1
    $\begingroup$ how many pieces are there? If there are more than 5, an exhaustive search for even for 8 trumpet players is unlikely to finish before the next performance as there are about $2*7!*(8!)^5\approx 1.0*10^{27}$ situations. $\endgroup$ – Apass.Jack Feb 4 at 13:26
  • $\begingroup$ How do you want to measure the distance between the seating for one piece and the seating for the next piece? You mention "the number of switches"; are you assuming that a pair of players can switch seats, and you want to know the number of switches needed, and to get from one seating to another you'll restrict things to some sequence of switches? (continued) $\endgroup$ – D.W. Feb 21 at 23:15
0
$\begingroup$

I would suggest using the A* algorithm. The state is where each player is currently seating and the number of pieces you've played so far. Each edge represents a way that you can update the seating. Also, when you're in a state where, for the next piece to be played, everyone is sitting next to their partner on that piece, you can increment the number of pieces played at 0 cost. The start state has 0 pieces played, and the goal state is any state where you've played all the pieces. Then, A* will find the lowest-cost sequence of movements to complete the concern.

You'll need an admissible heuristic to estimate the cost to finish the concert, starting from a particular intermediate state. One very simple heuristic is: count the number of players who will have some future piece to play, where they're not currently sitting next to their partner on that piece, and divide by two. Perhaps a slightly better heuristic is to count, for each player, the number of future partners (for any piece not yet played) who they are not currently sitting next to, and divide by four. Assuming each switch costs one and there is no other way to update the seating, this is admissible, as each switch can only decrease this count by at most four.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.