Optimise 3D placement of rooms?

Given a graph where the nodes represent 3x3x1 开发者_开发技巧rooms and the vertices represent a need for closeness. How should they be placed in 3D space to optimise overall closeness?

Example (randomish) datastructure:

{
    room1: [room2, room3],
    room2: [room1, room4],
    room3: [room5],
    room4: [room2, room5, room1],
    room5: []
}

(I'm not exactly sure where I should be asking this question as it's different from most I see on stackoverflow. I am interested in programming solutions/heuristic algorithms.)

I assume you want adjacency.

In a backtracking search, maintain a queue of rooms ordered by how many other rooms they are connected to in the graph (the most constrained variable heuristic). Then, for each room in the queue:

• determine the possible grid positions it can take and pick one of them;
• in a loop, determine whether any other rooms exist which now can only be in one spot, put them there and remove them from the queue (forward checking);
• if any of the previous steps failed, backtrack to the last choice point (undo the changes to the grid).

Smells like a far cousin of a 3D bin packing problem, which is NP-complete. Try construction heuristics (first fit, best fit decreasing, ...) followed by metaheuristics (Tabu search, simulated annealing, genetic algorithms, ...). There is open source software out there for that, such as Drools Planner, openTS, jgap, ...