将连接的盒子放置在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减小时，该算法逐渐变成贪婪的优化器。您可以运行该算法的多次运行并选择最佳结果。这是一个模拟退火方案。