algorithm - 优化房间的 3D 布局？

Question

给定一个图，其中节点表示 3x3x1 房间，顶点表示需要接近。应该如何将它们放置在 3D 空间中以优化整体紧密度？

示例（随机）数据结构：

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

（我不确定我应该在哪里问这个问题，因为它与我在 stackoverflow 上看到的大多数问题不同。我对编程解决方案/启发式算法感兴趣。）

score 2 · Accepted Answer

闻起来像 3D装箱问题的远亲，这是 NP 完全问题。尝试构建启发式（第一次拟合，最佳拟合递减，...），然后是元启发式（禁忌搜索，模拟退火，遗传算法，...）。那里有开源软件，例如Drools Planner、openTS、jgap、...

score 2 · Accepted Answer

我假设你想要邻接。

在回溯搜索中，维护一个房间队列，按图中连接的其他房间数量排序（最受约束的变量启发式）。然后，对于队列中的每个房间：

2 回答 2