如何找到最佳的网格位置，以使网络中节点之间的距离最小化？

Question

如果我想在2D网格上显示网络的节点，但同时也想确保任意两个直接连接的节点之间的曼哈顿距离最小（每个单元格最多有一个节点），那么应该使用什么算法？

为了说明问题，我们提供一个基本示例：

一个网络有以下拓扑结构：A -> B -> C

一种网格放置的解决方案是将这3个项列在一起： | A | B | C | 任何相连节点之间的距离都是1个单元格。

假设另一个网络有以下拓扑结构：A -> B -> C -> D -> A 此网络的一种放置解决方案是： | A | B | | D | C | A和B、B和C、C和D以及D和A之间的距离均为1个单元格。B和D、A和C不直接连接，因此它们的距离不影响问题。

最优的排列方式是提供所有直接连接节点之间的最小总距离。

现在，如何对任意网络进行此操作？非常感谢您的帮助。 :)

- Andrew S. Allen

---

你能更精确地说明最优性函数吗？例如，对于一个有10001个连接的图，哪种情况更好：一个网格，其中除了最后一个连接的两个节点之外，所有连接节点之间的距离都为1，而最后一个连接节点之间的距离为1000（距离总和=11000，平方距离总和=1010000），还是一个网格，其中所有连接节点之间的距离都为2（距离总和=20000，平方距离总和=40000）？ - Mshnik

Mshnik，我应该提到未直接连接的节点之间的距离不影响问题。 - Andrew S. Allen

有趣。寻找最小总和应该与寻找最低平均值返回相同的答案（因为给定问题的每个答案大小相同），因此您可能希望选择这个选项。 - Mshnik

Answer 1

一种分治法可能会有所收获。考虑以下算法：

如果图的基数小于10：

1）创建一个3x3的网格。将该部分图的节点放置在网格上，以最小化距离。

2）返回3x3网格

否则

1）将图分成两组节点，对每个递归。每次递归返回一种布局该子集作为网格的最佳方式的图。理想情况下，您会找到此拆分的最小二分，但是该问题是NP-hard，因此可能需要近似？

2）通过创建一个单个网格并将两个递归调用的返回值相邻地放置来合并两个子图。您可以将递归调用的返回值旋转90度而不改变其距离总和，因此有16种（每个4个方向）方法可以将两个网格联合起来。大，但幸运的是恒定的。返回最小化总距离的联合网格。

显然，破坏此算法的因素是跨越子网格的连接。旋转过程只能部分修复这个问题。

如果你知道你的图是平面图，那么可能有一种最优解决方案。否则，对于任何一个出度>4的节点，你都必须选择至少一个邻居放在距离>=2的位置上，这时你可能会陷入近似解决方案中。

另一件需要考虑的事情是如何最优地将<=9个节点放置在3x3的网格中。问题在于，在子网格成本方面，可能有许多同样优秀的方法来放置节点，但你还要确保具有相关出边（从此子问题出去的边）的节点位于网格的同一侧。

- Mshnik