在给定的点集中选择最远点的子集

Question

想象一下,你给出了3个维度中n个点的集合S. 任意2点之间的距离是简单的欧几里德距离.您希望从该集合中选择k个点的子集Q,使得它们彼此相距最远.换句话说,不存在k个点的其他子集Q',使得Q中的所有成对距离的min小于Q'中的min.

如果n约为1600万,k约为300,我们如何有效地做到这一点？

我猜这个NP难,所以我们可能只想关注近似.我能想到的一个想法是使用多维缩放对一行中的这些点进行排序,然后使用二进制搜索的版本来获得该行上最远的点.

Answer 1

这被称为离散 p 色散 (maxmin) 问题。

White (1991)和Ravi 等人证明了最优界限。(1994)给出了问题的因子 2 近似值，后者证明这种启发式方法是最好的（除非 P=NP）。

因子 2 近似

因子 2 近似值如下：

Let V be the set of nodes/objects
Let i and j be two nodes at maximum distance
Let p be the number of objects to choose
p = set([i,j])
while size(P)<p:
  Find a node v in V-P such that min_{v' in P} dist(v,v') is maximum
  \That is: find the node with the greatest minimum distance to the set P
  P = P.union(v)
Output P

你可以像这样在 Python 中实现它：

Let V be the set of nodes/objects
Let i and j be two nodes at maximum distance
Let p be the number of objects to choose
p = set([i,j])
while size(P)<p:
  Find a node v in V-P such that min_{v' in P} dist(v,v') is maximum
  \That is: find the node with the greatest minimum distance to the set P
  P = P.union(v)
Output P

精确解

您也可以将其建模为 MIP。对于 p=50，6000 秒后 n=400，最优性差距仍然是 568%。近似算法需要 0.47 秒才能获得 100%（或更少）的最优性差距。一个简单的 Gurobi Python 表示可能如下所示：

#!/usr/bin/env python3

import numpy as np

p = 50
N = 400

print("Building distance matrix...")
d = np.random.rand(N,N) #Random matrix
d = (d + d.T)/2         #Make the matrix symmetric

print("Finding initial edge...")
maxdist  = 0
bestpair = ()
for i in range(N):
  for j in range(i+1,N):
    if d[i,j]>maxdist:
      maxdist = d[i,j]
      bestpair = (i,j)

P = set()
P.add(bestpair[0])
P.add(bestpair[1])

print("Finding optimal set...")
while len(P)<p:
  print("P size = {0}".format(len(P)))
  maxdist = 0
  vbest = None
  for v in range(N):
    if v in P:
      continue
    for vprime in P:
      if d[v,vprime]>maxdist:
        maxdist = d[v,vprime]
        vbest   = v
  P.add(vbest)

print(P)

缩放

显然，初始点的 O(N^2) 缩放很糟糕。通过识别该对必须位于数据集的凸包上，我们可以更有效地找到它们。这给了我们一个O(N log N) 的方法来找到这个对。一旦我们找到它，我们就像以前一样继续（使用 SciPy 进行加速）。

最好的缩放方式是使用 R*-tree 来有效地找到候选点 p 和集合 P 之间的最小距离。但这在 Python 中无法有效完成，因为for仍然涉及循环。

#!/usr/bin/env python
import numpy as np
import gurobipy as grb

p = 50
N = 400

print("Building distance matrix...")
d = np.random.rand(N,N) #Random matrix
d = (d + d.T)/2             #Make the matrix symmetric

m = grb.Model(name="MIP Model")

used  = [m.addVar(vtype=grb.GRB.BINARY) for i in range(N)]

objective = grb.quicksum( d[i,j]*used[i]*used[j] for i in range(0,N) for j in range(i+1,N) )

m.addConstr(
  lhs=grb.quicksum(used),
  sense=grb.GRB.EQUAL,
  rhs=p
)

# for maximization
m.ModelSense = grb.GRB.MAXIMIZE
m.setObjective(objective)

# m.Params.TimeLimit = 3*60

# solving with Glpk
ret = m.optimize()