假设我有一个完整的无向图G，每条边都有一段距离。具有长度l的边（u，v）的含义是“点u和v不可能比l更接近彼此”。我的目标是将这个图的节点放在一个平面上，这样就不会违反这些距离约束，并且这些点的凸包的总面积最小。举个例子，假设我有一堆电子元件要放在芯片上，每个元件都会产生一定数量的电干扰。如果我把组件放得太近，他们会开始互相干扰，导致整个系统无用。考虑到每个点应该距离每个点最小距离，将这些元件放在芯片上的最节省空间的方式是什么？飞机上的密集点？
我不知道如何开始思考这个问题。我也不知道这个问题可能会如何推广到更高维的情况（包装点进入超平面）。有谁知道解决这个问题的好方法吗？
我有一个最佳的解决方案，但你不会喜欢它:)。
让我们的标签我们的节点X ，X ，...，X ñ。令B =最大 I，J <Ñ（DIST（X 我，X Ĵ）），其中DIST（X 我，X Ĵ）是x 我和X之间的最小距离 j。对于每个i，将节点x i放置在位置（0，i * B）处。现在每个节点至少与所有其他节点相距B，并且凸包的面积为0.
这里的真正意义在于，最小化单独凸包的面积会给您一个无意义的解决方案。一个可能更好的措施是凸包的直径。
我猜这将很难找到最佳算法。如果事实证明这是一个NP难题，我不会感到惊讶。但是，如果您对能够提供体面解决方案的实用算法感兴趣，我建议您查看force-based graph drawing algorithms。
这里是一般的想法（一些更高的数学将出现）。它推广到任何数量的维度。
构造一个函数f，它为每个节点布局分配一个值 - 一个您想要最小化的值。在你的情况下，函数可以计算给定布局的凸包的面积+对于没有满足的每个约束的大惩罚。或者它可以是一个更简单的函数g，它合理地近似于前者：简而言之，当f变小时，我们希望g变小，反之亦然。选择一个相对简单的函数是很好的，因为你需要计算它的偏导数（关于节点的坐标）。
现在让我们假设您有100个节点，并且您希望将它们放在3D中。这意味着您有300个未知数（每个节点的100个节点乘以3个坐标）。功能f是从R到R的函数，理想情况下我们希望找到它是全局最小值。更现实的说，足够深的当地最低限度就足够了。
存在众所周知的用于找到这样的最小值的数值算法，例如：Conjugate gradient,BFGS。好的是，你并不需要详细了解它们，这些算法在很多语言中都可以实现。你所要做的就是提供一个计算f(x)和f'(x)的方法，该算法对算法请求的任何x以及初始布局x₀。
这是2D bin packing problem（这是NP难）与额外的限制。我听说模拟退火表现非常好，电路/芯片设计。
我实际上是looking for real-world test-data of a big bin packing problem对于Drools Planner。
你想查找图形绘制。在这种情况下，强制导向的技术可以给你一个很好的结果。 – novalis 2011-01-24 21:54:14
@ novalis-我意识到这些技术，但据我所知，没有任何证据表明这些技术可以提供最佳解决方案（甚至任何接近最佳解决方案的解决方案）。我正在寻找一个算法，这个算法可以在一些可预测的最优化因子内。 – templatetypedef 2011-01-24 21:59:07
而不是凸包的面积（每克里斯·霍普曼的答案），你可能想要最小化类似长宽比和从质心到最远点的半径的乘积。我假设这是有意义的，你的图形是完全密集的 - 你没有可以在相同位置堆叠的组件？ – Novelocrat 2011-01-25 05:09:00