algorithm - 将连接的盒子放在 2D 平面上

Question

给定 N 个矩形框和它们之间的 M 个连接，我想有效地将​​它们放置在一个平面上，以使所有连接的总长度保持最小。

我唯一的完整过程是将平面拆分为具有 N 个或更多空间的网格，并将具有最大连接数的框放置在网格中，从对角相对的角落空间开始。

当一个盒子连接到所有 N-1 个盒子并且这些是唯一的连接时，这可能效率不高。我们期望中心的一个盒子和它周围的所有其他盒子。

这样的问题有标准的解决方案吗？我能否获得有关如何解决此类问题的指示？

Answer 1

这是一个非线性优化问题，例如可以使用模拟退火或一般目标函数最小化（如梯度下降法）来解决。

给定盒子的任何布局，让 L 表示给定布局的所有连接的长度之和。你想最小化 L。一个简单的模拟退火方案是这样工作的：

layout = random_layout()
t = 1.0
While(true)
  L = sum_of_lengths(layout)
  layout' = move_one_box(layout)
  L' = sum_of_lengths(layout)
  if (L' < L  or  random(0..1) < t)
    layout = layout'
  t = t * 0.999

最初，该算法只是随机移动框，但是当 t 减小时，该算法逐渐变为贪婪优化器。您可以运行多次算法并选择最佳结果。这是一个模拟退火方案。