MHB Optimal Seating Arrangement Algorithm for Friendship Graphs

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: 111
  • 2017-04-09 (2).png
    2017-04-09 (2).png
    58.3 KB · Views: 127
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?
 
Hi all, I've been a roulette player for more than 10 years (although I took time off here and there) and it's only now that I'm trying to understand the physics of the game. Basically my strategy in roulette is to divide the wheel roughly into two halves (let's call them A and B). My theory is that in roulette there will invariably be variance. In other words, if A comes up 5 times in a row, B will be due to come up soon. However I have been proven wrong many times, and I have seen some...
Thread 'Detail of Diagonalization Lemma'
The following is more or less taken from page 6 of C. Smorynski's "Self-Reference and Modal Logic". (Springer, 1985) (I couldn't get raised brackets to indicate codification (Gödel numbering), so I use a box. The overline is assigning a name. The detail I would like clarification on is in the second step in the last line, where we have an m-overlined, and we substitute the expression for m. Are we saying that the name of a coded term is the same as the coded term? Thanks in advance.

Similar threads

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