二维网格中最小化0点到1点平均欧氏距离的n个1点最优分布求解

问题背景 #

我们首先考虑一个二维数组A，初始状态下所有位置都满足A(i,j)=0，即所有元素值为0。现在我们在数组中设置n个取值为1的点，满足sum(sum(A))=n。

核心问题 #

请问这n个1点的最优空间分布是什么样的，能够最小化所有0点到最近1点的平均欧氏距离？

参考实现逻辑（Matlab） #

A=zeros(10,10) % 生成10*10的全0网格
A(1:2)=1;
A(2,3)=1; 
A(4,3)=1; 
A(5,5)=1; % 测试用的赋值：n=4个点设为1

dmap = bwdist(A) % 计算欧氏距离图（每个0点到最近1点的最短距离）
dmap(dmap==0)=[]; % 过滤掉距离为0的点（即1点本身的位置）
average_min_distance_from_0_to_1 = mean(dmap)

我需要找到最优的1点分布（也就是上述代码中给A赋值1的相关行），使得average_min_distance_from_0_to_1在所有可能的排列中取值最小。
我猜测这是几何中位数问题的变体，但我的场景需要求解多个点的最优分布，而非单个点。 #

解决思路 #

这个问题本质是离散网格场景下的多点设施选址问题，核心目标是放置n个点最小化其余点到最近点的平均欧氏距离，可根据你的使用场景选择以下方案：

• 小尺寸网格可直接用暴力枚举：如果网格边长≤10且n≤5，直接穷举所有n个点的组合，计算对应平均距离后取最小值即可，复杂度为组合级，仅适合极小场景。
• 通用场景用Lloyd迭代算法：逻辑和k均值迭代类似，收敛速度快，绝大多数情况能得到接近全局最优的解，步骤如下：
  1. 随机在网格上生成n个初始1点位置
  2. 计算所有网格点到最近1点的距离，完成Voronoi划分，每个1点对应一个由所有离它最近的网格点组成的单元格
  3. 对每个单元格，计算该区域内所有点的几何中位数，把对应1点移动到这个中位数位置
  4. 重复步骤2~3，直到1点位置不再变化，或平均距离的下降幅度低于预设阈值
• 边界修正：如果是有限边界网格，最优分布会比无限平面的均匀六边形分布略微向内收缩，迭代过程不需要强制点均匀分布，算法会自动适配边界约束。

你提到的几何中位数确实是该问题的子问题：固定其他1点位置时，单个1点的最优位置就是它对应单元格内所有点的几何中位数。 #

内容的提问来源于stack exchange，提问作者Doby