Optimal Seating Arrangement Algorithm for Friendship Graphs

[happinessuni]

Hi all,

I am struggling the question, please see attachments.

Thanks a lot

View attachment 6522View attachment 6523

Devise an algorithm which, given a (directed) friendship graph (in the xkcd format), finds the optimal seating arrangement. Your algorithm should include the following:
 a description of the required input format
 appropriate weightings of the four types of edges in the given friendship graph
 an output (an optimal seating arrangement)
 sufficient explanation of the variables and data structures involved that the marker can tell what they are for.

 

[I like Serena]

Hi happinessuni! Welcome to MHB! (Smile)

Hmm... suppose we have n visitors and m seats.
Then the input could for instance be a nxn matrix with numbers indicating the strength of the relationship.
And combined with a mxm matrix indicating which seats are next to each other.
The output could be m numbers indicating which visitor sits on each seat.
Then the algorithm could try all ways that the visitors could be seated, evaluating how 'well' the seating is, and selecting the one with the most value.
If calculation time is an issue, there are several ways to optimize it... (Thinking)

Any thoughts?

 

[happinessuni]

Hi happinessuni! Welcome to MHB! (Smile)

Hmm... suppose we have n visitors and m seats.
Then the input could for instance be a nxn matrix with numbers indicating the strength of the relationship.
And combined with a mxm matrix indicating which seats are next to each other.
The output could be m numbers indicating which visitor sits on each seat.
Then the algorithm could try all ways that the visitors could be seated, evaluating how 'well' the seating is, and selecting the one with the most value.
If calculation time is an issue, there are several ways to optimize it... (Thinking)

Any thoughts?

Hi, Thanks for reply, I still didn't get the algorithm, could you please show me how to find it?