我在维度 d 中有一组 n 个点的 S，如果需要，我可以计算所有成对距离。我需要在这个集合中选择 k 个点，以便它们的成对距离之和是最大的。在其他稍微数学化的话中，我想要 S 中的 p1， ...， pk，这样 sum(i，j 我知道这个问题与这个问题
有关(与我的问题基本相同，但 k=2(，也许与这个问题有关(使用"最远"而不是"最接近"(。
我不太确定，但也许所有可能的解决方案都在凸包中？
任何合理的近似/启发式都可以。
虚拟奖励点 #1 用于适用于任何给出四分的函数的解决方案(其中一个可能是距离平方和的平方根(。
虚拟奖励点 #2 如果解决方案在 python + numpy/scipy 中很容易实现。
您的问题似乎类似于加权最小顶点覆盖问题(NP完全(。感谢 @Gareth Rees 在下面的评论，澄清了我在理解顶点覆盖与您要查找的集合的关系方面不正确。但是您仍然可以研究顶点覆盖问题和文献，因为您的问题可能会与它一起讨论，因为它们仍然共享一些特征。
如果您愿意使用直径而不是求和图权重，则可以使用您在问题中链接的最小直径集的方法。如果您当前的距离测量称为d(您希望点彼此相距最远的那个(，则只需定义d' = 1/d并使用d'求解最小距离问题。
某种形式的图形切割算法(例如规范化切割(与您寻求的子集之间也可能存在关系。如果将距离度量用作节点之间的图形权重或关联度，则可以修改现有的图形切割目标函数以匹配目标函数(查找具有最大总和权重的 k 个节点组(。
这似乎是一个组合上困难的问题。您可以考虑一些简单的事情，例如模拟退火。提案函数可以随机选择当前位于k -子集中的点，并将其随机替换为当前不在k -子集中的点。
您需要在温度期限内有一个良好的冷却计划，并且可能需要使用重新加热作为成本的函数。但是这种编程非常简单。只要n相当小，您就可以不断地随机选择k子集，并向总距离非常大的k子集退火。
这只会给你一个近似值，但即使是确定性方法也可能近似地解决这个问题。
下面是模拟退火代码可能是什么的第一个技巧。请注意，我不对此做出保证。如果计算距离太难或问题实例大小变得太大，则这可能是一个低效的解决方案。我正在使用非常朴素的几何冷却和固定的冷却速率，您可能还想修改一个更漂亮的建议，而不仅仅是随机交换节点。
all_nodes = np.asarray(...) # Set of nodes
all_dists = np.asarray(...) # Pairwise distances
N = len(all_nodes)
k = 10 # Or however many you want.
def calculate_distance(node_subset, distances):
# A function you write to determine sum of distances
# among a particular subset of nodes.
# Initial random subset of k elements
shuffle = np.random.shuffle(all_nodes)
current_subset = shuffle[0:k]
current_outsiders = shuffle[k:]
# Simulated annealing parameters.
temp = 100.0
cooling_rate = 0.95
num_iters = 10000
# Simulated annealing loop.
for ii in range(num_iters):
proposed_subset = current_subset.copy()
proposed_outsiders = current_outsiders.copy()
index_to_swap = np.random.randint(k)
outsider_to_swap = np.random.randint(N - k)
tmp = current_subset[index_to_swap]
proposed_subset[index_to_swap] = current_outsiders[outsider_to_swap]
proposed_outsiders[outsider_to_swap] = tmp
potential_change = np.exp((-1.0/temp)*
calculate_distance(proposed_subset,all_dists)/
calculate_distance(current_subset, all_dists))
if potential_change > 1 or potential_change >= np.random.rand():
current_subset = proposed_subset
current_outsiders = proposed_outsiders
temp = cooling_rate * temp
这个贪婪的算法怎么样：
- 将 S 中它们之间距离最大的 2 个点添加到解决方案中
- 在达到大小为 k 的解之前，将解到解中已有的所有点的距离之和最大的点添加到解中。
让我们调用任何 2 点之间的最大距离 D，对于我们添加到解决方案中的每个点，由于三角形不等式，我们至少添加 D。 所以解至少是 (k-1(*D，而任何解都有 (k-1(^2 个距离，它们都没有超过 D，所以在最坏的情况下，你会得到一个解 k 倍于最优值。
我不确定这是这种启发式可以证明的最严格的界限。
第 1 步：为所有对 pi，pj 预计算 dist(pi， pj(
第 2 步：构造一个完整的图形 V={p1,...,pn}，边权重 w_ij = dist(pi， pj(
第 3 步：解决最大边缘加权集团 (MEC( 问题。
MEC绝对是NP完备的，它与二次规划密切相关。 因此，如果 n 很大(甚至中等大小(，您可能会专注于启发式方法。
请注意，通过预先计算边权重，对距离函数没有限制
这是一个针对小 n 的工作(蛮力(实现，如果没有别的，它显示了生成器推导的表达能力：
selection = max(
itertools.combinations(points, k),
key=lambda candidate: sum(
dist(p, q) for p, q in itertools.combinations(candidate, 2)
)
)
虽然这最终会给dist打电话很多：
(k! / 2! / (k-2)!) * (n! / k! / (n-k)! == n! /(2(k-2)!(n-k)!)