如何从3D点集中采样N个点以最大化点对最小距离

你遇到的问题属于离散p-分散问题，目标是从N个点中选出p个点，最大化子集中两两距离的最小值，该问题属于NP难问题，针对你500个3D点选20个的场景，以下是几类可落地的高效方案：

先修复原贪心代码的bug #

你现有代码的核心逻辑是最远点采样（FPS），但存在一处功能错误：np.delete 不会修改原数组，你没有将返回值赋值给remained_points，导致每次迭代都在全量初始未选点中选择，没有移除已采样的点，可能出现重复采样的问题，修复对应行即可：

# 原错误代码
np.delete(remained_points, (imax), axis=0)
# 修复后
remained_points = np.delete(remained_points, imax, axis=0)

方案1：改进版贪心最远点采样（FPS） #

在修复bug的基础上，修改初始点选择逻辑即可大幅提升解的质量：不再固定选第一个点作为初始点，而是先计算所有点对的距离，选距离最远的两个点作为初始采样集，避免初始点偏差带来的局部最优问题。
该方案实现简单、运行速度极快，适合对性能要求高、对精度要求中等的场景，改进后的代码示例：

from scipy.spatial import distance_matrix
import numpy as np

def improved_fps(points, n):
    # 第一步：选距离最远的两个点作为初始采样集
    dist_matrix = distance_matrix(points, points)
    i, j = np.unravel_index(np.argmax(dist_matrix), dist_matrix.shape)
    sampled_indices = [i, j]
    remained_indices = list(set(range(len(points))) - set(sampled_indices))
    
    while len(sampled_indices) < n:
        remained_points = points[remained_indices]
        sampled_points = points[sampled_indices]
        min_dists = distance_matrix(remained_points, sampled_points).min(axis=1)
        imax_local = np.argmax(min_dists)
        imax_global = remained_indices[imax_local]
        sampled_indices.append(imax_global)
        remained_indices.pop(imax_local)
    
    return points[sampled_indices]

方案2：二分查找+最大独立集验证 #

就是你补充说明中提到的思路，解的质量远高于纯贪心算法，500点的规模运行无压力：

1. 先计算所有点对的距离，确定二分上下界：下界为0，上界为点集中的最大两两距离
2. 每次取中间值t作为阈值，构建欧氏图：两点距离小于t时就连边
3. 求该图的最大独立集大小，若大小≥20，说明可以选出20个两两距离≥t的点，上调二分下界，否则下调上界
4. 二分结束后，取对应最大t的独立集即可得到结果

方案3：启发式优化算法（模拟退火） #

如果需要接近全局最优的高质量解，可以用模拟退火算法，实现简单、调参成本低：

1. 初始解用改进版FPS的结果，减少迭代收敛时间
2. 每次迭代随机将一个已采样点替换为未采样点，计算新解的最小两两距离
3. 若新解更优则直接接受，否则按温度相关的概率接受，避免陷入局部最优
4. 迭代过程中逐步降低温度，最终收敛到接近全局最优的解
   20个点的规模迭代1万次仅需几十毫秒，解的质量远高于纯贪心方法。

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