平面上的最密堆积点？

Question

假设我有一张带有每条边距离信息的完全无向图G。其中边（u，v）长度为l，意思是“点u和v之间的最小距离为l”。我的目标是在平面上摆放这个图的节点，以便不违反任何这些距离限制，并且凸包的总面积最小。例如，假设我有一堆电子元件要放到芯片上，每个元件都会产生一定量的电磁干扰。如果我把元件放得太近，它们会开始互相干扰，使整个系统无法使用。给定每个点之间应该保持的最小距离，最节省空间的方法是如何将元件放在芯片上？

我甚至不知道如何开始思考这个问题。我也不知道如何将问题推广到更高维度的情况（将点打包到超平面中）。是否有人知道解决这个问题的好方法？

- templatetypedef

---

你想查找图形绘制。在这种情况下，强制定向技术可能会给你一个很好的结果。 - novalis

@novalis- 我知道这些技术，但据我所知，没有证明它们能提供最优解（甚至接近最优解）。我正在寻找一种算法，它可以在可预测的因素范围内接近最优解。 - templatetypedef

与其计算凸包的面积（根据Chris Hopman的回答），您可能更想要最小化类似于纵横比和重心到最远点半径的乘积之类的东西。我假设这对于有意义的图形来说是完全密集的——您没有可以在同一位置“堆叠”的组件？ - Phil Miller

问题的边缘长度必须满足一些约束条件才能有解。这些边缘必须满足一堆不等式。也许只检查三角形不等式就可以，但可能不够。 - Alexandre C.

@Alexnandre C. - 这些不等式有必要吗？例如，打破三角不等式似乎应该没问题，因为任何解决方案仍然必须遵守三角形的最长边。 - templatetypedef

Answer 1

我有一个最优解，但你可能不会喜欢它 :).

让我们将节点标记为x₀, x₁, ..., x_n。令B = max_{i,j < n}(dist(x_i, x_j))，其中dist(x_i, x_j)是x_i和x_j之间的最小距离。对于每个i，将节点x_i放置在位置(0, i*B)。现在每个节点都至少与其他节点相隔B，而凸包的面积为0。

这里真正的关键在于仅最小化凸包的面积将给出一个荒谬的解。一个可能更好的度量标准是凸包的直径。

- Chris Hopman

---

这是一个非常好的观点。如果您设置问题以使用直径，您有什么想法吗？您似乎是一个主要的算法专家，我很想听听您对这个问题的看法。 - templatetypedef

Answer 2

我猜想找到最优算法可能会很困难。如果证明它是NP-hard问题，我不会感到惊讶。但是，如果你对一种产生合理解的实用算法感兴趣，我建议你看一下基于力导向图绘制算法。

以下是该算法的普遍思路（需要使用一些高等数学）。它适用于任意数量的维度。

构建一个函数f，为每个节点布局分配一个值-这是您想要最小化的值。在您的案例中，该函数可以计算给定布局的凸包面积+未满足每个约束条件的大罚款。或者它可能是一个较简单的函数g，其合理地近似前者：简而言之，我们希望g在f变小时变小，并且反之亦然。选择相对简单的函数是好的，因为您需要计算其关于节点坐标的偏导数。

现在假设你有100个节点，想要将它们布局在三维空间中。这意味着你有300个未知数（每个节点有3个坐标，因此100个节点共有300个坐标）。函数f是从R³⁰⁰到R的函数，理想情况下，我们希望找到它的全局最小值。更现实的是，一个足够深的局部最小值就足够了。

有许多已知的数值算法可以找到这样的最小值，例如：共轭梯度法，BFGS。好消息是，你不需要详细了解它们，这些算法已经在许多语言中实现了。你所需要做的就是提供一种计算任何由算法请求的x的f(x)和f'(x)的方法，以及一个初始布局x₀。

- Bolo

---

我其实想过一段时间做这件事，但是没有任何保证所得到的图形近似最优的事实总是使我失去兴趣。 - templatetypedef

为了实际应用，您可以使用不同（随机）的初始布局多次运行算法，并且最佳结果应该令人满意。当然，仍然不能保证您接近最优解。从理论角度来看，这是一个非常有趣的问题！ - Bolo

Answer 3

这段文字的英译如下：

这是一个带有额外约束条件的二维 装箱问题（NP难问题）。我听说模拟退火在电路/芯片设计中表现得非常好。

实际上，我正在寻找一个大型装箱问题的真实世界测试数据，以供Drools Planner使用。

- Geoffrey De Smet

---

模拟退火算法确实非常适用于这类问题。寻找在网格化域中放置点的位置（带有约束条件：三角形必须“肥胖”，其直径必须按照域上的某些密度分布）看起来非常相似，可以用SA解决。 - Alexandre C.

我不确定我理解了...你是说这个问题通过从2D装箱问题进行约简而成为NP难问题？如果是这样，你如何证明它呢？如果不是，那么仅仅说你可以使用装箱来解决这个问题并不能说明它的复杂度。 - templatetypedef

@templatetypedef 说得好。由于我没有所有的约束条件，所以我不能断言它“绝对是NP难问题”。而且，即使我有所有的约束条件，证明某个问题是NP难问题也很困难 :) 不过，我仍然认为它很可能是NP难问题。 - Geoffrey De Smet