Geek Answers Handbook

Optimize 3D room placement?

The indicated graph is where the nodes represent 3x3x1 rooms, and the vertices represent the need for proximity. How to place them in a 3D space to optimize overall proximity?

Example (randomized) data structure:

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

(I'm not quite sure where I should ask this question, since it is different from most that I see on stackoverflow. I'm interested in programming solutions / heuristic algorithms.)

+4
source share
2 answers

I guess you want adjacency.

In the backtracking search, maintain a queue of rooms ordered by the number of other rooms to which they are connected on the chart (the most limited heuristic variable). Then for each room in the queue:

  • determine the possible grid positions that he can choose, and select one of them;
  • in a loop, determine if there are any other rooms that can now only be in one place, put them there and remove them from the queue ( check ahead );
  • If any of the previous steps failed, return to the last selection point (discard the changes in the grid).
+2
source

It smells like a cousin 3D bottle packaging problem , which is NP-complete. Try construction heuristics (first, customize, best reduce, ...), and then meta-heuristics (search in Tabu, simulated annealing, genetic algorithms, ...). There is open source software for this , such as Drools Planner , openTS, jgap, ...

+2
source

More articles:


All Articles