python - 从给定的 n 个点中选择最远的 k 个点

Question

我在维度 d 中有一组 n 个点，如果需要，我可以为其计算所有成对距离。我需要在此集合中选择 k 个点，以便它们的成对距离之和最大。换句话说，稍微多一些数学术语，我希望 S 中的 p1, ..., pk 使得 sum(i,j < k) dist(pi, pj) 最大。

我知道这个问题与 this one 有关(这与我的基本相同，但 k=2)并且可能到 this one (使用“最远”而不是“最近”)。

我不太确定，但也许所有可能的解决方案的所有点都在凸包中？

任何合理的近似/启发式都可以。

虚拟奖励点 #1 的解决方案适用于从四个点中给出分数的任何函数(其中一个可以是距离平方和的平方根)。

如果解决方案可以在 python + numpy/scipy 中轻松实现，则虚拟奖励点 #2。

Answer 1

您的问题似乎类似于 weighted minimum vertex cover problem (这是 NP 完全)。感谢@Gareth Rees 在下面的评论中澄清了我在理解顶点覆盖与您正在寻找的集合的关系方面是不正确的。但是您仍然可以研究顶点覆盖问题和文献，因为您的问题可能会与它一起讨论，因为它们仍然有一些共同特征。

如果您愿意使用直径而不是总图权重，则可以使用您在问题中链接的最小直径集的方法。如果您当前的距离度量称为 d(您希望点之间距离最远的那个)，那么只需定义 d' = 1/d 并求解最小距离d' 的问题。

某种形式的图形切割算法之间也可能存在关系，比如 normalized cut ，以及您寻找的子集。如果您的距离度量用作图权重或节点之间的亲和性，您可以修改现有的图切割目标函数以匹配您的目标函数(寻找具有最大总和权重的 k 节点组)。

这似乎是一个组合难题。您可能会考虑一些简单的事情，例如模拟退火。 proposal 函数可以随机选择当前在 k-subset 中的点，并用当前不在 k-subset 中的点随机替换它。

您需要针对温度项制定良好的冷却计划，并且可能需要根据成本使用再加热。但是这种编程真的很简单。只要 n 相当小，您就可以不断地随机选择 k-subsets 并退火到总和非常大的 k-subset距离。

这只会给你一个近似值，但即使是确定性方法也可能会近似解决这个问题。

下面是对模拟退火代码可能是什么的第一次破解。 请注意，我对此不做任何保证。如果计算距离太难或问题实例大小变得太大，这可能是一个低效的解决方案。我正在使用具有固定冷却速率的非常朴素的几何冷却，您可能还想修改一个比随机交换节点更奇特的建议。

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