从给定的n个点中选择距离最远的k个点

Question

从给定的n个点中选择距离最远的k个点

14

我有一个包含n个点的集合S，这些点在d维空间中，并且如果需要可以计算它们之间的所有两两距离。我需要从这个集合中选择k个点，使它们的两两距离之和最大。换句话说，我想要在S中选择p1, ..., pk，使得sum(i,j < k) dist(pi, pj)最大。

我知道这个问题与此问题相关（基本上与我的问题相同，但对于k=2），也许与此问题相关（只不过是选择'farthest'而不是'closest'）。

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

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

如果有一种适用于给出四个点得分的任何函数（其中一个可以是平方距离之和的平方根）的解决方案，那么可以获得虚拟的奖励积分#1。

如果该解决方案易于在python + numpy/scipy中实现，则可以获得虚拟奖励积分#2。

- Nathan

1

回复：凸包上的所有解决方案点：不幸的是，这并不正确，因为凸包可能少于“k”个顶点。 - us2012

那么，如果 k < _h_，其中 h 是凸包中点的数量，这是真的吗？ - Nathan

通常在图形中，“最远”/“最长”的问题比“最近”的问题更难。不要认为如果你能找到最接近的点/某物的最小值，那么你也可以用大部分相同的代码和时间找到最远的点/某物的最大值。 - Bakuriu

我之前提过类似的问题，得到了一些很好的答案：https://dev59.com/DVUM5IYBdhLWcg3wYvbl。我的问题与此不同的是，我想要优化距离的最小值而不是距离的总和。 - Shital Shah

4个回答

6

您的问题似乎与加权最小顶点覆盖问题类似（这是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

- ely

谢谢您的建议。我本来想用蒙特卡罗算法，但我一定会尝试这个模拟退火方法。我会等待几个小时/几天，看是否有更多“专业”的解决方案出现，但如果没有的话，我想我会选择这个方法。 - Nathan

关于取 d'=1/d 的建议，我不太确定这个处理方式是否合适，因为 1/d 看起来似乎并不是真正的“度量”，而我也不知道这会对提出的算法产生什么影响。 - Nathan

我不认同你的论点，即 OP 问题是 NP 完全问题，并且我也看不出与最小顶点覆盖的联系。（在最小顶点覆盖问题中，你正在尝试选择最小覆盖集，但在 OP 问题中，你必须恰好选取 k 个点。）你能否详细解释一下你回答中的这部分内容？ - Gareth Rees

我不知道有没有完美的连接，这就是我说“我不完全确定”的原因。我还在谈论加权最小顶点覆盖。并且由于图必然存在任意两点之间的边（因为它只是一种度量空间中的距离），所以我认为这避免了您提到的问题。也就是说，任何k个点将成为一个覆盖集，即使单个点也可以成为一个覆盖集，因此剩下的只是权重最小化问题。我不知道这种简化是否使其能够在多项式时间内求解，但很容易像双分图版本的最大独立集那样求解。 - ely

你是正确的，我对此有误。那么，完全图的任何顶点覆盖都将由图中的任意N-1个节点组成，这是正确的吗？ - ely

显示剩余3条评论

2

步骤1：预先计算所有点对pi，pj的距离dist(pi,pj)。

步骤2：构建完全图V={p1,...,pn}，其中边权值w_ij=dist(pi,pj)。

步骤3：解决最大边权独立集（MEC）问题。

MEC问题肯定是NP完全问题，并且与二次规划密切相关。因此，如果n很大（甚至中等大小），则可能需要关注启发式算法。

请注意，通过预先计算边权，对距离函数没有任何限制。

- Tom Swifty

0

这是一个适用于小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)!)

- Eric

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ron Teller · Accepted Answer

这个贪心算法怎么样：

在S中找到距离最远的两个点，将它们添加到解决方案中
直到达到大小为k的解决方案，将距离已经在解决方案中的所有点之和最大的点添加到解决方案中。

让我们称任意两点之间的最大距离为D，对于我们添加到解决方案中的每个点，由于三角不等式，我们至少会添加D。因此，解决方案至少为（k-1）* D，而任何解决方案都有（k-1）^2个距离，其中没有一个超过D，因此在最坏的情况下，您可以得到一个解决方案是最优解的k倍。

我不确定这是否是该启发式算法可以证明的最紧密的界限。