最小化顶点距离的算法 - Dwarf Fortress

Question

我玩Dwarf Fortress游戏。对我来说主要的挑战是有效地设计堡垒的布局。这意味着，每个行业流应尽可能密集，以尽量减少行进距离。

食品行业就是一个例子 .每个灰色椭圆代表一座建筑物。每个白色矩形代表来自建筑物的产品。

我的目标是找到一种算法，该算法可以将建筑物分布在 2D 网格上，使这些建筑物之间的距离从它们的连接方式来看是最小的。这意味着 fishery 和 loom 可以相距很远，但 loom 和 farmer's 应该尽可能靠近。

目前我考虑过使用一些现成的软件来模拟布局，但是一些算法提示就可以了。

目前我正在考虑一些力导向算法，但我不确定离散网格要求。

问题的形式化:是否存在适用于离散坐标的 Force Draw Graph 算法？

更新:我找到了 Force draw algorithm 的实现在 AS3 中(网络也包含 JS 版本)。我将尝试将其转换为离散版本。但我怀疑它是否会起作用...

更新 2:评论中要求进行一些进一步的限制。他们来了:每栋建筑占据虚拟网格上的单个单元格。建筑物可以位于相邻的单元格上。建筑物不能堆叠/重叠。(PS:在游戏中，每个建筑都有固定的尺寸，通常是 3x3，但我想让问题更笼统，以允许更多的方法)。

Answer 1

您几乎是在尝试解决平面规划问题的一个实例，在该实例中您试图最小化总“连接”长度。大多数这些问题都是 NP-hard 问题的实例，其中一些具有伪多项式运行时算法。

您可能感兴趣的一种特殊情况实际上可以在多项式时间内完全解决:如果您要放置的“盒子”或建筑物的相对位置提前已知。

有关如何解决此特殊情况的完整详细信息，请参阅 tutorial斯坦福几何编程，第 6 章，第 6.1 节，第一个示例，标题为“Floor planning”。另一个website还包括实现和解决问题的 matlab 代码(在第 8 章几何规划下。)