algorithm - 最大最小距离感中的最佳子样本

Question

我在 D 维度量空间中有一组 N 个点。我想以这样的方式选择其中的 K 个，使得子集中任意两点之间的最小距离最大。

例如，在三维欧几里德空间中，N=4 和 K=3，解决方案是具有最长短边的四面体的面。

有没有经典的方法来实现它？能否在多项式时间内精确求解？

我已经尽可能多地搜索了，但我还没有想出如何称呼这个问题。

在我的例子中，通常 N=50、K=10 和 D=300。

澄清:

蛮力方法是尝试 N 个点中 K 个点的每个组合，并确定每个子集中最接近的对。解决方案由产生最长对的子集给出。

用简单的方式完成，一个O(K^2)的过程，要重复N次!/K!(N-K)!次。

嗯，10^2 50!/10! 40! = 1027227817000

Answer 1

我认为您可能会发现有关单位圆盘图的论文内容丰富但令人沮丧。例如，http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.84.3113&rep=rep1&type=pdf指出 NP 完全中单位圆盘图上的最大独立集问题，即使圆盘表示是已知的。单位圆盘图是通过在平面上放置点并在每对点之间形成最多相隔单位距离的链接而得到的图。

所以我认为，如果你能在多项式时间内解决你的问题，你可以在单位圆盘图上针对不同的 K 值运行它，直到你找到一个值，在该值处，两个选定点之间的最小距离刚好超过 1，并且我认为这将是单位圆盘图上的最大独立集，这将解决多项式时间内的 NP 完全问题。

(正要跳上自行车所以有点仓促，但搜索关于单位圆盘图的论文至少可以找到一些有用的搜索词)

下面尝试逐条解释:

这是将这两个问题联系起来的另一种尝试。

有关最大独立集，请参阅 http://en.wikipedia.org/wiki/Maximum_independent_set#Finding_maximum_independent_sets .一个决策问题版本是“这个图中是否有 K 个顶点使得没有两个顶点由一条边连接？”如果你能解决这个问题，你当然可以找到最大独立集，方法是通过针对不同的 K 询问这个问题来找到最大的 K，然后通过询问删除一个或多个节点的图版本的问题来找到 K 节点。

我没有证明在单位圆盘图中找到最大独立集是 NP 完全的。另一个引用是 http://web.sau.edu/lilliskevinm/wirelessbib/ClarkColbournJohnson.pdf .

您的问题的决策版本是“是否存在任意两点之间的距离至少为 D 的 K 个点？”同样，您可以在多项式时间内解决此问题，前提是您可以在多项式时间内解决您的原始问题 - 反复尝试直到找到给出答案是的最大 D，然后删除点并看看会发生什么。

当两点之间的距离等于或小于 1 时，单位圆盘图就有一条边。因此，如果您可以解决原始问题的决策版本，则只需设置 D = 1 并解决您的问题，就可以解决单位圆盘图问题的决策版本。

所以我想我已经构建了一系列链接，表明如果你能解决你的问题，你就可以通过将它转化为你的问题来解决 NP 完全问题，这让我认为你的问题很难。