获得具有最大平均距离的点的子集
Obtain the subset of dots with maximal average distance
我有 N 个点。我知道它们的所有成对距离。我需要从它们中提取 select K 个点，这样平均成对距离将是最大的。
我只有一个愚蠢的想法来遍历每个点。
你有更聪明的想法如何获得这样的子集吗？
在没有任何假设的情况下，一般地解决这个问题会很好，但如果有帮助的话：N 大约是 10^3-10^4，K大约 10^2.
我的虚拟想法：
我从点 #1 开始搜索最远的点，所以我有一大块 2 个点，接下来我搜索第三个点，它到这两个点的平均距离最大，依此类推，直到我收集到 K 个点.应该对所有 N 个点重复此过程作为起始值。最后我将获得 N 个 K 点数组。从他们中我可能会选择一个平均距离最大的。
我不是 100% 确定，但这听起来像是一个 NP-Hard 问题。
作为近似值，您可以执行 K-Median Clustering 和 return 结果集群代表作为您的结果。聚类基本上试图
最小化属于同一簇的点的距离（这对您来说不重要）并最大化来自不同簇的点之间的距离（这就是您想要的）。
编辑：
再考虑一下，我认为您会想要尝试在数据集的外部限制上搜索点，以最大化平均成对距离。因此，您可以计算（凸）外壳并从那里选取点，也可以在您选取一个点时重新计算外壳。或者你可以从一个点 (a) 开始，搜索距离 (a) 最远的点 (b)，然后搜索距离 (b) 最远的点 (c) 等等（避免两次选择点，可能通过删除在你挑选它们之后）。这将确保您选择数据集边界处的点。
这可以看作是N个顶点的完全图上最重k子图问题的一个特例，其中权重满足三角不等式
问题的一般情况是 NP-hard，我猜测上述限制不足以使其成为多项式，尽管它们当然可以接受一些启发式方法。
对于近似解，您评估过贪心解还是贪心随机抽样式解？
附录
最近看到一篇论文，讨论权值满足三角不等式情况下的最大离差和最重子图问题：
Hassin et al., Approximation algorithms for maximal dispersion, Operations Research Letters 21 (1997), no. 3, 133–137, DOI 10.1016/S0167-6377(97)00034-5.
本文第3节针对本题对应的情况提供了一个简单的近似O(n2)贪心算法，并且作者证明结果至少是最大值的 1/2。
我有 N 个点。我知道它们的所有成对距离。我需要从它们中提取 select K 个点，这样平均成对距离将是最大的。
我只有一个愚蠢的想法来遍历每个点。
你有更聪明的想法如何获得这样的子集吗？
在没有任何假设的情况下，一般地解决这个问题会很好，但如果有帮助的话：N 大约是 10^3-10^4，K大约 10^2.
我的虚拟想法： 我从点 #1 开始搜索最远的点，所以我有一大块 2 个点，接下来我搜索第三个点，它到这两个点的平均距离最大，依此类推，直到我收集到 K 个点.应该对所有 N 个点重复此过程作为起始值。最后我将获得 N 个 K 点数组。从他们中我可能会选择一个平均距离最大的。
我不是 100% 确定，但这听起来像是一个 NP-Hard 问题。
作为近似值，您可以执行 K-Median Clustering 和 return 结果集群代表作为您的结果。聚类基本上试图
最小化属于同一簇的点的距离（这对您来说不重要）并最大化来自不同簇的点之间的距离（这就是您想要的）。
编辑：
再考虑一下，我认为您会想要尝试在数据集的外部限制上搜索点，以最大化平均成对距离。因此，您可以计算（凸）外壳并从那里选取点，也可以在您选取一个点时重新计算外壳。或者你可以从一个点 (a) 开始，搜索距离 (a) 最远的点 (b)，然后搜索距离 (b) 最远的点 (c) 等等（避免两次选择点，可能通过删除在你挑选它们之后）。这将确保您选择数据集边界处的点。
这可以看作是N个顶点的完全图上最重k子图问题的一个特例，其中权重满足三角不等式
问题的一般情况是 NP-hard，我猜测上述限制不足以使其成为多项式，尽管它们当然可以接受一些启发式方法。
对于近似解，您评估过贪心解还是贪心随机抽样式解？
附录
最近看到一篇论文，讨论权值满足三角不等式情况下的最大离差和最重子图问题：
Hassin et al., Approximation algorithms for maximal dispersion, Operations Research Letters 21 (1997), no. 3, 133–137, DOI 10.1016/S0167-6377(97)00034-5.
本文第3节针对本题对应的情况提供了一个简单的近似O(n2)贪心算法，并且作者证明结果至少是最大值的 1/2。