从给定的n点选择最远的k点

Question

我有一个维度为d的n个点的S ,我可以根据需要计算所有成对距离.我需要在这个集合中选择k个点,以便它们成对距离的总和是最大的.在其他稍微更多的数学词中,我想要S中的p1,...,pk使得sum(i,j <k)dist(pi,pj)是最大的.

我知道这个问题是关系到这一个(这基本上是我的一样,但对于k = 2),也许到这一个(使用而不是"最近""最远的").

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

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

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

如果解决方案很容易在python + numpy/scipy中实现,那么虚拟奖励点#2.

Answer 1

您的问题似乎与加权最小顶点覆盖问题类似(NP-complete).感谢@Gareth Rees对以下评论的澄清,说明我在理解顶点封面与您正在寻找的集合之间的关系时是错误的.但你仍然可以研究顶点覆盖问题和文献,因为你的问题可能会与它一起讨论,因为它们仍然分享一些功能.

如果您愿意使用直径而不是求和图重量,则可以使用您在问题中链接的最小直径集的方法.如果您当前的距离测量被调用d(您想要的点距离彼此最远),那么只需定义d' = 1/d并解决最小距离问题d'.

某种形式的图切割算法(如标准化切割)与您寻找的子集之间可能存在关联.如果距离度量用作节点之间的图形权重或亲和力,则可以修改现有的图形切割目标函数以匹配目标函数(查找具有最大总加权重的k个节点组).

这似乎是一个组合难题.您可能会考虑像模拟退火一样简单的事情 提议函数可以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

Answer 2

这个贪心算法怎么样:

1. 在S中添加两个点之间的距离最大的解决方案
2. 在达到大小为k的解决方案之前,在解决方案中添加从其到解决方案中已有的所有点的距离之和最大的点.

让我们调用任意2点D之间的最大距离,对于我们添加到解决方案的每个点,由于三角形不等式,我们至少添加D. 因此解决方案将至少为(k-1)*D,而任何解决方案都将具有(k-1)^ 2个距离,它们都不会超过D,因此在更糟糕的情况下,您将得到k倍于最佳值的解.

我不确定这是否可以证明这种启发式的最严格的界限.