我在D维度量空间中有一组N个点。我想以这样的方式选择它们中的K，使得子集中任意两点之间的最小距离最大。Maxmin距离感最好的子样本
例如，在3D欧几里德空间中N = 4且K = 3时，解是具有最长短边的四面体的面。
有没有经典的方法来实现这一目标？它能够在多项式时间内完全求解吗？
我已尽可能地使用Google搜索，但我还没有想出如何调用此问题。
在我的情况下，N = 50，K = 10，D = 300。
澄清：
蛮力的方法是尝试的N之中K个点每一个组合，并确定在每一个子集中的最接近的一对。解决方案由产生最长对的子集给出。
完成一个O（K^2）过程的简单方法，重复N！/K！（N-K）！倍。
哼，10^2 50！/10！ 40！ = 1027227817000
我认为你可能会发现单位磁盘图上的文件信息，但令人沮丧。例如，http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.84.3113&rep=rep1&type=pdf指出在NP-complete中单位磁盘图上的最大独立集问题，即使磁盘表示法已知。单位磁盘图是通过将点放置在平面中，并在每对点之间形成最多相隔单位距离的链接而获得的图形。
所以我认为，如果你可以用多项式时间解决你的问题，你可以在单位磁盘图上运行K值的不同值，直到找到两个选定点之间的最小距离刚刚超过一个值，我认为这将是单位磁盘图上的最大独立集，它将解决多项式时间内的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。
您的问题的决定版本是“是否存在K点，距离至少有两点之间的距离？”再次，如果可以在多项式时间内解决原始问题，则可以在多项式时间内解决此问题 - 一直播放，直到找到答案为yes的最大D，然后删除点并查看会发生什么。
甲单位圆图具有边缘的确切时间的两个点之间的距离为1或更小。所以如果你能解决原始问题的决定版本，你可以通过设置D = 1并解决你的问题来解决单位磁盘图形问题的决定版本。
所以我觉得我已经构建了一系列的展示，如果你能解决你的问题，你可以通过把它变成你的问题，这使我觉得你的问题是很难解决的NP完全问题链接。
这是一个非常有趣的方法，确实有点令人沮丧。如果发现精神上很难检查你的论点是否正确，尽管:( – 2012-07-23 07:53:02
我已经尝试了一步一步地添加我的论点一节 – mcdowella 2012-07-23 18:38:51
声音，你可以做，建立一个点与点之间的距离图，然后运行克鲁斯卡尔算法的修改版本来构建最大生成树 – higuaro 2012-07-20 20:38:16
最大生成树可以是V形，节点之间有很长的链接，但是两个节点没有通过非常靠近的链路连接。我能想到的一些明显的爬坡和贪心算法如此（通过扫描数据，并反复查看是否有交换迄今举行将改善的事情之一分新点），但他们不会放弃某些最优 – mcdowella 2012-07-21 05:14:17
假设我已经在N个点上构建了最大生成树。如何修剪树以获得我的K子样本？生成树以什么方式让我更接近解决方案？ – 2012-07-21 10:15:31