algorithm - 将连接的盒子放在二维平面上

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 减小时，该算法逐渐变为贪心优化器。您可以多次运行该算法并选择最佳结果。这是一个模拟退火方案。