与某些包装问题有关,出现以下问题:单位圈内10点 - 通过D3力布局找到最佳分布?
在边1的正方形内分布10个点,以使它们之间的最小距离达到最大。
在D3力布局模拟或任何其他方法的帮助下,请提供此类分布的示例,包括正方形和点的图形表示以及此类分布的点之间的最小距离值。
最小距离分布的答案赢得“答案徽章”! :)
(这个问题到目前为止,据我所知,不能由纯数学来解决,所以我来这里就模拟宝贵和急需帮助等)
与某些包装问题有关,出现以下问题:单位圈内10点 - 通过D3力布局找到最佳分布?
在边1的正方形内分布10个点,以使它们之间的最小距离达到最大。
在D3力布局模拟或任何其他方法的帮助下,请提供此类分布的示例,包括正方形和点的图形表示以及此类分布的点之间的最小距离值。
最小距离分布的答案赢得“答案徽章”! :)
(这个问题到目前为止,据我所知,不能由纯数学来解决,所以我来这里就模拟宝贵和急需帮助等)
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是点的集合。个别点需要被约束在单位面积内:
的目标则是:
有此问题的许多等同方案,比如,你可以通过旋转方块从一个解决方案中获得另一个解为了使其更容易解决,我们可以通过对点进行排序来打破一些对称性:每个点的坐标必须至少与其前一个点的坐标一样高。
这意味着我们现在可以使用曼哈顿距离而不是欧氏并没有计算坐标之间的差异,从而消除讨厌的广场时,担心负数:
将模型输入到您最喜欢的MIP系统中,然后出现类似上述的解决方案,曼哈顿距离点之间的最小距离为0.22222。请注意,正如我所提到的,您可以旋转方块以获得不同但等效的解决方案。