MHB Optimal Seating Arrangement Algorithm for Friendship Graphs

AI Thread Summary
An algorithm for determining an optimal seating arrangement in a directed friendship graph can be structured using an n x n matrix to represent relationship strengths and an m x m matrix for seat adjacency. The output should indicate which visitor occupies each seat, with the algorithm evaluating all possible seating arrangements to maximize overall satisfaction. To enhance efficiency, optimization techniques can be applied to reduce computation time. A clear explanation of the variables and data structures used is essential for understanding the algorithm's functionality. The discussion seeks further clarification on how to implement this algorithm effectively.
happinessuni
Messages
2
Reaction score
0
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.
 

Attachments

  • 2017-04-09 (1).png
    2017-04-09 (1).png
    11.9 KB · Views: 113
  • 2017-04-09 (2).png
    2017-04-09 (2).png
    58.3 KB · Views: 129
Physics news on Phys.org
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?
 
I like Serena said:
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?
 

Similar threads

Replies
2
Views
3K
Replies
1
Views
2K
Replies
13
Views
3K
Replies
2
Views
502K
Back
Top