javascript - 单位圆内的 10 个点 - 寻找 D3 力布局的最佳分布？

Question

与一些包装问题有关，出现了以下问题:

在边 1 的正方形内分布 10 个点，使它们之间的最小距离最大化。

在 D3 力布局模拟或任何其他方法的帮助下，请提供这种分布的示例，以及方形和点的图形表示，以及这种分布的点之间的最小距离值。

具有最大最小距离分布的答案赢得“答案徽章”! :)

(据我所知，这个问题无法用纯数学来解决，所以我来这里寻求有关模拟等方面的宝贵且急需的帮助)

Answer 1

TL;DR 一种最优解如下:

[{x: 0,       y: 0},
 {x: 0,       y: 0.22222},
 {x: 0,       y: 0.44444},
 {x: 0,       y: 0.66667},
 {x: 0,       y: 0.88889},
 {x: 0.11111, y: 1},
 {x: 0.33333, y: 1},
 {x: 0.55556, y: 1},
 {x: 0.77778, y: 1},
 {x: 1,       y: 1}]

详细解释:您可以通过 mixed integer program 来解决这个问题(尽管在这种情况下名称有点误导，因为没有整数)。基本模型非常简单:

其中 P 是点集。需要将各个点限制在单位正方形内:

目标是:

这个问题有很多等价的解决方案，例如，您可以通过旋转正方形从一个解决方案中得到另一个解决方案。为了更容易解决这个问题，我们可以通过对点施加顺序来打破一些对称性:每个点的坐标必须至少与其前一个点的坐标一样高。

这意味着我们现在可以使用曼哈顿距离而不是欧几里德距离，并且在计算坐标之间的差异时不必担心负数，从而消除了讨厌的方 block :

将模型输入到您最喜欢的 MIP 系统中，得到的解决方案与上述类似，点与点之间的最小曼哈顿距离为 0.22222。请注意，正如我所提到的，您可以旋转正方形以获得不同但等效的解决方案。