Algorithm for seating people with most shared hobbies

My data is of people and hobbies, with a many-to-many relationship. Each person has at least one hobby.

I need to find a way to seat all of the people around N seat tables, in such a way that there is a maximum number of shared hobbies between the people in each table. It is not required that each table has at least one shared hobby between all of the people seated around it. Also, 开发者_如何学JAVAtables do not necessarily have to be completely filled.

Any ideas would be much appreciated.

---

First of all, this is an NP-hard problem - for instance, any algorithm that can solve your problem, can solve the Longest Path problem of a weighted graph as follows:

• Each graph vertex is a person
• Any edge of the graph can be encoded by creating a new hobby, shared by only the two vertices/persons of the edge

(There might be a simpler reduction to an NP-complete problem, but I guess this will do).

Skiena would suggest Simulated Annealing, start with any arrangement, and make random choices. The trick is progressively lowering the probability that you accept a worsening change (thus, at the start you allow it some liberty to avoid local optima, but progressively it "cools off" and stabilizes at some area and make small refinements). You can also run it multiple times and keep the best solution.

You can probably hand-code something less sophisticated in the same spirit. I guess your problem instances are going to be small, so you are bound to find good solutions if you try to many of them (and try to randomly refine them).

Of course, if your problems are very small, you could just enumerate all permutations and find the best arrangement. (If you have n people, make sure you fix the position of someone and only generate the permutations for n - 1 people).